From c9278c5dba6abb74f98967b6c48386cbe8b07bc8 Mon Sep 17 00:00:00 2001 From: Uday Bondhugula Date: Thu, 31 May 2012 17:38:53 +0530 Subject: [PATCH] statement-wise -f/-l options for loop separation option->f/l (-f -l command-line args) provided first and last levels to optimize control overhead by separating / splitting loops at a global level. This patch allows -f/-l options to be set on a stmt-wise basis. Integer arrays options->fs, options->ls should be allocated by the user with options->fs_ls_size set to the number of elements (always equal to the number of statements). For any given loop, the first and last depths of statements under it are looked at to determine if the loop should be separated (max across all fs' and ls' is taken). A user has to set fs meaningfully, i.e., for eg., if two statements i & j have a fused loop and fs[i], fs[j] specify separation for that level for stmt i but not for stmt j, the input is ambiguous and we will in this case not separate (since a max is taken). options->fs/ls override f/l; if fs/ls are not set or are set inconsistently (max across ls[i] < max across fs[i]), f/l take over. fs/ls can only be set via the library interface for now. Signed-off-by: Uday Bondhugula Signed-off-by: Cedric Bastoul --- doc/cloog.texi | 27 +++++++++++++++++++- include/cloog/options.h | 4 +++ source/loop.c | 68 +++++++++++++++++++++++++++++++++++++++++++++---- source/options.c | 23 ++++++++++++++++- 4 files changed, 115 insertions(+), 7 deletions(-) diff --git a/doc/cloog.texi b/doc/cloog.texi index 0ec4e02..bcdc015 100644 --- a/doc/cloog.texi +++ b/doc/cloog.texi @@ -820,6 +820,7 @@ input file @code{basic.cloog} with default options by typing: @menu * Last Depth to Optimize Control:: * First Depth to Optimize Control:: +* Statement-wise First and Last Depths to Optimize Control * Simplify Convex Hull:: * Once Time Loop Elimination:: * Equality Spreading:: @@ -921,6 +922,26 @@ for (i=1;i<=N;i++) @{ @end group @end example +@node Statement-wise First and Last Depths to Optimize Control +@subsection Statement-wise First and Last Depths to Optimize Control @code{options->fs, options->ls} + +option->f/l (command-line arguments: -f and -l) provide first and last levels to optimize +control overhead at a global level (across the entire program / all statements) +by separating / splitting loops. option->fs/ls allow the equivalent of setting +-f/-l options on a statement-wise basis. Integer arrays options->fs, options->ls should +be allocated by the user with options->fs_ls_size set to the number of elements (always equal +to the number of statements). For any +given loop, the first and last depths of all statements under it are looked at +to determine if the loop should be separated (max across all fs' and ls' is +taken). A user has to set fs meaningfully, i.e., for eg., if two statements i & +j have a fused loop and fs[i], fs[j] specify separation for that level for stmt +i but not for stmt j, the input is ambiguous and we will in this case not +separate (since a max is taken). options->fs/ls override f/l; if fs/ls are not +set or are set inconsistently (max across ls[i] < max across fs[i]), f/l take +over. + +fs/ls can only be set via the library interface for now. + @node Simple Convex Hull @subsection Simple Convex Hull @code{-sh } @@ -1854,8 +1875,11 @@ by @code{usr}. @example @group struct cloogoptions -@{ int l; /* -l option. */ +@{ int l; /* -l option. */ int f; /* -f option. */ + int *ls; /* Statement-wise l option */ + int *fs; /* Statement-wise f option */ + int fs_ls_size; /* Size of the fs and ls arrays (same size) */ int strides; /* -strides option. */ int sh; /* -sh option. */ int first_unroll; /* -first-unroll option. */ @@ -1881,6 +1905,7 @@ As a reminder, the default values are: @itemize @bullet @item @math{l = -1} (optimize control until the innermost loops), @item @math{f = 1} (optimize control from the outermost loops), +@item @math{ls/fs = NULL} and @math{fs\_ls\_size = 0} (statement-wise l/f are not set), @item @math{strides = 0} (use only unit strides), @item @math{sh = 0} (do not compute simple convex hulls), @item @math{first\_unroll = -1} (do not perform unrolling), diff --git a/include/cloog/options.h b/include/cloog/options.h index 2233579..f4dd70e 100644 --- a/include/cloog/options.h +++ b/include/cloog/options.h @@ -62,6 +62,10 @@ struct cloogoptions /* OPTIONS FOR LOOP GENERATION */ int l ; /* Last level to optimize. */ int f ; /* First level to optimize. */ + + int *ls; /* Last level to optimize (statement-wise). */ + int *fs; /* First level to optimize (statement-wise). */ + int fs_ls_size; /* Size of the fs and ls arrays (same size) */ int stop ; /* Level to stop code generation. */ int strides ; /* 1 if user wants to handle non-unit strides (then loop * increment can be something else than one), 0 otherwise. diff --git a/source/loop.c b/source/loop.c index d93d8a7..9592503 100644 --- a/source/loop.c +++ b/source/loop.c @@ -1800,6 +1800,46 @@ CloogLoop *cloog_loop_recurse(CloogLoop *loop, return res; } + +/* Get the max across all 'first' depths for statements in this + * stmt list, and the max across all 'last' depths */ +void cloog_statement_get_fl(CloogStatement *s, int *f, int *l, + CloogOptions *options) +{ + if (s == NULL) return; + + int fs, ls; + + if (options->fs != NULL && options->ls != NULL) { + fs = options->fs[s->number-1]; + ls = options->ls[s->number-1]; + *f = (fs > *f)? fs: *f; + *l = (ls > *l)? ls: *l; + }else{ + *f = -1; + *l = -1; + } + + cloog_statement_get_fl(s->next, f, l, options); +} + +/* Get the max across all 'first' depths for statements under + * this loop, and the max across all 'last' depths */ +void cloog_loop_get_fl(CloogLoop *loop, int *f, int *l, + CloogOptions *options) +{ + if (loop == NULL) return; + + CloogBlock *block = loop->block; + + if (block != NULL && block->statement != NULL) { + cloog_statement_get_fl(block->statement, f, l, options); + } + + cloog_loop_get_fl(loop->inner, f, l, options); + cloog_loop_get_fl(loop->next, f, l, options); +} + /** * cloog_loop_generate_general function: * Adaptation from LoopGen 0.4 by F. Quillere. This function implements the @@ -1822,6 +1862,10 @@ CloogLoop *cloog_loop_recurse(CloogLoop *loop, * - 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. + * - May 31, 2012: statement-wise first and last depth for loop separation + * if options->fs and option->ls arrays are set, it will override what has + * been supplied via "-f/-l" + * */ CloogLoop *cloog_loop_generate_general(CloogLoop *loop, int level, int scalar, int *scaldims, int nb_scattdims, @@ -1831,13 +1875,27 @@ CloogLoop *cloog_loop_generate_general(CloogLoop *loop, int separate = 0; int constant = 0; + int first = -1; + int last = -1; + + now = NULL; + + /* Get the -f and -l for each statement */ + cloog_loop_get_fl(loop, &first, &last, options); + + /* If stmt-wise options are not set or set inconsistently, use -f/-l ones globally */ + if (first <= 0 || last < first) { + first = options->f; + last = options->l; + } + /* 3. Separate all projections into disjoint polyhedra. */ if (level > 0 && cloog_loop_is_constant(loop, level)) { res = cloog_loop_constant(loop, level); constant = 1; - } else if ((options->f > level+scalar) || (options->f < 0)) + }else if ((first > level+scalar) || (first < 0)) { res = cloog_loop_merge(loop, level, options); - else { + }else{ res = cloog_loop_separate(loop); separate = 1; } @@ -1853,7 +1911,7 @@ CloogLoop *cloog_loop_generate_general(CloogLoop *loop, /* 4. Recurse for each loop with the current domain as context. */ temp = res ; res = NULL ; - if (!level || (level+scalar < options->l) || (options->l < 0)) + if (!level || (level+scalar < last) || (last < 0)) res = cloog_loop_recurse(temp, level, scalar, scaldims, nb_scattdims, constant, options); else @@ -1877,8 +1935,8 @@ CloogLoop *cloog_loop_generate_general(CloogLoop *loop, * for an idea. */ if (options->backtrack && level && - ((level+scalar < options->l) || (options->l < 0)) && - ((options->f <= level+scalar) && !(options->f < 0))) + ((level+scalar < last) || (last < 0)) && + ((first <= level+scalar) && !(first < 0))) res = cloog_loop_generate_backtrack(res, level, options); /* Pray for my new paper to be accepted somewhere since the following stuff diff --git a/source/options.c b/source/options.c index ca7f2fa..3689c0c 100644 --- a/source/options.c +++ b/source/options.c @@ -115,10 +115,26 @@ void cloog_die(const char *msg, ...) * - April 19th 2003: first version. */ void cloog_options_print(FILE * foo, CloogOptions * options) -{ fprintf(foo,"Options:\n") ; +{ + int i; + + fprintf(foo,"Options:\n") ; fprintf(foo,"OPTIONS FOR LOOP GENERATION\n") ; fprintf(foo,"l = %3d,\n",options->l) ; fprintf(foo,"f = %3d,\n",options->f) ; + fprintf(foo,"fs = %3d,\n",options->f) ; + if (options->fs_ls_size>=1) { + fprintf(foo,"fs = "); + for (i=0; ifs_ls_size; i++) { + fprintf(foo,"%3d,\n",options->fs[i]) ; + } + fprintf(foo,"\n"); + fprintf(foo,"ls = "); + for (i=0; ifs_ls_size; i++) { + fprintf(foo,"%3d,\n",options->ls[i]) ; + } + fprintf(foo,"\n"); + } fprintf(foo,"stop = %3d,\n",options->stop) ; fprintf(foo,"strides = %3d,\n",options->strides) ; fprintf(foo,"sh = %3d,\n",options->sh); @@ -164,6 +180,8 @@ void cloog_options_free(CloogOptions *options) osl_scop_free(options->scop); } #endif + free(options->fs); + free(options->ls); free(options); } @@ -316,6 +334,9 @@ CloogOptions *cloog_options_malloc(CloogState *state) /* OPTIONS FOR LOOP GENERATION */ options->l = -1 ; /* Last level to optimize: infinity. */ options->f = 1 ; /* First level to optimize: the first. */ + options->ls = NULL ; /* Statement-wise l option is not set */ + options->fs = NULL ; /* Statement-wise f option is not set */ + options->fs_ls_size = 0; /* No statement-wise f/s control */ options->stop = -1 ; /* Generate all the code. */ options->strides = 0 ; /* Generate a code with unit strides. */ options->sh = 0; /* Compute actual convex hull. */ -- 2.11.4.GIT