diff options
Diffstat (limited to 'cloog-core/source/loop.c')
| -rw-r--r-- | cloog-core/source/loop.c | 2483 |
1 files changed, 2483 insertions, 0 deletions
diff --git a/cloog-core/source/loop.c b/cloog-core/source/loop.c new file mode 100644 index 0000000..176a655 --- /dev/null +++ b/cloog-core/source/loop.c @@ -0,0 +1,2483 @@ + + /**-------------------------------------------------------------------** + ** CLooG ** + **-------------------------------------------------------------------** + ** loop.c ** + **-------------------------------------------------------------------** + ** First version: october 26th 2001 ** + **-------------------------------------------------------------------**/ + + +/****************************************************************************** + * CLooG : the Chunky Loop Generator (experimental) * + ****************************************************************************** + * * + * Copyright (C) 2001-2005 Cedric Bastoul * + * * + * This library is free software; you can redistribute it and/or * + * modify it under the terms of the GNU Lesser General Public * + * License as published by the Free Software Foundation; either * + * version 2.1 of the License, or (at your option) any later version. * + * * + * This library is distributed in the hope that it will be useful, * + * but WITHOUT ANY WARRANTY; without even the implied warranty of * + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU * + * Lesser General Public License for more details. * + * * + * You should have received a copy of the GNU Lesser General Public * + * License along with this library; if not, write to the Free Software * + * Foundation, Inc., 51 Franklin Street, Fifth Floor, * + * Boston, MA 02110-1301 USA * + * * + * CLooG, the Chunky Loop Generator * + * Written by Cedric Bastoul, Cedric.Bastoul@inria.fr * + * * + ******************************************************************************/ +/* CAUTION: the english used for comments is probably the worst you ever read, + * please feel free to correct and improve it ! + */ + +# include <stdlib.h> +# include <stdio.h> +# include "../include/cloog/cloog.h" + +#define ALLOC(type) (type*)malloc(sizeof(type)) + + +/****************************************************************************** + * Memory leaks hunting * + ******************************************************************************/ + + +/** + * These functions and global variables are devoted to memory leaks hunting: we + * want to know at each moment how many CloogLoop structures had been allocated + * (cloog_loop_allocated) and how many had been freed (cloog_loop_freed). + * Each time a CloogLoog structure is allocated, a call to the function + * cloog_loop_leak_up() must be carried out, and respectively + * cloog_loop_leak_down() when a CloogLoop structure is freed. The special + * variable cloog_loop_max gives the maximal number of CloogLoop structures + * simultaneously alive (i.e. allocated and non-freed) in memory. + * - July 3rd->11th 2003: first version (memory leaks hunt and correction). + */ + + +static void cloog_loop_leak_up(CloogState *state) +{ + state->loop_allocated++; + if ((state->loop_allocated - state->loop_freed) > state->loop_max) + state->loop_max = state->loop_allocated - state->loop_freed; +} + + +static void cloog_loop_leak_down(CloogState *state) +{ + state->loop_freed++; +} + + +/****************************************************************************** + * Structure display function * + ******************************************************************************/ + + +/** + * cloog_loop_print_structure function: + * Displays a loop structure in a way that trends to be understandable without + * falling in a deep depression or, for the lucky ones, getting a headache... + * Written by Olivier Chorier, Luc Marchaud, Pierre Martin and Romain Tartiere. + * - April 24th 2005: Initial version. + * - May 21rd 2005: - New parameter `F' for destination file (ie stdout), + * - Minor tweaks. + * - May 26th 2005: Memory leak hunt. + * - June 2nd 2005: (Ced) Integration and minor fixes. + * -June 22nd 2005: (Ced) Adaptation for GMP. + */ +void cloog_loop_print_structure(FILE * file, CloogLoop * loop, int level) +{ int i, j, first=1 ; + + if (loop) + { /* Go to the right level. */ + for (i=0; i<level; i++) + fprintf(file,"|\t") ; + + fprintf(file,"+-- CloogLoop\n") ; + } + + /* For each loop. */ + while (loop) + { if (!first) + { /* Go to the right level. */ + for (i=0; i<level; i++) + fprintf(file,"|\t") ; + + fprintf(file,"| CloogLoop\n") ; + } + else + first = 0 ; + + /* A blank line. */ + for(j=0; j<=level+1; j++) + fprintf(file,"|\t") ; + fprintf(file,"\n") ; + + /* Print the domain. */ + cloog_domain_print_structure(file, loop->domain, level+1, "CloogDomain"); + + /* Print the stride. */ + for(j=0; j<=level; j++) + fprintf(file,"|\t") ; + if (loop->stride) { + fprintf(file, "Stride: "); + cloog_int_print(file, loop->stride->stride); + fprintf(file, "\n"); + fprintf(file, "Offset: "); + cloog_int_print(file, loop->stride->offset); + fprintf(file, "\n"); + } + + /* A blank line. */ + for(j=0; j<=level+1; j++) + fprintf(file,"|\t") ; + fprintf(file,"\n") ; + + /* Print the block. */ + cloog_block_print_structure(file,loop->block,level+1) ; + + /* A blank line. */ + for (i=0; i<=level+1; i++) + fprintf(file,"|\t") ; + fprintf(file,"\n") ; + + /* Print inner if any. */ + if (loop->inner) + cloog_loop_print_structure(file,loop->inner,level+1) ; + + /* And let's go for the next one. */ + loop = loop->next ; + + /* One more time something that is here only for a better look. */ + if (!loop) + { /* Two blank lines if this is the end of the linked list. */ + for (j=0; j<2; j++) + { for (i=0; i<=level; i++) + fprintf(file,"|\t") ; + + fprintf(file,"\n") ; + } + } + else + { /* A special blank line if the is a next loop. */ + for (i=0; i<=level; i++) + fprintf(file,"|\t") ; + fprintf(file,"V\n") ; + } + } +} + + +/** + * cloog_loop_print function: + * This function prints the content of a CloogLoop structure (start) into a + * file (file, possibly stdout). + * - June 2nd 2005: Now this very old function (probably as old as CLooG) is + * only a frontend to cloog_loop_print_structure, with a quite + * better human-readable representation. + */ +void cloog_loop_print(FILE * file, CloogLoop * loop) +{ cloog_loop_print_structure(file,loop,0) ; +} + + +/****************************************************************************** + * Memory deallocation function * + ******************************************************************************/ + + +/** + * cloog_loop_free function: + * This function frees the allocated memory for a CloogLoop structure (loop), + * and frees its inner loops and its next loops. + * - June 22nd 2005: Adaptation for GMP. + */ +void cloog_loop_free(CloogLoop * loop) +{ CloogLoop * next ; + + while (loop != NULL) { + cloog_loop_leak_down(loop->state); + + next = loop->next ; + cloog_domain_free(loop->domain) ; + cloog_domain_free(loop->unsimplified); + cloog_block_free(loop->block) ; + if (loop->inner != NULL) + cloog_loop_free(loop->inner) ; + + cloog_stride_free(loop->stride); + free(loop) ; + loop = next ; + } +} + + +/** + * cloog_loop_free_parts function: + * This function frees the allocated memory for some parts of a CloogLoop + * structure (loop), each other argument is a boolean having to be set to 1 if + * we want to free the corresponding part, 0 otherwise. This function applies + * the same freeing policy to its inner ans next loops recursively. + * - July 3rd 2003: first version. + * - June 22nd 2005: Adaptation for GMP. + */ +void cloog_loop_free_parts(loop, domain, block, inner, next) +CloogLoop * loop ; +int domain, block, inner, next ; +{ CloogLoop * follow ; + + while (loop != NULL) { + cloog_loop_leak_down(loop->state); + follow = loop->next ; + + if (domain) + cloog_domain_free(loop->domain) ; + + if (block) + cloog_block_free(loop->block) ; + + if ((inner) && (loop->inner != NULL)) + cloog_loop_free_parts(loop->inner,domain,block,inner,1) ; + + cloog_stride_free(loop->stride); + free(loop) ; + if (next) + loop = follow ; + else + loop = NULL ; + } +} + + +/****************************************************************************** + * Reading functions * + ******************************************************************************/ + + +/** + * Construct a CloogLoop structure from a given iteration domain + * and statement number. + */ +CloogLoop *cloog_loop_from_domain(CloogState *state, CloogDomain *domain, + int number) +{ + int nb_iterators; + CloogLoop * loop ; + CloogStatement * statement ; + + /* Memory allocation and information reading for the first domain: */ + loop = cloog_loop_malloc(state); + /* domain. */ + loop->domain = domain; + if (loop->domain != NULL) + nb_iterators = cloog_domain_dimension(loop->domain); + else + nb_iterators = 0 ; + /* included statement block. */ + statement = cloog_statement_alloc(state, number + 1); + loop->block = cloog_block_alloc(statement, 0, NULL, nb_iterators); + + return loop ; +} + + +/** + * cloog_loop_read function: + * This function reads loop data from a file (foo, possibly stdin) and + * returns a pointer to a CloogLoop structure containing the read information. + * This function can be used only for input file reading, when one loop is + * associated with one statement. + * - number is the statement block number carried by the loop (-1 if none). + * - nb_parameters is the number of parameters. + ** + * - September 9th 2002: first version. + * - April 16th 2005: adaptation to new CloogStatement struct (with number). + * - June 11th 2005: adaptation to new CloogBlock structure. + * - June 22nd 2005: Adaptation for GMP. + */ +CloogLoop *cloog_loop_read(CloogState *state, + FILE *foo, int number, int nb_parameters) +{ + int op1, op2, op3; + char s[MAX_STRING]; + CloogDomain *domain; + + domain = cloog_domain_union_read(state, foo, nb_parameters); + + /* To read that stupid "0 0 0" line. */ + while (fgets(s,MAX_STRING,foo) == 0) ; + while ((*s=='#' || *s=='\n') || (sscanf(s," %d %d %d",&op1,&op2,&op3)<3)) + fgets(s,MAX_STRING,foo) ; + + return cloog_loop_from_domain(state, domain, number); +} + + +/****************************************************************************** + * Processing functions * + ******************************************************************************/ + + +/** + * cloog_loop_malloc function: + * This function allocates the memory space for a CloogLoop structure and + * sets its fields with default values. Then it returns a pointer to the + * allocated space. + * - November 21th 2005: first version. + */ +CloogLoop *cloog_loop_malloc(CloogState *state) +{ CloogLoop * loop ; + + /* Memory allocation for the CloogLoop structure. */ + loop = (CloogLoop *)malloc(sizeof(CloogLoop)) ; + if (loop == NULL) + cloog_die("memory overflow.\n"); + cloog_loop_leak_up(state); + + + /* We set the various fields with default values. */ + loop->state = state; + loop->domain = NULL ; + loop->unsimplified = NULL; + loop->block = NULL ; + loop->usr = NULL; + loop->inner = NULL ; + loop->next = NULL ; + loop->otl = 0; + loop->stride = NULL; + + return loop ; +} + + +/** + * cloog_loop_alloc function: + * This function allocates the memory space for a CloogLoop structure and + * sets its fields with those given as input. Then it returns a pointer to the + * allocated space. + * - October 27th 2001: first version. + * - June 22nd 2005: Adaptation for GMP. + * - November 21th 2005: use of cloog_loop_malloc. + */ +CloogLoop *cloog_loop_alloc(CloogState *state, + CloogDomain *domain, int otl, CloogStride *stride, + CloogBlock *block, CloogLoop *inner, CloogLoop *next) +{ CloogLoop * loop ; + + loop = cloog_loop_malloc(state); + + loop->domain = domain ; + loop->block = block ; + loop->inner = inner ; + loop->next = next ; + loop->otl = otl; + loop->stride = cloog_stride_copy(stride); + + return(loop) ; +} + + +/** + * cloog_loop_add function: + * This function adds a CloogLoop structure (loop) at a given place (now) of a + * NULL terminated list of CloogLoop structures. The beginning of this list + * is (start). This function updates (now) to (loop), and updates (start) if the + * added element is the first one -that is when (start) is NULL-. + * - October 28th 2001: first version. + */ +void cloog_loop_add(CloogLoop ** start, CloogLoop ** now, CloogLoop * loop) +{ if (*start == NULL) + { *start = loop ; + *now = *start ; + } + else + { (*now)->next = loop ; + *now = (*now)->next ; + } +} + + +/** + * cloog_loop_add function: + * This function adds a CloogLoop structure (loop) at a given place (now) of a + * NULL terminated list of CloogLoop structures. The beginning of this list + * is (start). This function updates (now) to the end of the loop list (loop), + * and updates (start) if the added element is the first one -that is when + * (start) is NULL-. + * - September 9th 2005: first version. + */ +void cloog_loop_add_list(CloogLoop ** start, CloogLoop ** now, CloogLoop * loop) +{ if (*start == NULL) + { *start = loop ; + *now = *start ; + } + else + { (*now)->next = loop ; + *now = (*now)->next ; + } + + while ((*now)->next != NULL) + *now = (*now)->next ; +} + + +/** + * cloog_loop_copy function: + * This function returns a copy of the CloogLoop structure given as input. In + * fact, there is just new allocations for the CloogLoop structures, but their + * contents are the same. + * - October 28th 2001: first version. + * - July 3rd->11th 2003: memory leaks hunt and correction. + */ +CloogLoop * cloog_loop_copy(CloogLoop * source) +{ CloogLoop * loop ; + CloogBlock * block ; + CloogDomain * domain ; + + loop = NULL ; + if (source != NULL) + { domain = cloog_domain_copy(source->domain) ; + block = cloog_block_copy(source->block) ; + loop = cloog_loop_alloc(source->state, domain, source->otl, + source->stride, block, NULL, NULL); + loop->usr = source->usr; + loop->inner = cloog_loop_copy(source->inner) ; + loop->next = cloog_loop_copy(source->next) ; + } + return(loop) ; +} + + +/** + * cloog_loop_add_disjoint function: + * This function adds some CloogLoop structures at a given place (now) of a + * NULL terminated list of CloogLoop structures. The beginning of this list + * is (start). (loop) can be an union of polyhedra, this function separates the + * union into a list of *disjoint* polyhedra then adds the list. This function + * updates (now) to the end of the list and updates (start) if first added + * element is the first of the principal list -that is when (start) is NULL-. + * (loop) can be freed by this function, basically when its domain is actually + * a union of polyhedra, but don't worry, all the useful data are now stored + * inside the list (start). We do not use PolyLib's Domain_Disjoint function, + * since the number of union components is often higher (thus code size too). + * - October 28th 2001: first version. + * - November 14th 2001: bug correction (this one was hard to find !). + * - July 3rd->11th 2003: memory leaks hunt and correction. + * - June 22nd 2005: Adaptation for GMP. + * - October 27th 2005: (debug) included blocks were not copied for new loops. + */ +void cloog_loop_add_disjoint(start, now, loop) +CloogLoop ** start, ** now, * loop ; +{ + CloogLoop * sep, * inner ; + CloogDomain *domain, *seen, *temp, *rest; + CloogBlock * block ; + + if (cloog_domain_isconvex(loop->domain)) + cloog_loop_add(start,now,loop) ; + else { + domain = cloog_domain_simplify_union(loop->domain); + loop->domain = NULL ; + + /* We separate the first element of the rest of the union. */ + domain = cloog_domain_cut_first(domain, &rest); + + /* This first element is the first of the list of disjoint polyhedra. */ + sep = cloog_loop_alloc(loop->state, domain, 0, NULL, + loop->block, loop->inner, NULL); + cloog_loop_add(start,now,sep) ; + + seen = cloog_domain_copy(domain); + while (!cloog_domain_isempty(domain = rest)) { + temp = cloog_domain_cut_first(domain, &rest); + domain = cloog_domain_difference(temp, seen); + cloog_domain_free(temp); + + if (cloog_domain_isempty(domain)) { + cloog_domain_free(domain); + continue; + } + + /* Each new loop will have its own life, for instance we can free its + * inner loop and included block. Then each one must have its own copy + * of both 'inner' and 'block'. + */ + inner = cloog_loop_copy(loop->inner) ; + block = cloog_block_copy(loop->block) ; + + sep = cloog_loop_alloc(loop->state, cloog_domain_copy(domain), + 0, NULL, block, inner, NULL); + /* domain can be an union too. If so: recursion. */ + if (cloog_domain_isconvex(domain)) + cloog_loop_add(start,now,sep) ; + else + cloog_loop_add_disjoint(start,now,sep) ; + + if (cloog_domain_isempty(rest)) { + cloog_domain_free(domain); + break; + } + + seen = cloog_domain_union(seen, domain); + } + cloog_domain_free(rest); + cloog_domain_free(seen); + cloog_loop_free_parts(loop,0,0,0,0) ; + } +} + + +/** + * cloog_loop_disjoint function: + * This function returns a list of loops such that each loop with non-convex + * domain in the input list (loop) is separated into several loops where the + * domains are the components of the union of *disjoint* polyhedra equivalent + * to the original non-convex domain. See cloog_loop_add_disjoint comments + * for more details. + * - September 16th 2005: first version. + */ +CloogLoop * cloog_loop_disjoint(CloogLoop * loop) +{ CloogLoop *res=NULL, * now=NULL, * next ; + + /* Because this is often the case, don't waste time ! */ + if (loop && !loop->next && cloog_domain_isconvex(loop->domain)) + return loop ; + + while (loop != NULL) + { next = loop->next ; + loop->next = NULL ; + cloog_loop_add_disjoint(&res,&now,loop) ; + loop = next ; + } + + return res ; +} + + +/** + * cloog_loop_restrict function: + * This function returns the (loop) in the context of (context): it makes the + * intersection between the (loop) domain and the (context), then it returns + * a pointer to a new loop, with this intersection as domain. + ** + * - October 27th 2001: first version. + * - June 15th 2005: a memory leak fixed (domain was not freed when empty). + * - June 22nd 2005: Adaptation for GMP. + */ +CloogLoop *cloog_loop_restrict(CloogLoop *loop, CloogDomain *context) +{ int new_dimension ; + CloogDomain * domain, * extended_context, * new_domain ; + CloogLoop * new_loop ; + + domain = loop->domain ; + if (cloog_domain_dimension(domain) > cloog_domain_dimension(context)) + { + new_dimension = cloog_domain_dimension(domain); + extended_context = cloog_domain_extend(context, new_dimension); + new_domain = cloog_domain_intersection(extended_context,loop->domain) ; + cloog_domain_free(extended_context) ; + } + else + new_domain = cloog_domain_intersection(context,loop->domain) ; + + if (cloog_domain_isempty(new_domain)) + { cloog_domain_free(new_domain) ; + return(NULL) ; + } + else { + new_loop = cloog_loop_alloc(loop->state, new_domain, + 0, NULL, loop->block, loop->inner, NULL); + return(new_loop) ; + } +} + + +/** + * Call cloog_loop_restrict on each loop in the list "loop" and return + * the concatenated result. + */ +CloogLoop *cloog_loop_restrict_all(CloogLoop *loop, CloogDomain *context) +{ + CloogLoop *next; + CloogLoop *res = NULL; + CloogLoop **res_next = &res; + + for (; loop; loop = next) { + next = loop->next; + + *res_next = cloog_loop_restrict(loop, context); + if (*res_next) { + res_next = &(*res_next)->next; + cloog_loop_free_parts(loop, 1, 0, 0, 0); + } else { + loop->next = NULL; + cloog_loop_free(loop); + } + } + + return res; +} + + +/** + * Restrict the domains of the inner loops of each loop l in the given + * list of loops to the domain of the loop l. If the domains of all + * inner loops of a given loop l turn out to be empty, then remove l + * from the list. + */ +CloogLoop *cloog_loop_restrict_inner(CloogLoop *loop) +{ + CloogLoop *next; + CloogLoop *res; + CloogLoop **res_next = &res; + + for (; loop; loop = next) { + next = loop->next; + + loop->inner = cloog_loop_restrict_all(loop->inner, loop->domain); + if (loop->inner) { + *res_next = loop; + res_next = &(*res_next)->next; + } else { + loop->next = NULL; + cloog_loop_free(loop); + } + } + + *res_next = NULL; + + return res; +} + +/** + * cloog_loop_project function: + * This function returns the projection of (loop) on the (level) first + * dimensions (outer loops). It makes the projection of the (loop) domain, + * then it returns a pointer to a new loop, with this projection as domain. + ** + * - October 27th 2001: first version. + * - July 3rd->11th 2003: memory leaks hunt and correction. + * - June 22nd 2005: Adaptation for GMP. + */ +CloogLoop * cloog_loop_project(CloogLoop * loop, int level) +{ + CloogDomain * new_domain ; + CloogLoop * new_loop, * copy ; + + copy = cloog_loop_alloc(loop->state, loop->domain, loop->otl, loop->stride, + loop->block, loop->inner, NULL); + + if (cloog_domain_dimension(loop->domain) == level) + new_domain = cloog_domain_copy(loop->domain) ; + else + new_domain = cloog_domain_project(loop->domain, level); + + new_loop = cloog_loop_alloc(loop->state, new_domain, 0, NULL, + NULL, copy, NULL); + + return(new_loop) ; +} + + +/** + * Call cloog_loop_project on each loop in the list "loop" and return + * the concatenated result. + */ +CloogLoop *cloog_loop_project_all(CloogLoop *loop, int level) +{ + CloogLoop *next; + CloogLoop *res = NULL; + CloogLoop **res_next = &res; + + for (; loop; loop = next) { + next = loop->next; + + *res_next = cloog_loop_project(loop, level); + res_next = &(*res_next)->next; + cloog_loop_free_parts(loop, 0, 0, 0, 0); + } + + return res; +} + + +/** + * cloog_loop_concat function: + * This function returns a pointer to the concatenation of the + * CloogLoop lists given as input. + * - October 28th 2001: first version. + */ +CloogLoop * cloog_loop_concat(CloogLoop * a, CloogLoop * b) +{ CloogLoop * loop, * temp ; + + loop = a ; + temp = loop ; + if (loop != NULL) + { while (temp->next != NULL) + temp = temp->next ; + temp->next = b ; + } + else + loop = b ; + + return(loop) ; +} + + +/** + * cloog_loop_combine: + * Combine consecutive loops with identical domains into + * a single loop with the concatenation of their inner loops + * as inner loop. + */ +CloogLoop *cloog_loop_combine(CloogLoop *loop) +{ + CloogLoop *first, *second; + + for (first = loop; first; first = first->next) { + while (first->next) { + if (!cloog_domain_lazy_equal(first->domain, first->next->domain)) + break; + second = first->next; + first->inner = cloog_loop_concat(first->inner, second->inner); + first->next = second->next; + cloog_loop_free_parts(second, 1, 0, 0, 0); + } + } + + return loop; +} + +/** + * Remove loops from list that have an empty domain. + */ +CloogLoop *cloog_loop_remove_empty_domain_loops(CloogLoop *loop) +{ + CloogLoop *l, *res, *next, **res_next; + + res = NULL; + res_next = &res; + for (l = loop; l; l = next) { + next = l->next; + if (cloog_domain_isempty(l->domain)) + cloog_loop_free_parts(l, 1, 1, 1, 0); + else { + *res_next = l; + res_next = &(*res_next)->next; + } + } + *res_next = NULL; + + return res; +} + +CloogLoop *cloog_loop_decompose_inner(CloogLoop *loop, + int level, int scalar, int *scaldims, int nb_scattdims); + +/* For each loop with only one inner loop, replace the domain + * of the loop with the projection of the domain of the inner + * loop. To increase the number of loops with a single inner + * we first decompose the inner loops into strongly connected + * components. + */ +CloogLoop *cloog_loop_specialize(CloogLoop *loop, + int level, int scalar, int *scaldims, int nb_scattdims) +{ + int dim; + CloogDomain *domain; + CloogLoop *l; + + loop = cloog_loop_decompose_inner(loop, level, scalar, + scaldims, nb_scattdims); + + for (l = loop; l; l = l->next) { + if (l->inner->next) + continue; + if (!cloog_domain_isconvex(l->inner->domain)) + continue; + + dim = cloog_domain_dimension(l->domain); + domain = cloog_domain_project(l->inner->domain, dim); + if (cloog_domain_isconvex(domain)) { + cloog_domain_free(l->domain); + l->domain = domain; + } else { + cloog_domain_free(domain); + } + } + + return cloog_loop_remove_empty_domain_loops(loop); +} + +/** + * cloog_loop_separate function: + * This function implements the Quillere algorithm for separation of multiple + * loops: for a given set of polyhedra (loop), it computes a set of disjoint + * polyhedra such that the unions of these sets are equal, and returns this set. + * - October 28th 2001: first version. + * - November 14th 2001: elimination of some unused blocks. + * - August 13th 2002: (debug) in the case of union of polyhedra for one + * loop, redundant constraints are fired. + * - July 3rd->11th 2003: memory leaks hunt and correction. + * - June 22nd 2005: Adaptation for GMP. + * - October 16th 2005: Removal of the non-shared constraint elimination when + * there is only one loop in the list (seems to work + * without now, DomainSimplify may have been improved). + * The problem was visible with test/iftest2.cloog. + */ +CloogLoop * cloog_loop_separate(CloogLoop * loop) +{ int lazy_equal=0, disjoint = 0; + CloogLoop * new_loop, * new_inner, * res, * now, * temp, * Q, + * inner, * old /*, * previous, * next*/ ; + CloogDomain *UQ, *domain; + + if (loop == NULL) + return NULL ; + + loop = cloog_loop_combine(loop); + + if (loop->next == NULL) + return cloog_loop_disjoint(loop) ; + + UQ = cloog_domain_copy(loop->domain) ; + domain = cloog_domain_copy(loop->domain) ; + res = cloog_loop_alloc(loop->state, domain, 0, NULL, + loop->block, loop->inner, NULL); + + old = loop ; + while((loop = loop->next) != NULL) + { temp = NULL ; + + /* For all Q, add Q-loop associated with the blocks of Q alone, + * and Q inter loop associated with the blocks of Q and loop. + */ + for (Q = res; Q; Q = Q->next) { + /* Add (Q inter loop). */ + if ((disjoint = cloog_domain_lazy_disjoint(Q->domain,loop->domain))) + domain = NULL ; + else + { if ((lazy_equal = cloog_domain_lazy_equal(Q->domain,loop->domain))) + domain = cloog_domain_copy(Q->domain) ; + else + domain = cloog_domain_intersection(Q->domain,loop->domain) ; + + if (!cloog_domain_isempty(domain)) + { new_inner = cloog_loop_concat(cloog_loop_copy(Q->inner), + cloog_loop_copy(loop->inner)) ; + new_loop = cloog_loop_alloc(loop->state, domain, 0, NULL, + NULL, new_inner, NULL); + cloog_loop_add_disjoint(&temp,&now,new_loop) ; + } + else { + disjoint = 1; + cloog_domain_free(domain); + } + } + + /* Add (Q - loop). */ + if (disjoint) + domain = cloog_domain_copy(Q->domain) ; + else + { if (lazy_equal) + domain = cloog_domain_empty(Q->domain); + else + domain = cloog_domain_difference(Q->domain,loop->domain) ; + } + + if (!cloog_domain_isempty(domain)) { + new_loop = cloog_loop_alloc(loop->state, domain, 0, NULL, + NULL, Q->inner, NULL); + cloog_loop_add_disjoint(&temp,&now,new_loop) ; + } + else + { cloog_domain_free(domain) ; + /* If Q->inner is no more useful, we can free it. */ + inner = Q->inner ; + Q->inner = NULL ; + cloog_loop_free(inner) ; + } + } + + /* Add loop-UQ associated with the blocks of loop alone.*/ + if (cloog_domain_lazy_disjoint(loop->domain,UQ)) + domain = cloog_domain_copy(loop->domain) ; + else + { if (cloog_domain_lazy_equal(loop->domain,UQ)) + domain = cloog_domain_empty(UQ); + else + domain = cloog_domain_difference(loop->domain,UQ) ; + } + + if (!cloog_domain_isempty(domain)) { + new_loop = cloog_loop_alloc(loop->state, domain, 0, NULL, + NULL, loop->inner, NULL); + cloog_loop_add_disjoint(&temp,&now,new_loop) ; + } + else + { cloog_domain_free(domain) ; + /* If loop->inner is no more useful, we can free it. */ + cloog_loop_free(loop->inner) ; + } + + loop->inner = NULL ; + + if (loop->next != NULL) + UQ = cloog_domain_union(UQ, cloog_domain_copy(loop->domain)); + else + cloog_domain_free(UQ); + + cloog_loop_free_parts(res,1,0,0,1) ; + + res = temp ; + } + cloog_loop_free_parts(old,1,0,0,1) ; + + return(res) ; +} + + +static CloogDomain *bounding_domain(CloogDomain *dom, CloogOptions *options) +{ + if (options->sh) + return cloog_domain_simple_convex(dom); + else + return cloog_domain_convex(dom); +} + + +/** + * cloog_loop_merge function: + * This function is the 'soft' version of loop_separate if we are looking for + * a code much simpler (and less efficicient). This function returns the new + * CloogLoop list. + * - October 29th 2001: first version. + * - July 3rd->11th 2003: memory leaks hunt and correction. + * - June 22nd 2005: Adaptation for GMP. + */ +CloogLoop *cloog_loop_merge(CloogLoop *loop, int level, CloogOptions *options) +{ + CloogLoop *res, *new_inner, *old; + CloogDomain *new_domain, *temp; + + if (loop == NULL) + return loop; + + if (loop->next == NULL && cloog_domain_isconvex(loop->domain)) + return loop; + + old = loop; + temp = loop->domain; + loop->domain = NULL; + new_inner = loop->inner; + + for (loop = loop->next; loop; loop = loop->next) { + temp = cloog_domain_union(temp, loop->domain); + loop->domain = NULL; + new_inner = cloog_loop_concat(new_inner, loop->inner); + } + + new_domain = bounding_domain(temp, options); + + if (level > 0 && !cloog_domain_is_bounded(new_domain, level) && + cloog_domain_is_bounded(temp, level)) { + CloogDomain *splitter, *t2; + + cloog_domain_free(new_domain); + splitter = cloog_domain_bound_splitter(temp, level); + + res = NULL; + while (!cloog_domain_isconvex(splitter)) { + CloogDomain *first, *rest; + first = cloog_domain_cut_first(splitter, &rest); + splitter = rest; + t2 = cloog_domain_intersection(first, temp); + cloog_domain_free(first); + + new_domain = bounding_domain(t2, options); + cloog_domain_free(t2); + + if (cloog_domain_isempty(new_domain)) { + cloog_domain_free(new_domain); + continue; + } + res = cloog_loop_alloc(old->state, new_domain, 0, NULL, + NULL, cloog_loop_copy(new_inner), res); + } + + t2 = cloog_domain_intersection(splitter, temp); + cloog_domain_free(splitter); + + new_domain = bounding_domain(t2, options); + cloog_domain_free(t2); + + if (cloog_domain_isempty(new_domain)) { + cloog_domain_free(new_domain); + cloog_loop_free(new_inner); + } else + res = cloog_loop_alloc(old->state, new_domain, 0, NULL, + NULL, new_inner, res); + } else { + res = cloog_loop_alloc(old->state, new_domain, 0, NULL, + NULL, new_inner, NULL); + } + cloog_domain_free(temp); + + cloog_loop_free_parts(old, 0, 0, 0, 1); + + return res; +} + + +static int cloog_loop_count(CloogLoop *loop) +{ + int nb_loops; + + for (nb_loops = 0; loop; loop = loop->next) + nb_loops++; + + return nb_loops; +} + + +/** + * cloog_loop_sort function: + * Adaptation from LoopGen 0.4 by F. Quillere. This function sorts a list of + * parameterized disjoint polyhedra, in order to not have lexicographic order + * violation (see Quillere paper). + * - September 16th 2005: inclusion of cloog_loop_number (October 29th 2001). + */ +CloogLoop *cloog_loop_sort(CloogLoop *loop, int level) +{ + CloogLoop *res, *now, **loop_array; + CloogDomain **doms; + int i, nb_loops=0, * permut ; + + /* There is no need to sort the parameter domains. */ + if (!level) + return loop; + + /* We will need to know how many loops are in the list. */ + nb_loops = cloog_loop_count(loop); + + /* If there is only one loop, it's the end. */ + if (nb_loops == 1) + return(loop) ; + + /* We have to allocate memory for some useful components: + * - loop_array: the loop array, + * - doms: the array of domains to sort, + * - permut: will give us a possible sort (maybe not the only one). + */ + loop_array = (CloogLoop **)malloc(nb_loops*sizeof(CloogLoop *)) ; + doms = (CloogDomain **)malloc(nb_loops*sizeof(CloogDomain *)); + permut = (int *)malloc(nb_loops*sizeof(int)) ; + + /* We fill up the loop and domain arrays. */ + for (i=0;i<nb_loops;i++,loop=loop->next) + { loop_array[i] = loop ; + doms[i] = loop_array[i]->domain; + } + + /* cloog_domain_sort will fill up permut. */ + cloog_domain_sort(doms, nb_loops, level, permut); + + /* With permut and loop_array we build the sorted list. */ + res = NULL ; + for (i=0;i<nb_loops;i++) + { /* To avoid pointer looping... loop_add will rebuild the list. */ + loop_array[permut[i]-1]->next = NULL ; + cloog_loop_add(&res,&now,loop_array[permut[i]-1]) ; + } + + free(permut) ; + free(doms); + free(loop_array) ; + + return res; +} + + +/** + * cloog_loop_nest function: + * This function changes the loop list in such a way that we have no more than + * one dimension added by level. It returns an equivalent loop list with + * this property. + * - October 29th 2001: first version. + * - July 3rd->11th 2003: memory leaks hunt and correction. + * - June 22nd 2005: Adaptation for GMP. + * - November 21th 2005: (debug) now OK when cloog_loop_restrict returns NULL. + */ +CloogLoop *cloog_loop_nest(CloogLoop *loop, CloogDomain *context, int level) +{ int l ; + CloogLoop * p, * temp, * res, * now, * next ; + CloogDomain * new_domain ; + + loop = cloog_loop_disjoint(loop); + + res = NULL ; + /* Each domain is changed by its intersection with the context. */ + while (loop != NULL) + { p = cloog_loop_restrict(loop, context); + next = loop->next ; + + if (p != NULL) + { cloog_loop_free_parts(loop,1,0,0,0) ; + + temp = cloog_loop_alloc(p->state, p->domain, 0, NULL, + p->block, p->inner, NULL); + + /* If the intersection dimension is too big, we make projections smaller + * and smaller, and each projection includes the preceding projection + * (thus, in the target list, dimensions are added one by one). + */ + if (cloog_domain_dimension(p->domain) >= level) + for (l = cloog_domain_dimension(p->domain); l >= level; l--) { + new_domain = cloog_domain_project(p->domain, l); + temp = cloog_loop_alloc(p->state, new_domain, 0, NULL, + NULL, temp, NULL); + } + + /* p is no more useful (but its content yes !). */ + cloog_loop_free_parts(p,0,0,0,0) ; + + cloog_loop_add(&res,&now,temp) ; + } + else + cloog_loop_free_parts(loop,1,1,1,0) ; + + loop = next ; + } + + return(res) ; +} + + +/* Check if the domains of the inner loops impose a stride constraint + * on the given level. + * The core of the search is implemented in cloog_domain_list_stride. + * Here, we simply construct a list of domains to pass to this function + * and if a stride is found, we adjust the lower bounds by calling + * cloog_domain_stride_lower_bound. + */ +static int cloog_loop_variable_offset_stride(CloogLoop *loop, int level) +{ + CloogDomainList *list = NULL; + CloogLoop *inner; + CloogStride *stride; + + for (inner = loop->inner; inner; inner = inner->next) { + CloogDomainList *entry = ALLOC(CloogDomainList); + entry->domain = cloog_domain_copy(inner->domain); + entry->next = list; + list = entry; + } + + stride = cloog_domain_list_stride(list, level); + + cloog_domain_list_free(list); + + if (!stride) + return 0; + + loop->stride = stride; + loop->domain = cloog_domain_stride_lower_bound(loop->domain, level, stride); + + return 1; +} + + +/** + * cloog_loop_stride function: + * This function will find the stride of a loop for the iterator at the column + * number 'level' in the constraint matrix. It will update the lower bound of + * the iterator accordingly. Basically, the function will try to find in the + * inner loops a common condition on this iterator for the inner loop iterators + * to be integral. For instance, let us consider a loop with the iterator i, + * the iteration domain -4<=i<=n, and its two inner loops with the iterator j. + * The first inner loop has the constraint 3j=i, and the second one has the + * constraint 6j=i. Then the common constraint on i for j to be integral is + * i%3=0, the stride for i is 3. Lastly, we have to find the new lower bound + * for i: the first value satisfying the common constraint: -3. At the end, the + * iteration domain for i is -3<=i<=n and the stride for i is 3. + * + * The algorithm implemented in this function only allows for strides + * on loops with a lower bound that has a constant remainder on division + * by the stride. Before initiating this procedure, we first check + * if we can find a stride with a lower bound with a variable offset in + * cloog_loop_variable_offset_stride. + * + * - loop is the loop including the iteration domain of the considered iterator, + * - level is the column number of the iterator in the matrix of contraints. + ** + * - June 29th 2003: first version (work in progress since June 26th 2003). + * - July 14th 2003: simpler version. + * - June 22nd 2005: Adaptation for GMP (from S. Verdoolaege's 0.12.1 version). + */ +void cloog_loop_stride(CloogLoop * loop, int level) +{ int first_search ; + cloog_int_t stride, ref_offset, offset, potential; + CloogLoop * inner ; + + if (!cloog_domain_can_stride(loop->domain, level)) + return; + + if (cloog_loop_variable_offset_stride(loop, level)) + return; + + cloog_int_init(stride); + cloog_int_init(ref_offset); + cloog_int_init(offset); + cloog_int_init(potential); + + cloog_int_set_si(ref_offset, 0); + cloog_int_set_si(offset, 0); + + /* Default stride. */ + cloog_int_set_si(stride, 1); + first_search = 1 ; + inner = loop->inner ; + + while (inner != NULL) + { /* If the minimun stride has not been found yet, find the stride. */ + if ((first_search) || (!cloog_int_is_one(stride))) + { + cloog_domain_stride(inner->domain, level, &potential, &offset); + if (!cloog_int_is_one(potential) && (!first_search)) + { /* Offsets must be the same for common stride. */ + cloog_int_gcd(stride, potential, stride); + if (!cloog_int_is_zero(stride)) { + cloog_int_fdiv_r(offset, offset, stride); + cloog_int_fdiv_r(ref_offset, ref_offset, stride); + } + if (cloog_int_ne(offset,ref_offset)) + cloog_int_set_si(stride, 1); + } + else { + cloog_int_set(stride, potential); + cloog_int_set(ref_offset, offset); + } + + first_search = 0 ; + } + + inner = inner->next ; + } + + if (cloog_int_is_zero(stride)) + cloog_int_set_si(stride, 1); + + /* Update the values if necessary. */ + if (!cloog_int_is_one(stride)) + { /* Update the stride value. */ + if (!cloog_int_is_zero(offset)) + cloog_int_sub(offset, stride, offset); + loop->stride = cloog_stride_alloc(stride, offset); + loop->domain = cloog_domain_stride_lower_bound(loop->domain, level, + loop->stride); + } + + cloog_int_clear(stride); + cloog_int_clear(ref_offset); + cloog_int_clear(offset); + cloog_int_clear(potential); +} + + +void cloog_loop_otl(CloogLoop *loop, int level) +{ + if (cloog_domain_is_otl(loop->domain, level)) + loop->otl = 1; +} + + +/** + * cloog_loop_stop function: + * This function implements the 'stop' option : each domain of each loop + * in the list 'loop' is replaced by 'context'. 'context' should be the + * domain of the outer loop. By using this method, there are no more dimensions + * to scan and the simplification step will automaticaly remove the domains + * since they are the same as the corresponding contexts. The effect of this + * function is to stop the code generation at the level this function is called, + * the resulting code do not consider the next dimensions. + * - January 11th 2005: first version. + */ +CloogLoop * cloog_loop_stop(CloogLoop * loop, CloogDomain * context) +{ if (loop == NULL) + return NULL ; + else + { cloog_domain_free(loop->domain) ; + loop->domain = cloog_domain_copy(context) ; + loop->next = cloog_loop_stop(loop->next, context) ; + } + + return loop ; +} + + +static int level_is_constant(int level, int scalar, int *scaldims, int nb_scattdims) +{ + return level && (level+scalar <= nb_scattdims) && (scaldims[level+scalar-1]); +} + + +/** + * Compare the constant dimensions of loops 'l1' and 'l2' starting at 'scalar' + * and return -1 if the vector of constant dimensions of 'l1' is smaller + * than that of 'l2', 0 if they are the same and +1 if that of 'l1' is + * greater than that of 'l2'. + * This function should be called on the innermost loop (the loop + * containing a block). + * \param l1 Loop to be compared with l2. + * \param l2 Loop to be compared with l1. + * \param level Current non-scalar dimension. + * \param scaldims Boolean array saying whether a dimension is scalar or not. + * \param nb_scattdims Size of the scaldims array. + * \param scalar Current scalar dimension. + * \return -1 if (l1 < l2), 0 if (l1 == l2) and +1 if (l1 > l2) + */ +int cloog_loop_constant_cmp(CloogLoop *l1, CloogLoop *l2, int level, + int *scaldims, int nb_scattdims, int scalar) +{ + CloogBlock *b1, *b2; + b1 = l1->block; + b2 = l2->block; + while (level_is_constant(level, scalar, scaldims, nb_scattdims)) { + int cmp = cloog_int_cmp(b1->scaldims[scalar], b2->scaldims[scalar]); + if (cmp) + return cmp; + scalar++; + } + return 0; +} + + +/** + * cloog_loop_scalar_gt function: + * This function returns 1 if loop 'l1' is greater than loop 'l2' for the + * scalar dimension vector that begins at dimension 'scalar', 0 otherwise. What + * we want to know is whether a loop is scheduled before another one or not. + * This function solves the problem when the considered dimension for scheduling + * is a scalar dimension. Since there may be a succession of scalar dimensions, + * this function will reason about the vector of scalar dimension that begins + * at dimension 'level+scalar' and finish to the first non-scalar dimension. + * \param l1 Loop to be compared with l2. + * \param l2 Loop to be compared with l1. + * \param level Current non-scalar dimension. + * \param scaldims Boolean array saying whether a dimension is scalar or not. + * \param nb_scattdims Size of the scaldims array. + * \param scalar Current scalar dimension. + * \return 1 if (l1 > l2), 0 otherwise. + ** + * - September 9th 2005: first version. + * - October 15nd 2007: now "greater than" instead of "greater or equal". + */ +int cloog_loop_scalar_gt(l1, l2, level, scaldims, nb_scattdims, scalar) +CloogLoop * l1, * l2 ; +int level, * scaldims, nb_scattdims, scalar ; +{ + return cloog_loop_constant_cmp(l1, l2, level, scaldims, nb_scattdims, scalar) > 0; +} + + +/** + * cloog_loop_scalar_eq function: + * This function returns 1 if loop 'l1' is equal to loop 'l2' for the scalar + * dimension vector that begins at dimension 'scalar', 0 otherwise. What we want + * to know is whether two loops are scheduled for the same time or not. + * This function solves the problem when the considered dimension for scheduling + * is a scalar dimension. Since there may be a succession of scalar dimensions, + * this function will reason about the vector of scalar dimension that begins + * at dimension 'level+scalar' and finish to the first non-scalar dimension. + * - l1 and l2 are the loops to compare, + * - level is the current non-scalar dimension, + * - scaldims is the boolean array saying whether a dimension is scalar or not, + * - nb_scattdims is the size of the scaldims array, + * - scalar is the current scalar dimension. + ** + * - September 9th 2005 : first version. + */ +int cloog_loop_scalar_eq(l1, l2, level, scaldims, nb_scattdims, scalar) +CloogLoop * l1, * l2 ; +int level, * scaldims, nb_scattdims, scalar ; +{ + return cloog_loop_constant_cmp(l1, l2, level, scaldims, nb_scattdims, scalar) == 0; +} + + +/** + * cloog_loop_scalar_sort function: + * This function sorts a linked list of loops (loop) with respect to the + * scalar dimension vector that begins at dimension 'scalar'. Since there may + * be a succession of scalar dimensions, this function will reason about the + * vector of scalar dimension that begins at dimension 'level+scalar' and + * finish to the first non-scalar dimension. + * \param loop Loop list to sort. + * \param level Current non-scalar dimension. + * \param scaldims Boolean array saying whether a dimension is scalar or not. + * \param nb_scattdims Size of the scaldims array. + * \param scalar Current scalar dimension. + * \return A pointer to the sorted list. + ** + * - July 2nd 2005: first developments. + * - September 2nd 2005: first version. + * - October 15nd 2007: complete rewrite to remove bugs, now a bubble sort. + */ +CloogLoop * cloog_loop_scalar_sort(loop, level, scaldims, nb_scattdims, scalar) +CloogLoop * loop ; +int level, * scaldims, nb_scattdims, scalar ; +{ int ok ; + CloogLoop **current; + + do { + ok = 1; + for (current = &loop; (*current)->next; current = &(*current)->next) { + CloogLoop *next = (*current)->next; + if (cloog_loop_scalar_gt(*current,next,level,scaldims,nb_scattdims,scalar)) { + ok = 0; + (*current)->next = next->next; + next->next = *current; + *current = next; + } + } + } while (!ok); + + return loop ; +} + + +/** + * cloog_loop_generate_backtrack function: + * adaptation from LoopGen 0.4 by F. Quillere. This function implements the + * backtrack of the Quillere et al. algorithm (see the Quillere paper). + * It eliminates unused iterations of the current level for the new one. See the + * example called linearity-1-1 example with and without this part for an idea. + * - October 26th 2001: first version in cloog_loop_generate_general. + * - July 31th 2002: (debug) no more parasite loops (REALLY hard !). + * - October 30th 2005: extraction from cloog_loop_generate_general. + */ +CloogLoop *cloog_loop_generate_backtrack(CloogLoop *loop, + int level, CloogOptions *options) +{ + CloogDomain * domain ; + CloogLoop * now, * now2, * next, * next2, * end, * temp, * l, * inner, + * new_loop ; + + temp = loop ; + loop = NULL ; + + while (temp != NULL) + { l = NULL ; + inner = temp->inner ; + + while (inner != NULL) + { next = inner->next ; + /* This 'if' and its first part is the debug of july 31th 2002. */ + if (inner->block != NULL) { + end = cloog_loop_alloc(temp->state, inner->domain, 0, NULL, + inner->block, NULL, NULL); + domain = cloog_domain_copy(temp->domain) ; + new_loop = cloog_loop_alloc(temp->state, domain, 0, NULL, + NULL, end, NULL); + } + else + new_loop = cloog_loop_project(inner, level); + + cloog_loop_free_parts(inner,0,0,0,0) ; + cloog_loop_add(&l,&now2,new_loop) ; + inner = next ; + } + + temp->inner = NULL ; + + if (l != NULL) + { l = cloog_loop_separate(l) ; + l = cloog_loop_sort(l, level); + while (l != NULL) { + l->stride = cloog_stride_copy(l->stride); + cloog_loop_add(&loop,&now,l) ; + l = l->next ; + } + } + next2 = temp->next ; + cloog_loop_free_parts(temp,1,0,0,0) ; + temp = next2 ; + } + + return loop ; +} + + +/** + * Return 1 if we need to continue recursing to the specified level. + */ +int cloog_loop_more(CloogLoop *loop, int level, int scalar, int nb_scattdims) +{ + return level + scalar <= nb_scattdims || + cloog_domain_dimension(loop->domain) >= level; +} + +/** + * Return 1 if the domains of all loops in the given linked list + * have a fixed value at the given level. + * In principle, there would be no need to check that the fixed value is + * the same for each of these loops because this function is only + * called on a component. However, not all backends perform a proper + * decomposition into components. + */ +int cloog_loop_is_constant(CloogLoop *loop, int level) +{ + cloog_int_t c1, c2; + int r = 1; + + cloog_int_init(c1); + cloog_int_init(c2); + + if (!cloog_domain_lazy_isconstant(loop->domain, level - 1, &c1)) + r = 0; + + for (loop = loop->next; r && loop; loop = loop->next) { + if (!cloog_domain_lazy_isconstant(loop->domain, level - 1, &c2)) + r = 0; + else if (cloog_int_ne(c1, c2)) + r = 0; + } + + cloog_int_clear(c1); + cloog_int_clear(c2); + + return r; +} + +/** + * Assuming all domains in the given linked list of loop + * have a fixed values at level, return a single loop with + * a domain corresponding to this fixed value and with as + * list of inner loops the concatenation of all inner loops + * in the original list. + */ +CloogLoop *cloog_loop_constant(CloogLoop *loop, int level) +{ + CloogLoop *res, *inner, *tmp; + CloogDomain *domain, *context, *t; + + if (!loop) + return loop; + + inner = loop->inner; + for (tmp = loop->next; tmp; tmp = tmp->next) + inner = cloog_loop_concat(inner, tmp->inner); + + domain = cloog_domain_copy(loop->domain); + domain = cloog_domain_simple_convex(t = domain); + cloog_domain_free(t); + context = cloog_domain_project(domain, level - 1); + context = cloog_domain_extend(t = context, level); + cloog_domain_free(t); + domain = cloog_domain_simplify(t = domain, context); + cloog_domain_free(t); + cloog_domain_free(context); + + res = cloog_loop_alloc(loop->state, domain, 0, NULL, NULL, inner, NULL); + + cloog_loop_free_parts(loop, 1, 0, 0, 1); + + return res; +} + +CloogLoop *cloog_loop_generate_restricted_or_stop(CloogLoop *loop, + CloogDomain *context, + int level, int scalar, int *scaldims, int nb_scattdims, + CloogOptions *options); + +/** + * cloog_loop_generate_general function: + * Adaptation from LoopGen 0.4 by F. Quillere. This function implements the + * Quillere algorithm for polyhedron scanning from step 3 to 5. + * (see the Quillere paper). + * - loop is the loop for which we have to generate a scanning code, + * - level is the current non-scalar dimension, + * - scalar is the current scalar dimension, + * - scaldims is the boolean array saying whether a dimension is scalar or not, + * - nb_scattdims is the size of the scaldims array, + * - options are the general code generation options. + ** + * - October 26th 2001: first version. + * - July 3rd->11th 2003: memory leaks hunt and correction. + * - June 22nd 2005: Adaptation for GMP. + * - September 2nd 2005: The function have been cutted out in two pieces: + * cloog_loop_generate and this one, in order to handle + * the scalar dimension case more efficiently with + * cloog_loop_generate_scalar. + * - November 15th 2005: (debug) the result of the cloog_loop_generate call may + * be a list of polyhedra (especially if stop option is + * used): cloog_loop_add_list instead of cloog_loop_add. + */ +CloogLoop *cloog_loop_generate_general(CloogLoop *loop, + int level, int scalar, int *scaldims, int nb_scattdims, + CloogOptions *options) +{ + CloogLoop * res, * now, * temp, * l, * new_loop, * inner, * now2, * end, + * next, * into ; + CloogDomain * domain ; + int separate = 0; + + /* 3. Separate all projections into disjoint polyhedra. */ + if (level > 0 && cloog_loop_is_constant(loop, level)) + res = cloog_loop_constant(loop, level); + else if ((options->f > level+scalar) || (options->f < 0)) + res = cloog_loop_merge(loop, level, options); + else { + res = cloog_loop_separate(loop); + separate = 1; + } + + /* 3b. -correction- sort the loops to determine their textual order. */ + res = cloog_loop_sort(res, level); + + res = cloog_loop_restrict_inner(res); + + if (separate) + res = cloog_loop_specialize(res, level, scalar, scaldims, nb_scattdims); + + /* 4. Recurse for each loop with the current domain as context. */ + temp = res ; + res = NULL ; + if (!level || (level+scalar < options->l) || (options->l < 0)) + while(temp != NULL) + { if (level && options->strides) + cloog_loop_stride(temp, level); + if (level && options->otl) + cloog_loop_otl(temp, level); + inner = temp->inner ; + domain = temp->domain ; + into = NULL ; + while (inner != NULL) + { /* 4b. -ced- recurse for each sub-list of non terminal loops. */ + if (cloog_loop_more(inner, level + 1, scalar, nb_scattdims)) { + end = inner; + while ((end->next != NULL) && + cloog_loop_more(end->next, level + 1, scalar, nb_scattdims)) + end = end->next ; + + next = end->next ; + end->next = NULL ; + + l = cloog_loop_generate_restricted_or_stop(inner, domain, + level + 1, scalar, scaldims, nb_scattdims, options); + + if (l != NULL) + cloog_loop_add_list(&into,&now,l) ; + + inner = next ; + } + else + { cloog_loop_add(&into,&now,inner) ; + inner = inner->next ; + } + } + next = temp->next ; + temp->next = NULL ; + temp->inner = into ; + cloog_loop_add(&res,&now2,temp) ; + temp = next ; + } + else + while (temp != NULL) + { next = temp->next ; + l = cloog_loop_nest(temp->inner, temp->domain, level+1); + new_loop = cloog_loop_alloc(temp->state, temp->domain, 0, NULL, + NULL, l, NULL); + temp->inner = NULL ; + temp->next = NULL ; + cloog_loop_free_parts(temp,0,0,0,0) ; + cloog_loop_add(&res,&now,new_loop) ; + temp = next ; + } + + /* 5. eliminate unused iterations of the current level for the new one. See + * the example called linearity-1-1 example with and without this part + * for an idea. + */ + if (options->backtrack && level && + ((level+scalar < options->l) || (options->l < 0)) && + ((options->f <= level+scalar) && !(options->f < 0))) + res = cloog_loop_generate_backtrack(res, level, options); + + /* Pray for my new paper to be accepted somewhere since the following stuff + * is really amazing :-) ! + * Far long later: The paper has been accepted to PACT 2004 :-))). But there + * are still some bugs and I have no time to fix them. Thus now you have to + * pray for me to get an academic position for that really amazing stuff :-) ! + * Later again: OK, I get my academic position, but still I have not enough + * time to fix and clean this part... Pray again :-) !!! + */ + /* res = cloog_loop_unisolate(res,level) ;*/ + + return(res) ; +} + + +CloogLoop *cloog_loop_generate_restricted(CloogLoop *loop, + int level, int scalar, int *scaldims, int nb_scattdims, + CloogOptions *options); + + +/** + * cloog_loop_generate_scalar function: + * This function applies the simplified code generation scheme in the trivial + * case of scalar dimensions. When dealing with scalar dimensions, there is + * no need of costly polyhedral operations for separation or sorting: sorting + * is a question of comparing scalar vectors and separation amounts to consider + * only loops with the same scalar vector for the next step of the code + * generation process. This function achieves the separation/sorting process + * for the vector of scalar dimension that begins at dimension 'level+scalar' + * and finish to the first non-scalar dimension. + * - loop is the loop for which we have to generate a scanning code, + * - level is the current non-scalar dimension, + * - scalar is the current scalar dimension, + * - scaldims is the boolean array saying whether a dimension is scalar or not, + * - nb_scattdims is the size of the scaldims array, + * - options are the general code generation options. + ** + * - September 2nd 2005: First version. + */ +CloogLoop *cloog_loop_generate_scalar(CloogLoop *loop, + int level, int scalar, int *scaldims, int nb_scattdims, + CloogOptions *options) +{ CloogLoop * res, * now, * temp, * l, * end, * next, * ref ; + int scalar_new; + + /* We sort the loop list with respect to the current scalar vector. */ + res = cloog_loop_scalar_sort(loop,level,scaldims,nb_scattdims,scalar) ; + + scalar_new = scalar + scaldims[level + scalar - 1]; + + temp = res ; + res = NULL ; + while (temp != NULL) + { /* Then we will appy the general code generation process to each sub-list + * of loops with the same scalar vector. + */ + end = temp ; + ref = temp ; + + while((end->next != NULL) && + cloog_loop_more(end->next, level, scalar_new, nb_scattdims) && + cloog_loop_scalar_eq(ref,end->next,level,scaldims,nb_scattdims,scalar)) + end = end->next ; + + next = end->next ; + end->next = NULL ; + + /* For the next dimension, scalar value is updated by adding the scalar + * vector size, which is stored at scaldims[level+scalar-1]. + */ + if (cloog_loop_more(temp, level, scalar_new, nb_scattdims)) { + l = cloog_loop_generate_restricted(temp, level, scalar_new, + scaldims, nb_scattdims, options); + + if (l != NULL) + cloog_loop_add_list(&res, &now, l); + } else + cloog_loop_add(&res, &now, temp); + + temp = next ; + } + + return res ; +} + + +/* Compare loop with the next loop based on their constant dimensions. + * The result is < 0, == 0 or > 0 depending on whether the constant + * dimensions of loop are lexicographically smaller, equal or greater + * than those of loop->next. + * If loop is the last in the list, then it is assumed to be smaller + * than the "next" one. + */ +static int cloog_loop_next_scal_cmp(CloogLoop *loop) +{ + int i; + int nb_scaldims; + + if (!loop->next) + return -1; + + nb_scaldims = loop->block->nb_scaldims; + if (loop->next->block->nb_scaldims < nb_scaldims) + nb_scaldims = loop->next->block->nb_scaldims; + + for (i = 0; i < nb_scaldims; ++i) { + int cmp = cloog_int_cmp(loop->block->scaldims[i], + loop->next->block->scaldims[i]); + if (cmp) + return cmp; + } + return loop->block->nb_scaldims - loop->next->block->nb_scaldims; +} + + +/* Check whether the globally constant dimensions of a and b + * have the same value for all globally constant dimensions + * that are situated before any (locally) non-constant dimension. + */ +static int cloog_loop_equal_prefix(CloogLoop *a, CloogLoop *b, + int *scaldims, int nb_scattdims) +{ + int i; + int cst = 0; + int dim = 0; + + for (i = 0; i < nb_scattdims; ++i) { + if (!scaldims[i]) { + dim++; + continue; + } + if (!cloog_int_eq(a->block->scaldims[cst], b->block->scaldims[cst])) + break; + cst++; + } + for (i = i + 1; i < nb_scattdims; ++i) { + if (scaldims[i]) + continue; + if (!cloog_domain_lazy_isconstant(a->domain, dim, NULL)) + return 0; + /* No need to check that dim is also constant in b and that the + * constant values are equal. That will happen during the check + * whether the two domains are equal. + */ + dim++; + } + return 1; +} + + +/* Try to block adjacent loops in the loop list "loop". + * We only attempt blocking if the constant dimensions of the loops + * in the least are (not necessarily strictly) increasing. + * Then we look for a sublist such that the first (begin) has constant + * dimensions strictly larger than the previous loop in the complete + * list and such that the loop (end) after the last loop in the sublist + * has constant dimensions strictly larger than the last loop in the sublist. + * Furthermore, all loops in the sublist should have the same domain + * (with globally constant dimensions removed) and the difference + * (if any) in constant dimensions may only occur after all the + * (locally) constant dimensions. + * If we find such a sublist, then the blocks of all but the first + * are merged into the block of the first. + * + * Note that this function can only be called before the global + * blocklist has been created because it may otherwise modify and destroy + * elements on that list. + */ +CloogLoop *cloog_loop_block(CloogLoop *loop, int *scaldims, int nb_scattdims) +{ + CloogLoop *begin, *end, *l; + int begin_after_previous; + int end_after_previous; + + if (!loop->next) + return loop; + for (begin = loop; begin; begin = begin->next) { + if (!begin->block || !begin->block->scaldims) + return loop; + if (cloog_loop_next_scal_cmp(begin) > 0) + return loop; + } + + begin_after_previous = 1; + for (begin = loop; begin; begin = begin->next) { + if (!begin_after_previous) { + begin_after_previous = cloog_loop_next_scal_cmp(begin) < 0; + continue; + } + + end_after_previous = cloog_loop_next_scal_cmp(begin) < 0; + for (end = begin->next; end; end = end->next) { + if (!cloog_loop_equal_prefix(begin, end, scaldims, nb_scattdims)) + break; + if (!cloog_domain_lazy_equal(begin->domain, end->domain)) + break; + end_after_previous = cloog_loop_next_scal_cmp(end) < 0; + } + if (end != begin->next && end_after_previous) { + for (l = begin->next; l != end; l = begin->next) { + cloog_block_merge(begin->block, l->block); + begin->next = l->next; + cloog_loop_free_parts(l, 1, 0, 1, 0); + } + } + + begin_after_previous = cloog_loop_next_scal_cmp(begin) < 0; + } + + return loop; +} + + +/** + * Check whether for any fixed iteration of the outer loops, + * there is an iteration of loop1 that is lexicographically greater + * than an iteration of loop2. + * Return 1 if there exists (or may exist) such a pair. + * Return 0 if all iterations of loop1 are lexicographically smaller + * than the iterations of loop2. + * If no iteration is lexicographically greater, but if there are + * iterations that are equal to iterations of loop2, then return "def". + * This is useful for ensuring that such statements are not reordered. + * Some users, including the test_run target in test, expect + * the statements at a given point to be run in the original order. + * Passing the value "0" for "def" would allow such statements to be reordered + * and would allow for the detection of more components. + */ +int cloog_loop_follows(CloogLoop *loop1, CloogLoop *loop2, + int level, int scalar, int *scaldims, int nb_scattdims, int def) +{ + int dim1, dim2; + + dim1 = cloog_domain_dimension(loop1->domain); + dim2 = cloog_domain_dimension(loop2->domain); + while ((level <= dim1 && level <= dim2) || + level_is_constant(level, scalar, scaldims, nb_scattdims)) { + if (level_is_constant(level, scalar, scaldims, nb_scattdims)) { + int cmp = cloog_loop_constant_cmp(loop1, loop2, level, scaldims, + nb_scattdims, scalar); + if (cmp > 0) + return 1; + if (cmp < 0) + return 0; + scalar += scaldims[level + scalar - 1]; + } else { + int follows = cloog_domain_follows(loop1->domain, loop2->domain, + level); + if (follows > 0) + return 1; + if (follows < 0) + return 0; + level++; + } + } + + return def; +} + + +/* Structure for representing the nodes in the graph being traversed + * using Tarjan's algorithm. + * index represents the order in which nodes are visited. + * min_index is the index of the root of a (sub)component. + * on_stack indicates whether the node is currently on the stack. + */ +struct cloog_loop_sort_node { + int index; + int min_index; + int on_stack; +}; +/* Structure for representing the graph being traversed + * using Tarjan's algorithm. + * len is the number of nodes + * node is an array of nodes + * stack contains the nodes on the path from the root to the current node + * sp is the stack pointer + * index is the index of the last node visited + * order contains the elements of the components separated by -1 + * op represents the current position in order + */ +struct cloog_loop_sort { + int len; + struct cloog_loop_sort_node *node; + int *stack; + int sp; + int index; + int *order; + int op; +}; + +/* Allocate and initialize cloog_loop_sort structure. + */ +static struct cloog_loop_sort *cloog_loop_sort_alloc(int len) +{ + struct cloog_loop_sort *s; + int i; + + s = (struct cloog_loop_sort *)malloc(sizeof(struct cloog_loop_sort)); + assert(s); + s->len = len; + s->node = (struct cloog_loop_sort_node *) + malloc(len * sizeof(struct cloog_loop_sort_node)); + assert(s->node); + for (i = 0; i < len; ++i) + s->node[i].index = -1; + s->stack = (int *)malloc(len * sizeof(int)); + assert(s->stack); + s->order = (int *)malloc(2 * len * sizeof(int)); + assert(s->order); + + s->sp = 0; + s->index = 0; + s->op = 0; + + return s; +} + +/* Free cloog_loop_sort structure. + */ +static void cloog_loop_sort_free(struct cloog_loop_sort *s) +{ + free(s->node); + free(s->stack); + free(s->order); + free(s); +} + + +/* Check whether for any fixed iteration of the outer loops, + * there is an iteration of loop1 that is lexicographically greater + * than an iteration of loop2, where the iteration domains are + * available in the inner loops of the arguments. + * + * By using this functions to detect components, we ensure that + * two CloogLoops appear in the same component if some iterations of + * each loop should be executed before some iterations of the other loop. + * Since we also want two CloogLoops that have exactly the same + * iteration domain at the current level to be placed in the same component, + * we first check if these domains are indeed the same. + */ +static int inner_loop_follows(CloogLoop *loop1, CloogLoop *loop2, + int level, int scalar, int *scaldims, int nb_scattdims, int def) +{ + int f; + + f = cloog_domain_lazy_equal(loop1->domain, loop2->domain); + if (!f) + f = cloog_loop_follows(loop1->inner, loop2->inner, + level, scalar, scaldims, nb_scattdims, def); + + return f; +} + + +/* Perform Tarjan's algorithm for computing the strongly connected components + * in the graph with the individual CloogLoops as vertices. + * Two CloopLoops appear in the same component if they both (indirectly) + * "follow" each other, where the following relation is determined + * by the follows function. + */ +static void cloog_loop_components_tarjan(struct cloog_loop_sort *s, + CloogLoop **loop_array, int i, int level, int scalar, int *scaldims, + int nb_scattdims, + int (*follows)(CloogLoop *loop1, CloogLoop *loop2, + int level, int scalar, int *scaldims, int nb_scattdims, int def)) +{ + int j; + + s->node[i].index = s->index; + s->node[i].min_index = s->index; + s->node[i].on_stack = 1; + s->index++; + s->stack[s->sp++] = i; + + for (j = s->len - 1; j >= 0; --j) { + int f; + + if (j == i) + continue; + if (s->node[j].index >= 0 && + (!s->node[j].on_stack || + s->node[j].index > s->node[i].min_index)) + continue; + + f = follows(loop_array[i], loop_array[j], + level, scalar, scaldims, nb_scattdims, i > j); + if (!f) + continue; + + if (s->node[j].index < 0) { + cloog_loop_components_tarjan(s, loop_array, j, level, scalar, + scaldims, nb_scattdims, follows); + if (s->node[j].min_index < s->node[i].min_index) + s->node[i].min_index = s->node[j].min_index; + } else if (s->node[j].index < s->node[i].min_index) + s->node[i].min_index = s->node[j].index; + } + + if (s->node[i].index != s->node[i].min_index) + return; + + do { + j = s->stack[--s->sp]; + s->node[j].on_stack = 0; + s->order[s->op++] = j; + } while (j != i); + s->order[s->op++] = -1; +} + + +static int qsort_index_cmp(const void *p1, const void *p2) +{ + return *(int *)p1 - *(int *)p2; +} + +/* Sort the elements of the component starting at list. + * The list is terminated by a -1. + */ +static void sort_component(int *list) +{ + int len; + + for (len = 0; list[len] != -1; ++len) + ; + + qsort(list, len, sizeof(int), qsort_index_cmp); +} + +/* Given an array of indices "list" into the "loop_array" array, + * terminated by -1, construct a linked list of the corresponding + * entries and put the result in *res. + * The value returned is the number of CloogLoops in the (linked) list + */ +static int extract_component(CloogLoop **loop_array, int *list, CloogLoop **res) +{ + int i = 0; + + sort_component(list); + while (list[i] != -1) { + *res = loop_array[list[i]]; + res = &(*res)->next; + ++i; + } + *res = NULL; + + return i; +} + + +/** + * Call cloog_loop_generate_scalar or cloog_loop_generate_general + * on each of the strongly connected components in the list of CloogLoops + * pointed to by "loop". + * + * We use Tarjan's algorithm to find the strongly connected components. + * Note that this algorithm also topologically sorts the components. + * + * The components are treated separately to avoid spurious separations. + * The concatentation of the results may contain successive loops + * with the same bounds, so we try to combine such loops. + */ +CloogLoop *cloog_loop_generate_components(CloogLoop *loop, + int level, int scalar, int *scaldims, int nb_scattdims, + CloogOptions *options) +{ + int i, nb_loops; + CloogLoop *tmp; + CloogLoop *res, **res_next; + CloogLoop **loop_array; + struct cloog_loop_sort *s; + + if (level == 0 || !loop->next) + return cloog_loop_generate_general(loop, level, scalar, + scaldims, nb_scattdims, options); + + nb_loops = cloog_loop_count(loop); + + loop_array = (CloogLoop **)malloc(nb_loops * sizeof(CloogLoop *)); + assert(loop_array); + + for (i = 0, tmp = loop; i < nb_loops; i++, tmp = tmp->next) + loop_array[i] = tmp; + + s = cloog_loop_sort_alloc(nb_loops); + for (i = nb_loops - 1; i >= 0; --i) { + if (s->node[i].index >= 0) + continue; + cloog_loop_components_tarjan(s, loop_array, i, level, scalar, scaldims, + nb_scattdims, &inner_loop_follows); + } + + i = 0; + res = NULL; + res_next = &res; + while (nb_loops) { + int n = extract_component(loop_array, &s->order[i], &tmp); + i += n + 1; + nb_loops -= n; + *res_next = cloog_loop_generate_general(tmp, level, scalar, + scaldims, nb_scattdims, options); + while (*res_next) + res_next = &(*res_next)->next; + } + + cloog_loop_sort_free(s); + + free(loop_array); + + res = cloog_loop_combine(res); + + return res; +} + + +/* For each loop in the list "loop", decompose the list of + * inner loops into strongly connected components and put + * the components into separate loops at the top level. + */ +CloogLoop *cloog_loop_decompose_inner(CloogLoop *loop, + int level, int scalar, int *scaldims, int nb_scattdims) +{ + CloogLoop *l, *tmp; + CloogLoop **loop_array; + int i, n_loops, max_loops = 0; + struct cloog_loop_sort *s; + + for (l = loop; l; l = l->next) { + n_loops = cloog_loop_count(l->inner); + if (max_loops < n_loops) + max_loops = n_loops; + } + + if (max_loops <= 1) + return loop; + + loop_array = (CloogLoop **)malloc(max_loops * sizeof(CloogLoop *)); + assert(loop_array); + + for (l = loop; l; l = l->next) { + int n; + + for (i = 0, tmp = l->inner; tmp; i++, tmp = tmp->next) + loop_array[i] = tmp; + n_loops = i; + if (n_loops <= 1) + continue; + + s = cloog_loop_sort_alloc(n_loops); + for (i = n_loops - 1; i >= 0; --i) { + if (s->node[i].index >= 0) + continue; + cloog_loop_components_tarjan(s, loop_array, i, level, scalar, + scaldims, nb_scattdims, &cloog_loop_follows); + } + + n = extract_component(loop_array, s->order, &l->inner); + n_loops -= n; + i = n + 1; + while (n_loops) { + CloogLoop *inner; + + n = extract_component(loop_array, &s->order[i], &inner); + n_loops -= n; + i += n + 1; + tmp = cloog_loop_alloc(l->state, cloog_domain_copy(l->domain), + l->otl, l->stride, l->block, inner, l->next); + l->next = tmp; + l = tmp; + } + + cloog_loop_sort_free(s); + } + + free(loop_array); + + return loop; +} + + +CloogLoop *cloog_loop_generate_restricted(CloogLoop *loop, + int level, int scalar, int *scaldims, int nb_scattdims, + CloogOptions *options) +{ + /* To save both time and memory, we switch here depending on whether the + * current dimension is scalar (simplified processing) or not (general + * processing). + */ + if (level_is_constant(level, scalar, scaldims, nb_scattdims)) + return cloog_loop_generate_scalar(loop, level, scalar, + scaldims, nb_scattdims, options); + /* + * 2. Compute the projection of each polyhedron onto the outermost + * loop variable and the parameters. + */ + loop = cloog_loop_project_all(loop, level); + + return cloog_loop_generate_components(loop, level, scalar, scaldims, + nb_scattdims, options); +} + + +CloogLoop *cloog_loop_generate_restricted_or_stop(CloogLoop *loop, + CloogDomain *context, + int level, int scalar, int *scaldims, int nb_scattdims, + CloogOptions *options) +{ + /* If the user asked to stop code generation at this level, let's stop. */ + if ((options->stop >= 0) && (level+scalar >= options->stop+1)) + return cloog_loop_stop(loop,context) ; + + return cloog_loop_generate_restricted(loop, level, scalar, scaldims, + nb_scattdims, options); +} + + +/** + * cloog_loop_generate function: + * Adaptation from LoopGen 0.4 by F. Quillere. This function implements the + * Quillere algorithm for polyhedron scanning from step 1 to 2. + * (see the Quillere paper). + * - loop is the loop for which we have to generate a scanning code, + * - context is the context of the current loop (constraints on parameter and/or + * on outer loop counters), + * - level is the current non-scalar dimension, + * - scalar is the current scalar dimension, + * - scaldims is the boolean array saying whether a dimension is scalar or not, + * - nb_scattdims is the size of the scaldims array, + * - options are the general code generation options. + ** + * - October 26th 2001: first version. + * - July 3rd->11th 2003: memory leaks hunt and correction. + * - June 15th 2005: a memory leak fixed (loop was not entirely freed when + * the result of cloog_loop_restrict was NULL). + * - June 22nd 2005: Adaptation for GMP. + * - September 2nd 2005: The function have been cutted out in two pieces: + * cloog_loop_generate and this one, in order to handle + * the scalar dimension case more efficiently with + * cloog_loop_generate_scalar. + * - November 15th 2005: (debug) Condition for stop option no more take care of + * further scalar dimensions. + */ +CloogLoop *cloog_loop_generate(CloogLoop *loop, CloogDomain *context, + int level, int scalar, int *scaldims, int nb_scattdims, + CloogOptions *options) +{ + /* 1. Replace each polyhedron by its intersection with the context. + */ + loop = cloog_loop_restrict_all(loop, context); + if (!loop) + return NULL; + + return cloog_loop_generate_restricted_or_stop(loop, context, + level, scalar, scaldims, nb_scattdims, options); +} + + +/* + * Internal function for simplifying a single loop in a list of loops. + * See cloog_loop_simplify. + */ +static CloogLoop *loop_simplify(CloogLoop *loop, CloogDomain *context, + int level, int nb_scattdims, CloogOptions *options) +{ + int domain_dim; + CloogBlock * new_block ; + CloogLoop *simplified, *inner; + CloogDomain * domain, * simp, * inter, * extended_context ; + + if (!cloog_domain_isconvex(loop->domain)) + loop->domain = cloog_domain_simplify_union(loop->domain); + + domain = loop->domain ; + + domain_dim = cloog_domain_dimension(domain); + extended_context = cloog_domain_extend(context, domain_dim); + inter = cloog_domain_intersection(domain,extended_context) ; + simp = cloog_domain_simplify(domain, extended_context); + cloog_domain_free(extended_context) ; + + /* If the constraint system is never true, go to the next one. */ + if (cloog_domain_never_integral(simp)) { + cloog_loop_free(loop->inner); + cloog_domain_free(inter); + cloog_domain_free(simp); + return NULL; + } + + inner = cloog_loop_simplify(loop->inner, inter, level+1, nb_scattdims, + options); + + if ((inner == NULL) && (loop->block == NULL)) { + cloog_domain_free(inter); + cloog_domain_free(simp); + return NULL; + } + + new_block = cloog_block_copy(loop->block) ; + + simplified = cloog_loop_alloc(loop->state, simp, loop->otl, loop->stride, + new_block, inner, NULL); + + /* Only save the domains, if their level is still a scattering level. */ + if (options->save_domains && level <= nb_scattdims) + simplified->unsimplified = inter; + else + cloog_domain_free(inter); + + return(simplified) ; +} + + +/** + * cloog_loop_simplify function: + * This function implements the part 6. of the Quillere algorithm, it + * recursively simplifies each loop in the context of the preceding loop domain. + * It returns a pointer to the simplified loop list. + * The cloog_domain_simplify (DomainSimplify) behaviour is really bad with + * polyhedra union and some really awful sidesteppings were written, I plan + * to solve that... + * - October 31th 2001: first version. + * - July 3rd->11th 2003: memory leaks hunt and correction. + * - April 16th 2005: a memory leak fixed (extended_context was not freed). + * - June 15th 2005: a memory leak fixed (loop was not conveniently freed + * when the constraint system is never true). + * - October 27th 2005: - this function called before cloog_loop_fast_simplify + * is now the official cloog_loop_simplify function in + * replacement of a slower and more complex one (after + * deep changes in the pretty printer). + * - we use cloog_loop_disjoint to fix the problem when + * simplifying gives a union of polyhedra (before, it + * was under the responsibility of the pretty printer). + */ +CloogLoop *cloog_loop_simplify(CloogLoop *loop, CloogDomain *context, int level, + int nb_scattdims, CloogOptions *options) +{ + CloogLoop *now; + CloogLoop *res = NULL; + CloogLoop **next = &res; + + for (now = loop; now; now = now->next) { + *next = loop_simplify(now, context, level, nb_scattdims, options); + + now->inner = NULL; /* For loop integrity. */ + cloog_domain_free(now->domain); + now->domain = NULL; + + if (*next) + next = &(*next)->next; + } + cloog_loop_free(loop); + + /* Examples like test/iftest2.cloog give unions of polyhedra after + * simplifying, thus we have to make them disjoint. Another good reason to + * put the simplifying step in the Quillere backtrack. + */ + res = cloog_loop_disjoint(res); + + return res; +} + + +/** + * cloog_loop_scatter function: + * This function add the scattering (scheduling) informations in a loop. + */ +void cloog_loop_scatter(CloogLoop * loop, CloogScattering *scatt) +{ + loop->domain = cloog_domain_scatter(loop->domain, scatt); +} + |