loop_nest_annotate.c File Reference

#include <stdio.h>
#include <string.h>
#include "genC.h"
#include "boolean.h"
#include "arithmetique.h"
#include "vecteur.h"
#include "contrainte.h"
#include "ray_dte.h"
#include "sommet.h"
#include "sg.h"
#include "sc.h"
#include "polyedre.h"
#include "matrix.h"
#include "linear.h"
#include "ri.h"
#include "effects.h"
#include "database.h"
#include "ri-util.h"
#include "prettyprint.h"
#include "effects-util.h"
#include "constants.h"
#include "misc.h"
#include "control.h"
#include "text-util.h"
#include "pipsdbm.h"
#include "resources.h"
#include "properties.h"
#include "effects-simple.h"

Include dependency graph for loop_nest_annotate.c:

Go to the source code of this file.

Data Structures
struct	gpu_lna_context
	In modern PIPS programming, all is passed through a context instead of having a global variable. More...

Macros
#define	COMMA   ","
	Loop nests transformation phase for par4all : More...
#define	OPENPAREN   "("
#define	CLOSEPAREN   ")"

Functions
static bool	loop_push (loop l, gpu_lna_context *p)
	Push a loop that matches the criterion for annotation. More...
static void	loop_annotate (loop l, gpu_lna_context *p)
	Do the real annotation work on previously marked loops bottom-up. More...
bool	gpu_loop_nest_annotate_on_statement (statement s)
	annotates loop nests in the following way : More...
bool	gpu_loop_nest_annotate (const char *module_name)
static bool	parallelize_annotated_loop_nest (statement s)
	Callback for gen_recurse Parallelize perfectly nested loop nest, till we reach the magic comment. More...
bool	gpu_parallelize_annotated_loop_nest (const string mod_name)
	Parallelize the launcher based on loop nest annotate sentinels. More...
bool	clear_annotated_loop_nest (statement s)
	Callback for gen_recurse Remove annotation on a loop nest. More...
bool	gpu_clear_annotations_on_loop_nest (const string mod_name)
	Remove all annotations on a loop nest. More...

Macro Definition Documentation

CLOSEPAREN

#define CLOSEPAREN   ")"

Definition at line 104 of file loop_nest_annotate.c.

COMMA

#define COMMA   ","

Loop nests transformation phase for par4all :

gpu_loop_nest_annotate takes a module that is of the form :

typedef float float_t; void p4a_kernel_wrapper_1(float_t save[501][501], float_t space[501][501], int i, int j); void p4a_kernel_launcher_1(float_t save[501][501], float_t space[501][501]) { int i; int j; kernel2: for(i = 0; i <= 100; i += 1) for(j = 0; j <= 200; j += 1) p4a_kernel_wrapper_1(save, space, i+1, j+1); }

and transforms it into :

typedef float float_t; void p4a_kernel_wrapper_1(float_t save[501][501], float_t space[501][501], int i, int j); void p4a_kernel_launcher_1(float_t save[501][501], float_t space[501][501]) { int i; int j; kernel2: Loop nest P4A begin, 2D(200, 100) for(i = 0; i <= 100; i += 1) for(j = 0; j <= 200; j += 1) Loop nest P4A end if (i <= 100 && j <= 200) p4a_kernel_wrapper_1(save, space, i+1, j+1); }

for further generation of CUDA code. } Ansi includes
Newgen includes Pips includes

Definition at line 102 of file loop_nest_annotate.c.

OPENPAREN

#define OPENPAREN   "("

Definition at line 103 of file loop_nest_annotate.c.

Function Documentation

clear_annotated_loop_nest()

bool clear_annotated_loop_nest

(

statement

s

)

Callback for gen_recurse Remove annotation on a loop nest.

