2 /**-------------------------------------------------------------------**
4 **-------------------------------------------------------------------**
6 **-------------------------------------------------------------------**
7 ** First version: october 26th 2001 **
8 **-------------------------------------------------------------------**/
11 /******************************************************************************
12 * CLooG : the Chunky Loop Generator (experimental) *
13 ******************************************************************************
15 * Copyright (C) 2001-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 !
41 # include "../include/cloog/cloog.h"
44 /******************************************************************************
45 * Memory leaks hunting *
46 ******************************************************************************/
50 * These functions and global variables are devoted to memory leaks hunting: we
51 * want to know at each moment how many CloogLoop structures had been allocated
52 * (cloog_loop_allocated) and how many had been freed (cloog_loop_freed).
53 * Each time a CloogLoog structure is allocated, a call to the function
54 * cloog_loop_leak_up() must be carried out, and respectively
55 * cloog_loop_leak_down() when a CloogLoop structure is freed. The special
56 * variable cloog_loop_max gives the maximal number of CloogLoop structures
57 * simultaneously alive (i.e. allocated and non-freed) in memory.
58 * - July 3rd->11th 2003: first version (memory leaks hunt and correction).
62 int cloog_loop_allocated
= 0 ;
63 int cloog_loop_freed
= 0 ;
64 int cloog_loop_max
= 0 ;
67 static void cloog_loop_leak_up()
68 { cloog_loop_allocated
++ ;
69 if ((cloog_loop_allocated
-cloog_loop_freed
) > cloog_loop_max
)
70 cloog_loop_max
= cloog_loop_allocated
- cloog_loop_freed
;
74 static void cloog_loop_leak_down()
75 { cloog_loop_freed
++ ;
79 /******************************************************************************
80 * Structure display function *
81 ******************************************************************************/
85 * cloog_loop_print_structure function:
86 * Displays a loop structure in a way that trends to be understandable without
87 * falling in a deep depression or, for the lucky ones, getting a headache...
88 * Written by Olivier Chorier, Luc Marchaud, Pierre Martin and Romain Tartiere.
89 * - April 24th 2005: Initial version.
90 * - May 21rd 2005: - New parameter `F' for destination file (ie stdout),
92 * - May 26th 2005: Memory leak hunt.
93 * - June 2nd 2005: (Ced) Integration and minor fixes.
94 * -June 22nd 2005: (Ced) Adaptation for GMP.
96 void cloog_loop_print_structure(FILE * file
, CloogLoop
* loop
, int level
)
100 { /* Go to the right level. */
101 for (i
=0; i
<level
; i
++)
102 fprintf(file
,"|\t") ;
104 fprintf(file
,"+-- CloogLoop\n") ;
110 { /* Go to the right level. */
111 for (i
=0; i
<level
; i
++)
112 fprintf(file
,"|\t") ;
114 fprintf(file
,"| CloogLoop\n") ;
120 for(j
=0; j
<=level
+1; j
++)
121 fprintf(file
,"|\t") ;
124 /* Print the domain. */
125 cloog_domain_print_structure(file
, loop
->domain
, level
+1, "CloogDomain");
127 /* Print the stride. */
128 for(j
=0; j
<=level
; j
++)
129 fprintf(file
,"|\t") ;
130 fprintf(file
, "Stride: ") ;
131 cloog_int_print(file
, loop
->stride
);
132 fprintf(file
, "\n") ;
135 for(j
=0; j
<=level
+1; j
++)
136 fprintf(file
,"|\t") ;
139 /* Print the block. */
140 cloog_block_print_structure(file
,loop
->block
,level
+1) ;
143 for (i
=0; i
<=level
+1; i
++)
144 fprintf(file
,"|\t") ;
147 /* Print inner if any. */
149 cloog_loop_print_structure(file
,loop
->inner
,level
+1) ;
151 /* And let's go for the next one. */
154 /* One more time something that is here only for a better look. */
156 { /* Two blank lines if this is the end of the linked list. */
158 { for (i
=0; i
<=level
; i
++)
159 fprintf(file
,"|\t") ;
165 { /* A special blank line if the is a next loop. */
166 for (i
=0; i
<=level
; i
++)
167 fprintf(file
,"|\t") ;
168 fprintf(file
,"V\n") ;
175 * cloog_loop_print function:
176 * This function prints the content of a CloogLoop structure (start) into a
177 * file (file, possibly stdout).
178 * - June 2nd 2005: Now this very old function (probably as old as CLooG) is
179 * only a frontend to cloog_loop_print_structure, with a quite
180 * better human-readable representation.
182 void cloog_loop_print(FILE * file
, CloogLoop
* loop
)
183 { cloog_loop_print_structure(file
,loop
,0) ;
187 /******************************************************************************
188 * Memory deallocation function *
189 ******************************************************************************/
193 * cloog_loop_free function:
194 * This function frees the allocated memory for a CloogLoop structure (loop),
195 * and frees its inner loops and its next loops.
196 * - June 22nd 2005: Adaptation for GMP.
198 void cloog_loop_free(CloogLoop
* loop
)
202 { cloog_loop_leak_down() ;
205 cloog_domain_free(loop
->domain
) ;
206 cloog_block_free(loop
->block
) ;
207 if (loop
->inner
!= NULL
)
208 cloog_loop_free(loop
->inner
) ;
210 cloog_int_clear(loop
->stride
);
218 * cloog_loop_free_parts function:
219 * This function frees the allocated memory for some parts of a CloogLoop
220 * structure (loop), each other argument is a boolean having to be set to 1 if
221 * we want to free the corresponding part, 0 otherwise. This function applies
222 * the same freeing policy to its inner ans next loops recursively.
223 * - July 3rd 2003: first version.
224 * - June 22nd 2005: Adaptation for GMP.
226 void cloog_loop_free_parts(loop
, domain
, block
, inner
, next
)
228 int domain
, block
, inner
, next
;
229 { CloogLoop
* follow
;
232 { cloog_loop_leak_down() ;
233 follow
= loop
->next
;
236 cloog_domain_free(loop
->domain
) ;
239 cloog_block_free(loop
->block
) ;
241 if ((inner
) && (loop
->inner
!= NULL
))
242 cloog_loop_free_parts(loop
->inner
,domain
,block
,inner
,1) ;
244 cloog_int_clear(loop
->stride
);
254 /******************************************************************************
255 * Reading functions *
256 ******************************************************************************/
260 * cloog_loop_read function:
261 * This function reads loop data into a file (foo, possibly stdin) and
262 * returns a pointer to a CloogLoop structure containing the read information.
263 * This function can be used only for input file reading, when one loop is
264 * associated with one statement.
265 * - number is the statement block number carried by the loop (-1 if none).
266 * - nb_parameters is the number of parameters.
268 * - September 9th 2002: first version.
269 * - April 16th 2005: adaptation to new CloogStatement struct (with number).
270 * - June 11th 2005: adaptation to new CloogBlock structure.
271 * - June 22nd 2005: Adaptation for GMP.
273 CloogLoop
* cloog_loop_read(FILE * foo
, int number
, int nb_parameters
,
274 CloogOptions
*options
)
275 { int nb_iterators
, op1
, op2
, op3
;
278 CloogStatement
* statement
;
280 cloog_loop_leak_up() ;
282 /* Memory allocation and information reading for the first domain: */
283 loop
= (CloogLoop
*)malloc(sizeof(CloogLoop
)) ;
285 { fprintf(stderr
, "Memory Overflow.\n") ;
289 loop
->domain
= cloog_domain_union_read(foo
, nb_parameters
, options
);
290 if (loop
->domain
!= NULL
)
291 nb_iterators
= cloog_domain_dimension(loop
->domain
) - nb_parameters
;
294 /* stride is initialized to 1. */
295 cloog_int_init(loop
->stride
);
296 cloog_int_set_si(loop
->stride
, 1);
297 /* included statement block. */
298 statement
= cloog_statement_alloc(number
+1);
299 loop
->block
= cloog_block_alloc(statement
, 0, NULL
, nb_iterators
);
301 /* inner is NULL at beginning. */
306 /* To read that stupid "0 0 0" line. */
307 while (fgets(s
,MAX_STRING
,foo
) == 0) ;
308 while ((*s
=='#' || *s
=='\n') || (sscanf(s
," %d %d %d",&op1
,&op2
,&op3
)<3))
309 fgets(s
,MAX_STRING
,foo
) ;
315 /******************************************************************************
316 * Processing functions *
317 ******************************************************************************/
321 * cloog_loop_malloc function:
322 * This function allocates the memory space for a CloogLoop structure and
323 * sets its fields with default values. Then it returns a pointer to the
325 * - November 21th 2005: first version.
327 CloogLoop
* cloog_loop_malloc()
330 /* Memory allocation for the CloogLoop structure. */
331 loop
= (CloogLoop
*)malloc(sizeof(CloogLoop
)) ;
333 { fprintf(stderr
, "[CLooG]ERROR: memory overflow.\n") ;
336 cloog_loop_leak_up() ;
339 /* We set the various fields with default values. */
340 loop
->domain
= NULL
;
345 cloog_int_init(loop
->stride
);
346 cloog_int_set_si(loop
->stride
, 1);
353 * cloog_loop_alloc function:
354 * This function allocates the memory space for a CloogLoop structure and
355 * sets its fields with those given as input. Then it returns a pointer to the
357 * - October 27th 2001: first version.
358 * - June 22nd 2005: Adaptation for GMP.
359 * - November 21th 2005: use of cloog_loop_malloc.
361 CloogLoop
* cloog_loop_alloc(domain
, stride
, block
, inner
, next
)
362 CloogDomain
* domain
;
365 CloogLoop
* inner
, * next
;
368 loop
= cloog_loop_malloc() ;
370 loop
->domain
= domain
;
371 loop
->block
= block
;
372 loop
->inner
= inner
;
374 cloog_int_set(loop
->stride
, stride
);
381 * cloog_loop_add function:
382 * This function adds a CloogLoop structure (loop) at a given place (now) of a
383 * NULL terminated list of CloogLoop structures. The beginning of this list
384 * is (start). This function updates (now) to (loop), and updates (start) if the
385 * added element is the first one -that is when (start) is NULL-.
386 * - October 28th 2001: first version.
388 void cloog_loop_add(CloogLoop
** start
, CloogLoop
** now
, CloogLoop
* loop
)
389 { if (*start
== NULL
)
394 { (*now
)->next
= loop
;
395 *now
= (*now
)->next
;
401 * cloog_loop_add function:
402 * This function adds a CloogLoop structure (loop) at a given place (now) of a
403 * NULL terminated list of CloogLoop structures. The beginning of this list
404 * is (start). This function updates (now) to the end of the loop list (loop),
405 * and updates (start) if the added element is the first one -that is when
407 * - September 9th 2005: first version.
409 void cloog_loop_add_list(CloogLoop
** start
, CloogLoop
** now
, CloogLoop
* loop
)
410 { if (*start
== NULL
)
415 { (*now
)->next
= loop
;
416 *now
= (*now
)->next
;
419 while ((*now
)->next
!= NULL
)
420 *now
= (*now
)->next
;
425 * cloog_loop_copy function:
426 * This function returns a copy of the CloogLoop structure given as input. In
427 * fact, there is just new allocations for the CloogLoop structures, but their
428 * contents are the same.
429 * - October 28th 2001: first version.
430 * - July 3rd->11th 2003: memory leaks hunt and correction.
432 CloogLoop
* cloog_loop_copy(CloogLoop
* source
)
435 CloogDomain
* domain
;
439 { domain
= cloog_domain_copy(source
->domain
) ;
440 block
= cloog_block_copy(source
->block
) ;
441 loop
= cloog_loop_alloc(domain
,source
->stride
,block
,NULL
,NULL
) ;
442 loop
->usr
= source
->usr
;
443 loop
->inner
= cloog_loop_copy(source
->inner
) ;
444 loop
->next
= cloog_loop_copy(source
->next
) ;
451 * cloog_loop_add_disjoint function:
452 * This function adds some CloogLoop structures at a given place (now) of a
453 * NULL terminated list of CloogLoop structures. The beginning of this list
454 * is (start). (loop) can be an union of polyhedra, this function separates the
455 * union into a list of *disjoint* polyhedra then adds the list. This function
456 * updates (now) to the end of the list and updates (start) if first added
457 * element is the first of the principal list -that is when (start) is NULL-.
458 * (loop) can be freed by this function, basically when its domain is actually
459 * a union of polyhedra, but don't worry, all the useful data are now stored
460 * inside the list (start). We do not use PolyLib's Domain_Disjoint function,
461 * since the number of union components is often higher (thus code size too).
462 * - October 28th 2001: first version.
463 * - November 14th 2001: bug correction (this one was hard to find !).
464 * - July 3rd->11th 2003: memory leaks hunt and correction.
465 * - June 22nd 2005: Adaptation for GMP.
466 * - October 27th 2005: (debug) included blocks were not copied for new loops.
468 void cloog_loop_add_disjoint(start
, now
, loop
)
469 CloogLoop
** start
, ** now
, * loop
;
472 CloogLoop
* sep
, * inner
;
473 CloogDomain
* domain
, * convex
, * seen
, * seen_before
, * temp
, * rest
;
477 cloog_int_set_si(one
, 1);
479 if (cloog_domain_isconvex(loop
->domain
))
480 cloog_loop_add(start
,now
,loop
) ;
482 { /* Seems useless but may simplify the union expression (PolyLib pb). */
483 convex
= cloog_domain_convex(loop
->domain
) ;
484 temp
= cloog_domain_difference(convex
,loop
->domain
) ;
485 cloog_domain_free(loop
->domain
) ;
486 loop
->domain
= NULL
;
487 domain
= cloog_domain_difference(convex
,temp
) ;
488 cloog_domain_free(convex
) ;
489 cloog_domain_free(temp
) ;
491 /* We separate the first element of the rest of the union. */
492 rest
= cloog_domain_cut_first(domain
) ;
494 /* This first element is the first of the list of disjoint polyhedra. */
495 sep
= cloog_loop_alloc(domain
,one
,loop
->block
,loop
->inner
,NULL
) ;
496 cloog_loop_add(start
,now
,sep
) ;
498 /* If there are other elements, add a loop for each of them. */
500 { /* domain is used by the first element, and we will free 'seen', so... */
501 seen
= cloog_domain_copy(domain
) ;
503 while ((domain
= rest
) != NULL
)
504 { rest
= cloog_domain_cut_first(domain
) ;
505 temp
= cloog_domain_difference(domain
,seen
) ;
507 /* Each new loop will have its own life, for instance we can free its
508 * inner loop and included block. Then each one must have its own copy
509 * of both 'inner' and 'block'.
511 inner
= cloog_loop_copy(loop
->inner
) ;
512 block
= cloog_block_copy(loop
->block
) ;
514 sep
= cloog_loop_alloc(temp
,one
,block
,inner
,NULL
) ;
515 /* temp can be an union too. If so: recursion. */
516 if (cloog_domain_isconvex(temp
))
517 cloog_loop_add(start
,now
,sep
) ;
519 cloog_loop_add_disjoint(start
,now
,sep
) ;
523 seen
= cloog_domain_union(seen_before
,domain
) ;
525 cloog_domain_free(seen_before
) ;
526 cloog_domain_free(domain
) ;
529 cloog_loop_free_parts(loop
,0,0,0,0) ;
531 cloog_int_clear(one
);
536 * cloog_loop_disjoint function:
537 * This function returns a list of loops such that each loop with non-convex
538 * domain in the input list (loop) is separated into several loops where the
539 * domains are the components of the union of *disjoint* polyhedra equivalent
540 * to the original non-convex domain. See cloog_loop_add_disjoint comments
542 * - September 16th 2005: first version.
544 CloogLoop
* cloog_loop_disjoint(CloogLoop
* loop
)
545 { CloogLoop
*res
=NULL
, * now
=NULL
, * next
;
547 /* Because this is often the case, don't waste time ! */
548 if ((loop
!= NULL
) && cloog_domain_isconvex(loop
->domain
))
552 { next
= loop
->next
;
554 cloog_loop_add_disjoint(&res
,&now
,loop
) ;
563 * cloog_loop_restrict function:
564 * This function returns the (loop) in the context of (context): it makes the
565 * intersection between the (loop) domain and the (context), then it returns
566 * a pointer to a new loop, with this intersection as domain.
567 * - nb_par is the number of parameters.
569 * - October 27th 2001: first version.
570 * - June 15th 2005: a memory leak fixed (domain was not freed when empty).
571 * - June 22nd 2005: Adaptation for GMP.
573 CloogLoop
* cloog_loop_restrict(loop
, context
, nb_par
)
575 CloogDomain
* context
;
577 { int new_dimension
;
579 CloogDomain
* domain
, * extended_context
, * new_domain
;
580 CloogLoop
* new_loop
;
582 domain
= loop
->domain
;
583 if (cloog_domain_dimension(domain
) > cloog_domain_dimension(context
))
584 { new_dimension
= cloog_domain_dimension(domain
) - nb_par
;
585 extended_context
= cloog_domain_extend(context
,new_dimension
,nb_par
) ;
586 new_domain
= cloog_domain_intersection(extended_context
,loop
->domain
) ;
587 cloog_domain_free(extended_context
) ;
590 new_domain
= cloog_domain_intersection(context
,loop
->domain
) ;
592 if (cloog_domain_isempty(new_domain
))
593 { cloog_domain_free(new_domain
) ;
598 cloog_int_set_si(one
, 1);
599 new_loop
= cloog_loop_alloc(new_domain
,one
,loop
->block
,loop
->inner
,NULL
) ;
600 cloog_int_clear(one
);
607 * cloog_loop_project function:
608 * This function returns the projection of (loop) on the (level) first
609 * dimensions (outer loops). It makes the projection of the (loop) domain,
610 * then it returns a pointer to a new loop, with this projection as domain.
611 * - nb_par is the number of parameters.
613 * - October 27th 2001: first version.
614 * - July 3rd->11th 2003: memory leaks hunt and correction.
615 * - June 22nd 2005: Adaptation for GMP.
617 CloogLoop
* cloog_loop_project(CloogLoop
* loop
, int level
, int nb_par
)
620 CloogDomain
* new_domain
;
621 CloogLoop
* new_loop
, * copy
;
624 cloog_int_set_si(one
, 1);
626 copy
= cloog_loop_alloc(loop
->domain
,loop
->stride
,loop
->block
,
629 if ((cloog_domain_dimension(loop
->domain
)-nb_par
) == level
)
630 new_domain
= cloog_domain_copy(loop
->domain
) ;
632 new_domain
= cloog_domain_project(loop
->domain
,level
,nb_par
) ;
634 new_loop
= cloog_loop_alloc(new_domain
,one
,NULL
,copy
,NULL
) ;
635 cloog_int_clear(one
);
642 * cloog_loop_concat function:
643 * This function returns a pointer to the concatenation of the
644 * CloogLoop lists given as input.
645 * - October 28th 2001: first version.
647 CloogLoop
* cloog_loop_concat(CloogLoop
* a
, CloogLoop
* b
)
648 { CloogLoop
* loop
, * temp
;
653 { while (temp
->next
!= NULL
)
665 * cloog_loop_separate function:
666 * This function implements the Quillere algorithm for separation of multiple
667 * loops: for a given set of polyhedra (loop), it computes a set of disjoint
668 * polyhedra such that the unions of these sets are equal, and returns this set.
669 * - October 28th 2001: first version.
670 * - November 14th 2001: elimination of some unused blocks.
671 * - August 13th 2002: (debug) in the case of union of polyhedra for one
672 * loop, redundant constraints are fired.
673 * - July 3rd->11th 2003: memory leaks hunt and correction.
674 * - June 22nd 2005: Adaptation for GMP.
675 * - October 16th 2005: Removal of the non-shared constraint elimination when
676 * there is only one loop in the list (seems to work
677 * without now, DomainSimplify may have been improved).
678 * The problem was visible with test/iftest2.cloog.
680 CloogLoop
* cloog_loop_separate(CloogLoop
* loop
)
681 { int first
, lazy_equal
=0, lazy_disjoint
=0 ;
683 CloogLoop
* new_loop
, * new_inner
, * res
, * now
, * temp
, * Q
,
684 * inner
, * old
/*, * previous, * next*/ ;
685 CloogDomain
* UQ
, * old_UQ
, * domain
;
690 if (loop
->next
== NULL
)
691 return cloog_loop_disjoint(loop
) ;
694 cloog_int_set_si(one
, 1);
696 UQ
= cloog_domain_copy(loop
->domain
) ;
697 domain
= cloog_domain_copy(loop
->domain
) ;
698 res
= cloog_loop_alloc(domain
,one
,loop
->block
,loop
->inner
,NULL
) ;
701 while((loop
= loop
->next
) != NULL
)
705 /* For all Q, add Q-loop associated with the blocks of Q alone,
706 * and Q inter loop associated with the blocks of Q and loop.
710 { if (Q
->block
== NULL
)
711 { /* Add (Q inter loop). */
712 if((lazy_disjoint
=cloog_domain_lazy_disjoint(Q
->domain
,loop
->domain
)))
715 { if ((lazy_equal
= cloog_domain_lazy_equal(Q
->domain
,loop
->domain
)))
716 domain
= cloog_domain_copy(Q
->domain
) ;
718 domain
= cloog_domain_intersection(Q
->domain
,loop
->domain
) ;
720 if (!cloog_domain_isempty(domain
))
721 { new_inner
= cloog_loop_concat(cloog_loop_copy(Q
->inner
),
722 cloog_loop_copy(loop
->inner
)) ;
723 new_loop
= cloog_loop_alloc(domain
,one
,NULL
,new_inner
,NULL
) ;
724 cloog_loop_add_disjoint(&temp
,&now
,new_loop
) ;
727 cloog_domain_free(domain
) ;
730 /* Add (Q - loop). */
732 domain
= cloog_domain_copy(Q
->domain
) ;
735 domain
= cloog_domain_empty(cloog_domain_dimension(Q
->domain
)) ;
737 domain
= cloog_domain_difference(Q
->domain
,loop
->domain
) ;
740 if (!cloog_domain_isempty(domain
))
741 { new_loop
= cloog_loop_alloc(domain
,one
,NULL
,Q
->inner
,NULL
) ;
742 cloog_loop_add_disjoint(&temp
,&now
,new_loop
) ;
745 { cloog_domain_free(domain
) ;
746 /* If Q->inner is no more useful, we can free it. */
749 if (first
) /* For the first Q, inner is also old->inner. */
751 cloog_loop_free(inner
) ;
757 /* Add loop-UQ associated with the blocks of loop alone.*/
758 if (cloog_domain_lazy_disjoint(loop
->domain
,UQ
))
759 domain
= cloog_domain_copy(loop
->domain
) ;
761 { if (cloog_domain_lazy_equal(loop
->domain
,UQ
))
762 domain
= cloog_domain_empty(cloog_domain_dimension(UQ
)) ;
764 domain
= cloog_domain_difference(loop
->domain
,UQ
) ;
767 if (!cloog_domain_isempty(domain
))
768 { new_loop
= cloog_loop_alloc(domain
,one
,NULL
,loop
->inner
,NULL
) ;
769 cloog_loop_add_disjoint(&temp
,&now
,new_loop
) ;
772 { cloog_domain_free(domain
) ;
773 /* If loop->inner is no more useful, we can free it. */
774 cloog_loop_free(loop
->inner
) ;
780 if (loop
->next
!= NULL
)
781 UQ
= cloog_domain_union(UQ
,loop
->domain
) ;
783 cloog_domain_free(old_UQ
) ;
784 cloog_loop_free_parts(res
,1,0,0,1) ;
789 cloog_loop_free_parts(old
,1,0,0,1) ;
790 cloog_int_clear(one
);
797 * cloog_loop_merge_list
798 * Merge two lists of CloogLoops. The new list contains the
799 * elements of the two lists in the same order, but they may
801 * In particular, if the elements of a and b are ordered
802 * according to the inner loops of the order list, then so are the elements
805 static CloogLoop
*cloog_loop_merge_inner_list(CloogLoop
*a
, CloogLoop
*b
,
808 CloogLoop
*loop
, **next
;
811 for ( ; order
&& (a
||b
); order
= order
->next
) {
812 if (a
&& order
->inner
->block
== a
->block
) {
815 next
= &(*next
)->next
;
818 if (b
&& order
->inner
->block
== b
->block
) {
821 next
= &(*next
)->next
;
828 * cloog_loop_merge function:
829 * This function is the 'soft' version of loop_separate if we are looking for
830 * a code much simpler (and less efficicient). Here we merge loops if they have
831 * common parts in the iteration space (if the intersection of their domains is
832 * not empty), and let them isolated otherwise. This function returns the new
834 * - October 29th 2001: first version.
835 * - July 3rd->11th 2003: memory leaks hunt and correction.
836 * - June 22nd 2005: Adaptation for GMP.
838 CloogLoop
* cloog_loop_merge(CloogLoop
* loop
, int nb_par
, CloogOptions
* options
)
841 CloogLoop
* res
, * merge
, * now
, * Q
, * P
, * new_inner
, * next
, * old
;
842 CloogDomain
* new_domain
, * temp
;
844 if ((loop
== NULL
) || (loop
->next
== NULL
))
848 cloog_int_set_si(one
, 1);
850 /* First loop is added to the target list. */
851 res
= cloog_loop_alloc(loop
->domain
,one
,loop
->block
,loop
->inner
,NULL
) ;
853 /* Now the domain is in 'res' and it will be freed. */
854 loop
->domain
= NULL
;
856 /* And one by one, we see if we have to merge or to add the other loops. */
857 while((loop
= loop
->next
) != NULL
)
859 P
= cloog_loop_alloc(loop
->domain
,one
,loop
->block
,loop
->inner
,NULL
) ;
861 /* Now the domain is in 'P' and it will be freed. */
862 loop
->domain
= NULL
;
864 /* For each loop in the target list, if the intersection with the new loop
865 * is empty, we can add the new loop directly, otherwise, we can merge then
869 { temp
= cloog_domain_intersection(Q
->domain
,P
->domain
) ;
871 if (cloog_domain_isempty(temp
))
872 { cloog_domain_free(temp
) ;
873 cloog_loop_add_disjoint(&merge
,&now
,Q
) ;
876 { cloog_domain_free(temp
) ;
877 new_inner
= cloog_loop_merge_inner_list(Q
->inner
, P
->inner
, old
);
878 temp
= cloog_domain_union(P
->domain
,Q
->domain
) ;
880 new_domain
= cloog_domain_simple_convex(temp
, nb_par
);
882 new_domain
= cloog_domain_convex(temp
);
883 cloog_domain_free(temp
) ;
884 /* Q and P are no more used (but their content yes !).*/
885 cloog_loop_free_parts(P
,1,0,0,0) ;
886 cloog_loop_free_parts(Q
,1,0,0,0) ;
887 P
= cloog_loop_alloc(new_domain
,one
,NULL
,new_inner
,NULL
) ;
892 /* If there was merging, add it, otherwise add the loop lonely.
893 * DEBUG : ici pas besoin de s'assurer que P->next est NULL (possible que
894 * non si pas de fusion) car le dernier loop etudie a loop->next = NULL.
896 cloog_loop_add_disjoint(&merge
,&now
,P
) ;
899 cloog_loop_free_parts(old
,0,0,0,1) ;
900 cloog_int_clear(one
);
907 * cloog_loop_sort function:
908 * Adaptation from LoopGen 0.4 by F. Quillere. This function sorts a list of
909 * parameterized disjoint polyhedra, in order to not have lexicographic order
910 * violation (see Quillere paper).
911 * - September 16th 2005: inclusion of cloog_loop_number (October 29th 2001).
913 CloogLoop
* cloog_loop_sort(CloogLoop
* loop
, int level
, int nb_par
)
914 { CloogLoop
* res
, * now
, * temp
, ** loop_array
;
916 int i
, nb_loops
=0, * permut
;
918 /* We will need to know how many loops are in the list. */
925 /* If there is only one loop, it's the end. */
929 /* We have to allocate memory for some useful components:
930 * - loop_array: the loop array,
931 * - doms: the array of domains to sort,
932 * - permut: will give us a possible sort (maybe not the only one).
934 loop_array
= (CloogLoop
**)malloc(nb_loops
*sizeof(CloogLoop
*)) ;
935 doms
= (CloogDomain
**)malloc(nb_loops
*sizeof(CloogDomain
*));
936 permut
= (int *)malloc(nb_loops
*sizeof(int)) ;
938 /* We fill up the loop and domain arrays. */
939 for (i
=0;i
<nb_loops
;i
++,loop
=loop
->next
)
940 { loop_array
[i
] = loop
;
941 doms
[i
] = loop_array
[i
]->domain
;
944 /* cloog_domain_sort will fill up permut. */
945 cloog_domain_sort(doms
, nb_loops
, level
, nb_par
, permut
);
947 /* With permut and loop_array we build the sorted list. */
949 for (i
=0;i
<nb_loops
;i
++)
950 { /* To avoid pointer looping... loop_add will rebuild the list. */
951 loop_array
[permut
[i
]-1]->next
= NULL
;
952 cloog_loop_add(&res
,&now
,loop_array
[permut
[i
]-1]) ;
964 * cloog_loop_nest function:
965 * This function changes the loop list in such a way that we have no more than
966 * one dimension added by level. It returns an equivalent loop list with
968 * - October 29th 2001: first version.
969 * - July 3rd->11th 2003: memory leaks hunt and correction.
970 * - June 22nd 2005: Adaptation for GMP.
971 * - November 21th 2005: (debug) now OK when cloog_loop_restrict returns NULL.
973 CloogLoop
* cloog_loop_nest(loop
, context
, level
, nb_par
)
975 CloogDomain
* context
;
979 CloogLoop
* p
, * temp
, * res
, * now
, * next
;
980 CloogDomain
* new_domain
;
983 cloog_int_set_si(one
, 1);
986 /* Each domain is changed by its intersection with the context. */
988 { p
= cloog_loop_restrict(loop
,context
,nb_par
) ;
992 { cloog_loop_free_parts(loop
,1,0,0,0) ;
994 temp
= cloog_loop_alloc(p
->domain
,one
,p
->block
,p
->inner
,NULL
) ;
996 /* If the intersection dimension is too big, we make projections smaller
997 * and smaller, and each projection includes the preceding projection
998 * (thus, in the target list, dimensions are added one by one).
1000 if ((cloog_domain_dimension(p
->domain
)-nb_par
) > level
)
1001 for (l
=cloog_domain_dimension(p
->domain
)-nb_par
-1;l
>=level
;l
--)
1002 { new_domain
= cloog_domain_project(p
->domain
,l
,nb_par
) ;
1003 temp
= cloog_loop_alloc(new_domain
,one
,NULL
,temp
,NULL
) ;
1006 /* p is no more useful (but its content yes !). */
1007 cloog_loop_free_parts(p
,0,0,0,0) ;
1009 cloog_loop_add(&res
,&now
,temp
) ;
1012 cloog_loop_free_parts(loop
,1,1,1,0) ;
1016 cloog_int_clear(one
);
1023 * cloog_loop_stride function:
1024 * This function will find the stride of a loop for the iterator at the column
1025 * number 'level' in the constraint matrix. It will update the lower bound of
1026 * the iterator accordingly. Basically, the function will try to find in the
1027 * inner loops a common condition on this iterator for the inner loop iterators
1028 * to be integral. For instance, let us consider a loop with the iterator i,
1029 * the iteration domain -4<=i<=n, and its two inner loops with the iterator j.
1030 * The first inner loop has the constraint 3j=i, and the second one has the
1031 * constraint 6j=i. Then the common constraint on i for j to be integral is
1032 * i%3=0, the stride for i is 3. Lastly, we have to find the new lower bound
1033 * for i: the first value satisfying the common constraint: -3. At the end, the
1034 * iteration domain for i is -3<=i<=n and the stride for i is 3.
1035 * - loop is the loop including the iteration domain of the considered iterator,
1036 * - level is the column number of the iterator in the matrix of contraints.
1038 * - June 29th 2003: first version (work in progress since June 26th 2003).
1039 * - July 14th 2003: simpler version.
1040 * - June 22nd 2005: Adaptation for GMP (from S. Verdoolaege's 0.12.1 version).
1042 void cloog_loop_stride(CloogLoop
* loop
, int level
, int nb_par
)
1043 { int first_search
;
1044 cloog_int_t stride
, ref_offset
, offset
, potential
, lower
;
1047 cloog_int_init(stride
);
1048 cloog_int_init(ref_offset
);
1049 cloog_int_init(offset
);
1050 cloog_int_init(potential
);
1051 cloog_int_init(lower
);
1053 cloog_int_set_si(ref_offset
, 0);
1054 cloog_int_set_si(offset
, 0);
1055 cloog_int_set_si(lower
, 0);
1057 /* Default stride. */
1058 cloog_int_set_si(stride
, 1);
1060 inner
= loop
->inner
;
1062 if (cloog_domain_integral_lowerbound(loop
->domain
,level
,&lower
))
1063 while (inner
!= NULL
)
1064 { /* If the minimun stride has not been found yet, find the stride. */
1065 if ((first_search
) || (!cloog_int_is_one(stride
)))
1066 { cloog_domain_stride(inner
->domain
,level
,nb_par
,&potential
,&offset
) ;
1067 if (!cloog_int_is_one(potential
) && (!first_search
))
1068 { /* Offsets must be the same for common stride. */
1069 cloog_int_gcd(stride
, potential
, stride
);
1070 cloog_int_fdiv_r(offset
, offset
, stride
);
1071 cloog_int_fdiv_r(ref_offset
, ref_offset
, stride
);
1072 if (cloog_int_ne(offset
,ref_offset
))
1073 cloog_int_set_si(stride
, 1);
1076 cloog_int_set(stride
, potential
);
1077 cloog_int_set(ref_offset
, offset
);
1083 inner
= inner
->next
;
1086 /* Update the values if necessary. */
1087 if (!cloog_int_is_one(stride
))
1088 { /* Update the stride value. */
1089 cloog_int_set(loop
->stride
, stride
);
1090 /* The new lower bound l' is such that
1091 * (l' + offset) % s = 0 and l <= l' <= l+(s-1)
1092 * Let l' = k s - offset, then
1093 * k s - offset <= l + (s-1) <= k s - offset + (s-1)
1094 * Or l' = floor((l+offset+(s-1))/s) * s - offset
1095 * = (floor((l+offset-1)/s) + 1) * s - offset
1097 cloog_int_add(lower
, lower
, offset
);
1098 cloog_int_sub_ui(lower
, lower
, 1);
1099 cloog_int_fdiv_q(lower
, lower
, stride
);
1100 cloog_int_add_ui(lower
, lower
, 1);
1101 cloog_int_mul(lower
, lower
, stride
);
1102 cloog_int_sub(lower
, lower
, offset
);
1103 cloog_domain_lowerbound_update(loop
->domain
,level
,lower
) ;
1106 cloog_int_clear(stride
);
1107 cloog_int_clear(ref_offset
);
1108 cloog_int_clear(offset
);
1109 cloog_int_clear(potential
);
1110 cloog_int_clear(lower
);
1115 * cloog_loop_stop function:
1116 * This function implements the 'stop' option : each domain of each loop
1117 * in the list 'loop' is replaced by 'context'. 'context' should be the
1118 * domain of the outer loop. By using this method, there are no more dimensions
1119 * to scan and the simplification step will automaticaly remove the domains
1120 * since they are the same as the corresponding contexts. The effect of this
1121 * function is to stop the code generation at the level this function is called,
1122 * the resulting code do not consider the next dimensions.
1123 * - January 11th 2005: first version.
1125 CloogLoop
* cloog_loop_stop(CloogLoop
* loop
, CloogDomain
* context
)
1129 { cloog_domain_free(loop
->domain
) ;
1130 loop
->domain
= cloog_domain_copy(context
) ;
1131 loop
->next
= cloog_loop_stop(loop
->next
, context
) ;
1139 * cloog_loop_scalar_gt function:
1140 * This function returns 1 if loop 'l1' is greater than loop 'l2' for the
1141 * scalar dimension vector that begins at dimension 'scalar', 0 otherwise. What
1142 * we want to know is whether a loop is scheduled before another one or not.
1143 * This function solves the problem when the considered dimension for scheduling
1144 * is a scalar dimension. Since there may be a succession of scalar dimensions,
1145 * this function will reason about the vector of scalar dimension that begins
1146 * at dimension 'level+scalar' and finish to the first non-scalar dimension.
1147 * \param l1 Loop to be compared with l2.
1148 * \param l2 Loop to be compared with l1.
1149 * \param level Current non-scalar dimension.
1150 * \param scaldims Boolean array saying whether a dimension is scalar or not.
1151 * \param nb_scattdims Size of the scaldims array.
1152 * \param scalar Current scalar dimension.
1153 * \return 1 if (l1 > l2), 0 otherwise.
1155 * - September 9th 2005: first version.
1156 * - October 15nd 2007: now "greater than" instead of "greater or equal".
1158 int cloog_loop_scalar_gt(l1
, l2
, level
, scaldims
, nb_scattdims
, scalar
)
1159 CloogLoop
* l1
, * l2
;
1160 int level
, * scaldims
, nb_scattdims
, scalar
;
1161 { while ((scalar
< l1
->inner
->block
->nb_scaldims
) && scaldims
[level
+scalar
-1])
1162 { if (cloog_int_gt(l1
->inner
->block
->scaldims
[scalar
],
1163 l2
->inner
->block
->scaldims
[scalar
]))
1173 * cloog_loop_scalar_eq function:
1174 * This function returns 1 if loop 'l1' is equal to loop 'l2' for the scalar
1175 * dimension vector that begins at dimension 'scalar', 0 otherwise. What we want
1176 * to know is whether two loops are scheduled for the same time or not.
1177 * This function solves the problem when the considered dimension for scheduling
1178 * is a scalar dimension. Since there may be a succession of scalar dimensions,
1179 * this function will reason about the vector of scalar dimension that begins
1180 * at dimension 'level+scalar' and finish to the first non-scalar dimension.
1181 * - l1 and l2 are the loops to compare,
1182 * - level is the current non-scalar dimension,
1183 * - scaldims is the boolean array saying whether a dimension is scalar or not,
1184 * - nb_scattdims is the size of the scaldims array,
1185 * - scalar is the current scalar dimension.
1187 * - September 9th 2005 : first version.
1189 int cloog_loop_scalar_eq(l1
, l2
, level
, scaldims
, nb_scattdims
, scalar
)
1190 CloogLoop
* l1
, * l2
;
1191 int level
, * scaldims
, nb_scattdims
, scalar
;
1192 { while ((scalar
< l1
->inner
->block
->nb_scaldims
) && scaldims
[level
+scalar
-1])
1193 { if (cloog_int_eq(l1
->inner
->block
->scaldims
[scalar
],
1194 l2
->inner
->block
->scaldims
[scalar
]))
1204 * cloog_loop_scalar_sort function:
1205 * This function sorts a linked list of loops (loop) with respect to the
1206 * scalar dimension vector that begins at dimension 'scalar'. Since there may
1207 * be a succession of scalar dimensions, this function will reason about the
1208 * vector of scalar dimension that begins at dimension 'level+scalar' and
1209 * finish to the first non-scalar dimension.
1210 * \param loop Loop list to sort.
1211 * \param level Current non-scalar dimension.
1212 * \param scaldims Boolean array saying whether a dimension is scalar or not.
1213 * \param nb_scattdims Size of the scaldims array.
1214 * \param scalar Current scalar dimension.
1215 * \return A pointer to the sorted list.
1217 * - July 2nd 2005: first developments.
1218 * - September 2nd 2005: first version.
1219 * - October 15nd 2007: complete rewrite to remove bugs, now a bubble sort.
1221 CloogLoop
* cloog_loop_scalar_sort(loop
, level
, scaldims
, nb_scattdims
, scalar
)
1223 int level
, * scaldims
, nb_scattdims
, scalar
;
1225 CloogLoop
**current
;
1229 for (current
= &loop
; (*current
)->next
; current
= &(*current
)->next
) {
1230 CloogLoop
*next
= (*current
)->next
;
1231 if (cloog_loop_scalar_gt(*current
,next
,level
,scaldims
,nb_scattdims
,scalar
)) {
1233 (*current
)->next
= next
->next
;
1234 next
->next
= *current
;
1245 * cloog_loop_generate_backtrack function:
1246 * adaptation from LoopGen 0.4 by F. Quillere. This function implements the
1247 * backtrack of the Quillere et al. algorithm (see the Quillere paper).
1248 * It eliminates unused iterations of the current level for the new one. See the
1249 * example called linearity-1-1 example with and without this part for an idea.
1250 * - October 26th 2001: first version in cloog_loop_generate_general.
1251 * - July 31th 2002: (debug) no more parasite loops (REALLY hard !).
1252 * - October 30th 2005: extraction from cloog_loop_generate_general.
1254 CloogLoop
* cloog_loop_generate_backtrack(loop
, context
, level
, nb_par
, options
)
1256 CloogDomain
* context
;
1258 CloogOptions
* options
;
1261 CloogDomain
* domain
;
1262 CloogLoop
* now
, * now2
, * next
, * next2
, * end
, * temp
, * l
, * inner
,
1265 cloog_int_init(one
);
1266 cloog_int_set_si(one
, 1);
1271 while (temp
!= NULL
)
1273 inner
= temp
->inner
;
1275 while (inner
!= NULL
)
1276 { next
= inner
->next
;
1277 /* This 'if' and its first part is the debug of july 31th 2002. */
1278 if (inner
->block
!= NULL
)
1279 { end
= cloog_loop_alloc(inner
->domain
,one
,inner
->block
,NULL
,NULL
) ;
1280 domain
= cloog_domain_copy(temp
->domain
) ;
1281 new_loop
= cloog_loop_alloc(domain
,one
,NULL
,end
,NULL
) ;
1284 new_loop
= cloog_loop_project(inner
,level
,nb_par
) ;
1286 cloog_loop_free_parts(inner
,0,0,0,0) ;
1287 cloog_loop_add(&l
,&now2
,new_loop
) ;
1291 temp
->inner
= NULL
;
1294 { l
= cloog_loop_separate(l
) ;
1295 l
= cloog_loop_sort(l
,level
,nb_par
) ;
1297 cloog_int_set(l
->stride
, temp
->stride
);
1298 cloog_loop_add(&loop
,&now
,l
) ;
1302 next2
= temp
->next
;
1303 cloog_loop_free_parts(temp
,1,0,0,0) ;
1307 cloog_int_clear(one
);
1314 * cloog_loop_generate_general function:
1315 * Adaptation from LoopGen 0.4 by F. Quillere. This function implements the
1316 * Quillere algorithm for polyhedron scanning from step 3 to 5.
1317 * (see the Quillere paper).
1318 * - loop is the loop for which we have to generate a scanning code,
1319 * - context is the context of the current loop (constraints on parameter and/or
1320 * on outer loop counters),
1321 * - level is the current non-scalar dimension,
1322 * - scalar is the current scalar dimension,
1323 * - scaldims is the boolean array saying whether a dimension is scalar or not,
1324 * - nb_scattdims is the size of the scaldims array,
1325 * - nb_par is the number of parameters,
1326 * - options are the general code generation options.
1328 * - October 26th 2001: first version.
1329 * - July 3rd->11th 2003: memory leaks hunt and correction.
1330 * - June 22nd 2005: Adaptation for GMP.
1331 * - September 2nd 2005: The function have been cutted out in two pieces:
1332 * cloog_loop_generate and this one, in order to handle
1333 * the scalar dimension case more efficiently with
1334 * cloog_loop_generate_scalar.
1335 * - November 15th 2005: (debug) the result of the cloog_loop_generate call may
1336 * be a list of polyhedra (especially if stop option is
1337 * used): cloog_loop_add_list instead of cloog_loop_add.
1339 CloogLoop
* cloog_loop_generate_general(loop
, context
, level
, scalar
,
1340 scaldims
, nb_scattdims
, nb_par
, options
)
1342 CloogDomain
* context
;
1343 int level
, scalar
, * scaldims
, nb_scattdims
, nb_par
;
1344 CloogOptions
* options
;
1347 CloogLoop
* res
, * now
, * temp
, * l
, * new_loop
, * inner
, * now2
, * end
,
1349 CloogDomain
* domain
;
1351 /* 3. Separate all projections into disjoint polyhedra. */
1352 res
= ((options
->f
> level
+scalar
) || (options
->f
< 0)) ?
1353 cloog_loop_merge(loop
, nb_par
, options
) : cloog_loop_separate(loop
);
1355 /* 3b. -correction- sort the loops to determine their textual order. */
1356 res
= cloog_loop_sort(res
,level
,nb_par
) ;
1358 cloog_int_init(one
);
1359 cloog_int_set_si(one
, 1);
1361 /* 4. Recurse for each loop with the current domain as context. */
1364 if ((level
+scalar
< options
->l
) || (options
->l
< 0))
1366 { if (options
->strides
)
1367 cloog_loop_stride(temp
,level
,nb_par
) ;
1368 inner
= temp
->inner
;
1369 domain
= temp
->domain
;
1371 while (inner
!= NULL
)
1372 { /* 4b. -ced- recurse for each sub-list of non terminal loops. */
1373 if (cloog_domain_dimension(inner
->domain
) > (level
+ nb_par
))
1375 while ((end
->next
!= NULL
) &&
1376 (cloog_domain_dimension(end
->next
->domain
) > (level
+ nb_par
)))
1382 l
= cloog_loop_generate(inner
,domain
,level
+1,scalar
,
1383 scaldims
,nb_scattdims
,nb_par
,options
) ;
1386 cloog_loop_add_list(&into
,&now
,l
) ;
1391 { cloog_loop_add(&into
,&now
,inner
) ;
1392 inner
= inner
->next
;
1397 temp
->inner
= into
;
1398 cloog_loop_add(&res
,&now2
,temp
) ;
1402 while (temp
!= NULL
)
1403 { next
= temp
->next
;
1404 l
= cloog_loop_nest(temp
->inner
,temp
->domain
,level
+1,nb_par
) ;
1405 new_loop
= cloog_loop_alloc(temp
->domain
,one
,NULL
,l
,NULL
) ;
1406 temp
->inner
= NULL
;
1408 cloog_loop_free_parts(temp
,0,0,0,0) ;
1409 cloog_loop_add(&res
,&now
,new_loop
) ;
1413 /* 5. eliminate unused iterations of the current level for the new one. See
1414 * the example called linearity-1-1 example with and without this part
1417 if ((!options
->nobacktrack
) &&
1418 ((level
+scalar
< options
->l
) || (options
->l
< 0)) &&
1419 ((options
->f
<= level
+scalar
) && !(options
->f
< 0)))
1420 res
= cloog_loop_generate_backtrack(res
,context
,level
,nb_par
,options
) ;
1422 /* Pray for my new paper to be accepted somewhere since the following stuff
1423 * is really amazing :-) !
1424 * Far long later: The paper has been accepted to PACT 2004 :-))). But there
1425 * are still some bugs and I have no time to fix them. Thus now you have to
1426 * pray for me to get an academic position for that really amazing stuff :-) !
1427 * Later again: OK, I get my academic position, but still I have not enough
1428 * time to fix and clean this part... Pray again :-) !!!
1430 /* res = cloog_loop_unisolate(res,context,level,nb_par) ;*/
1432 cloog_int_clear(one
);
1438 * cloog_loop_generate_scalar function:
1439 * This function applies the simplified code generation scheme in the trivial
1440 * case of scalar dimensions. When dealing with scalar dimensions, there is
1441 * no need of costly polyhedral operations for separation or sorting: sorting
1442 * is a question of comparing scalar vectors and separation amounts to consider
1443 * only loops with the same scalar vector for the next step of the code
1444 * generation process. This function achieves the separation/sorting process
1445 * for the vector of scalar dimension that begins at dimension 'level+scalar'
1446 * and finish to the first non-scalar dimension.
1447 * - loop is the loop for which we have to generate a scanning code,
1448 * - context is the context of the current loop (constraints on parameter and/or
1449 * on outer loop counters),
1450 * - level is the current non-scalar dimension,
1451 * - scalar is the current scalar dimension,
1452 * - scaldims is the boolean array saying whether a dimension is scalar or not,
1453 * - nb_scattdims is the size of the scaldims array,
1454 * - nb_par is the number of parameters,
1455 * - options are the general code generation options.
1457 * - September 2nd 2005: First version.
1459 CloogLoop
* cloog_loop_generate_scalar(loop
, context
, level
, scalar
,
1460 scaldims
, nb_scattdims
, nb_par
, options
)
1462 CloogDomain
* context
;
1463 int level
, scalar
, * scaldims
, nb_scattdims
, nb_par
;
1464 CloogOptions
* options
;
1465 { CloogLoop
* res
, * now
, * temp
, * l
, * end
, * next
, * ref
;
1467 /* We sort the loop list with respect to the current scalar vector. */
1468 res
= cloog_loop_scalar_sort(loop
,level
,scaldims
,nb_scattdims
,scalar
) ;
1472 while (temp
!= NULL
)
1473 { /* Then we will appy the general code generation process to each sub-list
1474 * of loops with the same scalar vector.
1479 while((end
->next
!= NULL
) &&
1480 cloog_loop_scalar_eq(ref
,end
->next
,level
,scaldims
,nb_scattdims
,scalar
))
1486 /* For the next dimension, scalar value is updated by adding the scalar
1487 * vector size, which is stored at scaldims[level+scalar-1].
1489 l
= cloog_loop_generate_general(temp
,context
,level
,
1490 scalar
+scaldims
[level
+scalar
-1],
1491 scaldims
,nb_scattdims
,nb_par
,options
) ;
1494 cloog_loop_add_list(&res
,&now
,l
) ;
1504 * cloog_loop_generate function:
1505 * Adaptation from LoopGen 0.4 by F. Quillere. This function implements the
1506 * Quillere algorithm for polyhedron scanning from step 1 to 2.
1507 * (see the Quillere paper).
1508 * - loop is the loop for which we have to generate a scanning code,
1509 * - context is the context of the current loop (constraints on parameter and/or
1510 * on outer loop counters),
1511 * - level is the current non-scalar dimension,
1512 * - scalar is the current scalar dimension,
1513 * - scaldims is the boolean array saying whether a dimension is scalar or not,
1514 * - nb_scattdims is the size of the scaldims array,
1515 * - nb_par is the number of parameters,
1516 * - options are the general code generation options.
1518 * - October 26th 2001: first version.
1519 * - July 3rd->11th 2003: memory leaks hunt and correction.
1520 * - June 15th 2005: a memory leak fixed (loop was not entirely freed when
1521 * the result of cloog_loop_restrict was NULL).
1522 * - June 22nd 2005: Adaptation for GMP.
1523 * - September 2nd 2005: The function have been cutted out in two pieces:
1524 * cloog_loop_generate and this one, in order to handle
1525 * the scalar dimension case more efficiently with
1526 * cloog_loop_generate_scalar.
1527 * - November 15th 2005: (debug) Condition for stop option no more take care of
1528 * further scalar dimensions.
1530 CloogLoop
* cloog_loop_generate(loop
, context
, level
, scalar
,
1531 scaldims
, nb_scattdims
, nb_par
, options
)
1533 CloogDomain
* context
;
1534 int level
, scalar
, * scaldims
, nb_scattdims
, nb_par
;
1535 CloogOptions
* options
;
1536 { CloogLoop
* res
, * now
, * temp
, * next
, * old
;
1538 /* If the user asked to stop code generation at this level, let's stop. */
1539 if ((options
->stop
>= 0) && (level
+scalar
>= options
->stop
+1))
1540 return cloog_loop_stop(loop
,context
) ;
1544 /* 1. Replace each polyhedron by its intersection with the context.
1545 * 2. Compute the projection of each polyhedron onto the outermost
1546 * loop variable and the parameters.
1548 while (loop
!= NULL
)
1549 { next
= loop
->next
;
1550 temp
= cloog_loop_restrict(loop
,context
,nb_par
) ;
1554 temp
= cloog_loop_project(temp
,level
,nb_par
) ;
1555 cloog_loop_free_parts(old
,0,0,0,0) ;
1556 cloog_loop_add(&res
,&now
,temp
) ;
1557 cloog_loop_free_parts(loop
,1,0,0,0) ;
1560 { loop
->next
= NULL
;
1561 cloog_loop_free(loop
) ;
1569 /* To save both time and memory, we switch here depending on whether the
1570 * current dimension is scalar (simplified processing) or not (general
1573 if ((level
+scalar
<= nb_scattdims
) && (scaldims
[level
+scalar
-1]))
1574 res
= cloog_loop_generate_scalar(res
,context
,level
,scalar
,
1575 scaldims
,nb_scattdims
,nb_par
,options
) ;
1577 res
= cloog_loop_generate_general(res
,context
,level
,scalar
,
1578 scaldims
,nb_scattdims
,nb_par
,options
) ;
1585 * cloog_loop_simplify function:
1586 * This function implements the part 6. of the Quillere algorithm, it
1587 * recursively simplifies each loop in the context of the preceding loop domain.
1588 * It returns a pointer to the simplified loop list.
1589 * The cloog_domain_simplify (DomainSimplify) behaviour is really bad with
1590 * polyhedra union and some really awful sidesteppings were written, I plan
1592 * - October 31th 2001: first version.
1593 * - July 3rd->11th 2003: memory leaks hunt and correction.
1594 * - April 16th 2005: a memory leak fixed (extended_context was not freed).
1595 * - June 15th 2005: a memory leak fixed (loop was not conveniently freed
1596 * when the constraint system is never true).
1597 * - October 27th 2005: - this function called before cloog_loop_fast_simplify
1598 * is now the official cloog_loop_simplify function in
1599 * replacement of a slower and more complex one (after
1600 * deep changes in the pretty printer).
1601 * - we use cloog_loop_disjoint to fix the problem when
1602 * simplifying gives a union of polyhedra (before, it
1603 * was under the responsibility of the pretty printer).
1605 CloogLoop
* cloog_loop_simplify(loop
, context
, level
, nb_par
)
1607 CloogDomain
* context
;
1610 CloogBlock
* new_block
;
1611 CloogLoop
* simplified
, * inner
, * next
;
1612 CloogDomain
* domain
, * simp
, * inter
, * extended_context
;
1617 domain
= loop
->domain
;
1619 next
= cloog_loop_simplify(loop
->next
,context
,level
,nb_par
) ;
1621 domain_dim
= cloog_domain_dimension(domain
) - nb_par
;
1622 extended_context
=cloog_domain_extend(context
,domain_dim
,nb_par
);
1623 inter
= cloog_domain_intersection(domain
,extended_context
) ;
1624 simp
= cloog_domain_simplify(inter
,extended_context
) ;
1625 cloog_domain_free(extended_context
) ;
1627 /* If the constraint system is never true, go to the next one. */
1628 if (cloog_domain_never_integral(simp
)) {
1630 cloog_loop_free(loop
);
1631 cloog_domain_free(inter
);
1632 cloog_domain_free(simp
);
1636 inner
= cloog_loop_simplify(loop
->inner
,inter
,level
+1,nb_par
) ;
1637 cloog_domain_free(inter
) ;
1639 if ((inner
== NULL
) && (loop
->block
== NULL
))
1640 { loop
->inner
= NULL
; /* For loop integrity. */
1641 loop
->next
= NULL
; /* For loop integrity. */
1642 cloog_loop_free_parts(loop
,1,1,1,0) ;
1643 cloog_domain_free(simp
);
1647 new_block
= cloog_block_copy(loop
->block
) ;
1649 simplified
= cloog_loop_alloc(simp
,loop
->stride
,new_block
,inner
,next
) ;
1651 /* Examples like test/iftest2.cloog give unions of polyhedra after
1652 * simplifying, thus we we have to disjoint them. Another good reason to
1653 * put the simplifying step in the Quillere backtrack.
1655 simplified
= cloog_loop_disjoint(simplified
) ;
1657 loop
->inner
= NULL
; /* For loop integrity. */
1658 loop
->next
= NULL
; /* For loop integrity. */
1659 cloog_loop_free_parts(loop
,1,1,0,0) ;
1661 return(simplified
) ;
1666 * cloog_loop_scatter function:
1667 * This function add the scattering (scheduling) informations in a loop.
1669 void cloog_loop_scatter(CloogLoop
* loop
, CloogScattering
*scatt
)
1671 loop
->domain
= cloog_domain_scatter(loop
->domain
, scatt
);