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 library is free software; you can redistribute it and/or *
18 * modify it under the terms of the GNU Lesser General Public *
19 * License as published by the Free Software Foundation; either *
20 * version 2.1 of the License, or (at your option) any later version. *
22 * This library is distributed in the hope that it will be useful, *
23 * but WITHOUT ANY WARRANTY; without even the implied warranty of *
24 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU *
25 * Lesser General Public License for more details. *
27 * You should have received a copy of the GNU Lesser General Public *
28 * License along with this library; if not, write to the Free Software *
29 * Foundation, Inc., 51 Franklin Street, Fifth Floor, *
30 * Boston, MA 02110-1301 USA *
32 * CLooG, the Chunky Loop Generator *
33 * Written by Cedric Bastoul, Cedric.Bastoul@inria.fr *
35 ******************************************************************************/
36 /* CAUTION: the english used for comments is probably the worst you ever read,
37 * please feel free to correct and improve it !
42 # include "../include/cloog/cloog.h"
45 /******************************************************************************
46 * Memory leaks hunting *
47 ******************************************************************************/
51 * These functions and global variables are devoted to memory leaks hunting: we
52 * want to know at each moment how many CloogLoop structures had been allocated
53 * (cloog_loop_allocated) and how many had been freed (cloog_loop_freed).
54 * Each time a CloogLoog structure is allocated, a call to the function
55 * cloog_loop_leak_up() must be carried out, and respectively
56 * cloog_loop_leak_down() when a CloogLoop structure is freed. The special
57 * variable cloog_loop_max gives the maximal number of CloogLoop structures
58 * simultaneously alive (i.e. allocated and non-freed) in memory.
59 * - July 3rd->11th 2003: first version (memory leaks hunt and correction).
63 static void cloog_loop_leak_up(CloogState
*state
)
65 state
->loop_allocated
++;
66 if ((state
->loop_allocated
- state
->loop_freed
) > state
->loop_max
)
67 state
->loop_max
= state
->loop_allocated
- state
->loop_freed
;
71 static void cloog_loop_leak_down(CloogState
*state
)
77 /******************************************************************************
78 * Structure display function *
79 ******************************************************************************/
83 * cloog_loop_print_structure function:
84 * Displays a loop structure in a way that trends to be understandable without
85 * falling in a deep depression or, for the lucky ones, getting a headache...
86 * Written by Olivier Chorier, Luc Marchaud, Pierre Martin and Romain Tartiere.
87 * - April 24th 2005: Initial version.
88 * - May 21rd 2005: - New parameter `F' for destination file (ie stdout),
90 * - May 26th 2005: Memory leak hunt.
91 * - June 2nd 2005: (Ced) Integration and minor fixes.
92 * -June 22nd 2005: (Ced) Adaptation for GMP.
94 void cloog_loop_print_structure(FILE * file
, CloogLoop
* loop
, int level
)
98 { /* Go to the right level. */
99 for (i
=0; i
<level
; i
++)
100 fprintf(file
,"|\t") ;
102 fprintf(file
,"+-- CloogLoop\n") ;
108 { /* Go to the right level. */
109 for (i
=0; i
<level
; i
++)
110 fprintf(file
,"|\t") ;
112 fprintf(file
,"| CloogLoop\n") ;
118 for(j
=0; j
<=level
+1; j
++)
119 fprintf(file
,"|\t") ;
122 /* Print the domain. */
123 cloog_domain_print_structure(file
, loop
->domain
, level
+1, "CloogDomain");
125 /* Print the stride. */
126 for(j
=0; j
<=level
; j
++)
127 fprintf(file
,"|\t") ;
129 fprintf(file
, "Stride: ");
130 cloog_int_print(file
, loop
->stride
->stride
);
132 fprintf(file
, "Offset: ");
133 cloog_int_print(file
, loop
->stride
->offset
);
138 for(j
=0; j
<=level
+1; j
++)
139 fprintf(file
,"|\t") ;
142 /* Print the block. */
143 cloog_block_print_structure(file
,loop
->block
,level
+1) ;
146 for (i
=0; i
<=level
+1; i
++)
147 fprintf(file
,"|\t") ;
150 /* Print inner if any. */
152 cloog_loop_print_structure(file
,loop
->inner
,level
+1) ;
154 /* And let's go for the next one. */
157 /* One more time something that is here only for a better look. */
159 { /* Two blank lines if this is the end of the linked list. */
161 { for (i
=0; i
<=level
; i
++)
162 fprintf(file
,"|\t") ;
168 { /* A special blank line if the is a next loop. */
169 for (i
=0; i
<=level
; i
++)
170 fprintf(file
,"|\t") ;
171 fprintf(file
,"V\n") ;
178 * cloog_loop_print function:
179 * This function prints the content of a CloogLoop structure (start) into a
180 * file (file, possibly stdout).
181 * - June 2nd 2005: Now this very old function (probably as old as CLooG) is
182 * only a frontend to cloog_loop_print_structure, with a quite
183 * better human-readable representation.
185 void cloog_loop_print(FILE * file
, CloogLoop
* loop
)
186 { cloog_loop_print_structure(file
,loop
,0) ;
190 /******************************************************************************
191 * Memory deallocation function *
192 ******************************************************************************/
196 * cloog_loop_free function:
197 * This function frees the allocated memory for a CloogLoop structure (loop),
198 * and frees its inner loops and its next loops.
199 * - June 22nd 2005: Adaptation for GMP.
201 void cloog_loop_free(CloogLoop
* loop
)
204 while (loop
!= NULL
) {
205 cloog_loop_leak_down(loop
->state
);
208 cloog_domain_free(loop
->domain
) ;
209 cloog_block_free(loop
->block
) ;
210 if (loop
->inner
!= NULL
)
211 cloog_loop_free(loop
->inner
) ;
213 cloog_stride_free(loop
->stride
);
221 * cloog_loop_free_parts function:
222 * This function frees the allocated memory for some parts of a CloogLoop
223 * structure (loop), each other argument is a boolean having to be set to 1 if
224 * we want to free the corresponding part, 0 otherwise. This function applies
225 * the same freeing policy to its inner ans next loops recursively.
226 * - July 3rd 2003: first version.
227 * - June 22nd 2005: Adaptation for GMP.
229 void cloog_loop_free_parts(loop
, domain
, block
, inner
, next
)
231 int domain
, block
, inner
, next
;
232 { CloogLoop
* follow
;
234 while (loop
!= NULL
) {
235 cloog_loop_leak_down(loop
->state
);
236 follow
= loop
->next
;
239 cloog_domain_free(loop
->domain
) ;
242 cloog_block_free(loop
->block
) ;
244 if ((inner
) && (loop
->inner
!= NULL
))
245 cloog_loop_free_parts(loop
->inner
,domain
,block
,inner
,1) ;
247 cloog_stride_free(loop
->stride
);
257 /******************************************************************************
258 * Reading functions *
259 ******************************************************************************/
263 * Construct a CloogLoop structure from a given iteration domain
264 * and statement number.
266 CloogLoop
*cloog_loop_from_domain(CloogState
*state
, CloogDomain
*domain
,
271 CloogStatement
* statement
;
273 cloog_loop_leak_up(state
);
275 /* Memory allocation and information reading for the first domain: */
276 loop
= (CloogLoop
*)malloc(sizeof(CloogLoop
)) ;
278 cloog_die("memory overflow.\n");
281 loop
->domain
= domain
;
282 if (loop
->domain
!= NULL
)
283 nb_iterators
= cloog_domain_dimension(loop
->domain
);
287 /* assume no stride */
289 /* included statement block. */
290 statement
= cloog_statement_alloc(state
, number
+ 1);
291 loop
->block
= cloog_block_alloc(statement
, 0, NULL
, nb_iterators
);
293 /* inner is NULL at beginning. */
303 * cloog_loop_read function:
304 * This function reads loop data from a file (foo, possibly stdin) and
305 * returns a pointer to a CloogLoop structure containing the read information.
306 * This function can be used only for input file reading, when one loop is
307 * associated with one statement.
308 * - number is the statement block number carried by the loop (-1 if none).
309 * - nb_parameters is the number of parameters.
311 * - September 9th 2002: first version.
312 * - April 16th 2005: adaptation to new CloogStatement struct (with number).
313 * - June 11th 2005: adaptation to new CloogBlock structure.
314 * - June 22nd 2005: Adaptation for GMP.
316 CloogLoop
*cloog_loop_read(CloogState
*state
,
317 FILE *foo
, int number
, int nb_parameters
)
323 domain
= cloog_domain_union_read(state
, foo
, nb_parameters
);
325 /* To read that stupid "0 0 0" line. */
326 while (fgets(s
,MAX_STRING
,foo
) == 0) ;
327 while ((*s
=='#' || *s
=='\n') || (sscanf(s
," %d %d %d",&op1
,&op2
,&op3
)<3))
328 fgets(s
,MAX_STRING
,foo
) ;
330 return cloog_loop_from_domain(state
, domain
, number
);
334 /******************************************************************************
335 * Processing functions *
336 ******************************************************************************/
340 * cloog_loop_malloc function:
341 * This function allocates the memory space for a CloogLoop structure and
342 * sets its fields with default values. Then it returns a pointer to the
344 * - November 21th 2005: first version.
346 CloogLoop
*cloog_loop_malloc(CloogState
*state
)
349 /* Memory allocation for the CloogLoop structure. */
350 loop
= (CloogLoop
*)malloc(sizeof(CloogLoop
)) ;
352 cloog_die("memory overflow.\n");
353 cloog_loop_leak_up(state
);
356 /* We set the various fields with default values. */
358 loop
->domain
= NULL
;
371 * cloog_loop_alloc function:
372 * This function allocates the memory space for a CloogLoop structure and
373 * sets its fields with those given as input. Then it returns a pointer to the
375 * - October 27th 2001: first version.
376 * - June 22nd 2005: Adaptation for GMP.
377 * - November 21th 2005: use of cloog_loop_malloc.
379 CloogLoop
*cloog_loop_alloc(CloogState
*state
,
380 CloogDomain
*domain
, int otl
, CloogStride
*stride
,
381 CloogBlock
*block
, CloogLoop
*inner
, CloogLoop
*next
)
384 loop
= cloog_loop_malloc(state
);
386 loop
->domain
= domain
;
387 loop
->block
= block
;
388 loop
->inner
= inner
;
391 loop
->stride
= cloog_stride_copy(stride
);
398 * cloog_loop_add function:
399 * This function adds a CloogLoop structure (loop) at a given place (now) of a
400 * NULL terminated list of CloogLoop structures. The beginning of this list
401 * is (start). This function updates (now) to (loop), and updates (start) if the
402 * added element is the first one -that is when (start) is NULL-.
403 * - October 28th 2001: first version.
405 void cloog_loop_add(CloogLoop
** start
, CloogLoop
** now
, CloogLoop
* loop
)
406 { if (*start
== NULL
)
411 { (*now
)->next
= loop
;
412 *now
= (*now
)->next
;
418 * cloog_loop_add function:
419 * This function adds a CloogLoop structure (loop) at a given place (now) of a
420 * NULL terminated list of CloogLoop structures. The beginning of this list
421 * is (start). This function updates (now) to the end of the loop list (loop),
422 * and updates (start) if the added element is the first one -that is when
424 * - September 9th 2005: first version.
426 void cloog_loop_add_list(CloogLoop
** start
, CloogLoop
** now
, CloogLoop
* loop
)
427 { if (*start
== NULL
)
432 { (*now
)->next
= loop
;
433 *now
= (*now
)->next
;
436 while ((*now
)->next
!= NULL
)
437 *now
= (*now
)->next
;
442 * cloog_loop_copy function:
443 * This function returns a copy of the CloogLoop structure given as input. In
444 * fact, there is just new allocations for the CloogLoop structures, but their
445 * contents are the same.
446 * - October 28th 2001: first version.
447 * - July 3rd->11th 2003: memory leaks hunt and correction.
449 CloogLoop
* cloog_loop_copy(CloogLoop
* source
)
452 CloogDomain
* domain
;
456 { domain
= cloog_domain_copy(source
->domain
) ;
457 block
= cloog_block_copy(source
->block
) ;
458 loop
= cloog_loop_alloc(source
->state
, domain
, source
->otl
,
459 source
->stride
, block
, NULL
, NULL
);
460 loop
->usr
= source
->usr
;
461 loop
->inner
= cloog_loop_copy(source
->inner
) ;
462 loop
->next
= cloog_loop_copy(source
->next
) ;
469 * cloog_loop_add_disjoint function:
470 * This function adds some CloogLoop structures at a given place (now) of a
471 * NULL terminated list of CloogLoop structures. The beginning of this list
472 * is (start). (loop) can be an union of polyhedra, this function separates the
473 * union into a list of *disjoint* polyhedra then adds the list. This function
474 * updates (now) to the end of the list and updates (start) if first added
475 * element is the first of the principal list -that is when (start) is NULL-.
476 * (loop) can be freed by this function, basically when its domain is actually
477 * a union of polyhedra, but don't worry, all the useful data are now stored
478 * inside the list (start). We do not use PolyLib's Domain_Disjoint function,
479 * since the number of union components is often higher (thus code size too).
480 * - October 28th 2001: first version.
481 * - November 14th 2001: bug correction (this one was hard to find !).
482 * - July 3rd->11th 2003: memory leaks hunt and correction.
483 * - June 22nd 2005: Adaptation for GMP.
484 * - October 27th 2005: (debug) included blocks were not copied for new loops.
486 void cloog_loop_add_disjoint(start
, now
, loop
)
487 CloogLoop
** start
, ** now
, * loop
;
489 CloogLoop
* sep
, * inner
;
490 CloogDomain
*domain
, *seen
, *temp
, *rest
;
493 if (cloog_domain_isconvex(loop
->domain
))
494 cloog_loop_add(start
,now
,loop
) ;
496 domain
= cloog_domain_simplify_union(loop
->domain
);
497 loop
->domain
= NULL
;
499 /* We separate the first element of the rest of the union. */
500 domain
= cloog_domain_cut_first(domain
, &rest
);
502 /* This first element is the first of the list of disjoint polyhedra. */
503 sep
= cloog_loop_alloc(loop
->state
, domain
, 0, NULL
,
504 loop
->block
, loop
->inner
, NULL
);
505 cloog_loop_add(start
,now
,sep
) ;
507 seen
= cloog_domain_copy(domain
);
508 while (!cloog_domain_isempty(domain
= rest
)) {
509 temp
= cloog_domain_cut_first(domain
, &rest
);
510 domain
= cloog_domain_difference(temp
, seen
);
511 cloog_domain_free(temp
);
513 if (cloog_domain_isempty(domain
)) {
514 cloog_domain_free(domain
);
518 /* Each new loop will have its own life, for instance we can free its
519 * inner loop and included block. Then each one must have its own copy
520 * of both 'inner' and 'block'.
522 inner
= cloog_loop_copy(loop
->inner
) ;
523 block
= cloog_block_copy(loop
->block
) ;
525 sep
= cloog_loop_alloc(loop
->state
, cloog_domain_copy(domain
),
526 0, NULL
, block
, inner
, NULL
);
527 /* domain can be an union too. If so: recursion. */
528 if (cloog_domain_isconvex(domain
))
529 cloog_loop_add(start
,now
,sep
) ;
531 cloog_loop_add_disjoint(start
,now
,sep
) ;
533 if (cloog_domain_isempty(rest
)) {
534 cloog_domain_free(domain
);
538 seen
= cloog_domain_union(seen
, domain
);
540 cloog_domain_free(rest
);
541 cloog_domain_free(seen
);
542 cloog_loop_free_parts(loop
,0,0,0,0) ;
548 * cloog_loop_disjoint function:
549 * This function returns a list of loops such that each loop with non-convex
550 * domain in the input list (loop) is separated into several loops where the
551 * domains are the components of the union of *disjoint* polyhedra equivalent
552 * to the original non-convex domain. See cloog_loop_add_disjoint comments
554 * - September 16th 2005: first version.
556 CloogLoop
* cloog_loop_disjoint(CloogLoop
* loop
)
557 { CloogLoop
*res
=NULL
, * now
=NULL
, * next
;
559 /* Because this is often the case, don't waste time ! */
560 if (loop
&& !loop
->next
&& cloog_domain_isconvex(loop
->domain
))
564 { next
= loop
->next
;
566 cloog_loop_add_disjoint(&res
,&now
,loop
) ;
575 * cloog_loop_restrict function:
576 * This function returns the (loop) in the context of (context): it makes the
577 * intersection between the (loop) domain and the (context), then it returns
578 * a pointer to a new loop, with this intersection as domain.
580 * - October 27th 2001: first version.
581 * - June 15th 2005: a memory leak fixed (domain was not freed when empty).
582 * - June 22nd 2005: Adaptation for GMP.
584 CloogLoop
*cloog_loop_restrict(CloogLoop
*loop
, CloogDomain
*context
)
585 { int new_dimension
;
586 CloogDomain
* domain
, * extended_context
, * new_domain
;
587 CloogLoop
* new_loop
;
589 domain
= loop
->domain
;
590 if (cloog_domain_dimension(domain
) > cloog_domain_dimension(context
))
592 new_dimension
= cloog_domain_dimension(domain
);
593 extended_context
= cloog_domain_extend(context
, new_dimension
);
594 new_domain
= cloog_domain_intersection(extended_context
,loop
->domain
) ;
595 cloog_domain_free(extended_context
) ;
598 new_domain
= cloog_domain_intersection(context
,loop
->domain
) ;
600 if (cloog_domain_isempty(new_domain
))
601 { cloog_domain_free(new_domain
) ;
605 new_loop
= cloog_loop_alloc(loop
->state
, new_domain
,
606 0, NULL
, loop
->block
, loop
->inner
, NULL
);
613 * Call cloog_loop_restrict on each loop in the list "loop" and return
614 * the concatenated result.
616 CloogLoop
*cloog_loop_restrict_all(CloogLoop
*loop
, CloogDomain
*context
)
619 CloogLoop
*res
= NULL
;
620 CloogLoop
**res_next
= &res
;
622 for (; loop
; loop
= next
) {
625 *res_next
= cloog_loop_restrict(loop
, context
);
627 res_next
= &(*res_next
)->next
;
628 cloog_loop_free_parts(loop
, 1, 0, 0, 0);
631 cloog_loop_free(loop
);
638 CloogLoop
*cloog_loop_restrict_inner(CloogLoop
*loop
)
642 for (l
= loop
; l
; l
= l
->next
)
643 l
->inner
= cloog_loop_restrict_all(l
->inner
, l
->domain
);
649 * cloog_loop_project function:
650 * This function returns the projection of (loop) on the (level) first
651 * dimensions (outer loops). It makes the projection of the (loop) domain,
652 * then it returns a pointer to a new loop, with this projection as domain.
654 * - October 27th 2001: first version.
655 * - July 3rd->11th 2003: memory leaks hunt and correction.
656 * - June 22nd 2005: Adaptation for GMP.
658 CloogLoop
* cloog_loop_project(CloogLoop
* loop
, int level
)
660 CloogDomain
* new_domain
;
661 CloogLoop
* new_loop
, * copy
;
663 copy
= cloog_loop_alloc(loop
->state
, loop
->domain
, loop
->otl
, loop
->stride
,
664 loop
->block
, loop
->inner
, NULL
);
666 if (cloog_domain_dimension(loop
->domain
) == level
)
667 new_domain
= cloog_domain_copy(loop
->domain
) ;
669 new_domain
= cloog_domain_project(loop
->domain
, level
);
671 new_loop
= cloog_loop_alloc(loop
->state
, new_domain
, 0, NULL
,
679 * Call cloog_loop_project on each loop in the list "loop" and return
680 * the concatenated result.
682 CloogLoop
*cloog_loop_project_all(CloogLoop
*loop
, int level
)
685 CloogLoop
*res
= NULL
;
686 CloogLoop
**res_next
= &res
;
688 for (; loop
; loop
= next
) {
691 *res_next
= cloog_loop_project(loop
, level
);
692 res_next
= &(*res_next
)->next
;
693 cloog_loop_free_parts(loop
, 0, 0, 0, 0);
701 * cloog_loop_concat function:
702 * This function returns a pointer to the concatenation of the
703 * CloogLoop lists given as input.
704 * - October 28th 2001: first version.
706 CloogLoop
* cloog_loop_concat(CloogLoop
* a
, CloogLoop
* b
)
707 { CloogLoop
* loop
, * temp
;
712 { while (temp
->next
!= NULL
)
724 * cloog_loop_combine:
725 * Combine consecutive loops with identical domains into
726 * a single loop with the concatenation of their inner loops
729 CloogLoop
*cloog_loop_combine(CloogLoop
*loop
)
731 CloogLoop
*first
, *second
;
733 for (first
= loop
; first
; first
= first
->next
) {
734 while (first
->next
) {
735 if (!cloog_domain_lazy_equal(first
->domain
, first
->next
->domain
))
737 second
= first
->next
;
738 first
->inner
= cloog_loop_concat(first
->inner
, second
->inner
);
739 first
->next
= second
->next
;
740 cloog_loop_free_parts(second
, 1, 0, 0, 0);
748 * Remove loops from list that have an empty domain.
750 CloogLoop
*cloog_loop_remove_empty_domain_loops(CloogLoop
*loop
)
752 CloogLoop
*l
, *res
, *next
, **res_next
;
756 for (l
= loop
; l
; l
= next
) {
758 if (cloog_domain_isempty(l
->domain
))
759 cloog_loop_free_parts(l
, 1, 1, 1, 0);
762 res_next
= &(*res_next
)->next
;
770 CloogLoop
*cloog_loop_decompose_inner(CloogLoop
*loop
,
771 int level
, int scalar
, int *scaldims
, int nb_scattdims
);
773 /* For each loop with only one inner loop, replace the domain
774 * of the loop with the projection of the domain of the inner
775 * loop. To increase the number of loops with a single inner
776 * we first decompose the inner loops into strongly connected
779 CloogLoop
*cloog_loop_specialize(CloogLoop
*loop
,
780 int level
, int scalar
, int *scaldims
, int nb_scattdims
)
785 loop
= cloog_loop_decompose_inner(loop
, level
, scalar
,
786 scaldims
, nb_scattdims
);
788 for (l
= loop
; l
; l
= l
->next
) {
791 if (!cloog_domain_isconvex(l
->inner
->domain
))
794 dim
= cloog_domain_dimension(l
->domain
);
795 cloog_domain_free(l
->domain
);
796 l
->domain
= cloog_domain_project(l
->inner
->domain
, dim
);
799 return cloog_loop_remove_empty_domain_loops(loop
);
803 * cloog_loop_separate function:
804 * This function implements the Quillere algorithm for separation of multiple
805 * loops: for a given set of polyhedra (loop), it computes a set of disjoint
806 * polyhedra such that the unions of these sets are equal, and returns this set.
807 * - October 28th 2001: first version.
808 * - November 14th 2001: elimination of some unused blocks.
809 * - August 13th 2002: (debug) in the case of union of polyhedra for one
810 * loop, redundant constraints are fired.
811 * - July 3rd->11th 2003: memory leaks hunt and correction.
812 * - June 22nd 2005: Adaptation for GMP.
813 * - October 16th 2005: Removal of the non-shared constraint elimination when
814 * there is only one loop in the list (seems to work
815 * without now, DomainSimplify may have been improved).
816 * The problem was visible with test/iftest2.cloog.
818 CloogLoop
* cloog_loop_separate(CloogLoop
* loop
)
819 { int lazy_equal
=0, disjoint
= 0;
820 CloogLoop
* new_loop
, * new_inner
, * res
, * now
, * temp
, * Q
,
821 * inner
, * old
/*, * previous, * next*/ ;
822 CloogDomain
*UQ
, *domain
;
827 loop
= cloog_loop_combine(loop
);
829 if (loop
->next
== NULL
)
830 return cloog_loop_disjoint(loop
) ;
832 UQ
= cloog_domain_copy(loop
->domain
) ;
833 domain
= cloog_domain_copy(loop
->domain
) ;
834 res
= cloog_loop_alloc(loop
->state
, domain
, 0, NULL
,
835 loop
->block
, loop
->inner
, NULL
);
838 while((loop
= loop
->next
) != NULL
)
841 /* For all Q, add Q-loop associated with the blocks of Q alone,
842 * and Q inter loop associated with the blocks of Q and loop.
844 for (Q
= res
; Q
; Q
= Q
->next
) {
845 /* Add (Q inter loop). */
846 if ((disjoint
= cloog_domain_lazy_disjoint(Q
->domain
,loop
->domain
)))
849 { if ((lazy_equal
= cloog_domain_lazy_equal(Q
->domain
,loop
->domain
)))
850 domain
= cloog_domain_copy(Q
->domain
) ;
852 domain
= cloog_domain_intersection(Q
->domain
,loop
->domain
) ;
854 if (!cloog_domain_isempty(domain
))
855 { new_inner
= cloog_loop_concat(cloog_loop_copy(Q
->inner
),
856 cloog_loop_copy(loop
->inner
)) ;
857 new_loop
= cloog_loop_alloc(loop
->state
, domain
, 0, NULL
,
858 NULL
, new_inner
, NULL
);
859 cloog_loop_add_disjoint(&temp
,&now
,new_loop
) ;
863 cloog_domain_free(domain
);
867 /* Add (Q - loop). */
869 domain
= cloog_domain_copy(Q
->domain
) ;
872 domain
= cloog_domain_empty(Q
->domain
);
874 domain
= cloog_domain_difference(Q
->domain
,loop
->domain
) ;
877 if (!cloog_domain_isempty(domain
)) {
878 new_loop
= cloog_loop_alloc(loop
->state
, domain
, 0, NULL
,
879 NULL
, Q
->inner
, NULL
);
880 cloog_loop_add_disjoint(&temp
,&now
,new_loop
) ;
883 { cloog_domain_free(domain
) ;
884 /* If Q->inner is no more useful, we can free it. */
887 cloog_loop_free(inner
) ;
891 /* Add loop-UQ associated with the blocks of loop alone.*/
892 if (cloog_domain_lazy_disjoint(loop
->domain
,UQ
))
893 domain
= cloog_domain_copy(loop
->domain
) ;
895 { if (cloog_domain_lazy_equal(loop
->domain
,UQ
))
896 domain
= cloog_domain_empty(UQ
);
898 domain
= cloog_domain_difference(loop
->domain
,UQ
) ;
901 if (!cloog_domain_isempty(domain
)) {
902 new_loop
= cloog_loop_alloc(loop
->state
, domain
, 0, NULL
,
903 NULL
, loop
->inner
, NULL
);
904 cloog_loop_add_disjoint(&temp
,&now
,new_loop
) ;
907 { cloog_domain_free(domain
) ;
908 /* If loop->inner is no more useful, we can free it. */
909 cloog_loop_free(loop
->inner
) ;
914 if (loop
->next
!= NULL
)
915 UQ
= cloog_domain_union(UQ
, cloog_domain_copy(loop
->domain
));
917 cloog_domain_free(UQ
);
919 cloog_loop_free_parts(res
,1,0,0,1) ;
923 cloog_loop_free_parts(old
,1,0,0,1) ;
929 static CloogDomain
*bounding_domain(CloogDomain
*dom
, CloogOptions
*options
)
932 return cloog_domain_simple_convex(dom
);
934 return cloog_domain_convex(dom
);
939 * cloog_loop_merge function:
940 * This function is the 'soft' version of loop_separate if we are looking for
941 * a code much simpler (and less efficicient). This function returns the new
943 * - October 29th 2001: first version.
944 * - July 3rd->11th 2003: memory leaks hunt and correction.
945 * - June 22nd 2005: Adaptation for GMP.
947 CloogLoop
*cloog_loop_merge(CloogLoop
*loop
, int level
, CloogOptions
*options
)
949 CloogLoop
*res
, *new_inner
, *old
;
950 CloogDomain
*new_domain
, *temp
;
955 if (loop
->next
== NULL
)
956 return cloog_loop_disjoint(loop
);
961 new_inner
= loop
->inner
;
963 for (loop
= loop
->next
; loop
; loop
= loop
->next
) {
964 temp
= cloog_domain_union(temp
, loop
->domain
);
966 new_inner
= cloog_loop_concat(new_inner
, loop
->inner
);
969 new_domain
= bounding_domain(temp
, options
);
971 if (level
> 0 && !cloog_domain_is_bounded(new_domain
, level
) &&
972 cloog_domain_is_bounded(temp
, level
)) {
973 CloogDomain
*splitter
, *t2
;
975 cloog_domain_free(new_domain
);
976 splitter
= cloog_domain_bound_splitter(temp
, level
);
979 while (!cloog_domain_isconvex(splitter
)) {
980 CloogDomain
*first
, *rest
;
981 first
= cloog_domain_cut_first(splitter
, &rest
);
983 t2
= cloog_domain_intersection(first
, temp
);
984 cloog_domain_free(first
);
986 new_domain
= bounding_domain(t2
, options
);
987 cloog_domain_free(t2
);
989 if (cloog_domain_isempty(new_domain
)) {
990 cloog_domain_free(new_domain
);
993 res
= cloog_loop_alloc(old
->state
, new_domain
, 0, NULL
,
994 NULL
, cloog_loop_copy(new_inner
), res
);
997 t2
= cloog_domain_intersection(splitter
, temp
);
998 cloog_domain_free(splitter
);
1000 new_domain
= bounding_domain(t2
, options
);
1001 cloog_domain_free(t2
);
1003 if (cloog_domain_isempty(new_domain
)) {
1004 cloog_domain_free(new_domain
);
1005 cloog_loop_free(new_inner
);
1007 res
= cloog_loop_alloc(old
->state
, new_domain
, 0, NULL
,
1008 NULL
, new_inner
, res
);
1010 res
= cloog_loop_alloc(old
->state
, new_domain
, 0, NULL
,
1011 NULL
, new_inner
, NULL
);
1013 cloog_domain_free(temp
);
1015 cloog_loop_free_parts(old
, 0, 0, 0, 1);
1021 static int cloog_loop_count(CloogLoop
*loop
)
1025 for (nb_loops
= 0; loop
; loop
= loop
->next
)
1033 * cloog_loop_sort function:
1034 * Adaptation from LoopGen 0.4 by F. Quillere. This function sorts a list of
1035 * parameterized disjoint polyhedra, in order to not have lexicographic order
1036 * violation (see Quillere paper).
1037 * - September 16th 2005: inclusion of cloog_loop_number (October 29th 2001).
1039 CloogLoop
*cloog_loop_sort(CloogLoop
*loop
, int level
)
1041 CloogLoop
*res
, *now
, **loop_array
;
1043 int i
, nb_loops
=0, * permut
;
1045 /* There is no need to sort the parameter domains. */
1049 /* We will need to know how many loops are in the list. */
1050 nb_loops
= cloog_loop_count(loop
);
1052 /* If there is only one loop, it's the end. */
1056 /* We have to allocate memory for some useful components:
1057 * - loop_array: the loop array,
1058 * - doms: the array of domains to sort,
1059 * - permut: will give us a possible sort (maybe not the only one).
1061 loop_array
= (CloogLoop
**)malloc(nb_loops
*sizeof(CloogLoop
*)) ;
1062 doms
= (CloogDomain
**)malloc(nb_loops
*sizeof(CloogDomain
*));
1063 permut
= (int *)malloc(nb_loops
*sizeof(int)) ;
1065 /* We fill up the loop and domain arrays. */
1066 for (i
=0;i
<nb_loops
;i
++,loop
=loop
->next
)
1067 { loop_array
[i
] = loop
;
1068 doms
[i
] = loop_array
[i
]->domain
;
1071 /* cloog_domain_sort will fill up permut. */
1072 cloog_domain_sort(doms
, nb_loops
, level
, permut
);
1074 /* With permut and loop_array we build the sorted list. */
1076 for (i
=0;i
<nb_loops
;i
++)
1077 { /* To avoid pointer looping... loop_add will rebuild the list. */
1078 loop_array
[permut
[i
]-1]->next
= NULL
;
1079 cloog_loop_add(&res
,&now
,loop_array
[permut
[i
]-1]) ;
1091 * cloog_loop_nest function:
1092 * This function changes the loop list in such a way that we have no more than
1093 * one dimension added by level. It returns an equivalent loop list with
1095 * - October 29th 2001: first version.
1096 * - July 3rd->11th 2003: memory leaks hunt and correction.
1097 * - June 22nd 2005: Adaptation for GMP.
1098 * - November 21th 2005: (debug) now OK when cloog_loop_restrict returns NULL.
1100 CloogLoop
*cloog_loop_nest(CloogLoop
*loop
, CloogDomain
*context
, int level
)
1102 CloogLoop
* p
, * temp
, * res
, * now
, * next
;
1103 CloogDomain
* new_domain
;
1105 loop
= cloog_loop_disjoint(loop
);
1108 /* Each domain is changed by its intersection with the context. */
1109 while (loop
!= NULL
)
1110 { p
= cloog_loop_restrict(loop
, context
);
1114 { cloog_loop_free_parts(loop
,1,0,0,0) ;
1116 temp
= cloog_loop_alloc(p
->state
, p
->domain
, 0, NULL
,
1117 p
->block
, p
->inner
, NULL
);
1119 /* If the intersection dimension is too big, we make projections smaller
1120 * and smaller, and each projection includes the preceding projection
1121 * (thus, in the target list, dimensions are added one by one).
1123 if (cloog_domain_dimension(p
->domain
) >= level
)
1124 for (l
= cloog_domain_dimension(p
->domain
); l
>= level
; l
--) {
1125 new_domain
= cloog_domain_project(p
->domain
, l
);
1126 temp
= cloog_loop_alloc(p
->state
, new_domain
, 0, NULL
,
1130 /* p is no more useful (but its content yes !). */
1131 cloog_loop_free_parts(p
,0,0,0,0) ;
1133 cloog_loop_add(&res
,&now
,temp
) ;
1136 cloog_loop_free_parts(loop
,1,1,1,0) ;
1146 * cloog_loop_stride function:
1147 * This function will find the stride of a loop for the iterator at the column
1148 * number 'level' in the constraint matrix. It will update the lower bound of
1149 * the iterator accordingly. Basically, the function will try to find in the
1150 * inner loops a common condition on this iterator for the inner loop iterators
1151 * to be integral. For instance, let us consider a loop with the iterator i,
1152 * the iteration domain -4<=i<=n, and its two inner loops with the iterator j.
1153 * The first inner loop has the constraint 3j=i, and the second one has the
1154 * constraint 6j=i. Then the common constraint on i for j to be integral is
1155 * i%3=0, the stride for i is 3. Lastly, we have to find the new lower bound
1156 * for i: the first value satisfying the common constraint: -3. At the end, the
1157 * iteration domain for i is -3<=i<=n and the stride for i is 3.
1158 * - loop is the loop including the iteration domain of the considered iterator,
1159 * - level is the column number of the iterator in the matrix of contraints.
1161 * - June 29th 2003: first version (work in progress since June 26th 2003).
1162 * - July 14th 2003: simpler version.
1163 * - June 22nd 2005: Adaptation for GMP (from S. Verdoolaege's 0.12.1 version).
1165 void cloog_loop_stride(CloogLoop
* loop
, int level
)
1166 { int first_search
;
1167 cloog_int_t stride
, ref_offset
, offset
, potential
;
1170 if (!cloog_domain_can_stride(loop
->domain
, level
))
1173 cloog_int_init(stride
);
1174 cloog_int_init(ref_offset
);
1175 cloog_int_init(offset
);
1176 cloog_int_init(potential
);
1178 cloog_int_set_si(ref_offset
, 0);
1179 cloog_int_set_si(offset
, 0);
1181 /* Default stride. */
1182 cloog_int_set_si(stride
, 1);
1184 inner
= loop
->inner
;
1186 while (inner
!= NULL
)
1187 { /* If the minimun stride has not been found yet, find the stride. */
1188 if ((first_search
) || (!cloog_int_is_one(stride
)))
1190 cloog_domain_stride(inner
->domain
, level
, &potential
, &offset
);
1191 if (!cloog_int_is_one(potential
) && (!first_search
))
1192 { /* Offsets must be the same for common stride. */
1193 cloog_int_gcd(stride
, potential
, stride
);
1194 if (!cloog_int_is_zero(stride
)) {
1195 cloog_int_fdiv_r(offset
, offset
, stride
);
1196 cloog_int_fdiv_r(ref_offset
, ref_offset
, stride
);
1198 if (cloog_int_ne(offset
,ref_offset
))
1199 cloog_int_set_si(stride
, 1);
1202 cloog_int_set(stride
, potential
);
1203 cloog_int_set(ref_offset
, offset
);
1209 inner
= inner
->next
;
1212 if (cloog_int_is_zero(stride
))
1213 cloog_int_set_si(stride
, 1);
1215 /* Update the values if necessary. */
1216 if (!cloog_int_is_one(stride
))
1217 { /* Update the stride value. */
1218 if (!cloog_int_is_zero(offset
))
1219 cloog_int_sub(offset
, stride
, offset
);
1220 loop
->stride
= cloog_stride_alloc(stride
, offset
);
1221 loop
->domain
= cloog_domain_stride_lower_bound(loop
->domain
, level
,
1225 cloog_int_clear(stride
);
1226 cloog_int_clear(ref_offset
);
1227 cloog_int_clear(offset
);
1228 cloog_int_clear(potential
);
1232 void cloog_loop_otl(CloogLoop
*loop
, int level
)
1234 if (cloog_domain_is_otl(loop
->domain
, level
))
1240 * cloog_loop_stop function:
1241 * This function implements the 'stop' option : each domain of each loop
1242 * in the list 'loop' is replaced by 'context'. 'context' should be the
1243 * domain of the outer loop. By using this method, there are no more dimensions
1244 * to scan and the simplification step will automaticaly remove the domains
1245 * since they are the same as the corresponding contexts. The effect of this
1246 * function is to stop the code generation at the level this function is called,
1247 * the resulting code do not consider the next dimensions.
1248 * - January 11th 2005: first version.
1250 CloogLoop
* cloog_loop_stop(CloogLoop
* loop
, CloogDomain
* context
)
1254 { cloog_domain_free(loop
->domain
) ;
1255 loop
->domain
= cloog_domain_copy(context
) ;
1256 loop
->next
= cloog_loop_stop(loop
->next
, context
) ;
1263 static int level_is_constant(int level
, int scalar
, int *scaldims
, int nb_scattdims
)
1265 return level
&& (level
+scalar
<= nb_scattdims
) && (scaldims
[level
+scalar
-1]);
1270 * Compare the constant dimensions of loops 'l1' and 'l2' starting at 'scalar'
1271 * and return -1 if the vector of constant dimensions of 'l1' is smaller
1272 * than that of 'l2', 0 if they are the same and +1 if that of 'l1' is
1273 * greater than that of 'l2'.
1274 * This function should be called on the innermost loop (the loop
1275 * containing a block).
1276 * \param l1 Loop to be compared with l2.
1277 * \param l2 Loop to be compared with l1.
1278 * \param level Current non-scalar dimension.
1279 * \param scaldims Boolean array saying whether a dimension is scalar or not.
1280 * \param nb_scattdims Size of the scaldims array.
1281 * \param scalar Current scalar dimension.
1282 * \return -1 if (l1 < l2), 0 if (l1 == l2) and +1 if (l1 > l2)
1284 int cloog_loop_constant_cmp(CloogLoop
*l1
, CloogLoop
*l2
, int level
,
1285 int *scaldims
, int nb_scattdims
, int scalar
)
1287 CloogBlock
*b1
, *b2
;
1290 while (level_is_constant(level
, scalar
, scaldims
, nb_scattdims
)) {
1291 int cmp
= cloog_int_cmp(b1
->scaldims
[scalar
], b2
->scaldims
[scalar
]);
1301 * cloog_loop_scalar_gt function:
1302 * This function returns 1 if loop 'l1' is greater than loop 'l2' for the
1303 * scalar dimension vector that begins at dimension 'scalar', 0 otherwise. What
1304 * we want to know is whether a loop is scheduled before another one or not.
1305 * This function solves the problem when the considered dimension for scheduling
1306 * is a scalar dimension. Since there may be a succession of scalar dimensions,
1307 * this function will reason about the vector of scalar dimension that begins
1308 * at dimension 'level+scalar' and finish to the first non-scalar dimension.
1309 * \param l1 Loop to be compared with l2.
1310 * \param l2 Loop to be compared with l1.
1311 * \param level Current non-scalar dimension.
1312 * \param scaldims Boolean array saying whether a dimension is scalar or not.
1313 * \param nb_scattdims Size of the scaldims array.
1314 * \param scalar Current scalar dimension.
1315 * \return 1 if (l1 > l2), 0 otherwise.
1317 * - September 9th 2005: first version.
1318 * - October 15nd 2007: now "greater than" instead of "greater or equal".
1320 int cloog_loop_scalar_gt(l1
, l2
, level
, scaldims
, nb_scattdims
, scalar
)
1321 CloogLoop
* l1
, * l2
;
1322 int level
, * scaldims
, nb_scattdims
, scalar
;
1324 return cloog_loop_constant_cmp(l1
, l2
, level
, scaldims
, nb_scattdims
, scalar
) > 0;
1329 * cloog_loop_scalar_eq function:
1330 * This function returns 1 if loop 'l1' is equal to loop 'l2' for the scalar
1331 * dimension vector that begins at dimension 'scalar', 0 otherwise. What we want
1332 * to know is whether two loops are scheduled for the same time or not.
1333 * This function solves the problem when the considered dimension for scheduling
1334 * is a scalar dimension. Since there may be a succession of scalar dimensions,
1335 * this function will reason about the vector of scalar dimension that begins
1336 * at dimension 'level+scalar' and finish to the first non-scalar dimension.
1337 * - l1 and l2 are the loops to compare,
1338 * - level is the current non-scalar dimension,
1339 * - scaldims is the boolean array saying whether a dimension is scalar or not,
1340 * - nb_scattdims is the size of the scaldims array,
1341 * - scalar is the current scalar dimension.
1343 * - September 9th 2005 : first version.
1345 int cloog_loop_scalar_eq(l1
, l2
, level
, scaldims
, nb_scattdims
, scalar
)
1346 CloogLoop
* l1
, * l2
;
1347 int level
, * scaldims
, nb_scattdims
, scalar
;
1349 return cloog_loop_constant_cmp(l1
, l2
, level
, scaldims
, nb_scattdims
, scalar
) == 0;
1354 * cloog_loop_scalar_sort function:
1355 * This function sorts a linked list of loops (loop) with respect to the
1356 * scalar dimension vector that begins at dimension 'scalar'. Since there may
1357 * be a succession of scalar dimensions, this function will reason about the
1358 * vector of scalar dimension that begins at dimension 'level+scalar' and
1359 * finish to the first non-scalar dimension.
1360 * \param loop Loop list to sort.
1361 * \param level Current non-scalar dimension.
1362 * \param scaldims Boolean array saying whether a dimension is scalar or not.
1363 * \param nb_scattdims Size of the scaldims array.
1364 * \param scalar Current scalar dimension.
1365 * \return A pointer to the sorted list.
1367 * - July 2nd 2005: first developments.
1368 * - September 2nd 2005: first version.
1369 * - October 15nd 2007: complete rewrite to remove bugs, now a bubble sort.
1371 CloogLoop
* cloog_loop_scalar_sort(loop
, level
, scaldims
, nb_scattdims
, scalar
)
1373 int level
, * scaldims
, nb_scattdims
, scalar
;
1375 CloogLoop
**current
;
1379 for (current
= &loop
; (*current
)->next
; current
= &(*current
)->next
) {
1380 CloogLoop
*next
= (*current
)->next
;
1381 if (cloog_loop_scalar_gt(*current
,next
,level
,scaldims
,nb_scattdims
,scalar
)) {
1383 (*current
)->next
= next
->next
;
1384 next
->next
= *current
;
1395 * cloog_loop_generate_backtrack function:
1396 * adaptation from LoopGen 0.4 by F. Quillere. This function implements the
1397 * backtrack of the Quillere et al. algorithm (see the Quillere paper).
1398 * It eliminates unused iterations of the current level for the new one. See the
1399 * example called linearity-1-1 example with and without this part for an idea.
1400 * - October 26th 2001: first version in cloog_loop_generate_general.
1401 * - July 31th 2002: (debug) no more parasite loops (REALLY hard !).
1402 * - October 30th 2005: extraction from cloog_loop_generate_general.
1404 CloogLoop
*cloog_loop_generate_backtrack(CloogLoop
*loop
,
1405 int level
, CloogOptions
*options
)
1407 CloogDomain
* domain
;
1408 CloogLoop
* now
, * now2
, * next
, * next2
, * end
, * temp
, * l
, * inner
,
1414 while (temp
!= NULL
)
1416 inner
= temp
->inner
;
1418 while (inner
!= NULL
)
1419 { next
= inner
->next
;
1420 /* This 'if' and its first part is the debug of july 31th 2002. */
1421 if (inner
->block
!= NULL
) {
1422 end
= cloog_loop_alloc(temp
->state
, inner
->domain
, 0, NULL
,
1423 inner
->block
, NULL
, NULL
);
1424 domain
= cloog_domain_copy(temp
->domain
) ;
1425 new_loop
= cloog_loop_alloc(temp
->state
, domain
, 0, NULL
,
1429 new_loop
= cloog_loop_project(inner
, level
);
1431 cloog_loop_free_parts(inner
,0,0,0,0) ;
1432 cloog_loop_add(&l
,&now2
,new_loop
) ;
1436 temp
->inner
= NULL
;
1439 { l
= cloog_loop_separate(l
) ;
1440 l
= cloog_loop_sort(l
, level
);
1442 l
->stride
= cloog_stride_copy(l
->stride
);
1443 cloog_loop_add(&loop
,&now
,l
) ;
1447 next2
= temp
->next
;
1448 cloog_loop_free_parts(temp
,1,0,0,0) ;
1457 * Return 1 if we need to continue recursing to the specified level.
1459 int cloog_loop_more(CloogLoop
*loop
, int level
, int scalar
, int nb_scattdims
)
1461 return level
+ scalar
<= nb_scattdims
||
1462 cloog_domain_dimension(loop
->domain
) >= level
;
1465 CloogLoop
*cloog_loop_generate_restricted_or_stop(CloogLoop
*loop
,
1466 CloogDomain
*context
,
1467 int level
, int scalar
, int *scaldims
, int nb_scattdims
,
1468 CloogOptions
*options
);
1471 * cloog_loop_generate_general function:
1472 * Adaptation from LoopGen 0.4 by F. Quillere. This function implements the
1473 * Quillere algorithm for polyhedron scanning from step 3 to 5.
1474 * (see the Quillere paper).
1475 * - loop is the loop for which we have to generate a scanning code,
1476 * - level is the current non-scalar dimension,
1477 * - scalar is the current scalar dimension,
1478 * - scaldims is the boolean array saying whether a dimension is scalar or not,
1479 * - nb_scattdims is the size of the scaldims array,
1480 * - options are the general code generation options.
1482 * - October 26th 2001: first version.
1483 * - July 3rd->11th 2003: memory leaks hunt and correction.
1484 * - June 22nd 2005: Adaptation for GMP.
1485 * - September 2nd 2005: The function have been cutted out in two pieces:
1486 * cloog_loop_generate and this one, in order to handle
1487 * the scalar dimension case more efficiently with
1488 * cloog_loop_generate_scalar.
1489 * - November 15th 2005: (debug) the result of the cloog_loop_generate call may
1490 * be a list of polyhedra (especially if stop option is
1491 * used): cloog_loop_add_list instead of cloog_loop_add.
1493 CloogLoop
*cloog_loop_generate_general(CloogLoop
*loop
,
1494 int level
, int scalar
, int *scaldims
, int nb_scattdims
,
1495 CloogOptions
*options
)
1497 CloogLoop
* res
, * now
, * temp
, * l
, * new_loop
, * inner
, * now2
, * end
,
1499 CloogDomain
* domain
;
1502 /* 3. Separate all projections into disjoint polyhedra. */
1503 if ((options
->f
> level
+scalar
) || (options
->f
< 0))
1504 res
= cloog_loop_merge(loop
, level
, options
);
1506 res
= cloog_loop_separate(loop
);
1510 /* 3b. -correction- sort the loops to determine their textual order. */
1511 res
= cloog_loop_sort(res
, level
);
1513 res
= cloog_loop_restrict_inner(res
);
1516 res
= cloog_loop_specialize(res
, level
, scalar
, scaldims
, nb_scattdims
);
1518 /* 4. Recurse for each loop with the current domain as context. */
1521 if (!level
|| (level
+scalar
< options
->l
) || (options
->l
< 0))
1523 { if (level
&& options
->strides
)
1524 cloog_loop_stride(temp
, level
);
1525 if (level
&& options
->otl
)
1526 cloog_loop_otl(temp
, level
);
1527 inner
= temp
->inner
;
1528 domain
= temp
->domain
;
1530 while (inner
!= NULL
)
1531 { /* 4b. -ced- recurse for each sub-list of non terminal loops. */
1532 if (cloog_loop_more(inner
, level
+ 1, scalar
, nb_scattdims
)) {
1534 while ((end
->next
!= NULL
) &&
1535 cloog_loop_more(end
->next
, level
+ 1, scalar
, nb_scattdims
))
1541 l
= cloog_loop_generate_restricted_or_stop(inner
, domain
,
1542 level
+ 1, scalar
, scaldims
, nb_scattdims
, options
);
1545 cloog_loop_add_list(&into
,&now
,l
) ;
1550 { cloog_loop_add(&into
,&now
,inner
) ;
1551 inner
= inner
->next
;
1556 temp
->inner
= into
;
1557 cloog_loop_add(&res
,&now2
,temp
) ;
1561 while (temp
!= NULL
)
1562 { next
= temp
->next
;
1563 l
= cloog_loop_nest(temp
->inner
, temp
->domain
, level
+1);
1564 new_loop
= cloog_loop_alloc(temp
->state
, temp
->domain
, 0, NULL
,
1566 temp
->inner
= NULL
;
1568 cloog_loop_free_parts(temp
,0,0,0,0) ;
1569 cloog_loop_add(&res
,&now
,new_loop
) ;
1573 /* 5. eliminate unused iterations of the current level for the new one. See
1574 * the example called linearity-1-1 example with and without this part
1577 if (options
->backtrack
&& level
&&
1578 ((level
+scalar
< options
->l
) || (options
->l
< 0)) &&
1579 ((options
->f
<= level
+scalar
) && !(options
->f
< 0)))
1580 res
= cloog_loop_generate_backtrack(res
, level
, options
);
1582 /* Pray for my new paper to be accepted somewhere since the following stuff
1583 * is really amazing :-) !
1584 * Far long later: The paper has been accepted to PACT 2004 :-))). But there
1585 * are still some bugs and I have no time to fix them. Thus now you have to
1586 * pray for me to get an academic position for that really amazing stuff :-) !
1587 * Later again: OK, I get my academic position, but still I have not enough
1588 * time to fix and clean this part... Pray again :-) !!!
1590 /* res = cloog_loop_unisolate(res,level) ;*/
1596 CloogLoop
*cloog_loop_generate_restricted(CloogLoop
*loop
,
1597 int level
, int scalar
, int *scaldims
, int nb_scattdims
,
1598 CloogOptions
*options
);
1602 * cloog_loop_generate_scalar function:
1603 * This function applies the simplified code generation scheme in the trivial
1604 * case of scalar dimensions. When dealing with scalar dimensions, there is
1605 * no need of costly polyhedral operations for separation or sorting: sorting
1606 * is a question of comparing scalar vectors and separation amounts to consider
1607 * only loops with the same scalar vector for the next step of the code
1608 * generation process. This function achieves the separation/sorting process
1609 * for the vector of scalar dimension that begins at dimension 'level+scalar'
1610 * and finish to the first non-scalar dimension.
1611 * - loop is the loop for which we have to generate a scanning code,
1612 * - level is the current non-scalar dimension,
1613 * - scalar is the current scalar dimension,
1614 * - scaldims is the boolean array saying whether a dimension is scalar or not,
1615 * - nb_scattdims is the size of the scaldims array,
1616 * - options are the general code generation options.
1618 * - September 2nd 2005: First version.
1620 CloogLoop
*cloog_loop_generate_scalar(CloogLoop
*loop
,
1621 int level
, int scalar
, int *scaldims
, int nb_scattdims
,
1622 CloogOptions
*options
)
1623 { CloogLoop
* res
, * now
, * temp
, * l
, * end
, * next
, * ref
;
1626 /* We sort the loop list with respect to the current scalar vector. */
1627 res
= cloog_loop_scalar_sort(loop
,level
,scaldims
,nb_scattdims
,scalar
) ;
1629 scalar_new
= scalar
+ scaldims
[level
+ scalar
- 1];
1633 while (temp
!= NULL
)
1634 { /* Then we will appy the general code generation process to each sub-list
1635 * of loops with the same scalar vector.
1640 while((end
->next
!= NULL
) &&
1641 cloog_loop_more(end
->next
, level
, scalar_new
, nb_scattdims
) &&
1642 cloog_loop_scalar_eq(ref
,end
->next
,level
,scaldims
,nb_scattdims
,scalar
))
1648 /* For the next dimension, scalar value is updated by adding the scalar
1649 * vector size, which is stored at scaldims[level+scalar-1].
1651 if (cloog_loop_more(temp
, level
, scalar_new
, nb_scattdims
)) {
1652 l
= cloog_loop_generate_restricted(temp
, level
, scalar_new
,
1653 scaldims
, nb_scattdims
, options
);
1656 cloog_loop_add_list(&res
, &now
, l
);
1658 cloog_loop_add(&res
, &now
, temp
);
1667 /* Compare loop with the next loop based on their constant dimensions.
1668 * The result is < 0, == 0 or > 0 depending on whether the constant
1669 * dimensions of loop are lexicographically smaller, equal or greater
1670 * than those of loop->next.
1671 * If loop is the last in the list, then it is assumed to be smaller
1672 * than the "next" one.
1674 static int cloog_loop_next_scal_cmp(CloogLoop
*loop
)
1682 nb_scaldims
= loop
->block
->nb_scaldims
;
1683 if (loop
->next
->block
->nb_scaldims
< nb_scaldims
)
1684 nb_scaldims
= loop
->next
->block
->nb_scaldims
;
1686 for (i
= 0; i
< nb_scaldims
; ++i
) {
1687 int cmp
= cloog_int_cmp(loop
->block
->scaldims
[i
],
1688 loop
->next
->block
->scaldims
[i
]);
1692 return loop
->block
->nb_scaldims
- loop
->next
->block
->nb_scaldims
;
1696 /* Check whether the globally constant dimensions of a and b
1697 * have the same value for all globally constant dimensions
1698 * that are situated before any (locally) non-constant dimension.
1700 static int cloog_loop_equal_prefix(CloogLoop
*a
, CloogLoop
*b
,
1701 int *scaldims
, int nb_scattdims
)
1707 for (i
= 0; i
< nb_scattdims
; ++i
) {
1712 if (!cloog_int_eq(a
->block
->scaldims
[cst
], b
->block
->scaldims
[cst
]))
1716 for (i
= i
+ 1; i
< nb_scattdims
; ++i
) {
1719 if (!cloog_domain_lazy_isconstant(a
->domain
, dim
))
1721 /* No need to check that dim is also constant in b and that the
1722 * constant values are equal. That will happen during the check
1723 * whether the two domains are equal.
1731 /* Try to block adjacent loops in the loop list "loop".
1732 * We only attempt blocking if the constant dimensions of the loops
1733 * in the least are (not necessarily strictly) increasing.
1734 * Then we look for a sublist such that the first (begin) has constant
1735 * dimensions strictly larger than the previous loop in the complete
1736 * list and such that the loop (end) after the last loop in the sublist
1737 * has constant dimensions strictly larger than the last loop in the sublist.
1738 * Furthermore, all loops in the sublist should have the same domain
1739 * (with globally constant dimensions removed) and the difference
1740 * (if any) in constant dimensions may only occur after all the
1741 * (locally) constant dimensions.
1742 * If we find such a sublist, then the blocks of all but the first
1743 * are merged into the block of the first.
1745 * Note that this function can only be called before the global
1746 * blocklist has been created because it may otherwise modify and destroy
1747 * elements on that list.
1749 CloogLoop
*cloog_loop_block(CloogLoop
*loop
, int *scaldims
, int nb_scattdims
)
1751 CloogLoop
*begin
, *end
, *l
;
1752 int begin_after_previous
;
1753 int end_after_previous
;
1757 for (begin
= loop
; begin
; begin
= begin
->next
) {
1758 if (!begin
->block
|| !begin
->block
->scaldims
)
1760 if (cloog_loop_next_scal_cmp(begin
) > 0)
1764 begin_after_previous
= 1;
1765 for (begin
= loop
; begin
; begin
= begin
->next
) {
1766 if (!begin_after_previous
) {
1767 begin_after_previous
= cloog_loop_next_scal_cmp(begin
) < 0;
1771 end_after_previous
= cloog_loop_next_scal_cmp(begin
) < 0;
1772 for (end
= begin
->next
; end
; end
= end
->next
) {
1773 if (!cloog_loop_equal_prefix(begin
, end
, scaldims
, nb_scattdims
))
1775 if (!cloog_domain_lazy_equal(begin
->domain
, end
->domain
))
1777 end_after_previous
= cloog_loop_next_scal_cmp(end
) < 0;
1779 if (end
!= begin
->next
&& end_after_previous
) {
1780 for (l
= begin
->next
; l
!= end
; l
= begin
->next
) {
1781 cloog_block_merge(begin
->block
, l
->block
);
1782 begin
->next
= l
->next
;
1783 cloog_loop_free_parts(l
, 1, 0, 1, 0);
1787 begin_after_previous
= cloog_loop_next_scal_cmp(begin
) < 0;
1795 * Check whether for any fixed iteration of the outer loops,
1796 * there is an iteration of loop1 that is lexicographically greater
1797 * than an iteration of loop2.
1798 * Return 1 if there exists (or may exist) such a pair.
1799 * Return 0 if all iterations of loop1 are lexicographically smaller
1800 * than the iterations of loop2.
1801 * If no iteration is lexicographically greater, but if there are
1802 * iterations that are equal to iterations of loop2, then return "def".
1803 * This is useful for ensuring that such statements are not reordered.
1804 * Some users, including the test_run target in test, expect
1805 * the statements at a given point to be run in the original order.
1806 * Passing the value "0" for "def" would allow such statements to be reordered
1807 * and would allow for the detection of more components.
1809 int cloog_loop_follows(CloogLoop
*loop1
, CloogLoop
*loop2
,
1810 int level
, int scalar
, int *scaldims
, int nb_scattdims
, int def
)
1814 dim1
= cloog_domain_dimension(loop1
->domain
);
1815 dim2
= cloog_domain_dimension(loop2
->domain
);
1816 while ((level
<= dim1
&& level
<= dim2
) ||
1817 level_is_constant(level
, scalar
, scaldims
, nb_scattdims
)) {
1818 if (level_is_constant(level
, scalar
, scaldims
, nb_scattdims
)) {
1819 int cmp
= cloog_loop_constant_cmp(loop1
, loop2
, level
, scaldims
,
1820 nb_scattdims
, scalar
);
1825 scalar
+= scaldims
[level
+ scalar
- 1];
1827 int follows
= cloog_domain_follows(loop1
->domain
, loop2
->domain
,
1841 /* Structure for representing the nodes in the graph being traversed
1842 * using Tarjan's algorithm.
1843 * index represents the order in which nodes are visited.
1844 * min_index is the index of the root of a (sub)component.
1845 * on_stack indicates whether the node is currently on the stack.
1847 struct cloog_loop_sort_node
{
1852 /* Structure for representing the graph being traversed
1853 * using Tarjan's algorithm.
1854 * len is the number of nodes
1855 * node is an array of nodes
1856 * stack contains the nodes on the path from the root to the current node
1857 * sp is the stack pointer
1858 * index is the index of the last node visited
1859 * order contains the elements of the components separated by -1
1860 * op represents the current position in order
1862 struct cloog_loop_sort
{
1864 struct cloog_loop_sort_node
*node
;
1872 /* Allocate and initialize cloog_loop_sort structure.
1874 static struct cloog_loop_sort
*cloog_loop_sort_alloc(int len
)
1876 struct cloog_loop_sort
*s
;
1879 s
= (struct cloog_loop_sort
*)malloc(sizeof(struct cloog_loop_sort
));
1882 s
->node
= (struct cloog_loop_sort_node
*)
1883 malloc(len
* sizeof(struct cloog_loop_sort_node
));
1885 for (i
= 0; i
< len
; ++i
)
1886 s
->node
[i
].index
= -1;
1887 s
->stack
= (int *)malloc(len
* sizeof(int));
1889 s
->order
= (int *)malloc(2 * len
* sizeof(int));
1899 /* Free cloog_loop_sort structure.
1901 static void cloog_loop_sort_free(struct cloog_loop_sort
*s
)
1910 /* Check whether for any fixed iteration of the outer loops,
1911 * there is an iteration of loop1 that is lexicographically greater
1912 * than an iteration of loop2, where the iteration domains are
1913 * available in the inner loops of the arguments.
1915 * By using this functions to detect components, we ensure that
1916 * two CloogLoops appear in the same component if some iterations of
1917 * each loop should be executed before some iterations of the other loop.
1918 * Since we also want two CloogLoops that have exactly the same
1919 * iteration domain at the current level to be placed in the same component,
1920 * we first check if these domains are indeed the same.
1922 static int inner_loop_follows(CloogLoop
*loop1
, CloogLoop
*loop2
,
1923 int level
, int scalar
, int *scaldims
, int nb_scattdims
, int def
)
1927 f
= cloog_domain_lazy_equal(loop1
->domain
, loop2
->domain
);
1929 f
= cloog_loop_follows(loop1
->inner
, loop2
->inner
,
1930 level
, scalar
, scaldims
, nb_scattdims
, def
);
1936 /* Perform Tarjan's algorithm for computing the strongly connected components
1937 * in the graph with the individual CloogLoops as vertices.
1938 * Two CloopLoops appear in the same component if they both (indirectly)
1939 * "follow" each other, where the following relation is determined
1940 * by the follows function.
1942 static void cloog_loop_components_tarjan(struct cloog_loop_sort
*s
,
1943 CloogLoop
**loop_array
, int i
, int level
, int scalar
, int *scaldims
,
1945 int (*follows
)(CloogLoop
*loop1
, CloogLoop
*loop2
,
1946 int level
, int scalar
, int *scaldims
, int nb_scattdims
, int def
))
1950 s
->node
[i
].index
= s
->index
;
1951 s
->node
[i
].min_index
= s
->index
;
1952 s
->node
[i
].on_stack
= 1;
1954 s
->stack
[s
->sp
++] = i
;
1956 for (j
= s
->len
- 1; j
>= 0; --j
) {
1961 if (s
->node
[j
].index
>= 0 &&
1962 (!s
->node
[j
].on_stack
||
1963 s
->node
[j
].index
> s
->node
[i
].min_index
))
1966 f
= follows(loop_array
[i
], loop_array
[j
],
1967 level
, scalar
, scaldims
, nb_scattdims
, i
> j
);
1971 if (s
->node
[j
].index
< 0) {
1972 cloog_loop_components_tarjan(s
, loop_array
, j
, level
, scalar
,
1973 scaldims
, nb_scattdims
, follows
);
1974 if (s
->node
[j
].min_index
< s
->node
[i
].min_index
)
1975 s
->node
[i
].min_index
= s
->node
[j
].min_index
;
1976 } else if (s
->node
[j
].index
< s
->node
[i
].min_index
)
1977 s
->node
[i
].min_index
= s
->node
[j
].index
;
1980 if (s
->node
[i
].index
!= s
->node
[i
].min_index
)
1984 j
= s
->stack
[--s
->sp
];
1985 s
->node
[j
].on_stack
= 0;
1986 s
->order
[s
->op
++] = j
;
1988 s
->order
[s
->op
++] = -1;
1992 static int qsort_index_cmp(const void *p1
, const void *p2
)
1994 return *(int *)p1
- *(int *)p2
;
1997 /* Sort the elements of the component starting at list.
1998 * The list is terminated by a -1.
2000 static void sort_component(int *list
)
2004 for (len
= 0; list
[len
] != -1; ++len
)
2007 qsort(list
, len
, sizeof(int), qsort_index_cmp
);
2010 /* Given an array of indices "list" into the "loop_array" array,
2011 * terminated by -1, construct a linked list of the corresponding
2012 * entries and put the result in *res.
2013 * The value returned is the number of CloogLoops in the (linked) list
2015 static int extract_component(CloogLoop
**loop_array
, int *list
, CloogLoop
**res
)
2019 sort_component(list
);
2020 while (list
[i
] != -1) {
2021 *res
= loop_array
[list
[i
]];
2022 res
= &(*res
)->next
;
2032 * Call cloog_loop_generate_scalar or cloog_loop_generate_general
2033 * on each of the strongly connected components in the list of CloogLoops
2034 * pointed to by "loop".
2036 * We use Tarjan's algorithm to find the strongly connected components.
2037 * Note that this algorithm also topologically sorts the components.
2039 * The components are treated separately to avoid spurious separations.
2040 * The concatentation of the results may contain successive loops
2041 * with the same bounds, so we try to combine such loops.
2043 CloogLoop
*cloog_loop_generate_components(CloogLoop
*loop
,
2044 int level
, int scalar
, int *scaldims
, int nb_scattdims
,
2045 CloogOptions
*options
)
2049 CloogLoop
*res
, **res_next
;
2050 CloogLoop
**loop_array
;
2051 struct cloog_loop_sort
*s
;
2053 if (level
== 0 || !loop
->next
)
2054 return cloog_loop_generate_general(loop
, level
, scalar
,
2055 scaldims
, nb_scattdims
, options
);
2057 nb_loops
= cloog_loop_count(loop
);
2059 loop_array
= (CloogLoop
**)malloc(nb_loops
* sizeof(CloogLoop
*));
2062 for (i
= 0, tmp
= loop
; i
< nb_loops
; i
++, tmp
= tmp
->next
)
2063 loop_array
[i
] = tmp
;
2065 s
= cloog_loop_sort_alloc(nb_loops
);
2066 for (i
= nb_loops
- 1; i
>= 0; --i
) {
2067 if (s
->node
[i
].index
>= 0)
2069 cloog_loop_components_tarjan(s
, loop_array
, i
, level
, scalar
, scaldims
,
2070 nb_scattdims
, &inner_loop_follows
);
2077 int n
= extract_component(loop_array
, &s
->order
[i
], &tmp
);
2080 *res_next
= cloog_loop_generate_general(tmp
, level
, scalar
,
2081 scaldims
, nb_scattdims
, options
);
2083 res_next
= &(*res_next
)->next
;
2086 cloog_loop_sort_free(s
);
2090 res
= cloog_loop_combine(res
);
2096 /* For each loop in the list "loop", decompose the list of
2097 * inner loops into strongly connected components and put
2098 * the components into separate loops at the top level.
2100 CloogLoop
*cloog_loop_decompose_inner(CloogLoop
*loop
,
2101 int level
, int scalar
, int *scaldims
, int nb_scattdims
)
2104 CloogLoop
**loop_array
;
2105 int i
, n_loops
, max_loops
= 0;
2106 struct cloog_loop_sort
*s
;
2108 for (l
= loop
; l
; l
= l
->next
) {
2109 n_loops
= cloog_loop_count(l
->inner
);
2110 if (max_loops
< n_loops
)
2111 max_loops
= n_loops
;
2117 loop_array
= (CloogLoop
**)malloc(max_loops
* sizeof(CloogLoop
*));
2120 for (l
= loop
; l
; l
= l
->next
) {
2123 for (i
= 0, tmp
= l
->inner
; tmp
; i
++, tmp
= tmp
->next
)
2124 loop_array
[i
] = tmp
;
2129 s
= cloog_loop_sort_alloc(n_loops
);
2130 for (i
= n_loops
- 1; i
>= 0; --i
) {
2131 if (s
->node
[i
].index
>= 0)
2133 cloog_loop_components_tarjan(s
, loop_array
, i
, level
, scalar
,
2134 scaldims
, nb_scattdims
, &cloog_loop_follows
);
2137 n
= extract_component(loop_array
, s
->order
, &l
->inner
);
2143 n
= extract_component(loop_array
, &s
->order
[i
], &inner
);
2146 tmp
= cloog_loop_alloc(l
->state
, cloog_domain_copy(l
->domain
),
2147 l
->otl
, l
->stride
, l
->block
, inner
, l
->next
);
2152 cloog_loop_sort_free(s
);
2161 CloogLoop
*cloog_loop_generate_restricted(CloogLoop
*loop
,
2162 int level
, int scalar
, int *scaldims
, int nb_scattdims
,
2163 CloogOptions
*options
)
2165 /* To save both time and memory, we switch here depending on whether the
2166 * current dimension is scalar (simplified processing) or not (general
2169 if (level_is_constant(level
, scalar
, scaldims
, nb_scattdims
))
2170 return cloog_loop_generate_scalar(loop
, level
, scalar
,
2171 scaldims
, nb_scattdims
, options
);
2173 * 2. Compute the projection of each polyhedron onto the outermost
2174 * loop variable and the parameters.
2176 loop
= cloog_loop_project_all(loop
, level
);
2178 return cloog_loop_generate_components(loop
, level
, scalar
, scaldims
,
2179 nb_scattdims
, options
);
2183 CloogLoop
*cloog_loop_generate_restricted_or_stop(CloogLoop
*loop
,
2184 CloogDomain
*context
,
2185 int level
, int scalar
, int *scaldims
, int nb_scattdims
,
2186 CloogOptions
*options
)
2188 /* If the user asked to stop code generation at this level, let's stop. */
2189 if ((options
->stop
>= 0) && (level
+scalar
>= options
->stop
+1))
2190 return cloog_loop_stop(loop
,context
) ;
2192 return cloog_loop_generate_restricted(loop
, level
, scalar
, scaldims
,
2193 nb_scattdims
, options
);
2198 * cloog_loop_generate function:
2199 * Adaptation from LoopGen 0.4 by F. Quillere. This function implements the
2200 * Quillere algorithm for polyhedron scanning from step 1 to 2.
2201 * (see the Quillere paper).
2202 * - loop is the loop for which we have to generate a scanning code,
2203 * - context is the context of the current loop (constraints on parameter and/or
2204 * on outer loop counters),
2205 * - level is the current non-scalar dimension,
2206 * - scalar is the current scalar dimension,
2207 * - scaldims is the boolean array saying whether a dimension is scalar or not,
2208 * - nb_scattdims is the size of the scaldims array,
2209 * - options are the general code generation options.
2211 * - October 26th 2001: first version.
2212 * - July 3rd->11th 2003: memory leaks hunt and correction.
2213 * - June 15th 2005: a memory leak fixed (loop was not entirely freed when
2214 * the result of cloog_loop_restrict was NULL).
2215 * - June 22nd 2005: Adaptation for GMP.
2216 * - September 2nd 2005: The function have been cutted out in two pieces:
2217 * cloog_loop_generate and this one, in order to handle
2218 * the scalar dimension case more efficiently with
2219 * cloog_loop_generate_scalar.
2220 * - November 15th 2005: (debug) Condition for stop option no more take care of
2221 * further scalar dimensions.
2223 CloogLoop
*cloog_loop_generate(CloogLoop
*loop
, CloogDomain
*context
,
2224 int level
, int scalar
, int *scaldims
, int nb_scattdims
,
2225 CloogOptions
*options
)
2227 /* 1. Replace each polyhedron by its intersection with the context.
2229 loop
= cloog_loop_restrict_all(loop
, context
);
2233 return cloog_loop_generate_restricted_or_stop(loop
, context
,
2234 level
, scalar
, scaldims
, nb_scattdims
, options
);
2239 * Internal function for simplifying a single loop in a list of loops.
2240 * See cloog_loop_simplify.
2242 static CloogLoop
*loop_simplify(CloogLoop
*loop
, CloogDomain
*context
,
2246 CloogBlock
* new_block
;
2247 CloogLoop
*simplified
, *inner
;
2248 CloogDomain
* domain
, * simp
, * inter
, * extended_context
;
2250 if (!cloog_domain_isconvex(loop
->domain
))
2251 loop
->domain
= cloog_domain_simplify_union(loop
->domain
);
2253 domain
= loop
->domain
;
2255 domain_dim
= cloog_domain_dimension(domain
);
2256 extended_context
= cloog_domain_extend(context
, domain_dim
);
2257 inter
= cloog_domain_intersection(domain
,extended_context
) ;
2258 simp
= cloog_domain_simplify(inter
,extended_context
) ;
2259 cloog_domain_free(extended_context
) ;
2261 /* If the constraint system is never true, go to the next one. */
2262 if (cloog_domain_never_integral(simp
)) {
2263 cloog_loop_free(loop
->inner
);
2264 cloog_domain_free(inter
);
2265 cloog_domain_free(simp
);
2269 inner
= cloog_loop_simplify(loop
->inner
, inter
, level
+1);
2270 cloog_domain_free(inter
) ;
2272 if ((inner
== NULL
) && (loop
->block
== NULL
)) {
2273 cloog_domain_free(simp
);
2277 new_block
= cloog_block_copy(loop
->block
) ;
2279 simplified
= cloog_loop_alloc(loop
->state
, simp
, loop
->otl
, loop
->stride
,
2280 new_block
, inner
, NULL
);
2282 return(simplified
) ;
2287 * cloog_loop_simplify function:
2288 * This function implements the part 6. of the Quillere algorithm, it
2289 * recursively simplifies each loop in the context of the preceding loop domain.
2290 * It returns a pointer to the simplified loop list.
2291 * The cloog_domain_simplify (DomainSimplify) behaviour is really bad with
2292 * polyhedra union and some really awful sidesteppings were written, I plan
2294 * - October 31th 2001: first version.
2295 * - July 3rd->11th 2003: memory leaks hunt and correction.
2296 * - April 16th 2005: a memory leak fixed (extended_context was not freed).
2297 * - June 15th 2005: a memory leak fixed (loop was not conveniently freed
2298 * when the constraint system is never true).
2299 * - October 27th 2005: - this function called before cloog_loop_fast_simplify
2300 * is now the official cloog_loop_simplify function in
2301 * replacement of a slower and more complex one (after
2302 * deep changes in the pretty printer).
2303 * - we use cloog_loop_disjoint to fix the problem when
2304 * simplifying gives a union of polyhedra (before, it
2305 * was under the responsibility of the pretty printer).
2307 CloogLoop
*cloog_loop_simplify(CloogLoop
*loop
, CloogDomain
*context
, int level
)
2310 CloogLoop
*res
= NULL
;
2311 CloogLoop
**next
= &res
;
2313 for (now
= loop
; now
; now
= now
->next
) {
2314 *next
= loop_simplify(now
, context
, level
);
2316 now
->inner
= NULL
; /* For loop integrity. */
2317 cloog_domain_free(now
->domain
);
2321 next
= &(*next
)->next
;
2323 cloog_loop_free(loop
);
2325 /* Examples like test/iftest2.cloog give unions of polyhedra after
2326 * simplifying, thus we we have to disjoint them. Another good reason to
2327 * put the simplifying step in the Quillere backtrack.
2329 res
= cloog_loop_disjoint(res
);
2336 * cloog_loop_scatter function:
2337 * This function add the scattering (scheduling) informations in a loop.
2339 void cloog_loop_scatter(CloogLoop
* loop
, CloogScattering
*scatt
)
2341 loop
->domain
= cloog_domain_scatter(loop
->domain
, scatt
);