Definition at line 465 of file loop_nest_annotate.c.

                                            {
  string comment = statement_comments(s);
  if(comment  && !empty_comments_p(comment)
      && (NULL != strstr(comment, "Loop nest P4A end")|| NULL != strstr(comment, "Loop nest P4A begin"))) {
    // clear the comment
    // We may instead filter out only the annotation inside the comment
    statement_comments(s) = string_undefined;
  }
  return true;
}

References comment(), empty_comments_p(), statement_comments, and string_undefined.

Referenced by gpu_clear_annotations_on_loop_nest().

Here is the call graph for this function:

Here is the caller graph for this function:

gpu_clear_annotations_on_loop_nest()

bool gpu_clear_annotations_on_loop_nest

(

const string

mod_name

)

Remove all annotations on a loop nest.

Parameters

mod_name

od_name

Definition at line 477 of file loop_nest_annotate.c.

                                                               {
  // Use this module name and this environment variable to set
  statement module_statement = PIPS_PHASE_PRELUDE(mod_name,
      "GPU_IFY_DEBUG_LEVEL");
 
  // Parallelize loops
  gen_recurse(module_statement,
      statement_domain, clear_annotated_loop_nest, gen_null);
 
  // Put back the new statement module
  PIPS_PHASE_POSTLUDE(module_statement)
  ;
  // The macro above does a "return TRUE" indeed.
}

References clear_annotated_loop_nest(), gen_null(), gen_recurse, module_statement, PIPS_PHASE_POSTLUDE, PIPS_PHASE_PRELUDE, and statement_domain.

Here is the call graph for this function:

gpu_loop_nest_annotate()

bool gpu_loop_nest_annotate

(

const char *

module_name

)

Parameters

module_name

odule_name

Definition at line 406 of file loop_nest_annotate.c.

                                                     {
  // Use this module name and this environment variable to set
  statement module_statement =
      PIPS_PHASE_PRELUDE(module_name, "P4A_LOOP_NEST_ANOTATE_DEBUG_LEVEL");
 
  gpu_loop_nest_annotate_on_statement(module_statement);
 
  // Put back the new statement module
  PIPS_PHASE_POSTLUDE(module_statement)
  ;
  // The macro above does a "return TRUE" indeed.
}

References gpu_loop_nest_annotate_on_statement(), module_name(), module_statement, PIPS_PHASE_POSTLUDE, and PIPS_PHASE_PRELUDE.

Here is the call graph for this function:

gpu_loop_nest_annotate_on_statement()

bool gpu_loop_nest_annotate_on_statement

(

statement

s

)

annotates loop nests in the following way :

loop_nest_annotate.c

for(i=0; i<=100; i++) for(j=0; j<=200; j++) foo();

==>

// Loop nest P4A begin,2D(200, 100) for(i=0; i<=100; i++) for(j=0; j<=200; j++) // Loop nest P4A end if (i<=100&&j<=200) foo();

for loops must have been transformed into loops.

Parameters

mod_name

name of the module

Returns

true

Initialize context

Annotate the loop nests of the module.

