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 domain
= cloog_domain_cut_first(domain
, &rest
);
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 seen
= cloog_domain_copy(domain
);
499 while (!cloog_domain_isempty(domain
= rest
)) {
500 temp
= cloog_domain_cut_first(domain
, &rest
);
501 domain
= cloog_domain_difference(temp
, seen
);
502 cloog_domain_free(temp
);
504 if (cloog_domain_isempty(domain
)) {
505 cloog_domain_free(domain
);
509 /* Each new loop will have its own life, for instance we can free its
510 * inner loop and included block. Then each one must have its own copy
511 * of both 'inner' and 'block'.
513 inner
= cloog_loop_copy(loop
->inner
) ;
514 block
= cloog_block_copy(loop
->block
) ;
516 sep
= cloog_loop_alloc(cloog_domain_copy(domain
), one
, block
, inner
, NULL
);
517 /* domain can be an union too. If so: recursion. */
518 if (cloog_domain_isconvex(domain
))
519 cloog_loop_add(start
,now
,sep
) ;
521 cloog_loop_add_disjoint(start
,now
,sep
) ;
523 if (cloog_domain_isempty(rest
)) {
524 cloog_domain_free(domain
);
529 seen
= cloog_domain_union(seen_before
, domain
);
530 cloog_domain_free(domain
);
531 cloog_domain_free(seen_before
);
533 cloog_domain_free(rest
);
534 cloog_domain_free(seen
);
535 cloog_loop_free_parts(loop
,0,0,0,0) ;
537 cloog_int_clear(one
);
542 * cloog_loop_disjoint function:
543 * This function returns a list of loops such that each loop with non-convex
544 * domain in the input list (loop) is separated into several loops where the
545 * domains are the components of the union of *disjoint* polyhedra equivalent
546 * to the original non-convex domain. See cloog_loop_add_disjoint comments
548 * - September 16th 2005: first version.
550 CloogLoop
* cloog_loop_disjoint(CloogLoop
* loop
)
551 { CloogLoop
*res
=NULL
, * now
=NULL
, * next
;
553 /* Because this is often the case, don't waste time ! */
554 if ((loop
!= NULL
) && cloog_domain_isconvex(loop
->domain
))
558 { next
= loop
->next
;
560 cloog_loop_add_disjoint(&res
,&now
,loop
) ;
569 * cloog_loop_restrict function:
570 * This function returns the (loop) in the context of (context): it makes the
571 * intersection between the (loop) domain and the (context), then it returns
572 * a pointer to a new loop, with this intersection as domain.
573 * - nb_par is the number of parameters.
575 * - October 27th 2001: first version.
576 * - June 15th 2005: a memory leak fixed (domain was not freed when empty).
577 * - June 22nd 2005: Adaptation for GMP.
579 CloogLoop
* cloog_loop_restrict(loop
, context
, nb_par
)
581 CloogDomain
* context
;
583 { int new_dimension
;
585 CloogDomain
* domain
, * extended_context
, * new_domain
;
586 CloogLoop
* new_loop
;
588 domain
= loop
->domain
;
589 if (cloog_domain_dimension(domain
) > cloog_domain_dimension(context
))
590 { new_dimension
= cloog_domain_dimension(domain
) - nb_par
;
591 extended_context
= cloog_domain_extend(context
,new_dimension
,nb_par
) ;
592 new_domain
= cloog_domain_intersection(extended_context
,loop
->domain
) ;
593 cloog_domain_free(extended_context
) ;
596 new_domain
= cloog_domain_intersection(context
,loop
->domain
) ;
598 if (cloog_domain_isempty(new_domain
))
599 { cloog_domain_free(new_domain
) ;
604 cloog_int_set_si(one
, 1);
605 new_loop
= cloog_loop_alloc(new_domain
,one
,loop
->block
,loop
->inner
,NULL
) ;
606 cloog_int_clear(one
);
613 * cloog_loop_project function:
614 * This function returns the projection of (loop) on the (level) first
615 * dimensions (outer loops). It makes the projection of the (loop) domain,
616 * then it returns a pointer to a new loop, with this projection as domain.
617 * - nb_par is the number of parameters.
619 * - October 27th 2001: first version.
620 * - July 3rd->11th 2003: memory leaks hunt and correction.
621 * - June 22nd 2005: Adaptation for GMP.
623 CloogLoop
* cloog_loop_project(CloogLoop
* loop
, int level
, int nb_par
)
626 CloogDomain
* new_domain
;
627 CloogLoop
* new_loop
, * copy
;
630 cloog_int_set_si(one
, 1);
632 copy
= cloog_loop_alloc(loop
->domain
,loop
->stride
,loop
->block
,
635 if ((cloog_domain_dimension(loop
->domain
)-nb_par
) == level
)
636 new_domain
= cloog_domain_copy(loop
->domain
) ;
638 new_domain
= cloog_domain_project(loop
->domain
,level
,nb_par
) ;
640 new_loop
= cloog_loop_alloc(new_domain
,one
,NULL
,copy
,NULL
) ;
641 cloog_int_clear(one
);
648 * cloog_loop_concat function:
649 * This function returns a pointer to the concatenation of the
650 * CloogLoop lists given as input.
651 * - October 28th 2001: first version.
653 CloogLoop
* cloog_loop_concat(CloogLoop
* a
, CloogLoop
* b
)
654 { CloogLoop
* loop
, * temp
;
659 { while (temp
->next
!= NULL
)
671 * cloog_loop_separate function:
672 * This function implements the Quillere algorithm for separation of multiple
673 * loops: for a given set of polyhedra (loop), it computes a set of disjoint
674 * polyhedra such that the unions of these sets are equal, and returns this set.
675 * - October 28th 2001: first version.
676 * - November 14th 2001: elimination of some unused blocks.
677 * - August 13th 2002: (debug) in the case of union of polyhedra for one
678 * loop, redundant constraints are fired.
679 * - July 3rd->11th 2003: memory leaks hunt and correction.
680 * - June 22nd 2005: Adaptation for GMP.
681 * - October 16th 2005: Removal of the non-shared constraint elimination when
682 * there is only one loop in the list (seems to work
683 * without now, DomainSimplify may have been improved).
684 * The problem was visible with test/iftest2.cloog.
686 CloogLoop
* cloog_loop_separate(CloogLoop
* loop
)
687 { int first
, lazy_equal
=0, lazy_disjoint
=0 ;
689 CloogLoop
* new_loop
, * new_inner
, * res
, * now
, * temp
, * Q
,
690 * inner
, * old
/*, * previous, * next*/ ;
691 CloogDomain
* UQ
, * old_UQ
, * domain
;
696 if (loop
->next
== NULL
)
697 return cloog_loop_disjoint(loop
) ;
700 cloog_int_set_si(one
, 1);
702 UQ
= cloog_domain_copy(loop
->domain
) ;
703 domain
= cloog_domain_copy(loop
->domain
) ;
704 res
= cloog_loop_alloc(domain
,one
,loop
->block
,loop
->inner
,NULL
) ;
707 while((loop
= loop
->next
) != NULL
)
711 /* For all Q, add Q-loop associated with the blocks of Q alone,
712 * and Q inter loop associated with the blocks of Q and loop.
716 { if (Q
->block
== NULL
)
717 { /* Add (Q inter loop). */
718 if((lazy_disjoint
=cloog_domain_lazy_disjoint(Q
->domain
,loop
->domain
)))
721 { if ((lazy_equal
= cloog_domain_lazy_equal(Q
->domain
,loop
->domain
)))
722 domain
= cloog_domain_copy(Q
->domain
) ;
724 domain
= cloog_domain_intersection(Q
->domain
,loop
->domain
) ;
726 if (!cloog_domain_isempty(domain
))
727 { new_inner
= cloog_loop_concat(cloog_loop_copy(Q
->inner
),
728 cloog_loop_copy(loop
->inner
)) ;
729 new_loop
= cloog_loop_alloc(domain
,one
,NULL
,new_inner
,NULL
) ;
730 cloog_loop_add_disjoint(&temp
,&now
,new_loop
) ;
733 cloog_domain_free(domain
) ;
736 /* Add (Q - loop). */
738 domain
= cloog_domain_copy(Q
->domain
) ;
741 domain
= cloog_domain_empty(Q
->domain
);
743 domain
= cloog_domain_difference(Q
->domain
,loop
->domain
) ;
746 if (!cloog_domain_isempty(domain
))
747 { new_loop
= cloog_loop_alloc(domain
,one
,NULL
,Q
->inner
,NULL
) ;
748 cloog_loop_add_disjoint(&temp
,&now
,new_loop
) ;
751 { cloog_domain_free(domain
) ;
752 /* If Q->inner is no more useful, we can free it. */
755 if (first
) /* For the first Q, inner is also old->inner. */
757 cloog_loop_free(inner
) ;
763 /* Add loop-UQ associated with the blocks of loop alone.*/
764 if (cloog_domain_lazy_disjoint(loop
->domain
,UQ
))
765 domain
= cloog_domain_copy(loop
->domain
) ;
767 { if (cloog_domain_lazy_equal(loop
->domain
,UQ
))
768 domain
= cloog_domain_empty(UQ
);
770 domain
= cloog_domain_difference(loop
->domain
,UQ
) ;
773 if (!cloog_domain_isempty(domain
))
774 { new_loop
= cloog_loop_alloc(domain
,one
,NULL
,loop
->inner
,NULL
) ;
775 cloog_loop_add_disjoint(&temp
,&now
,new_loop
) ;
778 { cloog_domain_free(domain
) ;
779 /* If loop->inner is no more useful, we can free it. */
780 cloog_loop_free(loop
->inner
) ;
786 if (loop
->next
!= NULL
)
787 UQ
= cloog_domain_union(UQ
,loop
->domain
) ;
789 cloog_domain_free(old_UQ
) ;
790 cloog_loop_free_parts(res
,1,0,0,1) ;
795 cloog_loop_free_parts(old
,1,0,0,1) ;
796 cloog_int_clear(one
);
803 * cloog_loop_merge_list
804 * Merge two lists of CloogLoops. The new list contains the
805 * elements of the two lists in the same order, but they may
807 * In particular, if the elements of a and b are ordered
808 * according to the inner loops of the order list, then so are the elements
811 static CloogLoop
*cloog_loop_merge_inner_list(CloogLoop
*a
, CloogLoop
*b
,
814 CloogLoop
*loop
, **next
;
817 for ( ; order
&& (a
||b
); order
= order
->next
) {
818 if (a
&& order
->inner
->block
== a
->block
) {
821 next
= &(*next
)->next
;
824 if (b
&& order
->inner
->block
== b
->block
) {
827 next
= &(*next
)->next
;
834 * cloog_loop_merge function:
835 * This function is the 'soft' version of loop_separate if we are looking for
836 * a code much simpler (and less efficicient). Here we merge loops if they have
837 * common parts in the iteration space (if the intersection of their domains is
838 * not empty), and let them isolated otherwise. This function returns the new
840 * - October 29th 2001: first version.
841 * - July 3rd->11th 2003: memory leaks hunt and correction.
842 * - June 22nd 2005: Adaptation for GMP.
844 CloogLoop
* cloog_loop_merge(CloogLoop
* loop
, int nb_par
, CloogOptions
* options
)
847 CloogLoop
* res
, * merge
, * now
, * Q
, * P
, * new_inner
, * next
, * old
;
848 CloogDomain
* new_domain
, * temp
;
853 if (loop
->next
== NULL
)
854 return cloog_loop_disjoint(loop
);
857 cloog_int_set_si(one
, 1);
859 /* First loop is added to the target list. */
860 res
= cloog_loop_alloc(loop
->domain
,one
,loop
->block
,loop
->inner
,NULL
) ;
862 /* Now the domain is in 'res' and it will be freed. */
863 loop
->domain
= NULL
;
865 /* And one by one, we see if we have to merge or to add the other loops. */
866 while((loop
= loop
->next
) != NULL
)
868 P
= cloog_loop_alloc(loop
->domain
,one
,loop
->block
,loop
->inner
,NULL
) ;
870 /* Now the domain is in 'P' and it will be freed. */
871 loop
->domain
= NULL
;
873 /* For each loop in the target list, if the intersection with the new loop
874 * is empty, we can add the new loop directly, otherwise, we can merge then
878 { temp
= cloog_domain_intersection(Q
->domain
,P
->domain
) ;
880 if (cloog_domain_isempty(temp
))
881 { cloog_domain_free(temp
) ;
882 cloog_loop_add_disjoint(&merge
,&now
,Q
) ;
885 { cloog_domain_free(temp
) ;
886 new_inner
= cloog_loop_merge_inner_list(Q
->inner
, P
->inner
, old
);
887 temp
= cloog_domain_union(P
->domain
,Q
->domain
) ;
889 new_domain
= cloog_domain_simple_convex(temp
, nb_par
);
891 new_domain
= cloog_domain_convex(temp
);
892 cloog_domain_free(temp
) ;
893 /* Q and P are no more used (but their content yes !).*/
894 cloog_loop_free_parts(P
,1,0,0,0) ;
895 cloog_loop_free_parts(Q
,1,0,0,0) ;
896 P
= cloog_loop_alloc(new_domain
,one
,NULL
,new_inner
,NULL
) ;
901 /* If there was merging, add it, otherwise add the loop lonely.
902 * DEBUG : ici pas besoin de s'assurer que P->next est NULL (possible que
903 * non si pas de fusion) car le dernier loop etudie a loop->next = NULL.
905 cloog_loop_add_disjoint(&merge
,&now
,P
) ;
908 cloog_loop_free_parts(old
,0,0,0,1) ;
909 cloog_int_clear(one
);
916 * cloog_loop_sort function:
917 * Adaptation from LoopGen 0.4 by F. Quillere. This function sorts a list of
918 * parameterized disjoint polyhedra, in order to not have lexicographic order
919 * violation (see Quillere paper).
920 * - September 16th 2005: inclusion of cloog_loop_number (October 29th 2001).
922 CloogLoop
* cloog_loop_sort(CloogLoop
* loop
, int level
, int nb_par
)
923 { CloogLoop
* res
, * now
, * temp
, ** loop_array
;
925 int i
, nb_loops
=0, * permut
;
927 /* We will need to know how many loops are in the list. */
934 /* If there is only one loop, it's the end. */
938 /* We have to allocate memory for some useful components:
939 * - loop_array: the loop array,
940 * - doms: the array of domains to sort,
941 * - permut: will give us a possible sort (maybe not the only one).
943 loop_array
= (CloogLoop
**)malloc(nb_loops
*sizeof(CloogLoop
*)) ;
944 doms
= (CloogDomain
**)malloc(nb_loops
*sizeof(CloogDomain
*));
945 permut
= (int *)malloc(nb_loops
*sizeof(int)) ;
947 /* We fill up the loop and domain arrays. */
948 for (i
=0;i
<nb_loops
;i
++,loop
=loop
->next
)
949 { loop_array
[i
] = loop
;
950 doms
[i
] = loop_array
[i
]->domain
;
953 /* cloog_domain_sort will fill up permut. */
954 cloog_domain_sort(doms
, nb_loops
, level
, nb_par
, permut
);
956 /* With permut and loop_array we build the sorted list. */
958 for (i
=0;i
<nb_loops
;i
++)
959 { /* To avoid pointer looping... loop_add will rebuild the list. */
960 loop_array
[permut
[i
]-1]->next
= NULL
;
961 cloog_loop_add(&res
,&now
,loop_array
[permut
[i
]-1]) ;
973 * cloog_loop_nest function:
974 * This function changes the loop list in such a way that we have no more than
975 * one dimension added by level. It returns an equivalent loop list with
977 * - October 29th 2001: first version.
978 * - July 3rd->11th 2003: memory leaks hunt and correction.
979 * - June 22nd 2005: Adaptation for GMP.
980 * - November 21th 2005: (debug) now OK when cloog_loop_restrict returns NULL.
982 CloogLoop
* cloog_loop_nest(loop
, context
, level
, nb_par
)
984 CloogDomain
* context
;
988 CloogLoop
* p
, * temp
, * res
, * now
, * next
;
989 CloogDomain
* new_domain
;
992 cloog_int_set_si(one
, 1);
995 /* Each domain is changed by its intersection with the context. */
997 { p
= cloog_loop_restrict(loop
,context
,nb_par
) ;
1001 { cloog_loop_free_parts(loop
,1,0,0,0) ;
1003 temp
= cloog_loop_alloc(p
->domain
,one
,p
->block
,p
->inner
,NULL
) ;
1005 /* If the intersection dimension is too big, we make projections smaller
1006 * and smaller, and each projection includes the preceding projection
1007 * (thus, in the target list, dimensions are added one by one).
1009 if ((cloog_domain_dimension(p
->domain
)-nb_par
) > level
)
1010 for (l
=cloog_domain_dimension(p
->domain
)-nb_par
-1;l
>=level
;l
--)
1011 { new_domain
= cloog_domain_project(p
->domain
,l
,nb_par
) ;
1012 temp
= cloog_loop_alloc(new_domain
,one
,NULL
,temp
,NULL
) ;
1015 /* p is no more useful (but its content yes !). */
1016 cloog_loop_free_parts(p
,0,0,0,0) ;
1018 cloog_loop_add(&res
,&now
,temp
) ;
1021 cloog_loop_free_parts(loop
,1,1,1,0) ;
1025 cloog_int_clear(one
);
1032 * cloog_loop_stride function:
1033 * This function will find the stride of a loop for the iterator at the column
1034 * number 'level' in the constraint matrix. It will update the lower bound of
1035 * the iterator accordingly. Basically, the function will try to find in the
1036 * inner loops a common condition on this iterator for the inner loop iterators
1037 * to be integral. For instance, let us consider a loop with the iterator i,
1038 * the iteration domain -4<=i<=n, and its two inner loops with the iterator j.
1039 * The first inner loop has the constraint 3j=i, and the second one has the
1040 * constraint 6j=i. Then the common constraint on i for j to be integral is
1041 * i%3=0, the stride for i is 3. Lastly, we have to find the new lower bound
1042 * for i: the first value satisfying the common constraint: -3. At the end, the
1043 * iteration domain for i is -3<=i<=n and the stride for i is 3.
1044 * - loop is the loop including the iteration domain of the considered iterator,
1045 * - level is the column number of the iterator in the matrix of contraints.
1047 * - June 29th 2003: first version (work in progress since June 26th 2003).
1048 * - July 14th 2003: simpler version.
1049 * - June 22nd 2005: Adaptation for GMP (from S. Verdoolaege's 0.12.1 version).
1051 void cloog_loop_stride(CloogLoop
* loop
, int level
, int nb_par
)
1052 { int first_search
;
1053 cloog_int_t stride
, ref_offset
, offset
, potential
, lower
;
1056 cloog_int_init(stride
);
1057 cloog_int_init(ref_offset
);
1058 cloog_int_init(offset
);
1059 cloog_int_init(potential
);
1060 cloog_int_init(lower
);
1062 cloog_int_set_si(ref_offset
, 0);
1063 cloog_int_set_si(offset
, 0);
1064 cloog_int_set_si(lower
, 0);
1066 /* Default stride. */
1067 cloog_int_set_si(stride
, 1);
1069 inner
= loop
->inner
;
1071 if (cloog_domain_integral_lowerbound(loop
->domain
,level
,&lower
))
1072 while (inner
!= NULL
)
1073 { /* If the minimun stride has not been found yet, find the stride. */
1074 if ((first_search
) || (!cloog_int_is_one(stride
)))
1075 { cloog_domain_stride(inner
->domain
,level
,nb_par
,&potential
,&offset
) ;
1076 if (!cloog_int_is_one(potential
) && (!first_search
))
1077 { /* Offsets must be the same for common stride. */
1078 cloog_int_gcd(stride
, potential
, stride
);
1079 cloog_int_fdiv_r(offset
, offset
, stride
);
1080 cloog_int_fdiv_r(ref_offset
, ref_offset
, stride
);
1081 if (cloog_int_ne(offset
,ref_offset
))
1082 cloog_int_set_si(stride
, 1);
1085 cloog_int_set(stride
, potential
);
1086 cloog_int_set(ref_offset
, offset
);
1092 inner
= inner
->next
;
1095 /* Update the values if necessary. */
1096 if (!cloog_int_is_one(stride
))
1097 { /* Update the stride value. */
1098 cloog_int_set(loop
->stride
, stride
);
1099 /* The new lower bound l' is such that
1100 * (l' + offset) % s = 0 and l <= l' <= l+(s-1)
1101 * Let l' = k s - offset, then
1102 * k s - offset <= l + (s-1) <= k s - offset + (s-1)
1103 * Or l' = floor((l+offset+(s-1))/s) * s - offset
1104 * = (floor((l+offset-1)/s) + 1) * s - offset
1106 cloog_int_add(lower
, lower
, offset
);
1107 cloog_int_sub_ui(lower
, lower
, 1);
1108 cloog_int_fdiv_q(lower
, lower
, stride
);
1109 cloog_int_add_ui(lower
, lower
, 1);
1110 cloog_int_mul(lower
, lower
, stride
);
1111 cloog_int_sub(lower
, lower
, offset
);
1112 loop
->domain
= cloog_domain_lowerbound_update(loop
->domain
, level
, lower
);
1115 cloog_int_clear(stride
);
1116 cloog_int_clear(ref_offset
);
1117 cloog_int_clear(offset
);
1118 cloog_int_clear(potential
);
1119 cloog_int_clear(lower
);
1124 * cloog_loop_stop function:
1125 * This function implements the 'stop' option : each domain of each loop
1126 * in the list 'loop' is replaced by 'context'. 'context' should be the
1127 * domain of the outer loop. By using this method, there are no more dimensions
1128 * to scan and the simplification step will automaticaly remove the domains
1129 * since they are the same as the corresponding contexts. The effect of this
1130 * function is to stop the code generation at the level this function is called,
1131 * the resulting code do not consider the next dimensions.
1132 * - January 11th 2005: first version.
1134 CloogLoop
* cloog_loop_stop(CloogLoop
* loop
, CloogDomain
* context
)
1138 { cloog_domain_free(loop
->domain
) ;
1139 loop
->domain
= cloog_domain_copy(context
) ;
1140 loop
->next
= cloog_loop_stop(loop
->next
, context
) ;
1148 * cloog_loop_scalar_gt function:
1149 * This function returns 1 if loop 'l1' is greater than loop 'l2' for the
1150 * scalar dimension vector that begins at dimension 'scalar', 0 otherwise. What
1151 * we want to know is whether a loop is scheduled before another one or not.
1152 * This function solves the problem when the considered dimension for scheduling
1153 * is a scalar dimension. Since there may be a succession of scalar dimensions,
1154 * this function will reason about the vector of scalar dimension that begins
1155 * at dimension 'level+scalar' and finish to the first non-scalar dimension.
1156 * \param l1 Loop to be compared with l2.
1157 * \param l2 Loop to be compared with l1.
1158 * \param level Current non-scalar dimension.
1159 * \param scaldims Boolean array saying whether a dimension is scalar or not.
1160 * \param nb_scattdims Size of the scaldims array.
1161 * \param scalar Current scalar dimension.
1162 * \return 1 if (l1 > l2), 0 otherwise.
1164 * - September 9th 2005: first version.
1165 * - October 15nd 2007: now "greater than" instead of "greater or equal".
1167 int cloog_loop_scalar_gt(l1
, l2
, level
, scaldims
, nb_scattdims
, scalar
)
1168 CloogLoop
* l1
, * l2
;
1169 int level
, * scaldims
, nb_scattdims
, scalar
;
1170 { while ((scalar
< l1
->inner
->block
->nb_scaldims
) && scaldims
[level
+scalar
-1])
1171 { if (cloog_int_gt(l1
->inner
->block
->scaldims
[scalar
],
1172 l2
->inner
->block
->scaldims
[scalar
]))
1182 * cloog_loop_scalar_eq function:
1183 * This function returns 1 if loop 'l1' is equal to loop 'l2' for the scalar
1184 * dimension vector that begins at dimension 'scalar', 0 otherwise. What we want
1185 * to know is whether two loops are scheduled for the same time or not.
1186 * This function solves the problem when the considered dimension for scheduling
1187 * is a scalar dimension. Since there may be a succession of scalar dimensions,
1188 * this function will reason about the vector of scalar dimension that begins
1189 * at dimension 'level+scalar' and finish to the first non-scalar dimension.
1190 * - l1 and l2 are the loops to compare,
1191 * - level is the current non-scalar dimension,
1192 * - scaldims is the boolean array saying whether a dimension is scalar or not,
1193 * - nb_scattdims is the size of the scaldims array,
1194 * - scalar is the current scalar dimension.
1196 * - September 9th 2005 : first version.
1198 int cloog_loop_scalar_eq(l1
, l2
, level
, scaldims
, nb_scattdims
, scalar
)
1199 CloogLoop
* l1
, * l2
;
1200 int level
, * scaldims
, nb_scattdims
, scalar
;
1201 { while ((scalar
< l1
->inner
->block
->nb_scaldims
) && scaldims
[level
+scalar
-1])
1202 { if (cloog_int_eq(l1
->inner
->block
->scaldims
[scalar
],
1203 l2
->inner
->block
->scaldims
[scalar
]))
1213 * cloog_loop_scalar_sort function:
1214 * This function sorts a linked list of loops (loop) with respect to the
1215 * scalar dimension vector that begins at dimension 'scalar'. Since there may
1216 * be a succession of scalar dimensions, this function will reason about the
1217 * vector of scalar dimension that begins at dimension 'level+scalar' and
1218 * finish to the first non-scalar dimension.
1219 * \param loop Loop list to sort.
1220 * \param level Current non-scalar dimension.
1221 * \param scaldims Boolean array saying whether a dimension is scalar or not.
1222 * \param nb_scattdims Size of the scaldims array.
1223 * \param scalar Current scalar dimension.
1224 * \return A pointer to the sorted list.
1226 * - July 2nd 2005: first developments.
1227 * - September 2nd 2005: first version.
1228 * - October 15nd 2007: complete rewrite to remove bugs, now a bubble sort.
1230 CloogLoop
* cloog_loop_scalar_sort(loop
, level
, scaldims
, nb_scattdims
, scalar
)
1232 int level
, * scaldims
, nb_scattdims
, scalar
;
1234 CloogLoop
**current
;
1238 for (current
= &loop
; (*current
)->next
; current
= &(*current
)->next
) {
1239 CloogLoop
*next
= (*current
)->next
;
1240 if (cloog_loop_scalar_gt(*current
,next
,level
,scaldims
,nb_scattdims
,scalar
)) {
1242 (*current
)->next
= next
->next
;
1243 next
->next
= *current
;
1254 * cloog_loop_generate_backtrack function:
1255 * adaptation from LoopGen 0.4 by F. Quillere. This function implements the
1256 * backtrack of the Quillere et al. algorithm (see the Quillere paper).
1257 * It eliminates unused iterations of the current level for the new one. See the
1258 * example called linearity-1-1 example with and without this part for an idea.
1259 * - October 26th 2001: first version in cloog_loop_generate_general.
1260 * - July 31th 2002: (debug) no more parasite loops (REALLY hard !).
1261 * - October 30th 2005: extraction from cloog_loop_generate_general.
1263 CloogLoop
* cloog_loop_generate_backtrack(loop
, context
, level
, nb_par
, options
)
1265 CloogDomain
* context
;
1267 CloogOptions
* options
;
1270 CloogDomain
* domain
;
1271 CloogLoop
* now
, * now2
, * next
, * next2
, * end
, * temp
, * l
, * inner
,
1274 cloog_int_init(one
);
1275 cloog_int_set_si(one
, 1);
1280 while (temp
!= NULL
)
1282 inner
= temp
->inner
;
1284 while (inner
!= NULL
)
1285 { next
= inner
->next
;
1286 /* This 'if' and its first part is the debug of july 31th 2002. */
1287 if (inner
->block
!= NULL
)
1288 { end
= cloog_loop_alloc(inner
->domain
,one
,inner
->block
,NULL
,NULL
) ;
1289 domain
= cloog_domain_copy(temp
->domain
) ;
1290 new_loop
= cloog_loop_alloc(domain
,one
,NULL
,end
,NULL
) ;
1293 new_loop
= cloog_loop_project(inner
,level
,nb_par
) ;
1295 cloog_loop_free_parts(inner
,0,0,0,0) ;
1296 cloog_loop_add(&l
,&now2
,new_loop
) ;
1300 temp
->inner
= NULL
;
1303 { l
= cloog_loop_separate(l
) ;
1304 l
= cloog_loop_sort(l
,level
,nb_par
) ;
1306 cloog_int_set(l
->stride
, temp
->stride
);
1307 cloog_loop_add(&loop
,&now
,l
) ;
1311 next2
= temp
->next
;
1312 cloog_loop_free_parts(temp
,1,0,0,0) ;
1316 cloog_int_clear(one
);
1323 * cloog_loop_generate_general function:
1324 * Adaptation from LoopGen 0.4 by F. Quillere. This function implements the
1325 * Quillere algorithm for polyhedron scanning from step 3 to 5.
1326 * (see the Quillere paper).
1327 * - loop is the loop for which we have to generate a scanning code,
1328 * - context is the context of the current loop (constraints on parameter and/or
1329 * on outer loop counters),
1330 * - level is the current non-scalar dimension,
1331 * - scalar is the current scalar dimension,
1332 * - scaldims is the boolean array saying whether a dimension is scalar or not,
1333 * - nb_scattdims is the size of the scaldims array,
1334 * - nb_par is the number of parameters,
1335 * - options are the general code generation options.
1337 * - October 26th 2001: first version.
1338 * - July 3rd->11th 2003: memory leaks hunt and correction.
1339 * - June 22nd 2005: Adaptation for GMP.
1340 * - September 2nd 2005: The function have been cutted out in two pieces:
1341 * cloog_loop_generate and this one, in order to handle
1342 * the scalar dimension case more efficiently with
1343 * cloog_loop_generate_scalar.
1344 * - November 15th 2005: (debug) the result of the cloog_loop_generate call may
1345 * be a list of polyhedra (especially if stop option is
1346 * used): cloog_loop_add_list instead of cloog_loop_add.
1348 CloogLoop
* cloog_loop_generate_general(loop
, context
, level
, scalar
,
1349 scaldims
, nb_scattdims
, nb_par
, options
)
1351 CloogDomain
* context
;
1352 int level
, scalar
, * scaldims
, nb_scattdims
, nb_par
;
1353 CloogOptions
* options
;
1356 CloogLoop
* res
, * now
, * temp
, * l
, * new_loop
, * inner
, * now2
, * end
,
1358 CloogDomain
* domain
;
1360 /* 3. Separate all projections into disjoint polyhedra. */
1361 res
= ((options
->f
> level
+scalar
) || (options
->f
< 0)) ?
1362 cloog_loop_merge(loop
, nb_par
, options
) : cloog_loop_separate(loop
);
1364 /* 3b. -correction- sort the loops to determine their textual order. */
1365 res
= cloog_loop_sort(res
,level
,nb_par
) ;
1367 cloog_int_init(one
);
1368 cloog_int_set_si(one
, 1);
1370 /* 4. Recurse for each loop with the current domain as context. */
1373 if ((level
+scalar
< options
->l
) || (options
->l
< 0))
1375 { if (options
->strides
)
1376 cloog_loop_stride(temp
,level
,nb_par
) ;
1377 inner
= temp
->inner
;
1378 domain
= temp
->domain
;
1380 while (inner
!= NULL
)
1381 { /* 4b. -ced- recurse for each sub-list of non terminal loops. */
1382 if (cloog_domain_dimension(inner
->domain
) > (level
+ nb_par
))
1384 while ((end
->next
!= NULL
) &&
1385 (cloog_domain_dimension(end
->next
->domain
) > (level
+ nb_par
)))
1391 l
= cloog_loop_generate(inner
,domain
,level
+1,scalar
,
1392 scaldims
,nb_scattdims
,nb_par
,options
) ;
1395 cloog_loop_add_list(&into
,&now
,l
) ;
1400 { cloog_loop_add(&into
,&now
,inner
) ;
1401 inner
= inner
->next
;
1406 temp
->inner
= into
;
1407 cloog_loop_add(&res
,&now2
,temp
) ;
1411 while (temp
!= NULL
)
1412 { next
= temp
->next
;
1413 l
= cloog_loop_nest(temp
->inner
,temp
->domain
,level
+1,nb_par
) ;
1414 new_loop
= cloog_loop_alloc(temp
->domain
,one
,NULL
,l
,NULL
) ;
1415 temp
->inner
= NULL
;
1417 cloog_loop_free_parts(temp
,0,0,0,0) ;
1418 cloog_loop_add(&res
,&now
,new_loop
) ;
1422 /* 5. eliminate unused iterations of the current level for the new one. See
1423 * the example called linearity-1-1 example with and without this part
1426 if ((!options
->nobacktrack
) &&
1427 ((level
+scalar
< options
->l
) || (options
->l
< 0)) &&
1428 ((options
->f
<= level
+scalar
) && !(options
->f
< 0)))
1429 res
= cloog_loop_generate_backtrack(res
,context
,level
,nb_par
,options
) ;
1431 /* Pray for my new paper to be accepted somewhere since the following stuff
1432 * is really amazing :-) !
1433 * Far long later: The paper has been accepted to PACT 2004 :-))). But there
1434 * are still some bugs and I have no time to fix them. Thus now you have to
1435 * pray for me to get an academic position for that really amazing stuff :-) !
1436 * Later again: OK, I get my academic position, but still I have not enough
1437 * time to fix and clean this part... Pray again :-) !!!
1439 /* res = cloog_loop_unisolate(res,context,level,nb_par) ;*/
1441 cloog_int_clear(one
);
1447 * cloog_loop_generate_scalar function:
1448 * This function applies the simplified code generation scheme in the trivial
1449 * case of scalar dimensions. When dealing with scalar dimensions, there is
1450 * no need of costly polyhedral operations for separation or sorting: sorting
1451 * is a question of comparing scalar vectors and separation amounts to consider
1452 * only loops with the same scalar vector for the next step of the code
1453 * generation process. This function achieves the separation/sorting process
1454 * for the vector of scalar dimension that begins at dimension 'level+scalar'
1455 * and finish to the first non-scalar dimension.
1456 * - loop is the loop for which we have to generate a scanning code,
1457 * - context is the context of the current loop (constraints on parameter and/or
1458 * on outer loop counters),
1459 * - level is the current non-scalar dimension,
1460 * - scalar is the current scalar dimension,
1461 * - scaldims is the boolean array saying whether a dimension is scalar or not,
1462 * - nb_scattdims is the size of the scaldims array,
1463 * - nb_par is the number of parameters,
1464 * - options are the general code generation options.
1466 * - September 2nd 2005: First version.
1468 CloogLoop
* cloog_loop_generate_scalar(loop
, context
, level
, scalar
,
1469 scaldims
, nb_scattdims
, nb_par
, options
)
1471 CloogDomain
* context
;
1472 int level
, scalar
, * scaldims
, nb_scattdims
, nb_par
;
1473 CloogOptions
* options
;
1474 { CloogLoop
* res
, * now
, * temp
, * l
, * end
, * next
, * ref
;
1476 /* We sort the loop list with respect to the current scalar vector. */
1477 res
= cloog_loop_scalar_sort(loop
,level
,scaldims
,nb_scattdims
,scalar
) ;
1481 while (temp
!= NULL
)
1482 { /* Then we will appy the general code generation process to each sub-list
1483 * of loops with the same scalar vector.
1488 while((end
->next
!= NULL
) &&
1489 cloog_loop_scalar_eq(ref
,end
->next
,level
,scaldims
,nb_scattdims
,scalar
))
1495 /* For the next dimension, scalar value is updated by adding the scalar
1496 * vector size, which is stored at scaldims[level+scalar-1].
1498 l
= cloog_loop_generate_general(temp
,context
,level
,
1499 scalar
+scaldims
[level
+scalar
-1],
1500 scaldims
,nb_scattdims
,nb_par
,options
) ;
1503 cloog_loop_add_list(&res
,&now
,l
) ;
1513 * cloog_loop_generate function:
1514 * Adaptation from LoopGen 0.4 by F. Quillere. This function implements the
1515 * Quillere algorithm for polyhedron scanning from step 1 to 2.
1516 * (see the Quillere paper).
1517 * - loop is the loop for which we have to generate a scanning code,
1518 * - context is the context of the current loop (constraints on parameter and/or
1519 * on outer loop counters),
1520 * - level is the current non-scalar dimension,
1521 * - scalar is the current scalar dimension,
1522 * - scaldims is the boolean array saying whether a dimension is scalar or not,
1523 * - nb_scattdims is the size of the scaldims array,
1524 * - nb_par is the number of parameters,
1525 * - options are the general code generation options.
1527 * - October 26th 2001: first version.
1528 * - July 3rd->11th 2003: memory leaks hunt and correction.
1529 * - June 15th 2005: a memory leak fixed (loop was not entirely freed when
1530 * the result of cloog_loop_restrict was NULL).
1531 * - June 22nd 2005: Adaptation for GMP.
1532 * - September 2nd 2005: The function have been cutted out in two pieces:
1533 * cloog_loop_generate and this one, in order to handle
1534 * the scalar dimension case more efficiently with
1535 * cloog_loop_generate_scalar.
1536 * - November 15th 2005: (debug) Condition for stop option no more take care of
1537 * further scalar dimensions.
1539 CloogLoop
* cloog_loop_generate(loop
, context
, level
, scalar
,
1540 scaldims
, nb_scattdims
, nb_par
, options
)
1542 CloogDomain
* context
;
1543 int level
, scalar
, * scaldims
, nb_scattdims
, nb_par
;
1544 CloogOptions
* options
;
1545 { CloogLoop
* res
, * now
, * temp
, * next
, * old
;
1547 /* If the user asked to stop code generation at this level, let's stop. */
1548 if ((options
->stop
>= 0) && (level
+scalar
>= options
->stop
+1))
1549 return cloog_loop_stop(loop
,context
) ;
1553 /* 1. Replace each polyhedron by its intersection with the context.
1554 * 2. Compute the projection of each polyhedron onto the outermost
1555 * loop variable and the parameters.
1557 while (loop
!= NULL
)
1558 { next
= loop
->next
;
1559 temp
= cloog_loop_restrict(loop
,context
,nb_par
) ;
1563 temp
= cloog_loop_project(temp
,level
,nb_par
) ;
1564 cloog_loop_free_parts(old
,0,0,0,0) ;
1565 cloog_loop_add(&res
,&now
,temp
) ;
1566 cloog_loop_free_parts(loop
,1,0,0,0) ;
1569 { loop
->next
= NULL
;
1570 cloog_loop_free(loop
) ;
1578 /* To save both time and memory, we switch here depending on whether the
1579 * current dimension is scalar (simplified processing) or not (general
1582 if ((level
+scalar
<= nb_scattdims
) && (scaldims
[level
+scalar
-1]))
1583 res
= cloog_loop_generate_scalar(res
,context
,level
,scalar
,
1584 scaldims
,nb_scattdims
,nb_par
,options
) ;
1586 res
= cloog_loop_generate_general(res
,context
,level
,scalar
,
1587 scaldims
,nb_scattdims
,nb_par
,options
) ;
1594 * cloog_loop_simplify function:
1595 * This function implements the part 6. of the Quillere algorithm, it
1596 * recursively simplifies each loop in the context of the preceding loop domain.
1597 * It returns a pointer to the simplified loop list.
1598 * The cloog_domain_simplify (DomainSimplify) behaviour is really bad with
1599 * polyhedra union and some really awful sidesteppings were written, I plan
1601 * - October 31th 2001: first version.
1602 * - July 3rd->11th 2003: memory leaks hunt and correction.
1603 * - April 16th 2005: a memory leak fixed (extended_context was not freed).
1604 * - June 15th 2005: a memory leak fixed (loop was not conveniently freed
1605 * when the constraint system is never true).
1606 * - October 27th 2005: - this function called before cloog_loop_fast_simplify
1607 * is now the official cloog_loop_simplify function in
1608 * replacement of a slower and more complex one (after
1609 * deep changes in the pretty printer).
1610 * - we use cloog_loop_disjoint to fix the problem when
1611 * simplifying gives a union of polyhedra (before, it
1612 * was under the responsibility of the pretty printer).
1614 CloogLoop
* cloog_loop_simplify(loop
, context
, level
, nb_par
)
1616 CloogDomain
* context
;
1619 CloogBlock
* new_block
;
1620 CloogLoop
* simplified
, * inner
, * next
;
1621 CloogDomain
* domain
, * simp
, * inter
, * extended_context
;
1626 domain
= loop
->domain
;
1628 next
= cloog_loop_simplify(loop
->next
,context
,level
,nb_par
) ;
1630 domain_dim
= cloog_domain_dimension(domain
) - nb_par
;
1631 extended_context
=cloog_domain_extend(context
,domain_dim
,nb_par
);
1632 inter
= cloog_domain_intersection(domain
,extended_context
) ;
1633 simp
= cloog_domain_simplify(inter
,extended_context
) ;
1634 cloog_domain_free(extended_context
) ;
1636 /* If the constraint system is never true, go to the next one. */
1637 if (cloog_domain_never_integral(simp
)) {
1639 cloog_loop_free(loop
);
1640 cloog_domain_free(inter
);
1641 cloog_domain_free(simp
);
1645 inner
= cloog_loop_simplify(loop
->inner
,inter
,level
+1,nb_par
) ;
1646 cloog_domain_free(inter
) ;
1648 if ((inner
== NULL
) && (loop
->block
== NULL
))
1649 { loop
->inner
= NULL
; /* For loop integrity. */
1650 loop
->next
= NULL
; /* For loop integrity. */
1651 cloog_loop_free_parts(loop
,1,1,1,0) ;
1652 cloog_domain_free(simp
);
1656 new_block
= cloog_block_copy(loop
->block
) ;
1658 simplified
= cloog_loop_alloc(simp
,loop
->stride
,new_block
,inner
,next
) ;
1660 /* Examples like test/iftest2.cloog give unions of polyhedra after
1661 * simplifying, thus we we have to disjoint them. Another good reason to
1662 * put the simplifying step in the Quillere backtrack.
1664 simplified
= cloog_loop_disjoint(simplified
) ;
1666 loop
->inner
= NULL
; /* For loop integrity. */
1667 loop
->next
= NULL
; /* For loop integrity. */
1668 cloog_loop_free_parts(loop
,1,1,0,0) ;
1670 return(simplified
) ;
1675 * cloog_loop_scatter function:
1676 * This function add the scattering (scheduling) informations in a loop.
1678 void cloog_loop_scatter(CloogLoop
* loop
, CloogScattering
*scatt
)
1680 loop
->domain
= cloog_domain_scatter(loop
->domain
, scatt
);