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 extern int cloog_value_allocated
;
63 extern int cloog_value_freed
;
64 extern int cloog_value_max
;
67 int cloog_loop_allocated
= 0 ;
68 int cloog_loop_freed
= 0 ;
69 int cloog_loop_max
= 0 ;
72 void cloog_loop_leak_up()
73 { cloog_loop_allocated
++ ;
74 if ((cloog_loop_allocated
-cloog_loop_freed
) > cloog_loop_max
)
75 cloog_loop_max
= cloog_loop_allocated
- cloog_loop_freed
;
79 void cloog_loop_leak_down()
80 { cloog_loop_freed
++ ;
84 /******************************************************************************
85 * Structure display function *
86 ******************************************************************************/
90 * cloog_loop_print_structure function:
91 * Displays a loop structure in a way that trends to be understandable without
92 * falling in a deep depression or, for the lucky ones, getting a headache...
93 * Written by Olivier Chorier, Luc Marchaud, Pierre Martin and Romain Tartiere.
94 * - April 24th 2005: Initial version.
95 * - May 21rd 2005: - New parameter `F' for destination file (ie stdout),
97 * - May 26th 2005: Memory leak hunt.
98 * - June 2nd 2005: (Ced) Integration and minor fixes.
99 * -June 22nd 2005: (Ced) Adaptation for GMP.
101 void cloog_loop_print_structure(FILE * file
, CloogLoop
* loop
, int level
)
102 { int i
, j
, first
=1 ;
105 { /* Go to the right level. */
106 for (i
=0; i
<level
; i
++)
107 fprintf(file
,"|\t") ;
109 fprintf(file
,"+-- CloogLoop\n") ;
115 { /* Go to the right level. */
116 for (i
=0; i
<level
; i
++)
117 fprintf(file
,"|\t") ;
119 fprintf(file
,"| CloogLoop\n") ;
125 for(j
=0; j
<=level
+1; j
++)
126 fprintf(file
,"|\t") ;
129 /* Print the domain. */
130 cloog_domain_print_structure(file
,loop
->domain
,level
+1) ;
132 /* Print the stride. */
133 for(j
=0; j
<=level
; j
++)
134 fprintf(file
,"|\t") ;
135 fprintf(file
, "Stride: ") ;
136 value_print(file
,VALUE_FMT
,loop
->stride
) ;
137 fprintf(file
, "\n") ;
140 for(j
=0; j
<=level
+1; j
++)
141 fprintf(file
,"|\t") ;
144 /* Print the block. */
145 cloog_block_print_structure(file
,loop
->block
,level
+1) ;
148 for (i
=0; i
<=level
+1; i
++)
149 fprintf(file
,"|\t") ;
152 /* Print inner if any. */
154 cloog_loop_print_structure(file
,loop
->inner
,level
+1) ;
156 /* And let's go for the next one. */
159 /* One more time something that is here only for a better look. */
161 { /* Two blank lines if this is the end of the linked list. */
163 { for (i
=0; i
<=level
; i
++)
164 fprintf(file
,"|\t") ;
170 { /* A special blank line if the is a next loop. */
171 for (i
=0; i
<=level
; i
++)
172 fprintf(file
,"|\t") ;
173 fprintf(file
,"V\n") ;
180 * cloog_loop_print function:
181 * This function prints the content of a CloogLoop structure (start) into a
182 * file (file, possibly stdout).
183 * - June 2nd 2005: Now this very old function (probably as old as CLooG) is
184 * only a frontend to cloog_loop_print_structure, with a quite
185 * better human-readable representation.
187 void cloog_loop_print(FILE * file
, CloogLoop
* loop
)
188 { cloog_loop_print_structure(file
,loop
,0) ;
192 /******************************************************************************
193 * Memory deallocation function *
194 ******************************************************************************/
198 * cloog_loop_free function:
199 * This function frees the allocated memory for a CloogLoop structure (loop),
200 * and frees its inner loops and its next loops.
201 * - June 22nd 2005: Adaptation for GMP.
203 void cloog_loop_free(CloogLoop
* loop
)
207 { cloog_loop_leak_down() ;
210 cloog_domain_free(loop
->domain
) ;
211 cloog_block_free(loop
->block
) ;
212 if (loop
->inner
!= NULL
)
213 cloog_loop_free(loop
->inner
) ;
215 value_clear_c(loop
->stride
) ;
223 * cloog_loop_free_parts function:
224 * This function frees the allocated memory for some parts of a CloogLoop
225 * structure (loop), each other argument is a boolean having to be set to 1 if
226 * we want to free the corresponding part, 0 otherwise. This function applies
227 * the same freeing policy to its inner ans next loops recursively.
228 * - July 3rd 2003: first version.
229 * - June 22nd 2005: Adaptation for GMP.
231 void cloog_loop_free_parts(loop
, domain
, block
, inner
, next
)
233 int domain
, block
, inner
, next
;
234 { CloogLoop
* follow
;
237 { cloog_loop_leak_down() ;
238 follow
= loop
->next
;
241 cloog_domain_free(loop
->domain
) ;
244 cloog_block_free(loop
->block
) ;
246 if ((inner
) && (loop
->inner
!= NULL
))
247 cloog_loop_free_parts(loop
->inner
,domain
,block
,inner
,1) ;
249 value_clear_c(loop
->stride
) ;
259 /******************************************************************************
260 * Reading functions *
261 ******************************************************************************/
265 * cloog_loop_read function:
266 * This function reads loop data into a file (foo, posibly stdin) and
267 * returns a pointer to a CloogLoop structure containing the read information.
268 * This function can be used only for input file reading, when one loop is
269 * associated with one statement.
270 * - number is the statement block number carried by the loop (-1 if none).
271 * - nb_parameters is the number of parameters.
273 * - September 9th 2002: first version.
274 * - April 16th 2005: adaptation to new CloogStatement struct (with number).
275 * - June 11th 2005: adaptation to new CloogBlock structure.
276 * - June 22nd 2005: Adaptation for GMP.
278 CloogLoop
* cloog_loop_read(FILE * foo
, int number
, int nb_parameters
)
279 { int nb_iterators
, op1
, op2
, op3
;
282 CloogStatement
* statement
;
284 cloog_loop_leak_up() ;
286 /* Memory allocation and information reading for the first domain: */
287 loop
= (CloogLoop
*)malloc(sizeof(CloogLoop
)) ;
289 { fprintf(stderr
, "Memory Overflow.\n") ;
293 loop
->domain
= cloog_domain_union_read(foo
) ;
294 if (loop
->domain
!= NULL
)
295 nb_iterators
= cloog_domain_dimension(loop
->domain
) - nb_parameters
;
298 /* stride is initialized to 1. */
299 value_init_c(loop
->stride
) ;
300 value_set_si(loop
->stride
,1) ;
301 /* included statement block. */
302 statement
= cloog_statement_alloc(number
) ;
303 loop
->block
= cloog_block_alloc(statement
,NULL
,0,NULL
,nb_iterators
) ;
304 /* inner is NULL at beginning. */
309 /* To read that stupid "0 0 0" line. */
310 while (fgets(s
,MAX_STRING
,foo
) == 0) ;
311 while ((*s
=='#' || *s
=='\n') || (sscanf(s
," %d %d %d",&op1
,&op2
,&op3
)<3))
312 fgets(s
,MAX_STRING
,foo
) ;
318 /******************************************************************************
319 * Processing functions *
320 ******************************************************************************/
324 * cloog_loop_malloc function:
325 * This function allocates the memory space for a CloogLoop structure and
326 * sets its fields with default values. Then it returns a pointer to the
328 * - November 21th 2005: first version.
330 CloogLoop
* cloog_loop_malloc()
333 /* Memory allocation for the CloogLoop structure. */
334 loop
= (CloogLoop
*)malloc(sizeof(CloogLoop
)) ;
336 { fprintf(stderr
, "[CLooG]ERROR: memory overflow.\n") ;
339 cloog_loop_leak_up() ;
342 /* We set the various fields with default values. */
343 loop
->domain
= NULL
;
347 value_init_c(loop
->stride
) ;
348 value_set_si(loop
->stride
,1) ;
355 * cloog_loop_alloc function:
356 * This function allocates the memory space for a CloogLoop structure and
357 * sets its fields with those given as input. Then it returns a pointer to the
359 * - October 27th 2001: first version.
360 * - June 22nd 2005: Adaptation for GMP.
361 * - November 21th 2005: use of cloog_loop_malloc.
363 CloogLoop
* cloog_loop_alloc(domain
, stride
, block
, inner
, next
)
364 CloogDomain
* domain
;
367 CloogLoop
* inner
, * next
;
370 loop
= cloog_loop_malloc() ;
372 loop
->domain
= domain
;
373 loop
->block
= block
;
374 loop
->inner
= inner
;
376 value_assign(loop
->stride
,stride
) ;
383 * cloog_loop_add function:
384 * This function adds a CloogLoop structure (loop) at a given place (now) of a
385 * NULL terminated list of CloogLoop structures. The beginning of this list
386 * is (start). This function updates (now) to (loop), and updates (start) if the
387 * added element is the first one -that is when (start) is NULL-.
388 * - October 28th 2001: first version.
390 void cloog_loop_add(CloogLoop
** start
, CloogLoop
** now
, CloogLoop
* loop
)
391 { if (*start
== NULL
)
396 { (*now
)->next
= loop
;
397 *now
= (*now
)->next
;
403 * cloog_loop_add function:
404 * This function adds a CloogLoop structure (loop) at a given place (now) of a
405 * NULL terminated list of CloogLoop structures. The beginning of this list
406 * is (start). This function updates (now) to the end of the loop list (loop),
407 * and updates (start) if the added element is the first one -that is when
409 * - September 9th 2005: first version.
411 void cloog_loop_add_list(CloogLoop
** start
, CloogLoop
** now
, CloogLoop
* loop
)
412 { if (*start
== NULL
)
417 { (*now
)->next
= loop
;
418 *now
= (*now
)->next
;
421 while ((*now
)->next
!= NULL
)
422 *now
= (*now
)->next
;
427 * cloog_loop_copy function:
428 * This function returns a copy of the CloogLoop structure given as input. In
429 * fact, there is just new allocations for the CloogLoop structures, but their
430 * contents are the same.
431 * - October 28th 2001: first version.
432 * - July 3rd->11th 2003: memory leaks hunt and correction.
434 CloogLoop
* cloog_loop_copy(CloogLoop
* source
)
437 CloogDomain
* domain
;
441 { domain
= cloog_domain_copy(source
->domain
) ;
442 block
= cloog_block_copy(source
->block
) ;
443 loop
= cloog_loop_alloc(domain
,source
->stride
,block
,NULL
,NULL
) ;
444 loop
->inner
= cloog_loop_copy(source
->inner
) ;
445 loop
->next
= cloog_loop_copy(source
->next
) ;
452 * cloog_loop_add_disjoint function:
453 * This function adds some CloogLoop structures at a given place (now) of a
454 * NULL terminated list of CloogLoop structures. The beginning of this list
455 * is (start). (loop) can be an union of polyhedra, this function separates the
456 * union into a list of *disjoint* polyhedra then adds the list. This function
457 * updates (now) to the end of the list and updates (start) if first added
458 * element is the first of the principal list -that is when (start) is NULL-.
459 * (loop) can be freed by this function, basically when its domain is actually
460 * a union of polyhedra, but don't worry, all the useful data are now stored
461 * inside the list (start). We do not use PolyLib's Domain_Disjoint function,
462 * since the number of union components is often higher (thus code size too).
463 * - October 28th 2001: first version.
464 * - November 14th 2001: bug correction (this one was hard to find !).
465 * - July 3rd->11th 2003: memory leaks hunt and correction.
466 * - June 22nd 2005: Adaptation for GMP.
467 * - October 27th 2005: (debug) included blocks were not copied for new loops.
469 void cloog_loop_add_disjoint(start
, now
, loop
)
470 CloogLoop
** start
, ** now
, * loop
;
472 CloogLoop
* sep
, * inner
;
473 CloogDomain
* domain
, * convex
, * seen
, * seen_before
, * temp
, * rest
;
477 value_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) ;
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
) ;
597 { value_init_c(one
) ;
598 value_set_si(one
,1) ;
599 new_loop
= cloog_loop_alloc(new_domain
,one
,loop
->block
,loop
->inner
,NULL
) ;
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
)
619 CloogDomain
* new_domain
;
620 CloogLoop
* new_loop
, * copy
;
623 value_set_si(one
,1) ;
625 copy
= cloog_loop_alloc(loop
->domain
,loop
->stride
,loop
->block
,
628 if ((cloog_domain_dimension(loop
->domain
)-nb_par
) == level
)
629 new_domain
= cloog_domain_copy(loop
->domain
) ;
631 new_domain
= cloog_domain_project(loop
->domain
,level
,nb_par
) ;
633 new_loop
= cloog_loop_alloc(new_domain
,one
,NULL
,copy
,NULL
) ;
641 * cloog_loop_concat function:
642 * This function returns a pointer to the concatenation of the
643 * CloogLoop lists given as input.
644 * - October 28th 2001: first version.
646 CloogLoop
* cloog_loop_concat(CloogLoop
* a
, CloogLoop
* b
)
647 { CloogLoop
* loop
, * temp
;
652 { while (temp
->next
!= NULL
)
664 * cloog_loop_separate function:
665 * This function implements the Quillere algorithm for separation of multiple
666 * loops: for a given set of polyhedra (loop), it computes a set of disjoint
667 * polyhedra such that the unions of these sets are equal, and returns this set.
668 * - October 28th 2001: first version.
669 * - November 14th 2001: elimination of some unused blocks.
670 * - August 13th 2002: (debug) in the case of union of polyhedra for one
671 * loop, redundant constraints are fired.
672 * - July 3rd->11th 2003: memory leaks hunt and correction.
673 * - June 22nd 2005: Adaptation for GMP.
674 * - October 16th 2005: Removal of the non-shared constraint elimination when
675 * there is only one loop in the list (seems to work
676 * without now, DomainSimplify may have been improved).
677 * The problem was visible with test/iftest2.cloog.
679 CloogLoop
* cloog_loop_separate(CloogLoop
* loop
)
680 { int first
, lazy_equal
=0, lazy_disjoint
=0 ;
682 CloogLoop
* new_loop
, * new_inner
, * res
, * now
, * temp
, * Q
,
683 * inner
, * old
/*, * previous, * next*/ ;
684 CloogDomain
* UQ
, * old_UQ
, * domain
;
689 if (loop
->next
== NULL
)
690 return cloog_loop_disjoint(loop
) ;
693 value_set_si(one
,1) ;
695 UQ
= cloog_domain_copy(loop
->domain
) ;
696 domain
= cloog_domain_copy(loop
->domain
) ;
697 res
= cloog_loop_alloc(domain
,one
,loop
->block
,loop
->inner
,NULL
) ;
700 while((loop
= loop
->next
) != NULL
)
704 /* For all Q, add Q-loop associated with the blocks of Q alone,
705 * and Q inter loop associated with the blocks of Q and loop.
709 { if (Q
->block
== NULL
)
710 { /* Add (Q inter loop). */
711 if((lazy_disjoint
=cloog_domain_lazy_disjoint(Q
->domain
,loop
->domain
)))
714 { if ((lazy_equal
= cloog_domain_lazy_equal(Q
->domain
,loop
->domain
)))
715 domain
= cloog_domain_copy(Q
->domain
) ;
717 domain
= cloog_domain_intersection(Q
->domain
,loop
->domain
) ;
719 if (!cloog_domain_isempty(domain
))
720 { new_inner
= cloog_loop_concat(cloog_loop_copy(Q
->inner
),
721 cloog_loop_copy(loop
->inner
)) ;
722 new_loop
= cloog_loop_alloc(domain
,one
,NULL
,new_inner
,NULL
) ;
723 cloog_loop_add_disjoint(&temp
,&now
,new_loop
) ;
726 cloog_domain_free(domain
) ;
729 /* Add (Q - loop). */
731 domain
= cloog_domain_copy(Q
->domain
) ;
734 domain
= cloog_domain_empty(cloog_domain_dimension(Q
->domain
)) ;
736 domain
= cloog_domain_difference(Q
->domain
,loop
->domain
) ;
739 if (!cloog_domain_isempty(domain
))
740 { new_loop
= cloog_loop_alloc(domain
,one
,NULL
,Q
->inner
,NULL
) ;
741 cloog_loop_add_disjoint(&temp
,&now
,new_loop
) ;
744 { cloog_domain_free(domain
) ;
745 /* If Q->inner is no more useful, we can free it. */
748 if (first
) /* For the first Q, inner is also old->inner. */
750 cloog_loop_free(inner
) ;
756 /* Add loop-UQ associated with the blocks of loop alone.*/
757 if (cloog_domain_lazy_disjoint(loop
->domain
,UQ
))
758 domain
= cloog_domain_copy(loop
->domain
) ;
760 { if (cloog_domain_lazy_equal(loop
->domain
,UQ
))
761 domain
= cloog_domain_empty(cloog_domain_dimension(UQ
)) ;
763 domain
= cloog_domain_difference(loop
->domain
,UQ
) ;
766 if (!cloog_domain_isempty(domain
))
767 { new_loop
= cloog_loop_alloc(domain
,one
,NULL
,loop
->inner
,NULL
) ;
768 cloog_loop_add_disjoint(&temp
,&now
,new_loop
) ;
771 { cloog_domain_free(domain
) ;
772 /* If loop->inner is no more useful, we can free it. */
773 cloog_loop_free(loop
->inner
) ;
779 if (loop
->next
!= NULL
)
780 UQ
= cloog_domain_union(UQ
,loop
->domain
) ;
782 cloog_domain_free(old_UQ
) ;
783 cloog_loop_free_parts(res
,1,0,0,1) ;
788 cloog_loop_free_parts(old
,1,0,0,1) ;
796 * cloog_loop_merge function:
797 * This function is the 'soft' version of loop_separate if we are looking for
798 * a code much simpler (and less efficicient). Here we merge loops if they have
799 * common parts in the iteration space (if the intersection of their domains is
800 * not empty), and let them isolated otherwise. This function returns the new
802 * - October 29th 2001: first version.
803 * - July 3rd->11th 2003: memory leaks hunt and correction.
804 * - June 22nd 2005: Adaptation for GMP.
806 CloogLoop
* cloog_loop_merge(CloogLoop
* loop
)
808 CloogLoop
* res
, * merge
, * now
, * Q
, * P
, * new_inner
, * next
, * old
;
809 CloogDomain
* new_domain
, * temp
;
811 if ((loop
== NULL
) || (loop
->next
== NULL
))
815 value_set_si(one
,1) ;
817 /* First loop is added to the target list. */
818 res
= cloog_loop_alloc(loop
->domain
,one
,loop
->block
,loop
->inner
,NULL
) ;
820 /* Now the domain is in 'res' and it will be freed. */
821 loop
->domain
= NULL
;
823 /* And one by one, we see if we have to merge or to add the other loops. */
824 while((loop
= loop
->next
) != NULL
)
826 P
= cloog_loop_alloc(loop
->domain
,one
,loop
->block
,loop
->inner
,NULL
) ;
828 /* Now the domain is in 'P' and it will be freed. */
829 loop
->domain
= NULL
;
831 /* For each loop in the target list, if the intersection with the new loop
832 * is empty, we can add the new loop directly, otherwise, we can merge then
836 { temp
= cloog_domain_intersection(Q
->domain
,P
->domain
) ;
838 if (cloog_domain_isempty(temp
))
839 { cloog_domain_free(temp
) ;
840 cloog_loop_add_disjoint(&merge
,&now
,Q
) ;
843 { cloog_domain_free(temp
) ;
844 new_inner
= cloog_loop_concat(Q
->inner
,P
->inner
) ;
845 temp
= cloog_domain_union(P
->domain
,Q
->domain
) ;
846 new_domain
= cloog_domain_convex(temp
) ;
847 cloog_domain_free(temp
) ;
848 /* Q and P are no more used (but their content yes !).*/
849 cloog_loop_free_parts(P
,1,0,0,0) ;
850 cloog_loop_free_parts(Q
,1,0,0,0) ;
851 P
= cloog_loop_alloc(new_domain
,one
,NULL
,new_inner
,NULL
) ;
856 /* If there was merging, add it, otherwise add the loop lonely.
857 * DEBUG : ici pas besoin de s'assurer que P->next est NULL (possible que
858 * non si pas de fusion) car le dernier loop etudie a loop->next = NULL.
860 cloog_loop_add_disjoint(&merge
,&now
,P
) ;
863 cloog_loop_free_parts(old
,0,0,0,1) ;
871 * cloog_loop_sort function:
872 * Adaptation from LoopGen 0.4 by F. Quillere. This function sorts a list of
873 * parameterized disjoint polyhedra, in order to not have lexicographic order
874 * violation (see Quillere paper).
875 * - September 16th 2005: inclusion of cloog_loop_number (October 29th 2001).
877 CloogLoop
* cloog_loop_sort(CloogLoop
* loop
, int level
, int nb_par
)
878 { CloogLoop
* res
, * now
, * temp
, ** loop_array
;
880 int i
, nb_loops
=0, * permut
;
882 /* We will need to know how many loops are in the list. */
889 /* If there is only one loop, it's the end. */
893 /* We have to allocate memory for some useful components:
894 * - loop_array: the loop array,
895 * - pols: the array of domains to sort,
896 * - permut: will give us a possible sort (maybe not the only one).
898 loop_array
= (CloogLoop
**)malloc(nb_loops
*sizeof(CloogLoop
*)) ;
899 pols
= (Polyhedron
**)malloc(nb_loops
*sizeof(Polyhedron
*)) ;
900 permut
= (int *)malloc(nb_loops
*sizeof(int)) ;
902 /* We fill up the loop and domain arrays. */
903 for (i
=0;i
<nb_loops
;i
++,loop
=loop
->next
)
904 { loop_array
[i
] = loop
;
905 pols
[i
] = cloog_domain_polyhedron(loop_array
[i
]->domain
) ;
908 /* cloog_domain_sort will fill up permut. */
909 cloog_domain_sort(pols
,nb_loops
,level
,nb_par
,permut
) ;
911 /* With permut and loop_array we build the sorted list. */
913 for (i
=0;i
<nb_loops
;i
++)
914 { /* To avoid pointer looping... loop_add will rebuild the list. */
915 loop_array
[permut
[i
]-1]->next
= NULL
;
916 cloog_loop_add(&res
,&now
,loop_array
[permut
[i
]-1]) ;
928 * cloog_loop_nest function:
929 * This function changes the loop list in such a way that we have no more than
930 * one dimension added by level. It returns an equivalent loop list with
932 * - October 29th 2001: first version.
933 * - July 3rd->11th 2003: memory leaks hunt and correction.
934 * - June 22nd 2005: Adaptation for GMP.
935 * - November 21th 2005: (debug) now OK when cloog_loop_restrict returns NULL.
937 CloogLoop
* cloog_loop_nest(loop
, context
, level
, nb_par
)
939 CloogDomain
* context
;
943 CloogLoop
* p
, * temp
, * res
, * now
, * next
;
944 CloogDomain
* new_domain
;
947 value_set_si(one
,1) ;
950 /* Each domain is changed by its intersection with the context. */
952 { p
= cloog_loop_restrict(loop
,context
,nb_par
) ;
956 { cloog_loop_free_parts(loop
,1,0,0,0) ;
958 temp
= cloog_loop_alloc(p
->domain
,one
,p
->block
,p
->inner
,NULL
) ;
960 /* If the intersection dimension is too big, we make projections smaller
961 * and smaller, and each projection includes the preceding projection
962 * (thus, in the target list, dimensions are added one by one).
964 if ((cloog_domain_dimension(p
->domain
)-nb_par
) > level
)
965 for (l
=cloog_domain_dimension(p
->domain
)-nb_par
-1;l
>=level
;l
--)
966 { new_domain
= cloog_domain_project(p
->domain
,l
,nb_par
) ;
967 temp
= cloog_loop_alloc(new_domain
,one
,NULL
,temp
,NULL
) ;
970 /* p is no more useful (but its content yes !). */
971 cloog_loop_free_parts(p
,0,0,0,0) ;
973 cloog_loop_add(&res
,&now
,temp
) ;
976 cloog_loop_free_parts(loop
,1,1,1,0) ;
987 * cloog_loop_stride function:
988 * This function will find the stride of a loop for the iterator at the column
989 * number 'level' in the constraint matrix. It will update the lower bound of
990 * the iterator accordingly. Basically, the function will try to find in the
991 * inner loops a common condition on this iterator for the inner loop iterators
992 * to be integral. For instance, let us consider a loop with the iterator i,
993 * the iteration domain -4<=i<=n, and its two inner loops with the iterator j.
994 * The first inner loop has the constraint 3j=i, and the second one has the
995 * constraint 6j=i. Then the common constraint on i for j to be integral is
996 * i%3=0, the stride for i is 3. Lastly, we have to find the new lower bound
997 * for i: the first value satisfying the common constraint: -3. At the end, the
998 * iteration domain for i is -3<=i<=n and the stride for i is 3.
999 * - loop is the loop including the iteration domain of the considered iterator,
1000 * - level is the column number of the iterator in the matrix of contraints.
1002 * - June 29th 2003: first version (work in progress since June 26th 2003).
1003 * - July 14th 2003: simpler version.
1004 * - June 22nd 2005: Adaptation for GMP (from S. Verdoolaege's 0.12.1 version).
1006 void cloog_loop_stride(CloogLoop
* loop
, int level
, int nb_par
)
1007 { int first_search
;
1008 Value stride
, ref_offset
, offset
, potential
, lower
;
1011 value_init_c(stride
) ;
1012 value_init_c(ref_offset
) ;
1013 value_init_c(offset
) ;
1014 value_init_c(potential
) ;
1015 value_init_c(lower
) ;
1017 value_set_si(ref_offset
,0) ;
1018 value_set_si(offset
,0) ;
1019 value_set_si(lower
,0) ;
1021 /* Default stride. */
1022 value_set_si(stride
,1) ;
1024 inner
= loop
->inner
;
1026 if (cloog_domain_integral_lowerbound(loop
->domain
,level
,&lower
))
1027 while (inner
!= NULL
)
1028 { /* If the minimun stride has not been found yet, find the stride. */
1029 if ((first_search
) || (value_notone_p(stride
)))
1030 { cloog_domain_stride(inner
->domain
,level
,nb_par
,&potential
,&offset
) ;
1031 if (value_notone_p(potential
) && (!first_search
))
1032 { /* Offsets must be the same. */
1033 if (value_eq(offset
,ref_offset
))
1034 Gcd(potential
,stride
,&stride
) ;
1036 value_set_si(stride
,1) ;
1039 { value_assign(stride
,potential
) ;
1040 value_assign(ref_offset
,offset
) ;
1046 inner
= inner
->next
;
1049 /* Update the values if necessary. */
1050 if (value_notone_p(stride
))
1051 { /* Update the stride value. */
1052 value_assign(loop
->stride
,stride
) ;
1053 /* Update the lower bound (too late to do something more intelligent !). */
1054 /* Here we want potential = ((lower-offset)%stride). */
1055 value_substract(potential
,lower
,offset
) ;
1056 value_modulus(potential
,potential
,stride
) ;
1057 while (value_notzero_p(potential
))
1058 { value_increment(lower
,lower
) ;
1059 value_substract(potential
,lower
,offset
) ;
1060 value_modulus(potential
,potential
,stride
) ;
1062 cloog_domain_lowerbound_update(loop
->domain
,level
,lower
) ;
1065 value_clear_c(stride
) ;
1066 value_clear_c(ref_offset
) ;
1067 value_clear_c(offset
) ;
1068 value_clear_c(potential
) ;
1069 value_clear_c(lower
) ;
1074 * cloog_loop_stop function:
1075 * This function implements the 'stop' option : each domain of each loop
1076 * in the list 'loop' is replaced by 'context'. 'context' should be the
1077 * domain of the outer loop. By using this method, there are no more dimensions
1078 * to scan and the simplification step will automaticaly remove the domains
1079 * since they are the same as the corresponding contexts. The effect of this
1080 * function is to stop the code generation at the level this function is called,
1081 * the resulting code do not consider the next dimensions.
1082 * - January 11th 2005: first version.
1084 CloogLoop
* cloog_loop_stop(CloogLoop
* loop
, CloogDomain
* context
)
1088 { cloog_domain_free(loop
->domain
) ;
1089 loop
->domain
= cloog_domain_copy(context
) ;
1090 loop
->next
= cloog_loop_stop(loop
->next
, context
) ;
1098 * cloog_loop_scalar_ge function:
1099 * This function returns 1 if loop 'l1' is greater or equal to loop 'l2' for the
1100 * scalar dimension vector that begins at dimension 'scalar', 0 otherwise. What
1101 * we want to know is whether a loop is scheduled before another one or not.
1102 * This function solves the problem when the considered dimension for scheduling
1103 * is a scalar dimension. Since there may be a succession of scalar dimensions,
1104 * this function will reason about the vector of scalar dimension that begins
1105 * at dimension 'level+scalar' and finish to the first non-scalar dimension.
1106 * - l1 and l2 are the loops to compare,
1107 * - level is the current non-scalar dimension,
1108 * - scaldims is the boolean array saying whether a dimension is scalar or not,
1109 * - nb_scattdims is the size of the scaldims array,
1110 * - scalar is the current scalar dimension.
1112 * - September 9th 2005 : first version.
1114 int cloog_loop_scalar_ge(l1
, l2
, level
, scaldims
, nb_scattdims
, scalar
)
1115 CloogLoop
* l1
, * l2
;
1116 int level
, * scaldims
, nb_scattdims
, scalar
;
1117 { while ((scalar
< l1
->inner
->block
->nb_scaldims
) && scaldims
[level
+scalar
-1])
1118 { if (value_ge(l1
->inner
->block
->scaldims
[scalar
],
1119 l2
->inner
->block
->scaldims
[scalar
]))
1129 * cloog_loop_scalar_eq function:
1130 * This function returns 1 if loop 'l1' is equal to loop 'l2' for the scalar
1131 * dimension vector that begins at dimension 'scalar', 0 otherwise. What we want
1132 * to know is whether two loops are scheduled for the same time or not.
1133 * This function solves the problem when the considered dimension for scheduling
1134 * is a scalar dimension. Since there may be a succession of scalar dimensions,
1135 * this function will reason about the vector of scalar dimension that begins
1136 * at dimension 'level+scalar' and finish to the first non-scalar dimension.
1137 * - l1 and l2 are the loops to compare,
1138 * - level is the current non-scalar dimension,
1139 * - scaldims is the boolean array saying whether a dimension is scalar or not,
1140 * - nb_scattdims is the size of the scaldims array,
1141 * - scalar is the current scalar dimension.
1143 * - September 9th 2005 : first version.
1145 int cloog_loop_scalar_eq(l1
, l2
, level
, scaldims
, nb_scattdims
, scalar
)
1146 CloogLoop
* l1
, * l2
;
1147 int level
, * scaldims
, nb_scattdims
, scalar
;
1148 { while ((scalar
< l1
->inner
->block
->nb_scaldims
) && scaldims
[level
+scalar
-1])
1149 { if (value_eq(l1
->inner
->block
->scaldims
[scalar
],
1150 l2
->inner
->block
->scaldims
[scalar
]))
1160 * cloog_loop_scalar_sort function:
1161 * This function sorts a linked list of loops (loop) with respect to the
1162 * scalar dimension vector that begins at dimension 'scalar'. Since there may
1163 * be a succession of scalar dimensions, this function will reason about the
1164 * vector of scalar dimension that begins at dimension 'level+scalar' and
1165 * finish to the first non-scalar dimension.
1166 * - loop is the loop list to sort,
1167 * - level is the current non-scalar dimension,
1168 * - scaldims is the boolean array saying whether a dimension is scalar or not,
1169 * - nb_scattdims is the size of the scaldims array,
1170 * - scalar is the current scalar dimension.
1172 * - July 2nd 2005: first developments.
1173 * - September 2nd 2005: first version.
1175 CloogLoop
* cloog_loop_scalar_sort(loop
, level
, scaldims
, nb_scattdims
, scalar
)
1177 int level
, * scaldims
, nb_scattdims
, scalar
;
1178 { CloogLoop
* unsorted
, * previous_unsorted
, * current
, * previous_current
;
1183 /* We start from the second element.*/
1184 unsorted
= loop
->next
;
1185 previous_unsorted
= loop
;
1187 while (unsorted
!= NULL
)
1188 { /* We look for the unsorted element place in the list. */
1190 previous_current
= NULL
;
1192 while((current
!= unsorted
) &&
1193 (cloog_loop_scalar_ge(unsorted
,current
,level
,
1194 scaldims
,nb_scattdims
,scalar
)))
1195 { previous_current
= current
;
1196 current
= current
->next
;
1199 if (current
== unsorted
)
1200 { /* If the unsorted element is yet at the right place, restart with the
1201 * next unsorted element.
1203 previous_unsorted
= unsorted
;
1204 unsorted
= unsorted
->next
;
1207 { /* We have to insert the unsorted element after previous_current. */
1208 previous_unsorted
->next
= unsorted
->next
;
1209 if (previous_current
== NULL
)
1210 { /* Insertion at the very first place. */
1211 unsorted
->next
= loop
;
1215 { /* Insertion after previous_current. */
1216 unsorted
->next
= previous_current
->next
;
1217 previous_current
->next
= unsorted
;
1219 /* Restart with the next unsorted element. */
1220 unsorted
= previous_unsorted
->next
;
1229 * cloog_loop_generate_backtrack function:
1230 * adaptation from LoopGen 0.4 by F. Quillere. This function implements the
1231 * backtrack of the Quillere et al. algorithm (see the Quillere paper).
1232 * It eliminates unused iterations of the current level for the new one. See the
1233 * example called linearity-1-1 example with and without this part for an idea.
1234 * - October 26th 2001: first version in cloog_loop_generate_general.
1235 * - July 31th 2002: (debug) no more parasite loops (REALLY hard !).
1236 * - October 30th 2005: extraction from cloog_loop_generate_general.
1238 CloogLoop
* cloog_loop_generate_backtrack(loop
, context
, level
, nb_par
, options
)
1240 CloogDomain
* context
;
1242 CloogOptions
* options
;
1244 CloogDomain
* domain
;
1245 CloogLoop
* now
, * now2
, * next
, * next2
, * end
, * temp
, * l
, * inner
,
1249 value_set_si(one
,1) ;
1254 while (temp
!= NULL
)
1256 inner
= temp
->inner
;
1258 while (inner
!= NULL
)
1259 { next
= inner
->next
;
1260 /* This 'if' and its first part is the debug of july 31th 2002. */
1261 if (inner
->block
!= NULL
)
1262 { end
= cloog_loop_alloc(inner
->domain
,one
,inner
->block
,NULL
,NULL
) ;
1263 domain
= cloog_domain_copy(temp
->domain
) ;
1264 new_loop
= cloog_loop_alloc(domain
,one
,NULL
,end
,NULL
) ;
1267 new_loop
= cloog_loop_project(inner
,level
,nb_par
) ;
1269 cloog_loop_free_parts(inner
,0,0,0,0) ;
1270 cloog_loop_add(&l
,&now2
,new_loop
) ;
1274 temp
->inner
= NULL
;
1277 { l
= cloog_loop_separate(l
) ;
1278 l
= cloog_loop_sort(l
,level
,nb_par
) ;
1280 { value_assign(l
->stride
,temp
->stride
) ;
1281 cloog_loop_add(&loop
,&now
,l
) ;
1285 next2
= temp
->next
;
1286 cloog_loop_free_parts(temp
,1,0,0,0) ;
1290 value_clear_c(one
) ;
1297 * cloog_loop_generate_general function:
1298 * Adaptation from LoopGen 0.4 by F. Quillere. This function implements the
1299 * Quillere algorithm for polyhedron scanning from step 3 to 5.
1300 * (see the Quillere paper).
1301 * - loop is the loop for which we have to generate a scanning code,
1302 * - context is the context of the current loop (constraints on parameter and/or
1303 * on outer loop counters),
1304 * - level is the current non-scalar dimension,
1305 * - scalar is the current scalar dimension,
1306 * - scaldims is the boolean array saying whether a dimension is scalar or not,
1307 * - nb_scattdims is the size of the scaldims array,
1308 * - nb_par is the number of parameters,
1309 * - options are the general code generation options.
1311 * - October 26th 2001: first version.
1312 * - July 3rd->11th 2003: memory leaks hunt and correction.
1313 * - June 22nd 2005: Adaptation for GMP.
1314 * - September 2nd 2005: The function have been cutted out in two pieces:
1315 * cloog_loop_generate and this one, in order to handle
1316 * the scalar dimension case more efficiently with
1317 * cloog_loop_generate_scalar.
1318 * - November 15th 2005: (debug) the result of the cloog_loop_generate call may
1319 * be a list of polyhedra (especially if stop option is
1320 * used): cloog_loop_add_list instead of cloog_loop_add.
1322 CloogLoop
* cloog_loop_generate_general(loop
, context
, level
, scalar
,
1323 scaldims
, nb_scattdims
, nb_par
, options
)
1325 CloogDomain
* context
;
1326 int level
, scalar
, * scaldims
, nb_scattdims
, nb_par
;
1327 CloogOptions
* options
;
1329 CloogLoop
* res
, * now
, * temp
, * l
, * new_loop
, * inner
, * now2
, * end
,
1331 CloogDomain
* domain
;
1333 /* 3. Separate all projections into disjoint polyhedra. */
1334 res
= ((options
->f
> level
+scalar
) || (options
->f
< 0)) ?
1335 cloog_loop_merge(loop
) : cloog_loop_separate(loop
) ;
1337 /* 3b. -correction- sort the loops to determine their textual order. */
1338 res
= cloog_loop_sort(res
,level
,nb_par
) ;
1341 value_set_si(one
,1) ;
1343 /* 4. Recurse for each loop with the current domain as context. */
1346 if ((level
+scalar
< options
->l
) || (options
->l
< 0))
1348 { if (options
->strides
)
1349 cloog_loop_stride(temp
,level
,nb_par
) ;
1350 inner
= temp
->inner
;
1351 domain
= temp
->domain
;
1353 while (inner
!= NULL
)
1354 { /* 4b. -ced- recurse for each sub-list of non terminal loops. */
1355 if (cloog_domain_dimension(inner
->domain
) > (level
+ nb_par
))
1357 while ((end
->next
!= NULL
) &&
1358 (cloog_domain_dimension(end
->next
->domain
) > (level
+ nb_par
)))
1364 l
= cloog_loop_generate(inner
,domain
,level
+1,scalar
,
1365 scaldims
,nb_scattdims
,nb_par
,options
) ;
1368 cloog_loop_add_list(&into
,&now
,l
) ;
1373 { cloog_loop_add(&into
,&now
,inner
) ;
1374 inner
= inner
->next
;
1379 temp
->inner
= into
;
1380 cloog_loop_add(&res
,&now2
,temp
) ;
1384 while (temp
!= NULL
)
1385 { next
= temp
->next
;
1386 l
= cloog_loop_nest(temp
->inner
,temp
->domain
,level
+1,nb_par
) ;
1387 new_loop
= cloog_loop_alloc(temp
->domain
,one
,NULL
,l
,NULL
) ;
1388 temp
->inner
= NULL
;
1390 cloog_loop_free_parts(temp
,0,0,0,0) ;
1391 cloog_loop_add(&res
,&now
,new_loop
) ;
1395 /* 5. eliminate unused iterations of the current level for the new one. See
1396 * the example called linearity-1-1 example with and without this part
1399 if ((!options
->nobacktrack
) &&
1400 ((level
+scalar
< options
->l
) || (options
->l
< 0)) &&
1401 ((options
->f
<= level
+scalar
) && !(options
->f
< 0)))
1402 res
= cloog_loop_generate_backtrack(res
,context
,level
,nb_par
,options
) ;
1404 /* Pray for my new paper to be accepted somewhere since the following stuff
1405 * is really amazing :-) !
1406 * Far long later: The paper has been accepted to PACT 2004 :-))). But there
1407 * are still some bugs and I have no time to fix them. Thus now you have to
1408 * pray for me to get an academic position for that really amazing stuff :-) !
1409 * Later again: OK, I get my academic position, but still I have not enough
1410 * time to fix and clean this part... Pray again :-) !!!
1412 /* res = cloog_loop_unisolate(res,context,level,nb_par) ;*/
1414 value_clear_c(one
) ;
1420 * cloog_loop_generate_scalar function:
1421 * This function applies the simplified code generation scheme in the trivial
1422 * case of scalar dimensions. When dealing with scalar dimensions, there is
1423 * no need of costly polyhedral operations for separation or sorting: sorting
1424 * is a question of comparing scalar vectors and separation amounts to consider
1425 * only loops with the same scalar vector for the next step of the code
1426 * generation process. This function achieves the separation/sorting process
1427 * for the vector of scalar dimension that begins at dimension 'level+scalar'
1428 * and finish to the first non-scalar dimension.
1429 * - loop is the loop for which we have to generate a scanning code,
1430 * - context is the context of the current loop (constraints on parameter and/or
1431 * on outer loop counters),
1432 * - level is the current non-scalar dimension,
1433 * - scalar is the current scalar dimension,
1434 * - scaldims is the boolean array saying whether a dimension is scalar or not,
1435 * - nb_scattdims is the size of the scaldims array,
1436 * - nb_par is the number of parameters,
1437 * - options are the general code generation options.
1439 * - September 2nd 2005: First version.
1441 CloogLoop
* cloog_loop_generate_scalar(loop
, context
, level
, scalar
,
1442 scaldims
, nb_scattdims
, nb_par
, options
)
1444 CloogDomain
* context
;
1445 int level
, scalar
, * scaldims
, nb_scattdims
, nb_par
;
1446 CloogOptions
* options
;
1447 { CloogLoop
* res
, * now
, * temp
, * l
, * end
, * next
, * ref
;
1449 /* We sort the loop list with respect to the current scalar vector. */
1450 res
= cloog_loop_scalar_sort(loop
,level
,scaldims
,nb_scattdims
,scalar
) ;
1454 while (temp
!= NULL
)
1455 { /* Then we will appy the general code generation process to each sub-list
1456 * of loops with the same scalar vector.
1461 while((end
->next
!= NULL
) &&
1462 cloog_loop_scalar_eq(ref
,end
->next
,level
,scaldims
,nb_scattdims
,scalar
))
1468 /* For the next dimension, scalar value is updated by adding the scalar
1469 * vector size, which is stored at scaldims[level+scalar-1].
1471 l
= cloog_loop_generate_general(temp
,context
,level
,
1472 scalar
+scaldims
[level
+scalar
-1],
1473 scaldims
,nb_scattdims
,nb_par
,options
) ;
1476 cloog_loop_add_list(&res
,&now
,l
) ;
1486 * cloog_loop_generate function:
1487 * Adaptation from LoopGen 0.4 by F. Quillere. This function implements the
1488 * Quillere algorithm for polyhedron scanning from step 1 to 2.
1489 * (see the Quillere paper).
1490 * - loop is the loop for which we have to generate a scanning code,
1491 * - context is the context of the current loop (constraints on parameter and/or
1492 * on outer loop counters),
1493 * - level is the current non-scalar dimension,
1494 * - scalar is the current scalar dimension,
1495 * - scaldims is the boolean array saying whether a dimension is scalar or not,
1496 * - nb_scattdims is the size of the scaldims array,
1497 * - nb_par is the number of parameters,
1498 * - options are the general code generation options.
1500 * - October 26th 2001: first version.
1501 * - July 3rd->11th 2003: memory leaks hunt and correction.
1502 * - June 15th 2005: a memory leak fixed (loop was not entirely freed when
1503 * the result of cloog_loop_restrict was NULL).
1504 * - June 22nd 2005: Adaptation for GMP.
1505 * - September 2nd 2005: The function have been cutted out in two pieces:
1506 * cloog_loop_generate and this one, in order to handle
1507 * the scalar dimension case more efficiently with
1508 * cloog_loop_generate_scalar.
1509 * - November 15th 2005: (debug) Condition for stop option no more take care of
1510 * further scalar dimensions.
1512 CloogLoop
* cloog_loop_generate(loop
, context
, level
, scalar
,
1513 scaldims
, nb_scattdims
, nb_par
, options
)
1515 CloogDomain
* context
;
1516 int level
, scalar
, * scaldims
, nb_scattdims
, nb_par
;
1517 CloogOptions
* options
;
1518 { CloogLoop
* res
, * now
, * temp
, * next
, * old
;
1520 /* If the user asked to stop code generation at this level, let's stop. */
1521 if ((options
->stop
>= 0) && (level
+scalar
>= options
->stop
+1))
1522 return cloog_loop_stop(loop
,context
) ;
1526 /* 1. Replace each polyhedron by its intersection with the context.
1527 * 2. Compute the projection of each polyhedron onto the outermost
1528 * loop variable and the parameters.
1530 while (loop
!= NULL
)
1531 { next
= loop
->next
;
1532 temp
= cloog_loop_restrict(loop
,context
,nb_par
) ;
1536 temp
= cloog_loop_project(temp
,level
,nb_par
) ;
1537 cloog_loop_free_parts(old
,0,0,0,0) ;
1538 cloog_loop_add(&res
,&now
,temp
) ;
1539 cloog_loop_free_parts(loop
,1,0,0,0) ;
1542 { loop
->next
= NULL
;
1543 cloog_loop_free(loop
) ;
1551 /* To save both time and memory, we switch here depending on whether the
1552 * current dimension is scalar (simplified processing) or not (general
1555 if ((level
+scalar
<= nb_scattdims
) && (scaldims
[level
+scalar
-1]))
1556 res
= cloog_loop_generate_scalar(res
,context
,level
,scalar
,
1557 scaldims
,nb_scattdims
,nb_par
,options
) ;
1559 res
= cloog_loop_generate_general(res
,context
,level
,scalar
,
1560 scaldims
,nb_scattdims
,nb_par
,options
) ;
1567 * cloog_loop_simplify function:
1568 * This function implements the part 6. of the Quillere algorithm, it
1569 * recursively simplifies each loop in the context of the preceding loop domain.
1570 * It returns a pointer to the simplified loop list.
1571 * The cloog_domain_simplify (DomainSimplify) behaviour is really bad with
1572 * polyhedra union and some really awful sidesteppings were written, I plan
1574 * - October 31th 2001: first version.
1575 * - July 3rd->11th 2003: memory leaks hunt and correction.
1576 * - April 16th 2005: a memory leak fixed (extended_context was not freed).
1577 * - June 15th 2005: a memory leak fixed (loop was not conveniently freed
1578 * when the constraint system is never true).
1579 * - October 27th 2005: - this function called before cloog_loop_fast_simplify
1580 * is now the official cloog_loop_simplify function in
1581 * replacement of a slower and more complex one (after
1582 * deep changes in the pretty printer).
1583 * - we use cloog_loop_disjoint to fix the problem when
1584 * simplifying gives a union of polyhedra (before, it
1585 * was under the responsibility of the pretty printer).
1587 CloogLoop
* cloog_loop_simplify(loop
, context
, level
, nb_par
)
1589 CloogDomain
* context
;
1592 CloogBlock
* new_block
;
1593 CloogLoop
* simplified
, * inner
, * next
;
1594 CloogDomain
* domain
, * simp
, * inter
, * extended_context
;
1599 domain
= loop
->domain
;
1601 /* If the constraint system is never true, go to the next one. */
1602 while (cloog_domain_never_integral(domain
))
1603 { next
= loop
->next
;
1605 cloog_loop_free(loop
) ;
1611 domain
= loop
->domain
;
1615 next
= cloog_loop_simplify(loop
->next
,context
,level
,nb_par
) ;
1616 inner
= cloog_loop_simplify(loop
->inner
,domain
,level
+1,nb_par
) ;
1618 if ((inner
== NULL
) && (loop
->block
== NULL
))
1619 { loop
->inner
= NULL
; /* For loop integrity. */
1620 loop
->next
= NULL
; /* For loop integrity. */
1621 cloog_loop_free_parts(loop
,1,1,1,0) ;
1625 new_block
= cloog_block_copy(loop
->block
) ;
1627 domain_dim
= cloog_domain_dimension(domain
) - nb_par
;
1628 extended_context
=cloog_domain_extend(context
,domain_dim
,nb_par
);
1629 inter
= cloog_domain_intersection(domain
,extended_context
) ;
1630 simp
= cloog_domain_simplify(inter
,extended_context
) ;
1631 cloog_domain_free(inter
) ;
1632 cloog_domain_free(extended_context
) ;
1634 simplified
= cloog_loop_alloc(simp
,loop
->stride
,new_block
,inner
,next
) ;
1636 /* Examples like test/iftest2.cloog give unions of polyhedra after
1637 * simplifying, thus we we have to disjoint them. Another good reason to
1638 * put the simplifying step in the Quillere backtrack.
1640 simplified
= cloog_loop_disjoint(simplified
) ;
1642 loop
->inner
= NULL
; /* For loop integrity. */
1643 loop
->next
= NULL
; /* For loop integrity. */
1644 cloog_loop_free_parts(loop
,1,1,0,0) ;
1646 return(simplified
) ;
1651 * cloog_loop_scatter function:
1652 * This function add the scattering (scheduling) informations in a loop.
1653 * - November 4th 2001: first version.
1655 void cloog_loop_scatter(CloogLoop
* loop
, CloogDomain
* scatt
)
1657 CloogDomain
* domain
, * ext
, * newdom
, * newpart
, * temp
;
1659 domain
= loop
->domain
;
1661 scatt_dim
= cloog_domain_dimension(scatt
) - cloog_domain_dimension(domain
) ;
1663 /* For each polyhedron of domain (it can be an union of polyhedra). */
1664 while (domain
!= NULL
)
1665 { /* Extend the domain by adding the scattering dimensions as the new
1666 * first domain dimensions.
1668 ext
= cloog_domain_extend(domain
,scatt_dim
,cloog_domain_dimension(domain
)) ;
1669 /* Then add the scattering constraints. */
1670 newpart
= cloog_domain_addconstraints(scatt
,ext
) ;
1671 cloog_domain_free(ext
) ;
1675 newdom
= cloog_domain_union(newdom
,newpart
) ;
1676 cloog_domain_free(temp
) ;
1677 cloog_domain_free(newpart
) ;
1682 /* We don't want to free the rest of the list. */
1684 domain
= cloog_domain_cut_first(temp
) ;
1685 cloog_domain_free(temp
) ;
1688 loop
->domain
= newdom
;