Rename members of cloogblock to match CLooG master
[cloog-merge.git] / source / loop.c
blob68ddc67d1c24957a306cf384b124f69cb82df365
2 /**-------------------------------------------------------------------**
3 ** CLooG **
4 **-------------------------------------------------------------------**
5 ** loop.c **
6 **-------------------------------------------------------------------**
7 ** First version: october 26th 2001 **
8 **-------------------------------------------------------------------**/
11 /******************************************************************************
12 * CLooG : the Chunky Loop Generator (experimental) *
13 ******************************************************************************
14 * *
15 * Copyright (C) 2001-2005 Cedric Bastoul *
16 * *
17 * This is free software; you can redistribute it and/or modify it under the *
18 * terms of the GNU General Public License as published by the Free Software *
19 * Foundation; either version 2 of the License, or (at your option) any later *
20 * version. *
21 * *
22 * This software is distributed in the hope that it will be useful, but *
23 * WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY *
24 * or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License *
25 * for more details. *
26 * *
27 * You should have received a copy of the GNU General Public License along *
28 * with software; if not, write to the Free Software Foundation, Inc., *
29 * 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA *
30 * *
31 * CLooG, the Chunky Loop Generator *
32 * Written by Cedric Bastoul, Cedric.Bastoul@inria.fr *
33 * *
34 ******************************************************************************/
35 /* CAUTION: the english used for comments is probably the worst you ever read,
36 * please feel free to correct and improve it !
39 # include <stdlib.h>
40 # include <stdio.h>
41 # include "../include/cloog/cloog.h"
44 /******************************************************************************
45 * Memory leaks hunting *
46 ******************************************************************************/
49 /**
50 * These functions and global variables are devoted to memory leaks hunting: we
51 * want to know at each moment how many CloogLoop structures had been allocated
52 * (cloog_loop_allocated) and how many had been freed (cloog_loop_freed).
53 * Each time a CloogLoog structure is allocated, a call to the function
54 * cloog_loop_leak_up() must be carried out, and respectively
55 * cloog_loop_leak_down() when a CloogLoop structure is freed. The special
56 * variable cloog_loop_max gives the maximal number of CloogLoop structures
57 * simultaneously alive (i.e. allocated and non-freed) in memory.
58 * - July 3rd->11th 2003: first version (memory leaks hunt and correction).
62 extern int cloog_value_allocated ;
63 extern int cloog_value_freed ;
64 extern int cloog_value_max ;
67 int cloog_loop_allocated = 0 ;
68 int cloog_loop_freed = 0 ;
69 int cloog_loop_max = 0 ;
72 static void cloog_loop_leak_up (void)
74 cloog_loop_allocated ++ ;
75 if ((cloog_loop_allocated-cloog_loop_freed) > cloog_loop_max)
76 cloog_loop_max = cloog_loop_allocated - cloog_loop_freed ;
80 static void cloog_loop_leak_down (void)
81 { cloog_loop_freed ++ ;
85 /******************************************************************************
86 * Structure display function *
87 ******************************************************************************/
90 /**
91 * cloog_loop_print_structure function:
92 * Displays a loop structure in a way that trends to be understandable without
93 * falling in a deep depression or, for the lucky ones, getting a headache...
94 * Written by Olivier Chorier, Luc Marchaud, Pierre Martin and Romain Tartiere.
95 * - April 24th 2005: Initial version.
96 * - May 21rd 2005: - New parameter `F' for destination file (ie stdout),
97 * - Minor tweaks.
98 * - May 26th 2005: Memory leak hunt.
99 * - June 2nd 2005: (Ced) Integration and minor fixes.
100 * -June 22nd 2005: (Ced) Adaptation for GMP.
102 void cloog_loop_print_structure(FILE * file, CloogLoop * loop, int level)
103 { int i, j, first=1 ;
105 if (loop)
106 { /* Go to the right level. */
107 for (i=0; i<level; i++)
108 fprintf(file,"|\t") ;
110 fprintf(file,"+-- CloogLoop\n") ;
113 /* For each loop. */
114 while (loop)
115 { if (!first)
116 { /* Go to the right level. */
117 for (i=0; i<level; i++)
118 fprintf(file,"|\t") ;
120 fprintf(file,"| CloogLoop\n") ;
122 else
123 first = 0 ;
125 /* A blank line. */
126 for(j=0; j<=level+1; j++)
127 fprintf(file,"|\t") ;
128 fprintf(file,"\n") ;
130 /* Print the domain. */
131 cloog_domain_print_structure(file,cloog_loop_domain (loop),level+1) ;
133 /* Print the stride. */
134 for(j=0; j<=level; j++)
135 fprintf(file,"|\t") ;
136 fprintf(file, "Stride: ") ;
137 value_print(file,VALUE_FMT,loop->stride) ;
138 fprintf(file, "\n") ;
140 /* A blank line. */
141 for(j=0; j<=level+1; j++)
142 fprintf(file,"|\t") ;
143 fprintf(file,"\n") ;
145 /* Print the block. */
146 cloog_block_print_structure(file,cloog_loop_block (loop),level+1) ;
148 /* A blank line. */
149 for (i=0; i<=level+1; i++)
150 fprintf(file,"|\t") ;
151 fprintf(file,"\n") ;
153 /* Print inner if any. */
154 if (cloog_loop_inner (loop))
155 cloog_loop_print_structure (file,cloog_loop_inner (loop), level + 1);
157 /* And let's go for the next one. */
158 loop = cloog_loop_next (loop) ;
160 /* One more time something that is here only for a better look. */
161 if (!loop)
162 { /* Two blank lines if this is the end of the linked list. */
163 for (j=0; j<2; j++)
164 { for (i=0; i<=level; i++)
165 fprintf(file,"|\t") ;
167 fprintf(file,"\n") ;
170 else
171 { /* A special blank line if the is a next loop. */
172 for (i=0; i<=level; i++)
173 fprintf(file,"|\t") ;
174 fprintf(file,"V\n") ;
181 * cloog_loop_print function:
182 * This function prints the content of a CloogLoop structure (start) into a
183 * file (file, possibly stdout).
184 * - June 2nd 2005: Now this very old function (probably as old as CLooG) is
185 * only a frontend to cloog_loop_print_structure, with a quite
186 * better human-readable representation.
188 void cloog_loop_print(FILE * file, CloogLoop * loop)
189 { cloog_loop_print_structure(file,loop,0) ;
193 /******************************************************************************
194 * Memory deallocation function *
195 ******************************************************************************/
199 * cloog_loop_free function:
200 * This function frees the allocated memory for a CloogLoop structure (loop),
201 * and frees its inner loops and its next loops.
202 * - June 22nd 2005: Adaptation for GMP.
204 void cloog_loop_free(CloogLoop * loop)
205 { CloogLoop * next ;
207 while (loop != NULL)
208 { cloog_loop_leak_down() ;
210 next = cloog_loop_next (loop) ;
211 cloog_domain_free(cloog_loop_domain (loop)) ;
212 cloog_block_free(cloog_loop_block (loop)) ;
213 if (cloog_loop_inner (loop))
214 cloog_loop_free (cloog_loop_inner (loop));
216 value_clear_c (loop->stride);
217 free(loop) ;
218 loop = next ;
224 * cloog_loop_free_parts function:
225 * This function frees the allocated memory for some parts of a CloogLoop
226 * structure (loop), each other argument is a boolean having to be set to 1 if
227 * we want to free the corresponding part, 0 otherwise. This function applies
228 * the same freeing policy to its inner ans next loops recursively.
229 * - July 3rd 2003: first version.
230 * - June 22nd 2005: Adaptation for GMP.
232 static void
233 cloog_loop_free_parts (CloogLoop *loop, int domain, int block,
234 int inner, int next)
236 CloogLoop * follow ;
238 while (loop != NULL)
239 { cloog_loop_leak_down() ;
240 follow = cloog_loop_next (loop) ;
242 if (domain)
243 cloog_domain_free(cloog_loop_domain (loop)) ;
245 if (block)
246 cloog_block_free(cloog_loop_block (loop)) ;
248 if (inner && cloog_loop_inner (loop))
249 cloog_loop_free_parts (cloog_loop_inner (loop), domain, block, inner, 1);
251 value_clear_c (loop->stride);
252 free(loop) ;
253 if (next)
254 loop = follow ;
255 else
256 loop = NULL ;
261 /******************************************************************************
262 * Reading functions *
263 ******************************************************************************/
267 * cloog_loop_read function:
268 * This function reads loop data into a file (foo, possibly stdin) and
269 * returns a pointer to a CloogLoop structure containing the read information.
270 * This function can be used only for input file reading, when one loop is
271 * associated with one statement.
272 * - number is the statement block number carried by the loop (-1 if none).
273 * - nb_parameters is the number of parameters.
275 * - September 9th 2002: first version.
276 * - April 16th 2005: adaptation to new CloogStatement struct (with number).
277 * - June 11th 2005: adaptation to new CloogBlock structure.
278 * - June 22nd 2005: Adaptation for GMP.
280 CloogLoop * cloog_loop_read(FILE * foo, int number, int nb_parameters)
281 { int nb_iterators, op1, op2, op3 ;
282 char s[MAX_STRING] ;
283 CloogLoop * loop ;
284 CloogStatement * statement ;
286 cloog_loop_leak_up() ;
288 /* Memory allocation and information reading for the first domain: */
289 loop = (CloogLoop *)malloc(sizeof(CloogLoop)) ;
290 if (loop == NULL)
291 { fprintf(stderr, "Memory Overflow.\n") ;
292 exit(1) ;
294 /* domain. */
295 cloog_loop_set_domain (loop, cloog_domain_union_read (foo));
296 if (cloog_loop_domain (loop))
297 nb_iterators = cloog_domain_dim (cloog_loop_domain (loop)) - nb_parameters ;
298 else
299 nb_iterators = 0 ;
300 /* stride is initialized to 1. */
301 value_init_c (loop->stride);
302 value_set_si (loop->stride, 1);
303 /* included statement block. */
304 statement = cloog_statement_alloc(number+1);
305 cloog_loop_set_block (loop, cloog_block_alloc (statement, 0, NULL, nb_iterators));
306 cloog_loop_set_usr (loop, NULL);
307 /* inner is NULL at beginning. */
308 cloog_loop_set_inner (loop, NULL);
309 /* next element. */
310 cloog_loop_set_next (loop, NULL);
312 /* To read that stupid "0 0 0" line. */
313 while (fgets(s,MAX_STRING,foo) == 0) ;
314 while ((*s=='#' || *s=='\n') || (sscanf(s," %d %d %d",&op1,&op2,&op3)<3))
315 fgets(s,MAX_STRING,foo) ;
317 return loop ;
321 /******************************************************************************
322 * Processing functions *
323 ******************************************************************************/
327 * cloog_loop_malloc function:
328 * This function allocates the memory space for a CloogLoop structure and
329 * sets its fields with default values. Then it returns a pointer to the
330 * allocated space.
331 * - November 21th 2005: first version.
333 CloogLoop * cloog_loop_malloc (void)
335 CloogLoop * loop ;
337 /* Memory allocation for the CloogLoop structure. */
338 loop = (CloogLoop *)malloc(sizeof(CloogLoop)) ;
339 if (loop == NULL)
340 { fprintf(stderr, "[CLooG]ERROR: memory overflow.\n") ;
341 exit(1) ;
343 cloog_loop_leak_up() ;
346 /* We set the various fields with default values. */
347 cloog_loop_set_domain (loop, NULL);
348 cloog_loop_set_block (loop, NULL);
349 cloog_loop_set_usr (loop, NULL);
350 cloog_loop_set_inner (loop, NULL);
351 cloog_loop_set_next (loop, NULL);
352 value_init_c (loop->stride);
353 value_set_si (loop->stride, 1);
355 return loop ;
360 * cloog_loop_alloc function:
361 * This function allocates the memory space for a CloogLoop structure and
362 * sets its fields with those given as input. Then it returns a pointer to the
363 * allocated space.
364 * - October 27th 2001: first version.
365 * - June 22nd 2005: Adaptation for GMP.
366 * - November 21th 2005: use of cloog_loop_malloc.
368 static CloogLoop *
369 cloog_loop_alloc (CloogDomain *domain, Value stride, CloogBlock * block,
370 CloogLoop *inner, CloogLoop *next)
372 CloogLoop * loop ;
374 loop = cloog_loop_malloc() ;
376 cloog_loop_set_domain (loop, domain);
377 cloog_loop_set_block (loop, block);
378 cloog_loop_set_inner (loop, inner);
379 cloog_loop_set_next (loop, next);
380 value_assign (loop->stride, stride);
382 return(loop) ;
387 * cloog_loop_add function:
388 * This function adds a CloogLoop structure (loop) at a given place (now) of a
389 * NULL terminated list of CloogLoop structures. The beginning of this list
390 * is (start). This function updates (now) to (loop), and updates (start) if the
391 * added element is the first one -that is when (start) is NULL-.
392 * - October 28th 2001: first version.
394 static void
395 cloog_loop_add (CloogLoop ** start, CloogLoop ** now, CloogLoop * loop)
397 if (*start == NULL)
399 *start = loop ;
400 *now = *start ;
402 else
404 cloog_loop_set_next (*now, loop);
405 *now = cloog_loop_next (*now);
411 * cloog_loop_add function:
412 * This function adds a CloogLoop structure (loop) at a given place (now) of a
413 * NULL terminated list of CloogLoop structures. The beginning of this list
414 * is (start). This function updates (now) to the end of the loop list (loop),
415 * and updates (start) if the added element is the first one -that is when
416 * (start) is NULL-.
417 * - September 9th 2005: first version.
419 static void
420 cloog_loop_add_list (CloogLoop ** start, CloogLoop ** now, CloogLoop * loop)
422 cloog_loop_add (start, now, loop);
424 while (cloog_loop_next (*now))
425 *now = cloog_loop_next (*now);
430 * cloog_loop_copy function:
431 * This function returns a copy of the CloogLoop structure given as input. In
432 * fact, there is just new allocations for the CloogLoop structures, but their
433 * contents are the same.
434 * - October 28th 2001: first version.
435 * - July 3rd->11th 2003: memory leaks hunt and correction.
437 static CloogLoop *
438 cloog_loop_copy (CloogLoop * source)
439 { CloogLoop * loop ;
440 CloogBlock * block ;
441 CloogDomain * domain ;
443 loop = NULL ;
444 if (source != NULL)
446 domain = cloog_domain_copy (cloog_loop_domain (source));
447 block = cloog_block_copy (cloog_loop_block (source));
448 loop = cloog_loop_alloc(domain,source->stride,block,NULL,NULL) ;
449 cloog_loop_set_usr (loop, cloog_loop_usr (source));
450 cloog_loop_set_inner (loop, cloog_loop_copy (cloog_loop_inner (source)));
451 cloog_loop_set_next (loop, cloog_loop_copy (cloog_loop_next (source)));
453 return(loop) ;
458 * cloog_loop_add_disjoint function:
459 * This function adds some CloogLoop structures at a given place (now) of a
460 * NULL terminated list of CloogLoop structures. The beginning of this list
461 * is (start). (loop) can be an union of polyhedra, this function separates the
462 * union into a list of *disjoint* polyhedra then adds the list. This function
463 * updates (now) to the end of the list and updates (start) if first added
464 * element is the first of the principal list -that is when (start) is NULL-.
465 * (loop) can be freed by this function, basically when its domain is actually
466 * a union of polyhedra, but don't worry, all the useful data are now stored
467 * inside the list (start). We do not use PolyLib's Domain_Disjoint function,
468 * since the number of union components is often higher (thus code size too).
469 * - October 28th 2001: first version.
470 * - November 14th 2001: bug correction (this one was hard to find !).
471 * - July 3rd->11th 2003: memory leaks hunt and correction.
472 * - June 22nd 2005: Adaptation for GMP.
473 * - October 27th 2005: (debug) included blocks were not copied for new loops.
475 static void
476 cloog_loop_add_disjoint (CloogLoop **start, CloogLoop **now, CloogLoop *loop)
477 { Value one ;
478 CloogLoop * sep, * inner ;
479 CloogDomain * domain, * convex, * seen, * seen_before, * temp, * rest ;
480 CloogBlock * block ;
482 value_init_c(one) ;
483 value_set_si(one,1) ;
485 if (cloog_domain_isconvex (cloog_loop_domain (loop)))
486 cloog_loop_add(start,now,loop) ;
487 else
488 { /* Seems useless but may simplify the union expression (PolyLib pb). */
489 convex = cloog_domain_convex(cloog_loop_domain (loop)) ;
490 temp = cloog_domain_difference(convex,cloog_loop_domain (loop)) ;
491 cloog_domain_free(cloog_loop_domain (loop)) ;
492 cloog_loop_set_domain (loop, NULL);
493 domain = cloog_domain_difference(convex,temp) ;
494 cloog_domain_free(convex) ;
495 cloog_domain_free(temp) ;
497 /* We separate the first element of the rest of the union. */
498 rest = cloog_domain_cut_first(domain) ;
500 /* This first element is the first of the list of disjoint polyhedra. */
501 sep = cloog_loop_alloc (domain, one, cloog_loop_block (loop),
502 cloog_loop_inner (loop), NULL);
503 cloog_loop_add(start,now,sep) ;
505 /* If there are other elements, add a loop for each of them. */
506 if (rest != NULL)
507 { /* domain is used by the first element, and we will free 'seen', so... */
508 seen = cloog_domain_copy(domain) ;
510 while ((domain = rest) != NULL)
511 { rest = cloog_domain_cut_first(domain) ;
512 temp = cloog_domain_difference(domain,seen) ;
514 /* Each new loop will have its own life, for instance we can free its
515 * inner loop and included block. Then each one must have its own copy
516 * of both 'inner' and 'block'.
518 inner = cloog_loop_copy (cloog_loop_inner (loop)) ;
519 block = cloog_block_copy (cloog_loop_block (loop)) ;
521 sep = cloog_loop_alloc(temp,one,block,inner,NULL) ;
522 /* temp can be an union too. If so: recursion. */
523 if (cloog_domain_isconvex(temp))
524 cloog_loop_add(start,now,sep) ;
525 else
526 cloog_loop_add_disjoint(start,now,sep) ;
528 seen_before = seen ;
529 if (rest != NULL)
530 seen = cloog_domain_union(seen_before,domain) ;
532 cloog_domain_free(seen_before) ;
533 cloog_domain_free(domain) ;
536 cloog_loop_free_parts(loop,0,0,0,0) ;
538 value_clear_c(one) ;
543 * cloog_loop_disjoint function:
544 * This function returns a list of loops such that each loop with non-convex
545 * domain in the input list (loop) is separated into several loops where the
546 * domains are the components of the union of *disjoint* polyhedra equivalent
547 * to the original non-convex domain. See cloog_loop_add_disjoint comments
548 * for more details.
549 * - September 16th 2005: first version.
551 static CloogLoop *
552 cloog_loop_disjoint (CloogLoop * loop)
553 { CloogLoop *res=NULL, * now=NULL, * next ;
555 /* Because this is often the case, don't waste time ! */
556 if ((loop != NULL) && cloog_domain_isconvex(cloog_loop_domain (loop)))
557 return loop ;
559 while (loop != NULL)
561 next = cloog_loop_next (loop);
562 cloog_loop_set_next (loop, NULL);
563 cloog_loop_add_disjoint(&res,&now,loop) ;
564 loop = next ;
567 return res ;
572 * cloog_loop_restrict function:
573 * This function returns the (loop) in the context of (context): it makes the
574 * intersection between the (loop) domain and the (context), then it returns
575 * a pointer to a new loop, with this intersection as domain.
576 * - nb_par is the number of parameters.
578 * - October 27th 2001: first version.
579 * - June 15th 2005: a memory leak fixed (domain was not freed when empty).
580 * - June 22nd 2005: Adaptation for GMP.
582 static CloogLoop *
583 cloog_loop_restrict(CloogLoop *loop, CloogDomain *context, int nb_par)
584 { int new_dimension ;
585 Value one ;
586 CloogDomain * domain, * extended_context, * new_domain ;
587 CloogLoop * new_loop ;
589 domain = cloog_loop_domain (loop) ;
590 if (cloog_domain_dim(domain) > cloog_domain_dim(context))
591 { new_dimension = cloog_domain_dim(domain) - nb_par ;
592 extended_context = cloog_domain_extend(context,new_dimension,nb_par) ;
593 new_domain = cloog_domain_intersection(extended_context,cloog_loop_domain (loop)) ;
594 cloog_domain_free(extended_context) ;
596 else
597 new_domain = cloog_domain_intersection(context,cloog_loop_domain (loop)) ;
599 if (cloog_domain_isempty(new_domain))
600 { cloog_domain_free(new_domain) ;
601 return(NULL) ;
603 else
604 { value_init_c(one) ;
605 value_set_si(one,1) ;
606 new_loop = cloog_loop_alloc (new_domain, one, cloog_loop_block (loop),
607 cloog_loop_inner (loop), NULL);
608 value_clear_c(one) ;
609 return(new_loop) ;
615 * cloog_loop_project function:
616 * This function returns the projection of (loop) on the (level) first
617 * dimensions (outer loops). It makes the projection of the (loop) domain,
618 * then it returns a pointer to a new loop, with this projection as domain.
619 * - nb_par is the number of parameters.
621 * - October 27th 2001: first version.
622 * - July 3rd->11th 2003: memory leaks hunt and correction.
623 * - June 22nd 2005: Adaptation for GMP.
625 static CloogLoop *
626 cloog_loop_project(CloogLoop * loop, int level, int nb_par)
627 { Value one ;
628 CloogDomain * new_domain ;
629 CloogLoop * new_loop, * copy ;
631 value_init_c(one) ;
632 value_set_si(one,1) ;
634 copy = cloog_loop_alloc(cloog_loop_domain (loop),loop->stride,cloog_loop_block (loop),
635 cloog_loop_inner (loop),NULL) ;
637 new_domain = cloog_domain_project(cloog_loop_domain (loop),level,nb_par) ;
639 new_loop = cloog_loop_alloc(new_domain,one,NULL,copy,NULL) ;
640 value_clear_c(one) ;
642 return(new_loop) ;
647 * cloog_loop_concat function:
648 * This function returns a pointer to the concatenation of the
649 * CloogLoop lists given as input.
650 * - October 28th 2001: first version.
652 static CloogLoop *
653 cloog_loop_concat(CloogLoop * a, CloogLoop * b)
654 { CloogLoop * loop, * temp ;
656 loop = a ;
657 temp = loop ;
658 if (loop != NULL)
660 while (cloog_loop_next (temp))
661 temp = cloog_loop_next (temp);
663 cloog_loop_set_next (temp, b);
665 else
666 loop = b ;
668 return(loop) ;
673 * cloog_loop_separate function:
674 * This function implements the Quillere algorithm for separation of multiple
675 * loops: for a given set of polyhedra (loop), it computes a set of disjoint
676 * polyhedra such that the unions of these sets are equal, and returns this set.
677 * - October 28th 2001: first version.
678 * - November 14th 2001: elimination of some unused blocks.
679 * - August 13th 2002: (debug) in the case of union of polyhedra for one
680 * loop, redundant constraints are fired.
681 * - July 3rd->11th 2003: memory leaks hunt and correction.
682 * - June 22nd 2005: Adaptation for GMP.
683 * - October 16th 2005: Removal of the non-shared constraint elimination when
684 * there is only one loop in the list (seems to work
685 * without now, DomainSimplify may have been improved).
686 * The problem was visible with test/iftest2.cloog.
688 static CloogLoop * cloog_loop_separate(CloogLoop * loop)
689 { int first, lazy_equal=0, lazy_disjoint=0 ;
690 Value one ;
691 CloogLoop * new_loop, * new_inner, * res, * now, * temp, * Q,
692 * inner, * old /*, * previous, * next*/ ;
693 CloogDomain * UQ, * old_UQ, * domain ;
695 if (loop == NULL)
696 return NULL ;
698 if (cloog_loop_next (loop) == NULL)
699 return cloog_loop_disjoint (loop);
701 value_init_c(one) ;
702 value_set_si(one,1) ;
704 UQ = cloog_domain_copy(cloog_loop_domain (loop)) ;
705 domain = cloog_domain_copy(cloog_loop_domain (loop)) ;
706 res = cloog_loop_alloc(domain,one,cloog_loop_block (loop),cloog_loop_inner (loop),NULL) ;
708 old = loop ;
709 while ((loop = cloog_loop_next (loop)))
711 temp = NULL ;
712 first = 1 ;
714 /* For all Q, add Q-loop associated with the blocks of Q alone,
715 * and Q inter loop associated with the blocks of Q and loop.
717 Q = res ;
718 while (Q != NULL)
719 { if (cloog_loop_block (Q) == NULL)
720 { /* Add (Q inter loop). */
721 if((lazy_disjoint=cloog_domain_lazy_disjoint(cloog_loop_domain (Q),cloog_loop_domain (loop))))
722 domain = NULL ;
723 else
724 { if ((lazy_equal = cloog_domain_lazy_equal(cloog_loop_domain (Q),cloog_loop_domain (loop))))
725 domain = cloog_domain_copy(cloog_loop_domain (Q)) ;
726 else
727 domain = cloog_domain_intersection(cloog_loop_domain (Q),cloog_loop_domain (loop)) ;
729 if (!cloog_domain_isempty(domain))
730 { new_inner = cloog_loop_concat(cloog_loop_copy(cloog_loop_inner (Q)),
731 cloog_loop_copy(cloog_loop_inner (loop))) ;
732 new_loop = cloog_loop_alloc(domain,one,NULL,new_inner,NULL) ;
733 cloog_loop_add_disjoint(&temp,&now,new_loop) ;
735 else
736 cloog_domain_free(domain) ;
739 /* Add (Q - loop). */
740 if (lazy_disjoint)
741 domain = cloog_domain_copy(cloog_loop_domain (Q)) ;
742 else
743 { if (lazy_equal)
744 domain = cloog_domain_empty(cloog_domain_dim(cloog_loop_domain (Q))) ;
745 else
746 domain = cloog_domain_difference(cloog_loop_domain (Q),cloog_loop_domain (loop)) ;
749 if (!cloog_domain_isempty(domain))
750 { new_loop = cloog_loop_alloc(domain,one,NULL,cloog_loop_inner (Q),NULL) ;
751 cloog_loop_add_disjoint(&temp,&now,new_loop) ;
753 else
754 { cloog_domain_free(domain) ;
755 /* If cloog_loop_inner (Q) is no more useful, we can free it. */
756 inner = cloog_loop_inner (Q) ;
757 cloog_loop_set_inner (Q, NULL);
758 if (first) /* For the first Q, inner is also cloog_loop_inner (old). */
759 cloog_loop_set_inner (old, NULL);
760 cloog_loop_free(inner) ;
763 Q = cloog_loop_next (Q) ;
766 /* Add loop-UQ associated with the blocks of loop alone.*/
767 if (cloog_domain_lazy_disjoint(cloog_loop_domain (loop),UQ))
768 domain = cloog_domain_copy(cloog_loop_domain (loop)) ;
769 else
770 { if (cloog_domain_lazy_equal(cloog_loop_domain (loop),UQ))
771 domain = cloog_domain_empty(cloog_domain_dim(UQ)) ;
772 else
773 domain = cloog_domain_difference(cloog_loop_domain (loop),UQ) ;
776 if (!cloog_domain_isempty(domain))
777 { new_loop = cloog_loop_alloc(domain,one,NULL,cloog_loop_inner (loop),NULL) ;
778 cloog_loop_add_disjoint(&temp,&now,new_loop) ;
780 else
781 { cloog_domain_free(domain) ;
782 /* If cloog_loop_inner (loop) is no more useful, we can free it. */
783 cloog_loop_free(cloog_loop_inner (loop)) ;
786 cloog_loop_set_inner (loop, NULL);
788 old_UQ = UQ ;
789 if (cloog_loop_next (loop))
790 UQ = cloog_domain_union(UQ,cloog_loop_domain (loop)) ;
792 cloog_domain_free(old_UQ) ;
793 cloog_loop_free_parts(res,1,0,0,1) ;
795 first = 0 ;
796 res = temp ;
798 cloog_loop_free_parts(old,1,0,0,1) ;
799 value_clear_c(one) ;
801 return(res) ;
806 * cloog_loop_merge_list
807 * Merge two lists of CloogLoops. The new list contains the
808 * elements of the two lists in the same order, but they may
809 * be interleaved.
810 * In particular, if the elements of a and b are ordered
811 * according to the inner loops of the order list, then so are the elements
812 * in the new list.
814 static CloogLoop *cloog_loop_merge_inner_list(CloogLoop *a, CloogLoop *b,
815 CloogLoop *order)
817 CloogLoop *loop, **next;
818 next = &loop;
820 for ( ; order && (a||b); order = cloog_loop_next (order)) {
821 if (a && cloog_loop_block (cloog_loop_inner (order)) == cloog_loop_block (a)) {
822 *next = a;
823 a = cloog_loop_next (a);
824 next = cloog_loop_next_addr (*next);
825 continue;
827 if (b && cloog_loop_block (cloog_loop_inner (order)) == cloog_loop_block (b)) {
828 *next = b;
829 b = cloog_loop_next (b);
830 next = cloog_loop_next_addr (*next);
833 return loop;
837 * cloog_loop_merge function:
838 * This function is the 'soft' version of loop_separate if we are looking for
839 * a code much simpler (and less efficicient). Here we merge loops if they have
840 * common parts in the iteration space (if the intersection of their domains is
841 * not empty), and let them isolated otherwise. This function returns the new
842 * CloogLoop list.
843 * - October 29th 2001: first version.
844 * - July 3rd->11th 2003: memory leaks hunt and correction.
845 * - June 22nd 2005: Adaptation for GMP.
847 static CloogLoop * cloog_loop_merge(CloogLoop * loop, int nb_par, CloogOptions * options)
848 { Value one ;
849 CloogLoop * res, * merge, * now, * Q, * P, * new_inner, * next, * old ;
850 CloogDomain * new_domain, * temp ;
852 if ((loop == NULL) || (cloog_loop_next (loop) == NULL))
853 return loop ;
855 value_init_c(one) ;
856 value_set_si(one,1) ;
858 /* First loop is added to the target list. */
859 res = cloog_loop_alloc (cloog_loop_domain (loop), one,
860 cloog_loop_block (loop), cloog_loop_inner (loop), NULL);
861 old = loop ;
862 /* Now the domain is in 'res' and it will be freed. */
863 cloog_loop_set_domain (loop, NULL);
865 /* And one by one, we see if we have to merge or to add the other loops. */
866 while ((loop = cloog_loop_next (loop)))
868 merge = NULL ;
869 P = cloog_loop_alloc (cloog_loop_domain (loop), one,
870 cloog_loop_block (loop), cloog_loop_inner (loop), NULL) ;
871 Q = res ;
872 /* Now the domain is in 'P' and it will be freed. */
873 cloog_loop_set_domain (loop, NULL);
875 /* For each loop in the target list, if the intersection with the new loop
876 * is empty, we can add the new loop directly, otherwise, we can merge then
877 * add the fusion.
879 while (Q != NULL)
881 temp = cloog_domain_intersection(cloog_loop_domain (Q),cloog_loop_domain (P)) ;
882 next = cloog_loop_next (Q) ;
883 if (cloog_domain_isempty(temp))
884 { cloog_domain_free(temp) ;
885 cloog_loop_add_disjoint(&merge,&now,Q) ;
887 else
888 { cloog_domain_free(temp) ;
889 new_inner = cloog_loop_merge_inner_list(cloog_loop_inner (Q), cloog_loop_inner (P), old);
890 temp = cloog_domain_union(cloog_loop_domain (P),cloog_loop_domain (Q)) ;
891 if (options->sh)
892 new_domain = cloog_domain_simple_convex(temp, nb_par);
893 else
894 new_domain = cloog_domain_convex(temp);
895 cloog_domain_free(temp) ;
896 /* Q and P are no more used (but their content yes !).*/
897 cloog_loop_free_parts(P,1,0,0,0) ;
898 cloog_loop_free_parts(Q,1,0,0,0) ;
899 P = cloog_loop_alloc(new_domain,one,NULL,new_inner,NULL) ;
901 Q = next ;
904 /* If there was merging, add it, otherwise add the loop lonely.
905 * DEBUG : ici pas besoin de s'assurer que cloog_loop_next (P) est NULL (possible que
906 * non si pas de fusion) car le dernier loop etudie a cloog_loop_next (loop) = NULL.
908 cloog_loop_add_disjoint(&merge,&now,P) ;
909 res = merge ;
911 cloog_loop_free_parts(old,0,0,0,1) ;
912 value_clear_c(one) ;
914 return (res);
919 * cloog_loop_sort function:
920 * Adaptation from LoopGen 0.4 by F. Quillere. This function sorts a list of
921 * parameterized disjoint polyhedra, in order to not have lexicographic order
922 * violation (see Quillere paper).
923 * - September 16th 2005: inclusion of cloog_loop_number (October 29th 2001).
925 static CloogLoop * cloog_loop_sort(CloogLoop * loop, int level, int nb_par)
926 { CloogLoop * res, * now, * temp, ** loop_array ;
927 CloogDomain ** pols ;
928 int i, nb_loops=0, * permut ;
930 /* We will need to know how many loops are in the list. */
931 temp = loop ;
932 while (temp != NULL)
934 nb_loops ++ ;
935 temp = cloog_loop_next (temp) ;
938 /* If there is only one loop, it's the end. */
939 if (nb_loops == 1)
940 return(loop) ;
942 /* We have to allocate memory for some useful components:
943 * - loop_array: the loop array,
944 * - pols: the array of domains to sort,
945 * - permut: will give us a possible sort (maybe not the only one).
947 loop_array = (CloogLoop **)malloc(nb_loops*sizeof(CloogLoop *)) ;
948 pols = (CloogDomain **) malloc (nb_loops * sizeof (CloogDomain *)) ;
949 permut = (int *)malloc(nb_loops*sizeof(int)) ;
951 /* We fill up the loop and domain arrays. */
952 for (i=0;i<nb_loops;i++,loop=cloog_loop_next (loop))
954 loop_array[i] = loop ;
955 pols[i] = cloog_loop_domain (loop_array[i]) ;
958 /* cloog_domain_sort will fill up permut. */
959 cloog_domain_sort(pols,nb_loops,level,nb_par,permut) ;
961 /* With permut and loop_array we build the sorted list. */
962 res = NULL ;
963 for (i=0;i<nb_loops;i++)
964 { /* To avoid pointer looping... loop_add will rebuild the list. */
965 cloog_loop_set_next (loop_array[permut[i]-1], NULL);
966 cloog_loop_add(&res,&now,loop_array[permut[i]-1]) ;
969 free(permut) ;
970 free(pols) ;
971 free(loop_array) ;
973 return res;
978 * cloog_loop_nest function:
979 * This function changes the loop list in such a way that we have no more than
980 * one dimension added by level. It returns an equivalent loop list with
981 * this property.
982 * - October 29th 2001: first version.
983 * - July 3rd->11th 2003: memory leaks hunt and correction.
984 * - June 22nd 2005: Adaptation for GMP.
985 * - November 21th 2005: (debug) now OK when cloog_loop_restrict returns NULL.
987 static CloogLoop * cloog_loop_nest(CloogLoop *loop, CloogDomain *context, int level, int nb_par)
988 { int l ;
989 Value one ;
990 CloogLoop * p, * temp, * res, * now, * next ;
991 CloogDomain * new_domain ;
993 value_init_c(one) ;
994 value_set_si(one,1) ;
996 res = NULL ;
997 /* Each domain is changed by its intersection with the context. */
998 while (loop != NULL)
999 { p = cloog_loop_restrict(loop,context,nb_par) ;
1000 next = cloog_loop_next (loop) ;
1002 if (p != NULL)
1003 { cloog_loop_free_parts(loop,1,0,0,0) ;
1005 temp = cloog_loop_alloc(cloog_loop_domain (p),one,cloog_loop_block (p),cloog_loop_inner (p),NULL) ;
1007 /* If the intersection dimension is too big, we make projections smaller
1008 * and smaller, and each projection includes the preceding projection
1009 * (thus, in the target list, dimensions are added one by one).
1011 if ((((int) cloog_domain_dim (cloog_loop_domain (p))) - nb_par) > level)
1012 for (l=cloog_domain_dim(cloog_loop_domain (p))-nb_par-1;l>=level;l--)
1013 { new_domain = cloog_domain_project(cloog_loop_domain (p),l,nb_par) ;
1014 temp = cloog_loop_alloc(new_domain,one,NULL,temp,NULL) ;
1017 /* p is no more useful (but its content yes !). */
1018 cloog_loop_free_parts(p,0,0,0,0) ;
1020 cloog_loop_add(&res,&now,temp) ;
1022 else
1023 cloog_loop_free_parts(loop,1,1,1,0) ;
1025 loop = next ;
1027 value_clear_c(one) ;
1029 return(res) ;
1034 * cloog_loop_stride_1 function:
1035 * This function will find the stride of a loop for the iterator at the column
1036 * number 'level' in the constraint matrix. It will update the lower bound of
1037 * the iterator accordingly. Basically, the function will try to find in the
1038 * inner loops a common condition on this iterator for the inner loop iterators
1039 * to be integral. For instance, let us consider a loop with the iterator i,
1040 * the iteration domain -4<=i<=n, and its two inner loops with the iterator j.
1041 * The first inner loop has the constraint 3j=i, and the second one has the
1042 * constraint 6j=i. Then the common constraint on i for j to be integral is
1043 * i%3=0, the stride for i is 3. Lastly, we have to find the new lower bound
1044 * for i: the first value satisfying the common constraint: -3. At the end, the
1045 * iteration domain for i is -3<=i<=n and the stride for i is 3.
1046 * - loop is the loop including the iteration domain of the considered iterator,
1047 * - level is the column number of the iterator in the matrix of contraints.
1049 * - June 29th 2003: first version (work in progress since June 26th 2003).
1050 * - July 14th 2003: simpler version.
1051 * - June 22nd 2005: Adaptation for GMP (from S. Verdoolaege's 0.12.1 version).
1053 static void cloog_loop_stride_1 (CloogLoop * loop, int level, int nb_par)
1054 { int first_search ;
1055 Value stride, ref_offset, offset, potential, lower ;
1056 CloogLoop * inner ;
1058 value_init_c(stride) ;
1059 value_init_c(ref_offset) ;
1060 value_init_c(offset) ;
1061 value_init_c(potential) ;
1062 value_init_c(lower) ;
1064 value_set_si(ref_offset,0) ;
1065 value_set_si(offset,0) ;
1066 value_set_si(lower,0) ;
1068 /* Default stride. */
1069 value_set_si(stride,1) ;
1070 first_search = 1 ;
1071 inner = cloog_loop_inner (loop) ;
1073 if (cloog_domain_integral_lowerbound(cloog_loop_domain (loop),level,&lower))
1074 while (inner != NULL)
1075 { /* If the minimun stride has not been found yet, find the stride. */
1076 if ((first_search) || (value_notone_p(stride)))
1077 { cloog_domain_stride(cloog_loop_domain (inner),level,nb_par,&potential,&offset) ;
1078 if (value_notone_p(potential) && (!first_search))
1079 { /* Offsets must be the same for common stride. */
1080 Gcd(potential,stride,&stride) ;
1081 value_modulus(offset, offset, stride);
1082 value_modulus(ref_offset, ref_offset, stride);
1083 if (value_ne(offset,ref_offset))
1084 value_set_si(stride, 1);
1086 else
1087 { value_assign(stride,potential) ;
1088 value_assign(ref_offset,offset) ;
1091 first_search = 0 ;
1094 inner = cloog_loop_next (inner) ;
1097 /* Update the values if necessary. */
1098 if (value_notone_p(stride))
1099 { /* Update the stride value. */
1100 value_assign (loop->stride, stride);
1101 /* The new lower bound l' is such that
1102 * (l' + offset) % s = 0 and l <= l' <= l+(s-1)
1103 * Let l' = k s - offset, then
1104 * k s - offset <= l + (s-1) <= k s - offset + (s-1)
1105 * Or l' = floor((l+offset+(s-1))/s) * s - offset
1106 * = (floor((l+offset-1)/s) + 1) * s - offset
1108 value_addto(lower, lower, offset);
1109 value_decrement(lower, lower);
1110 value_pdivision(lower, lower, stride);
1111 value_increment(lower, lower);
1112 value_multiply(lower, lower, stride);
1113 value_subtract(lower, lower, offset);
1114 cloog_domain_lowerbound_update(cloog_loop_domain (loop),level,lower) ;
1117 value_clear_c(stride) ;
1118 value_clear_c(ref_offset) ;
1119 value_clear_c(offset) ;
1120 value_clear_c(potential) ;
1121 value_clear_c(lower) ;
1126 * cloog_loop_stop function:
1127 * This function implements the 'stop' option : each domain of each loop
1128 * in the list 'loop' is replaced by 'context'. 'context' should be the
1129 * domain of the outer loop. By using this method, there are no more dimensions
1130 * to scan and the simplification step will automaticaly remove the domains
1131 * since they are the same as the corresponding contexts. The effect of this
1132 * function is to stop the code generation at the level this function is called,
1133 * the resulting code do not consider the next dimensions.
1134 * - January 11th 2005: first version.
1136 static CloogLoop * cloog_loop_stop(CloogLoop * loop, CloogDomain * context)
1137 { if (loop == NULL)
1138 return NULL ;
1139 else
1141 cloog_domain_free(cloog_loop_domain (loop)) ;
1142 cloog_loop_set_domain (loop, cloog_domain_copy (context));
1143 cloog_loop_set_next (loop, cloog_loop_stop (cloog_loop_next (loop), context)) ;
1146 return loop ;
1151 * cloog_loop_scalar_gt function:
1152 * This function returns 1 if loop 'l1' is greater than loop 'l2' for the
1153 * scalar dimension vector that begins at dimension 'scalar', 0 otherwise. What
1154 * we want to know is whether a loop is scheduled before another one or not.
1155 * This function solves the problem when the considered dimension for scheduling
1156 * is a scalar dimension. Since there may be a succession of scalar dimensions,
1157 * this function will reason about the vector of scalar dimension that begins
1158 * at dimension 'level+scalar' and finish to the first non-scalar dimension.
1159 * \param l1 Loop to be compared with l2.
1160 * \param l2 Loop to be compared with l1.
1161 * \param level Current non-scalar dimension.
1162 * \param scaldims Boolean array saying whether a dimension is scalar or not.
1163 * \param nb_scattdims Size of the scaldims array.
1164 * \param scalar Current scalar dimension.
1165 * \return 1 if (l1 > l2), 0 otherwise.
1167 * - September 9th 2005: first version.
1168 * - October 15nd 2007: now "greater than" instead of "greater or equal".
1170 static int cloog_loop_scalar_gt(CloogLoop *l1, CloogLoop *l2, int level, int *scaldims, int scalar)
1172 while ((scalar < cloog_block_nb_scaldims (cloog_loop_block (cloog_loop_inner (l1))))
1173 && scaldims[level+scalar-1])
1175 if (value_gt (cloog_loop_block (cloog_loop_inner (l1))->scaldims[scalar],
1176 cloog_loop_block (cloog_loop_inner (l2))->scaldims[scalar]))
1177 scalar ++ ;
1178 else
1179 return 0 ;
1181 return 1 ;
1186 * cloog_loop_scalar_eq function:
1187 * This function returns 1 if loop 'l1' is equal to loop 'l2' for the scalar
1188 * dimension vector that begins at dimension 'scalar', 0 otherwise. What we want
1189 * to know is whether two loops are scheduled for the same time or not.
1190 * This function solves the problem when the considered dimension for scheduling
1191 * is a scalar dimension. Since there may be a succession of scalar dimensions,
1192 * this function will reason about the vector of scalar dimension that begins
1193 * at dimension 'level+scalar' and finish to the first non-scalar dimension.
1194 * - l1 and l2 are the loops to compare,
1195 * - level is the current non-scalar dimension,
1196 * - scaldims is the boolean array saying whether a dimension is scalar or not,
1197 * - scalar is the current scalar dimension.
1199 * - September 9th 2005 : first version.
1201 static int cloog_loop_scalar_eq(CloogLoop * l1, CloogLoop * l2, int level, int *scaldims, int scalar)
1203 while ((scalar < cloog_block_nb_scaldims (cloog_loop_block (cloog_loop_inner (l1))))
1204 && scaldims[level+scalar-1])
1206 if (value_eq (cloog_loop_block (cloog_loop_inner (l1))->scaldims[scalar],
1207 cloog_loop_block (cloog_loop_inner (l2))->scaldims[scalar]))
1208 scalar ++ ;
1209 else
1210 return 0 ;
1212 return 1 ;
1217 * cloog_loop_scalar_sort function:
1218 * This function sorts a linked list of loops (loop) with respect to the
1219 * scalar dimension vector that begins at dimension 'scalar'. Since there may
1220 * be a succession of scalar dimensions, this function will reason about the
1221 * vector of scalar dimension that begins at dimension 'level+scalar' and
1222 * finish to the first non-scalar dimension.
1223 * \param loop Loop list to sort.
1224 * \param level Current non-scalar dimension.
1225 * \param scaldims Boolean array saying whether a dimension is scalar or not.
1226 * \param scalar Current scalar dimension.
1227 * \return A pointer to the sorted list.
1229 * - July 2nd 2005: first developments.
1230 * - September 2nd 2005: first version.
1231 * - October 15nd 2007: complete rewrite to remove bugs, now a bubble sort.
1233 static CloogLoop * cloog_loop_scalar_sort(CloogLoop * loop, int level, int *scaldims, int scalar)
1234 { int ok ;
1235 CloogLoop **current;
1237 do {
1238 ok = 1;
1239 for (current = &loop; cloog_loop_next (*current); current = cloog_loop_next_addr (*current)) {
1240 CloogLoop *next = cloog_loop_next (*current);
1241 if (cloog_loop_scalar_gt(*current,next,level,scaldims,scalar)) {
1242 ok = 0;
1243 cloog_loop_set_next (*current, cloog_loop_next (next));
1244 cloog_loop_set_next (next, *current);
1245 *current = next;
1248 } while (!ok);
1250 return loop ;
1255 * cloog_loop_generate_backtrack function:
1256 * adaptation from LoopGen 0.4 by F. Quillere. This function implements the
1257 * backtrack of the Quillere et al. algorithm (see the Quillere paper).
1258 * It eliminates unused iterations of the current level for the new one. See the
1259 * example called linearity-1-1 example with and without this part for an idea.
1260 * - October 26th 2001: first version in cloog_loop_generate_general.
1261 * - July 31th 2002: (debug) no more parasite loops (REALLY hard !).
1262 * - October 30th 2005: extraction from cloog_loop_generate_general.
1264 static CloogLoop *
1265 cloog_loop_generate_backtrack (CloogLoop * loop, int level, int nb_par)
1266 { Value one ;
1267 CloogDomain * domain ;
1268 CloogLoop * now, * now2, * next, * next2, * end, * temp, * l, * inner,
1269 * new_loop ;
1271 value_init_c(one) ;
1272 value_set_si(one,1) ;
1274 temp = loop ;
1275 loop = NULL ;
1277 while (temp != NULL)
1278 { l = NULL ;
1279 inner = cloog_loop_inner (temp) ;
1281 while (inner != NULL)
1283 next = cloog_loop_next (inner) ;
1284 /* This 'if' and its first part is the debug of july 31th 2002. */
1285 if (cloog_loop_block (inner))
1287 end = cloog_loop_alloc (cloog_loop_domain (inner), one,
1288 cloog_loop_block (inner), NULL, NULL);
1289 domain = cloog_domain_copy(cloog_loop_domain (temp)) ;
1290 new_loop = cloog_loop_alloc(domain,one,NULL,end,NULL) ;
1292 else
1293 new_loop = cloog_loop_project(inner,level,nb_par) ;
1295 cloog_loop_free_parts(inner,0,0,0,0) ;
1296 cloog_loop_add(&l,&now2,new_loop) ;
1297 inner = next ;
1300 cloog_loop_set_inner (temp, NULL);
1302 if (l != NULL)
1303 { l = cloog_loop_separate(l) ;
1304 l = cloog_loop_sort(l,level,nb_par) ;
1305 while (l != NULL)
1307 value_assign (l->stride, temp->stride);
1308 cloog_loop_add(&loop,&now,l) ;
1309 l = cloog_loop_next (l) ;
1312 next2 = cloog_loop_next (temp) ;
1313 cloog_loop_free_parts(temp,1,0,0,0) ;
1314 temp = next2 ;
1317 value_clear_c(one) ;
1319 return loop ;
1324 * cloog_loop_generate_general function:
1325 * Adaptation from LoopGen 0.4 by F. Quillere. This function implements the
1326 * Quillere algorithm for polyhedron scanning from step 3 to 5.
1327 * (see the Quillere paper).
1328 * - loop is the loop for which we have to generate a scanning code,
1329 * - level is the current non-scalar dimension,
1330 * - scalar is the current scalar dimension,
1331 * - scaldims is the boolean array saying whether a dimension is scalar or not,
1332 * - nb_scattdims is the size of the scaldims array,
1333 * - nb_par is the number of parameters,
1334 * - options are the general code generation options.
1336 * - October 26th 2001: first version.
1337 * - July 3rd->11th 2003: memory leaks hunt and correction.
1338 * - June 22nd 2005: Adaptation for GMP.
1339 * - September 2nd 2005: The function have been cutted out in two pieces:
1340 * cloog_loop_generate and this one, in order to handle
1341 * the scalar dimension case more efficiently with
1342 * cloog_loop_generate_scalar.
1343 * - November 15th 2005: (debug) the result of the cloog_loop_generate call may
1344 * be a list of polyhedra (especially if stop option is
1345 * used): cloog_loop_add_list instead of cloog_loop_add.
1347 static CloogLoop * cloog_loop_generate_general(CloogLoop *loop, int level, int scalar,
1348 int *scaldims, int nb_scattdims, int nb_par,
1349 CloogOptions *options)
1350 { Value one ;
1351 CloogLoop * res, * now, * temp, * l, * new_loop, * inner, * now2, * end,
1352 * next, * into ;
1353 CloogDomain * domain ;
1355 /* 3. Separate all projections into disjoint polyhedra. */
1356 res = ((options->f > level+scalar) || (options->f < 0)) ?
1357 cloog_loop_merge(loop, nb_par, options) : cloog_loop_separate(loop);
1359 /* 3b. -correction- sort the loops to determine their textual order. */
1360 res = cloog_loop_sort(res,level,nb_par) ;
1362 value_init_c(one) ;
1363 value_set_si(one,1) ;
1365 /* 4. Recurse for each loop with the current domain as context. */
1366 temp = res ;
1367 res = NULL ;
1368 if ((level+scalar < options->l) || (options->l < 0))
1369 while(temp != NULL)
1370 { if (options->strides)
1371 cloog_loop_stride_1 (temp,level,nb_par) ;
1372 inner = cloog_loop_inner (temp) ;
1373 domain = cloog_loop_domain (temp) ;
1374 into = NULL ;
1375 while (inner != NULL)
1376 { /* 4b. -ced- recurse for each sub-list of non terminal loops. */
1377 if ((int) cloog_domain_dim(cloog_loop_domain (inner)) > (level + nb_par))
1378 { end = inner ;
1379 while ((cloog_loop_next (end)) &&
1380 ((int) cloog_domain_dim (cloog_loop_domain (cloog_loop_next (end))) > (level + nb_par)))
1381 end = cloog_loop_next (end) ;
1383 next = cloog_loop_next (end) ;
1384 cloog_loop_set_next (end, NULL);
1386 l = cloog_loop_generate(inner,domain,level+1,scalar,
1387 scaldims,nb_scattdims,nb_par,options) ;
1389 if (l != NULL)
1390 cloog_loop_add_list(&into,&now,l) ;
1392 inner = next ;
1394 else
1395 { cloog_loop_add(&into,&now,inner) ;
1396 inner = cloog_loop_next (inner) ;
1399 next = cloog_loop_next (temp) ;
1400 cloog_loop_set_next (temp, NULL);
1401 cloog_loop_set_inner (temp, into);
1402 cloog_loop_add(&res,&now2,temp) ;
1403 temp = next ;
1405 else
1406 while (temp != NULL)
1407 { next = cloog_loop_next (temp) ;
1408 l = cloog_loop_nest(cloog_loop_inner (temp),cloog_loop_domain (temp),level+1,nb_par) ;
1409 new_loop = cloog_loop_alloc(cloog_loop_domain (temp),one,NULL,l,NULL) ;
1410 cloog_loop_set_inner (temp, NULL);
1411 cloog_loop_set_next (temp, NULL);
1412 cloog_loop_free_parts(temp,0,0,0,0) ;
1413 cloog_loop_add(&res,&now,new_loop) ;
1414 temp = next ;
1417 /* 5. eliminate unused iterations of the current level for the new one. See
1418 * the example called linearity-1-1 example with and without this part
1419 * for an idea.
1421 if ((!options->nobacktrack) &&
1422 ((level+scalar < options->l) || (options->l < 0)) &&
1423 ((options->f <= level+scalar) && !(options->f < 0)))
1424 res = cloog_loop_generate_backtrack(res,level,nb_par) ;
1426 /* Pray for my new paper to be accepted somewhere since the following stuff
1427 * is really amazing :-) !
1428 * Far long later: The paper has been accepted to PACT 2004 :-))). But there
1429 * are still some bugs and I have no time to fix them. Thus now you have to
1430 * pray for me to get an academic position for that really amazing stuff :-) !
1431 * Later again: OK, I get my academic position, but still I have not enough
1432 * time to fix and clean this part... Pray again :-) !!!
1434 /* res = cloog_loop_unisolate(res,context,level,nb_par) ;*/
1436 value_clear_c(one) ;
1437 return(res) ;
1442 * cloog_loop_generate_scalar function:
1443 * This function applies the simplified code generation scheme in the trivial
1444 * case of scalar dimensions. When dealing with scalar dimensions, there is
1445 * no need of costly polyhedral operations for separation or sorting: sorting
1446 * is a question of comparing scalar vectors and separation amounts to consider
1447 * only loops with the same scalar vector for the next step of the code
1448 * generation process. This function achieves the separation/sorting process
1449 * for the vector of scalar dimension that begins at dimension 'level+scalar'
1450 * and finish to the first non-scalar dimension.
1451 * - loop is the loop for which we have to generate a scanning code,
1452 * - level is the current non-scalar dimension,
1453 * - scalar is the current scalar dimension,
1454 * - scaldims is the boolean array saying whether a dimension is scalar or not,
1455 * - nb_scattdims is the size of the scaldims array,
1456 * - nb_par is the number of parameters,
1457 * - options are the general code generation options.
1459 * - September 2nd 2005: First version.
1461 static CloogLoop *
1462 cloog_loop_generate_scalar(CloogLoop *loop, int level, int scalar,
1463 int *scaldims, int nb_scattdims, int nb_par,
1464 CloogOptions *options)
1465 { CloogLoop * res, * now, * temp, * l, * end, * next, * ref ;
1467 /* We sort the loop list with respect to the current scalar vector. */
1468 res = cloog_loop_scalar_sort(loop,level,scaldims,scalar) ;
1470 temp = res ;
1471 res = NULL ;
1472 while (temp != NULL)
1473 { /* Then we will appy the general code generation process to each sub-list
1474 * of loops with the same scalar vector.
1476 end = temp ;
1477 ref = temp ;
1479 while ((cloog_loop_next (end)) &&
1480 cloog_loop_scalar_eq(ref,cloog_loop_next (end),level,scaldims,scalar))
1481 end = cloog_loop_next (end) ;
1483 next = cloog_loop_next (end) ;
1484 cloog_loop_set_next (end, NULL);
1486 /* For the next dimension, scalar value is updated by adding the scalar
1487 * vector size, which is stored at scaldims[level+scalar-1].
1489 l = cloog_loop_generate_general(temp,level,
1490 scalar+scaldims[level+scalar-1],
1491 scaldims,nb_scattdims,nb_par,options) ;
1493 if (l != NULL)
1494 cloog_loop_add_list(&res,&now,l) ;
1496 temp = next ;
1499 return res ;
1504 * cloog_loop_generate function:
1505 * Adaptation from LoopGen 0.4 by F. Quillere. This function implements the
1506 * Quillere algorithm for polyhedron scanning from step 1 to 2.
1507 * (see the Quillere paper).
1508 * - loop is the loop for which we have to generate a scanning code,
1509 * - context is the context of the current loop (constraints on parameter and/or
1510 * on outer loop counters),
1511 * - level is the current non-scalar dimension,
1512 * - scalar is the current scalar dimension,
1513 * - scaldims is the boolean array saying whether a dimension is scalar or not,
1514 * - nb_scattdims is the size of the scaldims array,
1515 * - nb_par is the number of parameters,
1516 * - options are the general code generation options.
1518 * - October 26th 2001: first version.
1519 * - July 3rd->11th 2003: memory leaks hunt and correction.
1520 * - June 15th 2005: a memory leak fixed (loop was not entirely freed when
1521 * the result of cloog_loop_restrict was NULL).
1522 * - June 22nd 2005: Adaptation for GMP.
1523 * - September 2nd 2005: The function have been cutted out in two pieces:
1524 * cloog_loop_generate and this one, in order to handle
1525 * the scalar dimension case more efficiently with
1526 * cloog_loop_generate_scalar.
1527 * - November 15th 2005: (debug) Condition for stop option no more take care of
1528 * further scalar dimensions.
1530 CloogLoop * cloog_loop_generate(CloogLoop *loop, CloogDomain *context, int level,
1531 int scalar, int *scaldims, int nb_scattdims, int nb_par,
1532 CloogOptions *options)
1533 { CloogLoop * res, * now, * temp, * next, * old ;
1535 /* If the user asked to stop code generation at this level, let's stop. */
1536 if ((options->stop >= 0) && (level+scalar >= options->stop+1))
1537 return cloog_loop_stop(loop,context) ;
1539 res = NULL ;
1541 /* 1. Replace each polyhedron by its intersection with the context.
1542 * 2. Compute the projection of each polyhedron onto the outermost
1543 * loop variable and the parameters.
1545 while (loop != NULL)
1547 next = cloog_loop_next (loop) ;
1548 temp = cloog_loop_restrict(loop,context,nb_par) ;
1550 if (temp != NULL)
1551 { old = temp ;
1552 temp = cloog_loop_project(temp,level,nb_par) ;
1553 cloog_loop_free_parts(old,0,0,0,0) ;
1554 cloog_loop_add(&res,&now,temp) ;
1555 cloog_loop_free_parts(loop,1,0,0,0) ;
1557 else
1559 cloog_loop_set_next (loop, NULL);
1560 cloog_loop_free(loop) ;
1563 loop = next ;
1565 if (res == NULL)
1566 return NULL ;
1568 /* To save both time and memory, we switch here depending on whether the
1569 * current dimension is scalar (simplified processing) or not (general
1570 * processing).
1572 if ((level+scalar <= nb_scattdims) && (scaldims[level+scalar-1]))
1573 res = cloog_loop_generate_scalar(res,level,scalar,
1574 scaldims,nb_scattdims,nb_par,options) ;
1575 else
1576 res = cloog_loop_generate_general(res,level,scalar,
1577 scaldims,nb_scattdims,nb_par,options) ;
1579 return res ;
1584 * cloog_loop_simplify function:
1585 * This function implements the part 6. of the Quillere algorithm, it
1586 * recursively simplifies each loop in the context of the preceding loop domain.
1587 * It returns a pointer to the simplified loop list.
1588 * The cloog_domain_simplify (DomainSimplify) behaviour is really bad with
1589 * polyhedra union and some really awful sidesteppings were written, I plan
1590 * to solve that...
1591 * - October 31th 2001: first version.
1592 * - July 3rd->11th 2003: memory leaks hunt and correction.
1593 * - April 16th 2005: a memory leak fixed (extended_context was not freed).
1594 * - June 15th 2005: a memory leak fixed (loop was not conveniently freed
1595 * when the constraint system is never true).
1596 * - October 27th 2005: - this function called before cloog_loop_fast_simplify
1597 * is now the official cloog_loop_simplify function in
1598 * replacement of a slower and more complex one (after
1599 * deep changes in the pretty printer).
1600 * - we use cloog_loop_disjoint to fix the problem when
1601 * simplifying gives a union of polyhedra (before, it
1602 * was under the responsibility of the pretty printer).
1604 CloogLoop * cloog_loop_simplify(CloogLoop *loop, CloogDomain *context, int level, int nb_par)
1605 { int domain_dim ;
1606 CloogBlock * new_block ;
1607 CloogLoop * simplified, * inner, * next ;
1608 CloogDomain * domain, * simp, * inter, * extended_context ;
1610 if (loop == NULL)
1611 return(NULL) ;
1613 domain = cloog_loop_domain (loop) ;
1615 next = cloog_loop_simplify(cloog_loop_next (loop),context,level,nb_par) ;
1617 domain_dim = cloog_domain_dim(domain) - nb_par ;
1618 extended_context=cloog_domain_extend(context,domain_dim,nb_par);
1619 inter = cloog_domain_intersection(domain,extended_context) ;
1620 simp = cloog_domain_simplify(inter,extended_context) ;
1621 cloog_domain_free(extended_context) ;
1623 /* If the constraint system is never true, go to the next one. */
1624 if (cloog_domain_never_integral(simp)) {
1625 cloog_loop_set_next (loop, NULL);
1626 cloog_loop_free(loop);
1627 cloog_domain_free(inter);
1628 cloog_domain_free(simp);
1629 return next;
1632 inner = cloog_loop_simplify(cloog_loop_inner (loop),inter,level+1,nb_par) ;
1633 cloog_domain_free(inter) ;
1635 if ((inner == NULL) && (cloog_loop_block (loop) == NULL))
1636 { cloog_loop_set_inner (loop, NULL); /* For loop integrity. */
1637 cloog_loop_set_next (loop, NULL); /* For loop integrity. */
1638 cloog_loop_free_parts(loop,1,1,1,0) ;
1639 cloog_domain_free(simp);
1640 return(next) ;
1643 new_block = cloog_block_copy (cloog_loop_block (loop));
1645 simplified = cloog_loop_alloc (simp, loop->stride, new_block, inner, next);
1647 /* Examples like test/iftest2.cloog give unions of polyhedra after
1648 * simplifying, thus we we have to disjoint them. Another good reason to
1649 * put the simplifying step in the Quillere backtrack.
1651 simplified = cloog_loop_disjoint(simplified) ;
1653 cloog_loop_set_inner (loop, NULL); /* For loop integrity. */
1654 cloog_loop_set_next (loop, NULL); /* For loop integrity. */
1655 cloog_loop_free_parts(loop,1,1,0,0) ;
1657 return(simplified) ;
1661 * cloog_loop_scatter function:
1662 * This function add the scattering (scheduling) informations in a loop.
1664 void cloog_loop_scatter(CloogLoop * loop, CloogDomain * scatt)
1666 CloogDomain *scattered_domain;
1667 scattered_domain = cloog_domain_scatter(cloog_loop_domain (loop), scatt);
1668 cloog_loop_set_domain (loop, scattered_domain);