Clean up things: (hasn't it been done previously in loop_annotate?)

Definition at line 383 of file loop_nest_annotate.c.

                                                      {
  /* Initialize context */
  gpu_lna_context c;
  c.l_enclosing_loops = NIL;
  c.l_number_iter_exp = NIL;
  c.max_loop_nest_depth = -1;
  c.loop_nest_depth = 0;
  c.inner_reached = false;
  c.gpu_loop_nest_annotate_parallel_p
      = get_bool_property("GPU_LOOP_NEST_ANNOTATE_PARALLEL");
  c.fail_p = false;
  c.inner_loop = loop_undefined;
  c.guard_expression = expression_undefined;
 
  /* Annotate the loop nests of the module. */
  gen_context_recurse(s, &c, loop_domain, loop_push, loop_annotate);
 
  /* Clean up things: (hasn't it been done previously in loop_annotate?) */
  gen_free_list(c.l_number_iter_exp);
 
  return true;
}

References expression_undefined, gpu_lna_context::fail_p, gen_context_recurse, gen_free_list(), get_bool_property(), gpu_lna_context::gpu_loop_nest_annotate_parallel_p, gpu_lna_context::guard_expression, gpu_lna_context::inner_loop, gpu_lna_context::inner_reached, gpu_lna_context::l_enclosing_loops, gpu_lna_context::l_number_iter_exp, loop_annotate(), loop_domain, gpu_lna_context::loop_nest_depth, loop_push(), loop_undefined, gpu_lna_context::max_loop_nest_depth, and NIL.

Referenced by gpu_ify_statement(), and gpu_loop_nest_annotate().

Here is the call graph for this function:

Here is the caller graph for this function:

gpu_parallelize_annotated_loop_nest()

bool gpu_parallelize_annotated_loop_nest

(

const string

mod_name

)

Parallelize the launcher based on loop nest annotate sentinels.

Parameters

mod_name

od_name

Definition at line 445 of file loop_nest_annotate.c.

                                                                {
  // Use this module name and this environment variable to set
  statement module_statement = PIPS_PHASE_PRELUDE(mod_name,
      "GPU_IFY_DEBUG_LEVEL");
 
  // Parallelize loops
  gen_recurse(module_statement,
      statement_domain, parallelize_annotated_loop_nest, gen_null);
 
  // Put back the new statement module
  PIPS_PHASE_POSTLUDE(module_statement)
  ;
  // The macro above does a "return TRUE" indeed.
}

References gen_null(), gen_recurse, module_statement, parallelize_annotated_loop_nest(), PIPS_PHASE_POSTLUDE, PIPS_PHASE_PRELUDE, and statement_domain.

Here is the call graph for this function:

loop_annotate()

static void loop_annotate ( loop  l, gpu_lna_context *  p  )

static

Do the real annotation work on previously marked loops bottom-up.

We have to select the operators that are different in C and FORTRAN

The first time we enter this function is when we reach the innermost loop nest level.

We are at the innermost loop nest level

First we build the guard to be added to the loop body statement using the enclosing loops upper bounds. And we push on l_number_iter_exp an expression representing the number of iteration of each loop; currently, we do not check that variables modified inside loops are not used in loop bounds expressions. but we take care of loop indices used in deeper loop bounds.

first check if the lower bound depend on enclosing loop indices

We have to clean the list of effect from any "preference" since the next loop modify the references and can make our "preference" invalid

Keep the number of iterations for the generation of the outermost comment

We will have deepest loop size first:

We are now on our way back in the recursion; we do nothing, unless we are at the uppermost level.

Output inner dimension first:

Concatenate the dimension of the innermost loop:

Idem for other dimensions, but do not forget to insert the ', '

Then we add the comment : // Loop nest P4A end

reset context

Definition at line 153 of file loop_nest_annotate.c.

                                                       {
  /* We have to select the operators that are different in C and FORTRAN */
  string and_op =
      (get_prettyprint_language_tag() == is_language_c) ? C_AND_OPERATOR_NAME
                                                        : AND_OPERATOR_NAME;
  string
      less_op =
          (get_prettyprint_language_tag() == is_language_c) ? C_LESS_OR_EQUAL_OPERATOR_NAME
                                                            : LESS_OR_EQUAL_OPERATOR_NAME;
  /* The first time we enter this function is when we reach the innermost
   loop nest level.
   */
  if(p->inner_loop == loop_undefined) {
    expression guard_exp = expression_undefined;
 
    /* We are at the innermost loop nest level */
    p->inner_loop = l;
    /* First we build the guard to be added to the loop body statement using the
     enclosing loops upper bounds.
     And we push on l_number_iter_exp an expression representing the
     number of iteration of each loop;
     currently, we do not check that variables modified inside loops
     are not used in loop bounds expressions.
     but we take care of loop indices used in deeper loop bounds.
     */FOREACH(LOOP, c_loop, p->l_enclosing_loops) {
      entity c_index = loop_index(c_loop);
      range c_range = loop_range(c_loop);
      expression c_lower = copy_expression(range_lower(c_range));
      expression c_upper = copy_expression(range_upper(c_range));
      expression c_inc = range_increment(c_range);
      expression c_number_iter_exp = expression_undefined;
      expression c_guard;
 
      if(expression_constant_p(c_inc) && expression_to_int(c_inc) == 1) {
        /* first check if the lower bound depend on enclosing loop indices */
        list l_eff_lower_bound = proper_effects_of_expression(c_lower);
        list l_eff_upper_bound = proper_effects_of_expression(c_upper);
 
        /* We have to clean the list of effect from any "preference" since the
         * next loop modify the references and can make our "preference" invalid
         */
        void remove_preferences(void * obj);
        {
          FOREACH(effect,e,l_eff_lower_bound) {
            remove_preferences(e);
          }
        }
        {
          FOREACH(effect,e,l_eff_upper_bound) {
            remove_preferences(e);
          }
        }
 
        FOREACH(LOOP, other_loop, p->l_enclosing_loops) {
          if(other_loop != l) {
            range range_other_loop = loop_range(other_loop);
            expression lower_other_loop = range_lower(range_other_loop);
            expression upper_other_loop = range_upper(range_other_loop);
 
            if(effects_read_variable_p(l_eff_lower_bound,
                                       loop_index(other_loop))) {
              expression new_lower_1 = c_lower;
              expression new_lower_2 = copy_expression(c_lower);
              replace_entity_by_expression(new_lower_1,
                                           loop_index(other_loop),
                                           lower_other_loop);
              (void)simplify_expression(&new_lower_1);
              replace_entity_by_expression(new_lower_2,
                                           loop_index(other_loop),
                                           upper_other_loop);
 
              (void)simplify_expression(&new_lower_2);
              c_lower = make_min_expression(new_lower_1,
                                            new_lower_2,
                                            get_prettyprint_language_tag());
            }
            if(effects_read_variable_p(l_eff_upper_bound,
                                       loop_index(other_loop))) {
              expression new_upper_1 = c_upper;
              expression new_upper_2 = copy_expression(c_upper);
              replace_entity_by_expression(new_upper_1,
                                           loop_index(other_loop),
                                           lower_other_loop);
              (void)simplify_expression(&new_upper_1);
              replace_entity_by_expression(new_upper_2,
                                           loop_index(other_loop),
                                           upper_other_loop);
              (void)simplify_expression(&new_upper_2);
 
              c_upper = make_max_expression(new_upper_1,
                                            new_upper_2,
                                            get_prettyprint_language_tag());
            }
          }
        }
 
        c_guard
            = MakeBinaryCall(entity_intrinsic(less_op),
                             reference_to_expression(make_reference(c_index,
                                                                    NIL)),
                             copy_expression(range_upper(c_range)));
 
        if(expression_undefined_p(guard_exp))
          guard_exp = c_guard;
        else
          guard_exp = MakeBinaryCall(entity_intrinsic(and_op),
                                     guard_exp,
                                     c_guard);
 
        pips_debug(2, "guard expression : %s\n",
                   expression_to_string(guard_exp));
 
        /* Keep the number of iterations for the generation of the
         outermost comment */
        c_number_iter_exp = make_op_exp(MINUS_OPERATOR_NAME, c_upper, c_lower);
        c_number_iter_exp = make_op_exp(PLUS_OPERATOR_NAME,
                                        c_number_iter_exp,
                                        int_to_expression(1));
        /* We will have deepest loop size first: */
        p->l_number_iter_exp = CONS(EXPRESSION, c_number_iter_exp,
            p->l_number_iter_exp);
 
      } else {
        p->fail_p = true;
        pips_user_warning("case not handled: loop increment is not 1.\n");
      }
    }
    if(!p->fail_p) {
      p->guard_expression = guard_exp;
    }
 
  }
 
  /* We are now on our way back in the recursion; we do nothing, unless
   we are at the uppermost level.
   */
  if(gen_length(p->l_enclosing_loops) == 1) {
    if(!p->fail_p)
    // if the process has succeeded, we add the outermost comment :
    // Loop nest P4A begin, xD(upper_bound,..) and the inner guard.
    {
      statement current_stat = (statement)gen_get_ancestor(statement_domain, l);
      // Then we add the comment such as: '// Loop nest P4A begin,3D(200, 100)'
      string outer_s;
      (void)asprintf(&outer_s,
                     "%s Loop nest P4A begin,%dD" OPENPAREN,
                     get_comment_sentinel(),
                     p->loop_nest_depth);
 
      bool first_iteration = true;
      /* Output inner dimension first: */FOREACH(EXPRESSION, upper_exp, p->l_number_iter_exp) {
        string buf;
        string buf1 = expression_to_string(upper_exp);
        if(first_iteration)
          /* Concatenate the dimension of the innermost loop: */
          (void)asprintf(&buf, "%s%s", outer_s, buf1);
        else
          /* Idem for other dimensions, but do not forget to insert the ', ' */
          (void)asprintf(&buf, "%s%s%s", outer_s, COMMA" ", buf1);
        free(outer_s);
        free(buf1);
        outer_s = buf;
        first_iteration = false;
      }
      (void)asprintf(&statement_comments(current_stat),
                     "%s"CLOSEPAREN"\n",
                     outer_s);
      free(outer_s);
      statement guard_s = test_to_statement(make_test(p->guard_expression,
              loop_body(p->inner_loop),
              make_empty_block_statement()));
      /* Then we add the comment : // Loop nest P4A end */statement_comments(guard_s)
          = strdup(concatenate(get_comment_sentinel(),
                               " Loop nest P4A end\n",
                               NULL));
      loop_body(p->inner_loop) = guard_s;
 
      /* reset context */
      p->loop_nest_depth = 0;
      p->max_loop_nest_depth = -1;
      gen_free_list(p->l_number_iter_exp);
      p->l_number_iter_exp = NIL;
      p->fail_p = false;
      p->inner_loop = loop_undefined;
      p->guard_expression = expression_undefined;
    }
 
    else
    // the process has failed: we clean everything and reset context
    {
      p->loop_nest_depth = 0;
      p->max_loop_nest_depth = -1;
      gen_full_free_list(p->l_number_iter_exp);
      p->l_number_iter_exp = NIL;
      p->fail_p = false;
      p->inner_loop = loop_undefined;
      if(!expression_undefined_p(p->guard_expression)) {
        free_expression(p->guard_expression);
        p->guard_expression = expression_undefined;
      }
    }
  }
  if(gen_length(p->l_enclosing_loops)) {
    POP(p->l_enclosing_loops);
  }
  return;
}

References AND_OPERATOR_NAME, asprintf, buf, C_AND_OPERATOR_NAME, C_LESS_OR_EQUAL_OPERATOR_NAME, c_loop(), CLOSEPAREN, COMMA, concatenate(), CONS, copy_expression(), effects_read_variable_p(), entity_intrinsic(), EXPRESSION, expression_constant_p(), expression_to_int(), expression_to_string(), expression_undefined, expression_undefined_p, gpu_lna_context::fail_p, FOREACH, free(), free_expression(), gen_free_list(), gen_full_free_list(), gen_get_ancestor(), gen_length(), get_comment_sentinel(), get_prettyprint_language_tag(), gpu_lna_context::guard_expression, gpu_lna_context::inner_loop, int_to_expression(), is_language_c, gpu_lna_context::l_enclosing_loops, gpu_lna_context::l_number_iter_exp, LESS_OR_EQUAL_OPERATOR_NAME, LOOP, loop_body, loop_index, gpu_lna_context::loop_nest_depth, loop_range, loop_undefined, make_empty_block_statement(), make_max_expression(), make_min_expression(), make_op_exp(), make_reference(), make_test(), MakeBinaryCall(), gpu_lna_context::max_loop_nest_depth, MINUS_OPERATOR_NAME, NIL, OPENPAREN, pips_debug, pips_user_warning, PLUS_OPERATOR_NAME, POP, proper_effects_of_expression(), range_increment, range_lower, range_upper, reference_to_expression(), remove_preferences(), replace_entity_by_expression(), simplify_expression(), statement_comments, statement_domain, strdup(), and test_to_statement.

Referenced by gpu_loop_nest_annotate_on_statement().

Here is the call graph for this function:

Here is the caller graph for this function:

loop_push()

static bool loop_push ( loop  l, gpu_lna_context *  p  )

static

Push a loop that matches the criterion for annotation.

This is the first loop we met in this loop nest

Let's compute the loop_nest_depth

this loop does not belong to the perfectly nested loops

Definition at line 126 of file loop_nest_annotate.c.

                                                   {
  if(p->max_loop_nest_depth == -1) {
    /* This is the first loop we met in this loop nest */
    if(p->gpu_loop_nest_annotate_parallel_p && !loop_parallel_p(l)) {
      return true;
    }
 
    /* Let's compute the loop_nest_depth */
    statement current_stat = (statement)gen_get_ancestor(statement_domain, l);
    p->max_loop_nest_depth
        = p->gpu_loop_nest_annotate_parallel_p ? depth_of_parallel_perfect_loop_nest(current_stat)
                                               : depth_of_perfect_loop_nest(current_stat);
  }
 
  if(p->loop_nest_depth >= p->max_loop_nest_depth)
    /* this loop does not belong to the perfectly nested loops */
    return false;
  else {
    p->l_enclosing_loops = gen_nconc(p->l_enclosing_loops, CONS(LOOP, l, NIL));
    p->loop_nest_depth++;
    // Go on recursing:
    return true;
  }
  return false;
}

References CONS, depth_of_parallel_perfect_loop_nest(), depth_of_perfect_loop_nest(), gen_get_ancestor(), gen_nconc(), gpu_lna_context::gpu_loop_nest_annotate_parallel_p, gpu_lna_context::l_enclosing_loops, LOOP, gpu_lna_context::loop_nest_depth, loop_parallel_p(), gpu_lna_context::max_loop_nest_depth, NIL, and statement_domain.

Referenced by gpu_loop_nest_annotate_on_statement().

Here is the call graph for this function:

Here is the caller graph for this function:

parallelize_annotated_loop_nest()

static bool parallelize_annotated_loop_nest ( statement  s )

static

Callback for gen_recurse Parallelize perfectly nested loop nest, till we reach the magic comment.

FIXME : should detect the beginning sentinel, but since we use it in launcher, it has no importance at that time

Definition at line 426 of file loop_nest_annotate.c.

                                                         {
  char **comment=NULL;
  if(statement_loop_p(s)) {
    execution_tag(loop_execution(statement_loop(s))) = is_execution_parallel;
    // Check the inner comment to find out the sentinel and stop recursion
    comment = find_first_statement_comment(loop_body(statement_loop(s)));
  } else {
    comment = find_first_statement_comment(s);
  }
 
  // Check sentinel
  if(comment  && !empty_comments_p(*comment) && NULL != strstr(*comment, "Loop nest P4A end")) {
    // stop recursion
    return false;
  }
  return true;
}

References comment(), empty_comments_p(), execution_tag, find_first_statement_comment(), is_execution_parallel, loop_body, loop_execution, statement_loop(), and statement_loop_p().

Referenced by gpu_parallelize_annotated_loop_nest().

Here is the call graph for this function:

Here is the caller graph for this function: