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") ;
128 fprintf(file
, "Stride: ") ;
129 cloog_int_print(file
, loop
->stride
);
130 fprintf(file
, "\n") ;
131 fprintf(file
, "Offset: ") ;
132 cloog_int_print(file
, loop
->offset
);
133 fprintf(file
, "\n") ;
136 for(j
=0; j
<=level
+1; j
++)
137 fprintf(file
,"|\t") ;
140 /* Print the block. */
141 cloog_block_print_structure(file
,loop
->block
,level
+1) ;
144 for (i
=0; i
<=level
+1; i
++)
145 fprintf(file
,"|\t") ;
148 /* Print inner if any. */
150 cloog_loop_print_structure(file
,loop
->inner
,level
+1) ;
152 /* And let's go for the next one. */
155 /* One more time something that is here only for a better look. */
157 { /* Two blank lines if this is the end of the linked list. */
159 { for (i
=0; i
<=level
; i
++)
160 fprintf(file
,"|\t") ;
166 { /* A special blank line if the is a next loop. */
167 for (i
=0; i
<=level
; i
++)
168 fprintf(file
,"|\t") ;
169 fprintf(file
,"V\n") ;
176 * cloog_loop_print function:
177 * This function prints the content of a CloogLoop structure (start) into a
178 * file (file, possibly stdout).
179 * - June 2nd 2005: Now this very old function (probably as old as CLooG) is
180 * only a frontend to cloog_loop_print_structure, with a quite
181 * better human-readable representation.
183 void cloog_loop_print(FILE * file
, CloogLoop
* loop
)
184 { cloog_loop_print_structure(file
,loop
,0) ;
188 /******************************************************************************
189 * Memory deallocation function *
190 ******************************************************************************/
194 * cloog_loop_free function:
195 * This function frees the allocated memory for a CloogLoop structure (loop),
196 * and frees its inner loops and its next loops.
197 * - June 22nd 2005: Adaptation for GMP.
199 void cloog_loop_free(CloogLoop
* loop
)
202 while (loop
!= NULL
) {
203 cloog_loop_leak_down(loop
->state
);
206 cloog_domain_free(loop
->domain
) ;
207 cloog_block_free(loop
->block
) ;
208 if (loop
->inner
!= NULL
)
209 cloog_loop_free(loop
->inner
) ;
211 cloog_int_clear(loop
->stride
);
212 cloog_int_clear(loop
->offset
);
220 * cloog_loop_free_parts function:
221 * This function frees the allocated memory for some parts of a CloogLoop
222 * structure (loop), each other argument is a boolean having to be set to 1 if
223 * we want to free the corresponding part, 0 otherwise. This function applies
224 * the same freeing policy to its inner ans next loops recursively.
225 * - July 3rd 2003: first version.
226 * - June 22nd 2005: Adaptation for GMP.
228 void cloog_loop_free_parts(loop
, domain
, block
, inner
, next
)
230 int domain
, block
, inner
, next
;
231 { CloogLoop
* follow
;
233 while (loop
!= NULL
) {
234 cloog_loop_leak_down(loop
->state
);
235 follow
= loop
->next
;
238 cloog_domain_free(loop
->domain
) ;
241 cloog_block_free(loop
->block
) ;
243 if ((inner
) && (loop
->inner
!= NULL
))
244 cloog_loop_free_parts(loop
->inner
,domain
,block
,inner
,1) ;
246 cloog_int_clear(loop
->stride
);
247 cloog_int_clear(loop
->offset
);
257 /******************************************************************************
258 * Reading functions *
259 ******************************************************************************/
263 * cloog_loop_read function:
264 * This function reads loop data into a file (foo, possibly stdin) and
265 * returns a pointer to a CloogLoop structure containing the read information.
266 * This function can be used only for input file reading, when one loop is
267 * associated with one statement.
268 * - number is the statement block number carried by the loop (-1 if none).
269 * - nb_parameters is the number of parameters.
271 * - September 9th 2002: first version.
272 * - April 16th 2005: adaptation to new CloogStatement struct (with number).
273 * - June 11th 2005: adaptation to new CloogBlock structure.
274 * - June 22nd 2005: Adaptation for GMP.
276 CloogLoop
*cloog_loop_read(CloogState
*state
,
277 FILE * foo
, int number
, int nb_parameters
)
278 { int nb_iterators
, op1
, op2
, op3
;
281 CloogStatement
* statement
;
283 cloog_loop_leak_up(state
);
285 /* Memory allocation and information reading for the first domain: */
286 loop
= (CloogLoop
*)malloc(sizeof(CloogLoop
)) ;
288 cloog_die("memory overflow.\n");
291 loop
->domain
= cloog_domain_union_read(state
, foo
, nb_parameters
);
292 if (loop
->domain
!= NULL
)
293 nb_iterators
= cloog_domain_dimension(loop
->domain
);
296 /* stride is initialized to 1. */
297 cloog_int_init(loop
->stride
);
298 cloog_int_set_si(loop
->stride
, 1);
299 cloog_int_init(loop
->offset
);
300 cloog_int_set_si(loop
->offset
, 0);
301 /* included statement block. */
302 statement
= cloog_statement_alloc(state
, number
+ 1);
303 loop
->block
= cloog_block_alloc(statement
, 0, NULL
, nb_iterators
);
305 /* inner is NULL at beginning. */
310 /* To read that stupid "0 0 0" line. */
311 while (fgets(s
,MAX_STRING
,foo
) == 0) ;
312 while ((*s
=='#' || *s
=='\n') || (sscanf(s
," %d %d %d",&op1
,&op2
,&op3
)<3))
313 fgets(s
,MAX_STRING
,foo
) ;
319 /******************************************************************************
320 * Processing functions *
321 ******************************************************************************/
325 * cloog_loop_malloc function:
326 * This function allocates the memory space for a CloogLoop structure and
327 * sets its fields with default values. Then it returns a pointer to the
329 * - November 21th 2005: first version.
331 CloogLoop
*cloog_loop_malloc(CloogState
*state
)
334 /* Memory allocation for the CloogLoop structure. */
335 loop
= (CloogLoop
*)malloc(sizeof(CloogLoop
)) ;
337 cloog_die("memory overflow.\n");
338 cloog_loop_leak_up(state
);
341 /* We set the various fields with default values. */
343 loop
->domain
= NULL
;
348 cloog_int_init(loop
->stride
);
349 cloog_int_set_si(loop
->stride
, 1);
350 cloog_int_init(loop
->offset
);
351 cloog_int_set_si(loop
->offset
, 0);
358 * cloog_loop_alloc function:
359 * This function allocates the memory space for a CloogLoop structure and
360 * sets its fields with those given as input. Then it returns a pointer to the
362 * - October 27th 2001: first version.
363 * - June 22nd 2005: Adaptation for GMP.
364 * - November 21th 2005: use of cloog_loop_malloc.
366 CloogLoop
*cloog_loop_alloc(CloogState
*state
,
367 CloogDomain
*domain
, cloog_int_t stride
, cloog_int_t offset
,
368 CloogBlock
*block
, CloogLoop
*inner
, CloogLoop
*next
)
371 loop
= cloog_loop_malloc(state
);
373 loop
->domain
= domain
;
374 loop
->block
= block
;
375 loop
->inner
= inner
;
377 cloog_int_set(loop
->stride
, stride
);
378 cloog_int_set(loop
->offset
, offset
);
385 * cloog_loop_add function:
386 * This function adds a CloogLoop structure (loop) at a given place (now) of a
387 * NULL terminated list of CloogLoop structures. The beginning of this list
388 * is (start). This function updates (now) to (loop), and updates (start) if the
389 * added element is the first one -that is when (start) is NULL-.
390 * - October 28th 2001: first version.
392 void cloog_loop_add(CloogLoop
** start
, CloogLoop
** now
, CloogLoop
* loop
)
393 { if (*start
== NULL
)
398 { (*now
)->next
= loop
;
399 *now
= (*now
)->next
;
405 * cloog_loop_add function:
406 * This function adds a CloogLoop structure (loop) at a given place (now) of a
407 * NULL terminated list of CloogLoop structures. The beginning of this list
408 * is (start). This function updates (now) to the end of the loop list (loop),
409 * and updates (start) if the added element is the first one -that is when
411 * - September 9th 2005: first version.
413 void cloog_loop_add_list(CloogLoop
** start
, CloogLoop
** now
, CloogLoop
* loop
)
414 { if (*start
== NULL
)
419 { (*now
)->next
= loop
;
420 *now
= (*now
)->next
;
423 while ((*now
)->next
!= NULL
)
424 *now
= (*now
)->next
;
429 * cloog_loop_copy function:
430 * This function returns a copy of the CloogLoop structure given as input. In
431 * fact, there is just new allocations for the CloogLoop structures, but their
432 * contents are the same.
433 * - October 28th 2001: first version.
434 * - July 3rd->11th 2003: memory leaks hunt and correction.
436 CloogLoop
* cloog_loop_copy(CloogLoop
* source
)
439 CloogDomain
* domain
;
443 { domain
= cloog_domain_copy(source
->domain
) ;
444 block
= cloog_block_copy(source
->block
) ;
445 loop
= cloog_loop_alloc(source
->state
, domain
, source
->stride
,
446 source
->offset
, block
, NULL
, NULL
);
447 loop
->usr
= source
->usr
;
448 loop
->inner
= cloog_loop_copy(source
->inner
) ;
449 loop
->next
= cloog_loop_copy(source
->next
) ;
456 * cloog_loop_add_disjoint function:
457 * This function adds some CloogLoop structures at a given place (now) of a
458 * NULL terminated list of CloogLoop structures. The beginning of this list
459 * is (start). (loop) can be an union of polyhedra, this function separates the
460 * union into a list of *disjoint* polyhedra then adds the list. This function
461 * updates (now) to the end of the list and updates (start) if first added
462 * element is the first of the principal list -that is when (start) is NULL-.
463 * (loop) can be freed by this function, basically when its domain is actually
464 * a union of polyhedra, but don't worry, all the useful data are now stored
465 * inside the list (start). We do not use PolyLib's Domain_Disjoint function,
466 * since the number of union components is often higher (thus code size too).
467 * - October 28th 2001: first version.
468 * - November 14th 2001: bug correction (this one was hard to find !).
469 * - July 3rd->11th 2003: memory leaks hunt and correction.
470 * - June 22nd 2005: Adaptation for GMP.
471 * - October 27th 2005: (debug) included blocks were not copied for new loops.
473 void cloog_loop_add_disjoint(start
, now
, loop
)
474 CloogLoop
** start
, ** now
, * loop
;
476 CloogLoop
* sep
, * inner
;
477 CloogDomain
*domain
, *seen
, *seen_before
, *temp
, *rest
;
480 if (cloog_domain_isconvex(loop
->domain
))
481 cloog_loop_add(start
,now
,loop
) ;
483 domain
= cloog_domain_simplify_union(loop
->domain
);
484 loop
->domain
= NULL
;
486 /* We separate the first element of the rest of the union. */
487 domain
= cloog_domain_cut_first(domain
, &rest
);
489 /* This first element is the first of the list of disjoint polyhedra. */
490 sep
= cloog_loop_alloc(loop
->state
, domain
, loop
->state
->one
,
491 loop
->state
->zero
, loop
->block
, loop
->inner
, NULL
);
492 cloog_loop_add(start
,now
,sep
) ;
494 seen
= cloog_domain_copy(domain
);
495 while (!cloog_domain_isempty(domain
= rest
)) {
496 temp
= cloog_domain_cut_first(domain
, &rest
);
497 domain
= cloog_domain_difference(temp
, seen
);
498 cloog_domain_free(temp
);
500 if (cloog_domain_isempty(domain
)) {
501 cloog_domain_free(domain
);
505 /* Each new loop will have its own life, for instance we can free its
506 * inner loop and included block. Then each one must have its own copy
507 * of both 'inner' and 'block'.
509 inner
= cloog_loop_copy(loop
->inner
) ;
510 block
= cloog_block_copy(loop
->block
) ;
512 sep
= cloog_loop_alloc(loop
->state
, cloog_domain_copy(domain
),
513 loop
->state
->one
, loop
->state
->zero
,
515 /* domain can be an union too. If so: recursion. */
516 if (cloog_domain_isconvex(domain
))
517 cloog_loop_add(start
,now
,sep
) ;
519 cloog_loop_add_disjoint(start
,now
,sep
) ;
521 if (cloog_domain_isempty(rest
)) {
522 cloog_domain_free(domain
);
527 seen
= cloog_domain_union(seen_before
, domain
);
528 cloog_domain_free(domain
);
529 cloog_domain_free(seen_before
);
531 cloog_domain_free(rest
);
532 cloog_domain_free(seen
);
533 cloog_loop_free_parts(loop
,0,0,0,0) ;
539 * cloog_loop_disjoint function:
540 * This function returns a list of loops such that each loop with non-convex
541 * domain in the input list (loop) is separated into several loops where the
542 * domains are the components of the union of *disjoint* polyhedra equivalent
543 * to the original non-convex domain. See cloog_loop_add_disjoint comments
545 * - September 16th 2005: first version.
547 CloogLoop
* cloog_loop_disjoint(CloogLoop
* loop
)
548 { CloogLoop
*res
=NULL
, * now
=NULL
, * next
;
550 /* Because this is often the case, don't waste time ! */
551 if (loop
&& !loop
->next
&& cloog_domain_isconvex(loop
->domain
))
555 { next
= loop
->next
;
557 cloog_loop_add_disjoint(&res
,&now
,loop
) ;
566 * cloog_loop_restrict function:
567 * This function returns the (loop) in the context of (context): it makes the
568 * intersection between the (loop) domain and the (context), then it returns
569 * a pointer to a new loop, with this intersection as domain.
571 * - October 27th 2001: first version.
572 * - June 15th 2005: a memory leak fixed (domain was not freed when empty).
573 * - June 22nd 2005: Adaptation for GMP.
575 CloogLoop
*cloog_loop_restrict(CloogLoop
*loop
, CloogDomain
*context
)
576 { int new_dimension
;
577 CloogDomain
* domain
, * extended_context
, * new_domain
;
578 CloogLoop
* new_loop
;
580 domain
= loop
->domain
;
581 if (cloog_domain_dimension(domain
) > cloog_domain_dimension(context
))
583 new_dimension
= cloog_domain_dimension(domain
);
584 extended_context
= cloog_domain_extend(context
, new_dimension
);
585 new_domain
= cloog_domain_intersection(extended_context
,loop
->domain
) ;
586 cloog_domain_free(extended_context
) ;
589 new_domain
= cloog_domain_intersection(context
,loop
->domain
) ;
591 if (cloog_domain_isempty(new_domain
))
592 { cloog_domain_free(new_domain
) ;
596 new_loop
= cloog_loop_alloc(loop
->state
, new_domain
,
597 loop
->state
->one
, loop
->state
->zero
,
598 loop
->block
, loop
->inner
, NULL
);
605 * Call cloog_loop_restrict on each loop in the list "loop" and return
606 * the concatenated result.
608 CloogLoop
*cloog_loop_restrict_all(CloogLoop
*loop
, CloogDomain
*context
)
611 CloogLoop
*res
= NULL
;
612 CloogLoop
**res_next
= &res
;
614 for (; loop
; loop
= next
) {
617 *res_next
= cloog_loop_restrict(loop
, context
);
619 res_next
= &(*res_next
)->next
;
620 cloog_loop_free_parts(loop
, 1, 0, 0, 0);
623 cloog_loop_free(loop
);
631 * cloog_loop_project function:
632 * This function returns the projection of (loop) on the (level) first
633 * dimensions (outer loops). It makes the projection of the (loop) domain,
634 * then it returns a pointer to a new loop, with this projection as domain.
636 * - October 27th 2001: first version.
637 * - July 3rd->11th 2003: memory leaks hunt and correction.
638 * - June 22nd 2005: Adaptation for GMP.
640 CloogLoop
* cloog_loop_project(CloogLoop
* loop
, int level
)
642 CloogDomain
* new_domain
;
643 CloogLoop
* new_loop
, * copy
;
645 copy
= cloog_loop_alloc(loop
->state
, loop
->domain
, loop
->stride
, loop
->offset
,
646 loop
->block
, loop
->inner
, NULL
);
648 if (cloog_domain_dimension(loop
->domain
) == level
)
649 new_domain
= cloog_domain_copy(loop
->domain
) ;
651 new_domain
= cloog_domain_project(loop
->domain
, level
);
653 new_loop
= cloog_loop_alloc(loop
->state
, new_domain
, loop
->state
->one
,
654 loop
->state
->zero
, NULL
, copy
, NULL
);
661 * Call cloog_loop_project on each loop in the list "loop" and return
662 * the concatenated result.
664 CloogLoop
*cloog_loop_project_all(CloogLoop
*loop
, int level
)
667 CloogLoop
*res
= NULL
;
668 CloogLoop
**res_next
= &res
;
670 for (; loop
; loop
= next
) {
673 *res_next
= cloog_loop_project(loop
, level
);
674 res_next
= &(*res_next
)->next
;
675 cloog_loop_free_parts(loop
, 0, 0, 0, 0);
683 * cloog_loop_concat function:
684 * This function returns a pointer to the concatenation of the
685 * CloogLoop lists given as input.
686 * - October 28th 2001: first version.
688 CloogLoop
* cloog_loop_concat(CloogLoop
* a
, CloogLoop
* b
)
689 { CloogLoop
* loop
, * temp
;
694 { while (temp
->next
!= NULL
)
706 * cloog_loop_combine:
707 * Combine consecutive loops with identical domains into
708 * a single loop with the concatenation of their inner loops
711 CloogLoop
*cloog_loop_combine(CloogLoop
*loop
)
713 CloogLoop
*first
, *second
;
715 for (first
= loop
; first
; first
= first
->next
) {
716 while (first
->next
) {
717 if (!cloog_domain_lazy_equal(first
->domain
, first
->next
->domain
))
719 second
= first
->next
;
720 first
->inner
= cloog_loop_concat(first
->inner
, second
->inner
);
721 first
->next
= second
->next
;
722 cloog_loop_free_parts(second
, 1, 0, 0, 0);
730 * cloog_loop_separate function:
731 * This function implements the Quillere algorithm for separation of multiple
732 * loops: for a given set of polyhedra (loop), it computes a set of disjoint
733 * polyhedra such that the unions of these sets are equal, and returns this set.
734 * - October 28th 2001: first version.
735 * - November 14th 2001: elimination of some unused blocks.
736 * - August 13th 2002: (debug) in the case of union of polyhedra for one
737 * loop, redundant constraints are fired.
738 * - July 3rd->11th 2003: memory leaks hunt and correction.
739 * - June 22nd 2005: Adaptation for GMP.
740 * - October 16th 2005: Removal of the non-shared constraint elimination when
741 * there is only one loop in the list (seems to work
742 * without now, DomainSimplify may have been improved).
743 * The problem was visible with test/iftest2.cloog.
745 CloogLoop
* cloog_loop_separate(CloogLoop
* loop
)
746 { int lazy_equal
=0, disjoint
= 0;
747 CloogLoop
* new_loop
, * new_inner
, * res
, * now
, * temp
, * Q
,
748 * inner
, * old
/*, * previous, * next*/ ;
749 CloogDomain
* UQ
, * old_UQ
, * domain
;
754 loop
= cloog_loop_combine(loop
);
756 if (loop
->next
== NULL
)
757 return cloog_loop_disjoint(loop
) ;
759 UQ
= cloog_domain_copy(loop
->domain
) ;
760 domain
= cloog_domain_copy(loop
->domain
) ;
761 res
= cloog_loop_alloc(loop
->state
, domain
, loop
->state
->one
,
762 loop
->state
->zero
, loop
->block
, loop
->inner
, NULL
);
765 while((loop
= loop
->next
) != NULL
)
768 /* For all Q, add Q-loop associated with the blocks of Q alone,
769 * and Q inter loop associated with the blocks of Q and loop.
771 for (Q
= res
; Q
; Q
= Q
->next
) {
772 /* Add (Q inter loop). */
773 if ((disjoint
= cloog_domain_lazy_disjoint(Q
->domain
,loop
->domain
)))
776 { if ((lazy_equal
= cloog_domain_lazy_equal(Q
->domain
,loop
->domain
)))
777 domain
= cloog_domain_copy(Q
->domain
) ;
779 domain
= cloog_domain_intersection(Q
->domain
,loop
->domain
) ;
781 if (!cloog_domain_isempty(domain
))
782 { new_inner
= cloog_loop_concat(cloog_loop_copy(Q
->inner
),
783 cloog_loop_copy(loop
->inner
)) ;
784 new_loop
= cloog_loop_alloc(loop
->state
, domain
, loop
->state
->one
,
785 loop
->state
->zero
, NULL
, new_inner
, NULL
);
786 cloog_loop_add_disjoint(&temp
,&now
,new_loop
) ;
790 cloog_domain_free(domain
);
794 /* Add (Q - loop). */
796 domain
= cloog_domain_copy(Q
->domain
) ;
799 domain
= cloog_domain_empty(Q
->domain
);
801 domain
= cloog_domain_difference(Q
->domain
,loop
->domain
) ;
804 if (!cloog_domain_isempty(domain
)) {
805 new_loop
= cloog_loop_alloc(loop
->state
, domain
, loop
->state
->one
,
806 loop
->state
->zero
, NULL
, Q
->inner
, NULL
);
807 cloog_loop_add_disjoint(&temp
,&now
,new_loop
) ;
810 { cloog_domain_free(domain
) ;
811 /* If Q->inner is no more useful, we can free it. */
814 cloog_loop_free(inner
) ;
818 /* Add loop-UQ associated with the blocks of loop alone.*/
819 if (cloog_domain_lazy_disjoint(loop
->domain
,UQ
))
820 domain
= cloog_domain_copy(loop
->domain
) ;
822 { if (cloog_domain_lazy_equal(loop
->domain
,UQ
))
823 domain
= cloog_domain_empty(UQ
);
825 domain
= cloog_domain_difference(loop
->domain
,UQ
) ;
828 if (!cloog_domain_isempty(domain
)) {
829 new_loop
= cloog_loop_alloc(loop
->state
, domain
, loop
->state
->one
,
830 loop
->state
->zero
, NULL
, loop
->inner
, NULL
);
831 cloog_loop_add_disjoint(&temp
,&now
,new_loop
) ;
834 { cloog_domain_free(domain
) ;
835 /* If loop->inner is no more useful, we can free it. */
836 cloog_loop_free(loop
->inner
) ;
842 if (loop
->next
!= NULL
)
843 UQ
= cloog_domain_union(UQ
,loop
->domain
) ;
845 cloog_domain_free(old_UQ
) ;
846 cloog_loop_free_parts(res
,1,0,0,1) ;
850 cloog_loop_free_parts(old
,1,0,0,1) ;
857 * cloog_loop_merge_list
858 * Merge two lists of CloogLoops. The new list contains the
859 * elements of the two lists in the same order, but they may
861 * In particular, if the elements of a and b are ordered
862 * according to the inner loops of the order list, then so are the elements
865 static CloogLoop
*cloog_loop_merge_inner_list(CloogLoop
*a
, CloogLoop
*b
,
868 CloogLoop
*loop
, **next
;
871 for ( ; order
&& (a
||b
); order
= order
->next
) {
872 if (a
&& order
->inner
->block
== a
->block
) {
875 next
= &(*next
)->next
;
878 if (b
&& order
->inner
->block
== b
->block
) {
881 next
= &(*next
)->next
;
888 * cloog_loop_merge function:
889 * This function is the 'soft' version of loop_separate if we are looking for
890 * a code much simpler (and less efficicient). Here we merge loops if they have
891 * common parts in the iteration space (if the intersection of their domains is
892 * not empty), and let them isolated otherwise. This function returns the new
894 * - October 29th 2001: first version.
895 * - July 3rd->11th 2003: memory leaks hunt and correction.
896 * - June 22nd 2005: Adaptation for GMP.
898 CloogLoop
* cloog_loop_merge(CloogLoop
* loop
, CloogOptions
* options
)
900 CloogLoop
* res
, * merge
, * now
, * Q
, * P
, * new_inner
, * next
, * old
;
901 CloogDomain
* new_domain
, * temp
;
906 if (loop
->next
== NULL
)
907 return cloog_loop_disjoint(loop
);
909 /* First loop is added to the target list. */
910 res
= cloog_loop_alloc(loop
->state
, loop
->domain
, loop
->state
->one
,
911 loop
->state
->zero
, loop
->block
, loop
->inner
, NULL
);
913 /* Now the domain is in 'res' and it will be freed. */
914 loop
->domain
= NULL
;
916 /* And one by one, we see if we have to merge or to add the other loops. */
917 while((loop
= loop
->next
) != NULL
)
919 P
= cloog_loop_alloc(loop
->state
, loop
->domain
, loop
->state
->one
,
920 loop
->state
->zero
, loop
->block
, loop
->inner
, NULL
);
922 /* Now the domain is in 'P' and it will be freed. */
923 loop
->domain
= NULL
;
925 /* For each loop in the target list, if the intersection with the new loop
926 * is empty, we can add the new loop directly, otherwise, we can merge then
930 { temp
= cloog_domain_intersection(Q
->domain
,P
->domain
) ;
932 if (cloog_domain_isempty(temp
))
933 { cloog_domain_free(temp
) ;
934 cloog_loop_add_disjoint(&merge
,&now
,Q
) ;
937 { cloog_domain_free(temp
) ;
938 new_inner
= cloog_loop_merge_inner_list(Q
->inner
, P
->inner
, old
);
939 temp
= cloog_domain_union(P
->domain
,Q
->domain
) ;
941 new_domain
= cloog_domain_simple_convex(temp
);
943 new_domain
= cloog_domain_convex(temp
);
944 cloog_domain_free(temp
) ;
945 /* Q and P are no more used (but their content yes !).*/
946 cloog_loop_free_parts(P
,1,0,0,0) ;
947 cloog_loop_free_parts(Q
,1,0,0,0) ;
948 P
= cloog_loop_alloc(loop
->state
, new_domain
, loop
->state
->one
,
949 loop
->state
->zero
, NULL
, new_inner
, NULL
);
954 /* If there was merging, add it, otherwise add the loop lonely.
955 * DEBUG : ici pas besoin de s'assurer que P->next est NULL (possible que
956 * non si pas de fusion) car le dernier loop etudie a loop->next = NULL.
958 cloog_loop_add_disjoint(&merge
,&now
,P
) ;
961 cloog_loop_free_parts(old
,0,0,0,1) ;
967 static int cloog_loop_count(CloogLoop
*loop
)
971 for (nb_loops
= 0; loop
; loop
= loop
->next
)
979 * cloog_loop_sort function:
980 * Adaptation from LoopGen 0.4 by F. Quillere. This function sorts a list of
981 * parameterized disjoint polyhedra, in order to not have lexicographic order
982 * violation (see Quillere paper).
983 * - September 16th 2005: inclusion of cloog_loop_number (October 29th 2001).
985 CloogLoop
*cloog_loop_sort(CloogLoop
*loop
, int level
)
987 CloogLoop
*res
, *now
, **loop_array
;
989 int i
, nb_loops
=0, * permut
;
991 /* There is no need to sort the parameter domains. */
995 /* We will need to know how many loops are in the list. */
996 nb_loops
= cloog_loop_count(loop
);
998 /* If there is only one loop, it's the end. */
1002 /* We have to allocate memory for some useful components:
1003 * - loop_array: the loop array,
1004 * - doms: the array of domains to sort,
1005 * - permut: will give us a possible sort (maybe not the only one).
1007 loop_array
= (CloogLoop
**)malloc(nb_loops
*sizeof(CloogLoop
*)) ;
1008 doms
= (CloogDomain
**)malloc(nb_loops
*sizeof(CloogDomain
*));
1009 permut
= (int *)malloc(nb_loops
*sizeof(int)) ;
1011 /* We fill up the loop and domain arrays. */
1012 for (i
=0;i
<nb_loops
;i
++,loop
=loop
->next
)
1013 { loop_array
[i
] = loop
;
1014 doms
[i
] = loop_array
[i
]->domain
;
1017 /* cloog_domain_sort will fill up permut. */
1018 cloog_domain_sort(doms
, nb_loops
, level
, permut
);
1020 /* With permut and loop_array we build the sorted list. */
1022 for (i
=0;i
<nb_loops
;i
++)
1023 { /* To avoid pointer looping... loop_add will rebuild the list. */
1024 loop_array
[permut
[i
]-1]->next
= NULL
;
1025 cloog_loop_add(&res
,&now
,loop_array
[permut
[i
]-1]) ;
1037 * cloog_loop_nest function:
1038 * This function changes the loop list in such a way that we have no more than
1039 * one dimension added by level. It returns an equivalent loop list with
1041 * - October 29th 2001: first version.
1042 * - July 3rd->11th 2003: memory leaks hunt and correction.
1043 * - June 22nd 2005: Adaptation for GMP.
1044 * - November 21th 2005: (debug) now OK when cloog_loop_restrict returns NULL.
1046 CloogLoop
*cloog_loop_nest(CloogLoop
*loop
, CloogDomain
*context
, int level
)
1048 CloogLoop
* p
, * temp
, * res
, * now
, * next
;
1049 CloogDomain
* new_domain
;
1051 loop
= cloog_loop_disjoint(loop
);
1054 /* Each domain is changed by its intersection with the context. */
1055 while (loop
!= NULL
)
1056 { p
= cloog_loop_restrict(loop
, context
);
1060 { cloog_loop_free_parts(loop
,1,0,0,0) ;
1062 temp
= cloog_loop_alloc(p
->state
, p
->domain
, p
->state
->one
,
1063 p
->state
->zero
, p
->block
, p
->inner
, NULL
);
1065 /* If the intersection dimension is too big, we make projections smaller
1066 * and smaller, and each projection includes the preceding projection
1067 * (thus, in the target list, dimensions are added one by one).
1069 if (cloog_domain_dimension(p
->domain
) >= level
)
1070 for (l
= cloog_domain_dimension(p
->domain
); l
>= level
; l
--) {
1071 new_domain
= cloog_domain_project(p
->domain
, l
);
1072 temp
= cloog_loop_alloc(p
->state
, new_domain
, p
->state
->one
,
1073 p
->state
->zero
, NULL
, temp
, NULL
);
1076 /* p is no more useful (but its content yes !). */
1077 cloog_loop_free_parts(p
,0,0,0,0) ;
1079 cloog_loop_add(&res
,&now
,temp
) ;
1082 cloog_loop_free_parts(loop
,1,1,1,0) ;
1092 * cloog_loop_stride function:
1093 * This function will find the stride of a loop for the iterator at the column
1094 * number 'level' in the constraint matrix. It will update the lower bound of
1095 * the iterator accordingly. Basically, the function will try to find in the
1096 * inner loops a common condition on this iterator for the inner loop iterators
1097 * to be integral. For instance, let us consider a loop with the iterator i,
1098 * the iteration domain -4<=i<=n, and its two inner loops with the iterator j.
1099 * The first inner loop has the constraint 3j=i, and the second one has the
1100 * constraint 6j=i. Then the common constraint on i for j to be integral is
1101 * i%3=0, the stride for i is 3. Lastly, we have to find the new lower bound
1102 * for i: the first value satisfying the common constraint: -3. At the end, the
1103 * iteration domain for i is -3<=i<=n and the stride for i is 3.
1104 * - loop is the loop including the iteration domain of the considered iterator,
1105 * - level is the column number of the iterator in the matrix of contraints.
1107 * - June 29th 2003: first version (work in progress since June 26th 2003).
1108 * - July 14th 2003: simpler version.
1109 * - June 22nd 2005: Adaptation for GMP (from S. Verdoolaege's 0.12.1 version).
1111 void cloog_loop_stride(CloogLoop
* loop
, int level
)
1112 { int first_search
;
1113 cloog_int_t stride
, ref_offset
, offset
, potential
, lower
;
1116 cloog_int_init(stride
);
1117 cloog_int_init(ref_offset
);
1118 cloog_int_init(offset
);
1119 cloog_int_init(potential
);
1120 cloog_int_init(lower
);
1122 cloog_int_set_si(ref_offset
, 0);
1123 cloog_int_set_si(offset
, 0);
1124 cloog_int_set_si(lower
, 0);
1126 /* Default stride. */
1127 cloog_int_set_si(stride
, 1);
1129 inner
= loop
->inner
;
1131 if (cloog_domain_integral_lowerbound(loop
->domain
,level
,&lower
))
1132 while (inner
!= NULL
)
1133 { /* If the minimun stride has not been found yet, find the stride. */
1134 if ((first_search
) || (!cloog_int_is_one(stride
)))
1136 cloog_domain_stride(inner
->domain
, level
, &potential
, &offset
);
1137 if (!cloog_int_is_one(potential
) && (!first_search
))
1138 { /* Offsets must be the same for common stride. */
1139 cloog_int_gcd(stride
, potential
, stride
);
1140 if (!cloog_int_is_zero(stride
)) {
1141 cloog_int_fdiv_r(offset
, offset
, stride
);
1142 cloog_int_fdiv_r(ref_offset
, ref_offset
, stride
);
1144 if (cloog_int_ne(offset
,ref_offset
))
1145 cloog_int_set_si(stride
, 1);
1148 cloog_int_set(stride
, potential
);
1149 cloog_int_set(ref_offset
, offset
);
1155 inner
= inner
->next
;
1158 if (cloog_int_is_zero(stride
))
1159 cloog_int_set_si(stride
, 1);
1161 /* Update the values if necessary. */
1162 if (!cloog_int_is_one(stride
))
1163 { /* Update the stride value. */
1164 cloog_int_set(loop
->stride
, stride
);
1165 /* The new lower bound l' is such that
1166 * (l' + offset) % s = 0 and l <= l' <= l+(s-1)
1167 * Let l' = k s - offset, then
1168 * k s - offset <= l + (s-1) <= k s - offset + (s-1)
1169 * Or l' = floor((l+offset+(s-1))/s) * s - offset
1170 * = (floor((l+offset-1)/s) + 1) * s - offset
1172 cloog_int_add(lower
, lower
, offset
);
1173 cloog_int_sub_ui(lower
, lower
, 1);
1174 cloog_int_fdiv_q(lower
, lower
, stride
);
1175 cloog_int_add_ui(lower
, lower
, 1);
1176 cloog_int_mul(lower
, lower
, stride
);
1177 cloog_int_sub(lower
, lower
, offset
);
1178 loop
->domain
= cloog_domain_lowerbound_update(loop
->domain
, level
, lower
);
1179 cloog_int_set(loop
->offset
, lower
);
1182 cloog_int_clear(stride
);
1183 cloog_int_clear(ref_offset
);
1184 cloog_int_clear(offset
);
1185 cloog_int_clear(potential
);
1186 cloog_int_clear(lower
);
1191 * cloog_loop_stop function:
1192 * This function implements the 'stop' option : each domain of each loop
1193 * in the list 'loop' is replaced by 'context'. 'context' should be the
1194 * domain of the outer loop. By using this method, there are no more dimensions
1195 * to scan and the simplification step will automaticaly remove the domains
1196 * since they are the same as the corresponding contexts. The effect of this
1197 * function is to stop the code generation at the level this function is called,
1198 * the resulting code do not consider the next dimensions.
1199 * - January 11th 2005: first version.
1201 CloogLoop
* cloog_loop_stop(CloogLoop
* loop
, CloogDomain
* context
)
1205 { cloog_domain_free(loop
->domain
) ;
1206 loop
->domain
= cloog_domain_copy(context
) ;
1207 loop
->next
= cloog_loop_stop(loop
->next
, context
) ;
1214 static int level_is_constant(int level
, int scalar
, int *scaldims
, int nb_scattdims
)
1216 return level
&& (level
+scalar
<= nb_scattdims
) && (scaldims
[level
+scalar
-1]);
1221 * Compare the constant dimensions of loops 'l1' and 'l2' starting at 'scalar'
1222 * and return -1 if the vector of constant dimensions of 'l1' is smaller
1223 * than that of 'l2', 0 if they are the same and +1 if that of 'l1' is
1224 * greater than that of 'l2'.
1225 * \param l1 Loop to be compared with l2.
1226 * \param l2 Loop to be compared with l1.
1227 * \param level Current non-scalar dimension.
1228 * \param scaldims Boolean array saying whether a dimension is scalar or not.
1229 * \param nb_scattdims Size of the scaldims array.
1230 * \param scalar Current scalar dimension.
1231 * \return -1 if (l1 < l2), 0 if (l1 == l2) and +1 if (l1 > l2)
1233 int cloog_loop_constant_cmp(CloogLoop
*l1
, CloogLoop
*l2
, int level
,
1234 int *scaldims
, int nb_scattdims
, int scalar
)
1236 CloogBlock
*b1
, *b2
;
1237 b1
= l1
->inner
->block
;
1238 b2
= l2
->inner
->block
;
1239 while (level_is_constant(level
, scalar
, scaldims
, nb_scattdims
)) {
1240 int cmp
= cloog_int_cmp(b1
->scaldims
[scalar
], b2
->scaldims
[scalar
]);
1250 * cloog_loop_scalar_gt function:
1251 * This function returns 1 if loop 'l1' is greater than loop 'l2' for the
1252 * scalar dimension vector that begins at dimension 'scalar', 0 otherwise. What
1253 * we want to know is whether a loop is scheduled before another one or not.
1254 * This function solves the problem when the considered dimension for scheduling
1255 * is a scalar dimension. Since there may be a succession of scalar dimensions,
1256 * this function will reason about the vector of scalar dimension that begins
1257 * at dimension 'level+scalar' and finish to the first non-scalar dimension.
1258 * \param l1 Loop to be compared with l2.
1259 * \param l2 Loop to be compared with l1.
1260 * \param level Current non-scalar dimension.
1261 * \param scaldims Boolean array saying whether a dimension is scalar or not.
1262 * \param nb_scattdims Size of the scaldims array.
1263 * \param scalar Current scalar dimension.
1264 * \return 1 if (l1 > l2), 0 otherwise.
1266 * - September 9th 2005: first version.
1267 * - October 15nd 2007: now "greater than" instead of "greater or equal".
1269 int cloog_loop_scalar_gt(l1
, l2
, level
, scaldims
, nb_scattdims
, scalar
)
1270 CloogLoop
* l1
, * l2
;
1271 int level
, * scaldims
, nb_scattdims
, scalar
;
1273 return cloog_loop_constant_cmp(l1
, l2
, level
, scaldims
, nb_scattdims
, scalar
) > 0;
1278 * cloog_loop_scalar_eq function:
1279 * This function returns 1 if loop 'l1' is equal to loop 'l2' for the scalar
1280 * dimension vector that begins at dimension 'scalar', 0 otherwise. What we want
1281 * to know is whether two loops are scheduled for the same time or not.
1282 * This function solves the problem when the considered dimension for scheduling
1283 * is a scalar dimension. Since there may be a succession of scalar dimensions,
1284 * this function will reason about the vector of scalar dimension that begins
1285 * at dimension 'level+scalar' and finish to the first non-scalar dimension.
1286 * - l1 and l2 are the loops to compare,
1287 * - level is the current non-scalar dimension,
1288 * - scaldims is the boolean array saying whether a dimension is scalar or not,
1289 * - nb_scattdims is the size of the scaldims array,
1290 * - scalar is the current scalar dimension.
1292 * - September 9th 2005 : first version.
1294 int cloog_loop_scalar_eq(l1
, l2
, level
, scaldims
, nb_scattdims
, scalar
)
1295 CloogLoop
* l1
, * l2
;
1296 int level
, * scaldims
, nb_scattdims
, scalar
;
1298 return cloog_loop_constant_cmp(l1
, l2
, level
, scaldims
, nb_scattdims
, scalar
) == 0;
1303 * cloog_loop_scalar_sort function:
1304 * This function sorts a linked list of loops (loop) with respect to the
1305 * scalar dimension vector that begins at dimension 'scalar'. Since there may
1306 * be a succession of scalar dimensions, this function will reason about the
1307 * vector of scalar dimension that begins at dimension 'level+scalar' and
1308 * finish to the first non-scalar dimension.
1309 * \param loop Loop list to sort.
1310 * \param level Current non-scalar dimension.
1311 * \param scaldims Boolean array saying whether a dimension is scalar or not.
1312 * \param nb_scattdims Size of the scaldims array.
1313 * \param scalar Current scalar dimension.
1314 * \return A pointer to the sorted list.
1316 * - July 2nd 2005: first developments.
1317 * - September 2nd 2005: first version.
1318 * - October 15nd 2007: complete rewrite to remove bugs, now a bubble sort.
1320 CloogLoop
* cloog_loop_scalar_sort(loop
, level
, scaldims
, nb_scattdims
, scalar
)
1322 int level
, * scaldims
, nb_scattdims
, scalar
;
1324 CloogLoop
**current
;
1328 for (current
= &loop
; (*current
)->next
; current
= &(*current
)->next
) {
1329 CloogLoop
*next
= (*current
)->next
;
1330 if (cloog_loop_scalar_gt(*current
,next
,level
,scaldims
,nb_scattdims
,scalar
)) {
1332 (*current
)->next
= next
->next
;
1333 next
->next
= *current
;
1344 * cloog_loop_generate_backtrack function:
1345 * adaptation from LoopGen 0.4 by F. Quillere. This function implements the
1346 * backtrack of the Quillere et al. algorithm (see the Quillere paper).
1347 * It eliminates unused iterations of the current level for the new one. See the
1348 * example called linearity-1-1 example with and without this part for an idea.
1349 * - October 26th 2001: first version in cloog_loop_generate_general.
1350 * - July 31th 2002: (debug) no more parasite loops (REALLY hard !).
1351 * - October 30th 2005: extraction from cloog_loop_generate_general.
1353 CloogLoop
*cloog_loop_generate_backtrack(CloogLoop
*loop
,
1354 int level
, CloogOptions
*options
)
1356 CloogDomain
* domain
;
1357 CloogLoop
* now
, * now2
, * next
, * next2
, * end
, * temp
, * l
, * inner
,
1363 while (temp
!= NULL
)
1365 inner
= temp
->inner
;
1367 while (inner
!= NULL
)
1368 { next
= inner
->next
;
1369 /* This 'if' and its first part is the debug of july 31th 2002. */
1370 if (inner
->block
!= NULL
) {
1371 end
= cloog_loop_alloc(temp
->state
, inner
->domain
, temp
->state
->one
,
1372 temp
->state
->zero
, inner
->block
, NULL
, NULL
);
1373 domain
= cloog_domain_copy(temp
->domain
) ;
1374 new_loop
= cloog_loop_alloc(temp
->state
, domain
, temp
->state
->one
,
1375 temp
->state
->zero
, NULL
, end
, NULL
);
1378 new_loop
= cloog_loop_project(inner
, level
);
1380 cloog_loop_free_parts(inner
,0,0,0,0) ;
1381 cloog_loop_add(&l
,&now2
,new_loop
) ;
1385 temp
->inner
= NULL
;
1388 { l
= cloog_loop_separate(l
) ;
1389 l
= cloog_loop_sort(l
, level
);
1391 cloog_int_set(l
->stride
, temp
->stride
);
1392 cloog_int_set(l
->offset
, temp
->offset
);
1393 cloog_loop_add(&loop
,&now
,l
) ;
1397 next2
= temp
->next
;
1398 cloog_loop_free_parts(temp
,1,0,0,0) ;
1407 * cloog_loop_generate_general function:
1408 * Adaptation from LoopGen 0.4 by F. Quillere. This function implements the
1409 * Quillere algorithm for polyhedron scanning from step 3 to 5.
1410 * (see the Quillere paper).
1411 * - loop is the loop for which we have to generate a scanning code,
1412 * - level is the current non-scalar dimension,
1413 * - scalar is the current scalar dimension,
1414 * - scaldims is the boolean array saying whether a dimension is scalar or not,
1415 * - nb_scattdims is the size of the scaldims array,
1416 * - options are the general code generation options.
1418 * - October 26th 2001: first version.
1419 * - July 3rd->11th 2003: memory leaks hunt and correction.
1420 * - June 22nd 2005: Adaptation for GMP.
1421 * - September 2nd 2005: The function have been cutted out in two pieces:
1422 * cloog_loop_generate and this one, in order to handle
1423 * the scalar dimension case more efficiently with
1424 * cloog_loop_generate_scalar.
1425 * - November 15th 2005: (debug) the result of the cloog_loop_generate call may
1426 * be a list of polyhedra (especially if stop option is
1427 * used): cloog_loop_add_list instead of cloog_loop_add.
1429 CloogLoop
*cloog_loop_generate_general(CloogLoop
*loop
,
1430 int level
, int scalar
, int *scaldims
, int nb_scattdims
,
1431 CloogOptions
*options
)
1433 CloogLoop
* res
, * now
, * temp
, * l
, * new_loop
, * inner
, * now2
, * end
,
1435 CloogDomain
* domain
;
1437 /* 3. Separate all projections into disjoint polyhedra. */
1438 res
= ((options
->f
> level
+scalar
) || (options
->f
< 0)) ?
1439 cloog_loop_merge(loop
, options
) : cloog_loop_separate(loop
);
1441 /* 3b. -correction- sort the loops to determine their textual order. */
1442 res
= cloog_loop_sort(res
, level
);
1444 /* 4. Recurse for each loop with the current domain as context. */
1447 if (!level
|| (level
+scalar
< options
->l
) || (options
->l
< 0))
1449 { if (level
&& options
->strides
)
1450 cloog_loop_stride(temp
, level
);
1451 inner
= temp
->inner
;
1452 domain
= temp
->domain
;
1454 while (inner
!= NULL
)
1455 { /* 4b. -ced- recurse for each sub-list of non terminal loops. */
1456 if (cloog_domain_dimension(inner
->domain
) > level
)
1458 while ((end
->next
!= NULL
) &&
1459 (cloog_domain_dimension(end
->next
->domain
) > level
))
1465 l
= cloog_loop_generate(inner
,domain
,level
+1,scalar
,
1466 scaldims
, nb_scattdims
, options
);
1469 cloog_loop_add_list(&into
,&now
,l
) ;
1474 { cloog_loop_add(&into
,&now
,inner
) ;
1475 inner
= inner
->next
;
1480 temp
->inner
= into
;
1481 cloog_loop_add(&res
,&now2
,temp
) ;
1485 while (temp
!= NULL
)
1486 { next
= temp
->next
;
1487 l
= cloog_loop_nest(temp
->inner
, temp
->domain
, level
+1);
1488 new_loop
= cloog_loop_alloc(temp
->state
, temp
->domain
, temp
->state
->one
,
1489 temp
->state
->zero
, NULL
, l
, NULL
);
1490 temp
->inner
= NULL
;
1492 cloog_loop_free_parts(temp
,0,0,0,0) ;
1493 cloog_loop_add(&res
,&now
,new_loop
) ;
1497 /* 5. eliminate unused iterations of the current level for the new one. See
1498 * the example called linearity-1-1 example with and without this part
1501 if ((!options
->nobacktrack
) && level
&&
1502 ((level
+scalar
< options
->l
) || (options
->l
< 0)) &&
1503 ((options
->f
<= level
+scalar
) && !(options
->f
< 0)))
1504 res
= cloog_loop_generate_backtrack(res
, level
, options
);
1506 /* Pray for my new paper to be accepted somewhere since the following stuff
1507 * is really amazing :-) !
1508 * Far long later: The paper has been accepted to PACT 2004 :-))). But there
1509 * are still some bugs and I have no time to fix them. Thus now you have to
1510 * pray for me to get an academic position for that really amazing stuff :-) !
1511 * Later again: OK, I get my academic position, but still I have not enough
1512 * time to fix and clean this part... Pray again :-) !!!
1514 /* res = cloog_loop_unisolate(res,level) ;*/
1521 * cloog_loop_generate_scalar function:
1522 * This function applies the simplified code generation scheme in the trivial
1523 * case of scalar dimensions. When dealing with scalar dimensions, there is
1524 * no need of costly polyhedral operations for separation or sorting: sorting
1525 * is a question of comparing scalar vectors and separation amounts to consider
1526 * only loops with the same scalar vector for the next step of the code
1527 * generation process. This function achieves the separation/sorting process
1528 * for the vector of scalar dimension that begins at dimension 'level+scalar'
1529 * and finish to the first non-scalar dimension.
1530 * - loop is the loop for which we have to generate a scanning code,
1531 * - level is the current non-scalar dimension,
1532 * - scalar is the current scalar dimension,
1533 * - scaldims is the boolean array saying whether a dimension is scalar or not,
1534 * - nb_scattdims is the size of the scaldims array,
1535 * - options are the general code generation options.
1537 * - September 2nd 2005: First version.
1539 CloogLoop
*cloog_loop_generate_scalar(CloogLoop
*loop
,
1540 int level
, int scalar
, int *scaldims
, int nb_scattdims
,
1541 CloogOptions
*options
)
1542 { CloogLoop
* res
, * now
, * temp
, * l
, * end
, * next
, * ref
;
1544 /* We sort the loop list with respect to the current scalar vector. */
1545 res
= cloog_loop_scalar_sort(loop
,level
,scaldims
,nb_scattdims
,scalar
) ;
1549 while (temp
!= NULL
)
1550 { /* Then we will appy the general code generation process to each sub-list
1551 * of loops with the same scalar vector.
1556 while((end
->next
!= NULL
) &&
1557 cloog_loop_scalar_eq(ref
,end
->next
,level
,scaldims
,nb_scattdims
,scalar
))
1563 /* For the next dimension, scalar value is updated by adding the scalar
1564 * vector size, which is stored at scaldims[level+scalar-1].
1566 l
= cloog_loop_generate_general(temp
, level
,
1567 scalar
+scaldims
[level
+scalar
-1],
1568 scaldims
, nb_scattdims
, options
);
1571 cloog_loop_add_list(&res
,&now
,l
) ;
1580 /* Compare loop with the next loop based on their constant dimensions.
1581 * The result is < 0, == 0 or > 0 depending on whether the constant
1582 * dimensions of loop are lexicographically smaller, equal or greater
1583 * than those of loop->next.
1584 * If loop is the last in the list, then it is assumed to be smaller
1585 * than the "next" one.
1587 static int cloog_loop_next_scal_cmp(CloogLoop
*loop
)
1595 nb_scaldims
= loop
->block
->nb_scaldims
;
1596 if (loop
->next
->block
->nb_scaldims
< nb_scaldims
)
1597 nb_scaldims
= loop
->next
->block
->nb_scaldims
;
1599 for (i
= 0; i
< nb_scaldims
; ++i
) {
1600 int cmp
= cloog_int_cmp(loop
->block
->scaldims
[i
],
1601 loop
->next
->block
->scaldims
[i
]);
1605 return loop
->block
->nb_scaldims
- loop
->next
->block
->nb_scaldims
;
1609 /* Check whether the globally constant dimensions of a and b
1610 * have the same value for all globally constant dimensions
1611 * that are situated before any (locally) non-constant dimension.
1613 static int cloog_loop_equal_prefix(CloogLoop
*a
, CloogLoop
*b
,
1614 int *scaldims
, int nb_scattdims
)
1620 for (i
= 0; i
< nb_scattdims
; ++i
) {
1625 if (!cloog_int_eq(a
->block
->scaldims
[cst
], b
->block
->scaldims
[cst
]))
1629 for (i
= i
+ 1; i
< nb_scattdims
; ++i
) {
1632 if (!cloog_domain_lazy_isconstant(a
->domain
, dim
))
1634 /* No need to check that dim is also constant in b and that the
1635 * constant values are equal. That will happen during the check
1636 * whether the two domains are equal.
1644 /* Try to block adjacent loops in the loop list "loop".
1645 * We only attempt blocking if the constant dimensions of the loops
1646 * in the least are (not necessarily strictly) increasing.
1647 * Then we look for a sublist such that the first (begin) has constant
1648 * dimensions strictly larger than the previous loop in the complete
1649 * list and such that the loop (end) after the last loop in the sublist
1650 * has constant dimensions strictly larger than the last loop in the sublist.
1651 * Furthermore, all loops in the sublist should have the same domain
1652 * (with globally constant dimensions removed) and the difference
1653 * (if any) in constant dimensions may only occur after all the
1654 * (locally) constant dimensions.
1655 * If we find such a sublist, then the blocks of all but the first
1656 * are merged into the block of the first.
1658 * Note that this function can only be called before the global
1659 * blocklist has been created because it may otherwise modify and destroy
1660 * elements on that list.
1662 CloogLoop
*cloog_loop_block(CloogLoop
*loop
, int *scaldims
, int nb_scattdims
)
1664 CloogLoop
*begin
, *end
, *l
;
1665 int begin_after_previous
;
1666 int end_after_previous
;
1670 for (begin
= loop
; begin
; begin
= begin
->next
) {
1671 if (!begin
->block
|| !begin
->block
->scaldims
)
1673 if (cloog_loop_next_scal_cmp(loop
) > 0)
1677 begin_after_previous
= 1;
1678 for (begin
= loop
; begin
; begin
= begin
->next
) {
1679 if (!begin_after_previous
) {
1680 begin_after_previous
= cloog_loop_next_scal_cmp(begin
) < 0;
1684 end_after_previous
= cloog_loop_next_scal_cmp(begin
) < 0;
1685 for (end
= begin
->next
; end
; end
= end
->next
) {
1686 if (!cloog_loop_equal_prefix(begin
, end
, scaldims
, nb_scattdims
))
1688 if (!cloog_domain_lazy_equal(begin
->domain
, end
->domain
))
1690 end_after_previous
= cloog_loop_next_scal_cmp(end
) < 0;
1692 if (end
!= begin
->next
&& end_after_previous
) {
1693 for (l
= begin
->next
; l
!= end
; l
= begin
->next
) {
1694 cloog_block_merge(begin
->block
, l
->block
);
1695 begin
->next
= l
->next
;
1696 cloog_loop_free_parts(l
, 1, 0, 1, 0);
1700 begin_after_previous
= cloog_loop_next_scal_cmp(begin
) < 0;
1708 * cloog_loop_generate function:
1709 * Adaptation from LoopGen 0.4 by F. Quillere. This function implements the
1710 * Quillere algorithm for polyhedron scanning from step 1 to 2.
1711 * (see the Quillere paper).
1712 * - loop is the loop for which we have to generate a scanning code,
1713 * - context is the context of the current loop (constraints on parameter and/or
1714 * on outer loop counters),
1715 * - level is the current non-scalar dimension,
1716 * - scalar is the current scalar dimension,
1717 * - scaldims is the boolean array saying whether a dimension is scalar or not,
1718 * - nb_scattdims is the size of the scaldims array,
1719 * - options are the general code generation options.
1721 * - October 26th 2001: first version.
1722 * - July 3rd->11th 2003: memory leaks hunt and correction.
1723 * - June 15th 2005: a memory leak fixed (loop was not entirely freed when
1724 * the result of cloog_loop_restrict was NULL).
1725 * - June 22nd 2005: Adaptation for GMP.
1726 * - September 2nd 2005: The function have been cutted out in two pieces:
1727 * cloog_loop_generate and this one, in order to handle
1728 * the scalar dimension case more efficiently with
1729 * cloog_loop_generate_scalar.
1730 * - November 15th 2005: (debug) Condition for stop option no more take care of
1731 * further scalar dimensions.
1733 CloogLoop
*cloog_loop_generate(CloogLoop
*loop
, CloogDomain
*context
,
1734 int level
, int scalar
, int *scaldims
, int nb_scattdims
,
1735 CloogOptions
*options
)
1737 /* If the user asked to stop code generation at this level, let's stop. */
1738 if ((options
->stop
>= 0) && (level
+scalar
>= options
->stop
+1))
1739 return cloog_loop_stop(loop
,context
) ;
1741 /* 1. Replace each polyhedron by its intersection with the context.
1743 loop
= cloog_loop_restrict_all(loop
, context
);
1748 * 2. Compute the projection of each polyhedron onto the outermost
1749 * loop variable and the parameters.
1751 loop
= cloog_loop_project_all(loop
, level
);
1753 /* To save both time and memory, we switch here depending on whether the
1754 * current dimension is scalar (simplified processing) or not (general
1757 if (level_is_constant(level
, scalar
, scaldims
, nb_scattdims
))
1758 loop
= cloog_loop_generate_scalar(loop
, level
, scalar
,
1759 scaldims
, nb_scattdims
, options
);
1761 loop
= cloog_loop_generate_general(loop
, level
, scalar
,
1762 scaldims
, nb_scattdims
, options
);
1769 * Internal function for simplifying a single loop in a list of loops.
1770 * See cloog_loop_simplify.
1772 static CloogLoop
*loop_simplify(CloogLoop
*loop
, CloogDomain
*context
,
1776 CloogBlock
* new_block
;
1777 CloogLoop
*simplified
, *inner
;
1778 CloogDomain
* domain
, * simp
, * inter
, * extended_context
;
1780 domain
= loop
->domain
;
1782 domain_dim
= cloog_domain_dimension(domain
);
1783 extended_context
= cloog_domain_extend(context
, domain_dim
);
1784 inter
= cloog_domain_intersection(domain
,extended_context
) ;
1785 simp
= cloog_domain_simplify(inter
,extended_context
) ;
1786 cloog_domain_free(extended_context
) ;
1788 /* If the constraint system is never true, go to the next one. */
1789 if (cloog_domain_never_integral(simp
)) {
1790 cloog_loop_free(loop
->inner
);
1791 cloog_domain_free(inter
);
1792 cloog_domain_free(simp
);
1796 inner
= cloog_loop_simplify(loop
->inner
, inter
, level
+1);
1797 cloog_domain_free(inter
) ;
1799 if ((inner
== NULL
) && (loop
->block
== NULL
)) {
1800 cloog_domain_free(simp
);
1804 new_block
= cloog_block_copy(loop
->block
) ;
1806 simplified
= cloog_loop_alloc(loop
->state
, simp
, loop
->stride
, loop
->offset
,
1807 new_block
, inner
, NULL
);
1809 return(simplified
) ;
1814 * cloog_loop_simplify function:
1815 * This function implements the part 6. of the Quillere algorithm, it
1816 * recursively simplifies each loop in the context of the preceding loop domain.
1817 * It returns a pointer to the simplified loop list.
1818 * The cloog_domain_simplify (DomainSimplify) behaviour is really bad with
1819 * polyhedra union and some really awful sidesteppings were written, I plan
1821 * - October 31th 2001: first version.
1822 * - July 3rd->11th 2003: memory leaks hunt and correction.
1823 * - April 16th 2005: a memory leak fixed (extended_context was not freed).
1824 * - June 15th 2005: a memory leak fixed (loop was not conveniently freed
1825 * when the constraint system is never true).
1826 * - October 27th 2005: - this function called before cloog_loop_fast_simplify
1827 * is now the official cloog_loop_simplify function in
1828 * replacement of a slower and more complex one (after
1829 * deep changes in the pretty printer).
1830 * - we use cloog_loop_disjoint to fix the problem when
1831 * simplifying gives a union of polyhedra (before, it
1832 * was under the responsibility of the pretty printer).
1834 CloogLoop
*cloog_loop_simplify(CloogLoop
*loop
, CloogDomain
*context
, int level
)
1837 CloogLoop
*res
= NULL
;
1838 CloogLoop
**next
= &res
;
1840 for (now
= loop
; now
; now
= now
->next
) {
1841 *next
= loop_simplify(now
, context
, level
);
1843 now
->inner
= NULL
; /* For loop integrity. */
1844 cloog_domain_free(now
->domain
);
1848 next
= &(*next
)->next
;
1850 cloog_loop_free(loop
);
1852 /* Examples like test/iftest2.cloog give unions of polyhedra after
1853 * simplifying, thus we we have to disjoint them. Another good reason to
1854 * put the simplifying step in the Quillere backtrack.
1856 res
= cloog_loop_disjoint(res
);
1863 * cloog_loop_scatter function:
1864 * This function add the scattering (scheduling) informations in a loop.
1866 void cloog_loop_scatter(CloogLoop
* loop
, CloogScattering
*scatt
)
1868 loop
->domain
= cloog_domain_scatter(loop
->domain
, scatt
);