Methods dealing with loops

Some generic methods about loops and list of loops. More...

Functions
void	clean_enclosing_loops (void)
static void	rloops_mapping_of_statement ()
static void	rloops_mapping_of_unstructured (statement_mapping m, list loops, unstructured u)
static void	rloops_mapping_of_statement (statement_mapping m, list loops, statement s)
statement_mapping	loops_mapping_of_statement (statement stat)
static bool	distributable_statement_p (statement stat, set region)
set	distributable_loop (statement l)
	this functions checks if Kennedy's algorithm can be applied on the loop passed as argument. More...
bool	index_private_p (loop lo)
	returns true if loop lo's index is private for this loop More...
set	region_of_loop (statement l)
	this function returns the set of all statements belonging to the given loop even if the loop contains test, goto or unstructured control structures More...
void	region_of_statement (statement stat, set region)
	Should be rewritten with a gen_recurse to deal with the recent RI... More...
list	loop_private_variables_as_entites (loop obj, bool local, bool index)
	Get the variables local or private to a loop. More...
static void	loop_sort_locals (loop l)
void	sort_all_loop_locals (statement s)
bool	loop_parallel_p (loop l)
	Test if a loop is parallel. More...
bool	loop_sequential_p (loop l)
	Test if a loop is sequential. More...
bool	parallel_loop_statement_p (statement s)
	Test if a statement is a parallel loop. More...
int	depth_of_parallel_perfect_loop_nest (statement s)
	Compute the depth of a parallel perfect loop-nest. More...
int	depth_of_perfect_loop_nest (statement s)
	Compute the depth of a perfect loop-nest. More...
statement	get_first_inner_perfectly_nested_loop (statement stat)
	Return the inner loop in a perfect loop-nest. More...
bool	perfectly_nested_loop_p (statement stat)
	Test if a statement is a perfect loop-nest. More...
statement	perfectly_nested_loop_to_body (statement loop_nest)
	Extract the body of a perfectly nested loop body. More...
statement	perfectly_nested_loop_to_body_at_depth (statement s, int depth)
	Extract the loop-body of a perfect loop-nest at a given depth. More...
entity	perfectly_nested_loop_index_at_depth (statement s, int depth)
	Get the index of the loop at a given depth inside a loop-nest. More...
int	loop_increment_value (loop l)
bool	constant_step_loop_p (loop l)
	Test if a loop has a constant step loop. More...
bool	normal_loop_p (loop l)
	Test if a loop does have a 1-increment step. More...
static void	loop_update_statistics (loop l)
void	number_of_sequential_and_parallel_loops (statement stat, int *pseq, int *ppar)
	Compute the number of parallel and sequential loops found in a statement and update given variables. More...
void	print_number_of_loop_statistics (FILE *out, string msg, statement s)
	Compute the number of parallel and sequential loops found in a statement and output them on a stream with a message before. More...
void	print_parallelization_statistics (const char *module, const char *msg, statement s)
	Print out the number of sequential versus parallel loops. More...
list	copy_loops (list ll)
	Duplicate a loop list. More...
statement	make_new_loop_statement (entity i, expression low, expression up, expression inc, statement b, execution e)
	This is an ad'hoc function designed for do_loop_unroll_with_epilogue(). More...
list	statement_to_loop_statement_list (statement s)
	If statement s is a perfectly loop nest, return the corresponding loop list. More...
bool	range_contains_at_least_one_point_p (range r)
bool	loop_executed_at_least_once_p (loop l)
	Check if loop bound are constant and then if upper >= lower. More...
bool	range_contains_nothing_p (range r)
bool	loop_executed_never_p (loop l)
	Check if loop bound are constant and then if upper < lower. More...
bool	index_of_a_loop_p (Variable v, list loops)
	Check if variable v is an index for an enclosing loop. More...

Variables
int	Nbrdo
	loop.c More...
static int	nseq
	To store the number of sequential and parallel loops. More...
static int	npar

Detailed Description

Some generic methods about loops and list of loops.

There are many things elsewhere that should be factored out into here (static controlize...).

Function Documentation

clean_enclosing_loops()

void clean_enclosing_loops

(

void

)

warning: there are shared lists...

Definition at line 58 of file loop.c.

{
    /* warning: there are shared lists...
     */
    hash_table seen = hash_table_make(hash_pointer, 0);
 
    STATEMENT_MAPPING_MAP(s, l,
    {
        if (l && !hash_defined_p(seen, l))
        {
            gen_free_list((list)l);
            hash_put(seen, l, (char*) 1);
        }
    },
        get_enclosing_loops_map());
 
    hash_table_free(seen);
    free_enclosing_loops_map();
}

References free_enclosing_loops_map(), gen_free_list(), get_enclosing_loops_map(), hash_defined_p(), hash_pointer, hash_put(), hash_table_free(), hash_table_make(), seen, and STATEMENT_MAPPING_MAP.

Referenced by chains(), outliner_parameters(), prettyprint_dependence_graph_view(), rice_dependence_graph(), and rice_loop().

Here is the call graph for this function:

Here is the caller graph for this function:

constant_step_loop_p()

bool constant_step_loop_p

(

loop

l

)

Test if a loop has a constant step loop.

Definition at line 733 of file loop.c.

                                  {
  pips_debug(7, "doing\n");
  return(expression_constant_p(range_increment(loop_range(l))));
}

References expression_constant_p(), loop_range, pips_debug, and range_increment.

Referenced by normal_loop_p(), and static_controlize_loop().

Here is the call graph for this function:

Here is the caller graph for this function:

copy_loops()

list copy_loops

(

list

ll

)

Duplicate a loop list.

Parameters

ll

l

Definition at line 826 of file loop.c.

{
  list nll = gen_full_copy_list(ll);
 
  return nll;
}

References gen_full_copy_list().

Referenced by static_controlize_call().

Here is the call graph for this function:

Here is the caller graph for this function:

depth_of_parallel_perfect_loop_nest()

int depth_of_parallel_perfect_loop_nest

(

statement

s

)

Compute the depth of a parallel perfect loop-nest.

Returns

the depth of parallel perfect loop-nest found. If there is no loop here, return 0

No parallel loop found here

Definition at line 436 of file loop.c.

                                                     {
  // We can have blocks and declarations surrounding loops
  while(statement_block_p(s)) {
    statement prev = s;
    for(list iter=statement_block(s);!ENDP(iter);POP(iter)) {
      statement st = STATEMENT(CAR(iter));
      // We can ignore declarations... until there is an initialization !
      if(declaration_statement_p(st)) {
        FOREACH(entity,e,statement_declarations(st)) {
          if(!value_undefined_p(entity_initial(e))
              && !value_unknown_p(entity_initial(e))) {
            return 0;
          }
        }
        continue;
      } else if(gen_length(iter)!=1) {
        return 0;
      } else {
        s = st;
      }
    }
    if(s == prev) return 0;
  }
 
  if(parallel_loop_statement_p(s)) {
    // Get the loop
    loop l = statement_loop(s);
    // Count the current one and dig into the statement of the loop:
    return 1 + depth_of_parallel_perfect_loop_nest(loop_body(l));
  } else {
    /* No parallel loop found here */
    return 0;
  }
}

References CAR, declaration_statement_p(), ENDP, entity_initial, FOREACH, gen_length(), loop_body, parallel_loop_statement_p(), POP, STATEMENT, statement_block(), statement_block_p, statement_declarations, statement_loop(), value_undefined_p, and value_unknown_p.

Referenced by gpu_ify(), loop_push(), mark_loop_to_outline(), and old__gpu_ify().

Here is the call graph for this function:

Here is the caller graph for this function:

depth_of_perfect_loop_nest()

int depth_of_perfect_loop_nest

(

statement

s

)

Compute the depth of a perfect loop-nest.

Returns

the depth of perfect loop-nest found. If there is no loop here, return 0

No loop found here

Definition at line 476 of file loop.c.

                                            {
  // We can have blocks and declarations surrounding loops
  if(statement_block_p(s)) {
    if(ENDP(statement_block(s))) return 0;
    for(list iter=statement_block(s);!ENDP(iter);POP(iter)) {
      statement st = STATEMENT(CAR(iter));
      if(declaration_statement_p(st))//ok, skip this
        continue;
      else if(gen_length(iter)!=1) return 0;
      else
        s = st;
    }
  }
 
  if(statement_loop_p(s)) {
    // Get the loop
    loop l = statement_loop(s);
    // Count the current one and dig into the statement of the loop:
    return 1 + depth_of_perfect_loop_nest(loop_body(l));
  } else {
    /* No loop found here */
    return 0;
  }
}

References CAR, declaration_statement_p(), ENDP, gen_length(), loop_body, POP, STATEMENT, statement_block(), statement_block_p, statement_loop(), and statement_loop_p().

Referenced by loop_push().

Here is the call graph for this function:

Here is the caller graph for this function:

distributable_loop()

set distributable_loop

(

statement

l

)

this functions checks if Kennedy's algorithm can be applied on the loop passed as argument.

If yes, it returns a set containing all statements belonging to this loop including the initial loop itself. otherwise, it returns an undefined set.

Our version of Kennedy's algorithm can only be applied on loops containing no test, goto or unstructured control structures.

Definition at line 221 of file loop.c.

{
    set r;
 
    pips_assert("distributable_loop", statement_loop_p(l));
 
    r = set_make(set_pointer);
 
    if (distributable_statement_p(l, r)) {
        return(r);
    }
 
    set_free(r);
    return(set_undefined);
}

References distributable_statement_p(), pips_assert, set_free(), set_make(), set_pointer, set_undefined, and statement_loop_p().

Referenced by rdg_loop(), and rice_loop().

Here is the call graph for this function:

Here is the caller graph for this function:

distributable_statement_p()

static bool distributable_statement_p ( statement  stat, set  region  )

static

just to avoid a gcc warning

Definition at line 176 of file loop.c.

{
    instruction i = statement_instruction(stat);
 
    switch(instruction_tag(i))
    {
    case is_instruction_block:
        MAPL(ps, {
            if (!distributable_statement_p(STATEMENT(CAR(ps)),
                                          region)) {
                return(false);
            }
        }, instruction_block(i));
        return(true);
 
    case is_instruction_loop:
        region = set_add_element(region, region, (char *) stat);
        return(distributable_statement_p(loop_body(instruction_loop(i)),
                                         region));
 
    case is_instruction_call:
        region = set_add_element(region, region, (char *) stat);
        return(true);
 
    case is_instruction_whileloop:
    case is_instruction_goto:
    case is_instruction_unstructured:
    case is_instruction_test:
    case is_instruction_expression:
        return(false);
    default:
        pips_internal_error("unexpected tag %d", instruction_tag(i));
    }
 
    return((bool) 0); /* just to avoid a gcc warning */
}

References CAR, instruction_block, instruction_loop, instruction_tag, is_instruction_block, is_instruction_call, is_instruction_expression, is_instruction_goto, is_instruction_loop, is_instruction_test, is_instruction_unstructured, is_instruction_whileloop, loop_body, MAPL, pips_internal_error, region, set_add_element(), STATEMENT, and statement_instruction.

Referenced by distributable_loop().

Here is the call graph for this function:

Here is the caller graph for this function:

get_first_inner_perfectly_nested_loop()

statement get_first_inner_perfectly_nested_loop

(

statement

stat

)

Return the inner loop in a perfect loop-nest.

Parameters

stat	is the statement to test

Returns

the loop statement if we have a perfect loop nest, else statement_undefined

Parameters

stat

tat

Definition at line 508 of file loop.c.

                                                                {
  instruction ins = statement_instruction(stat);
  tag t = instruction_tag(ins);
 
  switch(t) {
    case is_instruction_block: {
      list lb = instruction_block(ins);
 
      if(lb != NIL && (lb->cdr) != NIL && (lb->cdr)->cdr == NIL
          && (continue_statement_p(STATEMENT(CAR(lb))))) {
        return get_first_inner_perfectly_nested_loop(STATEMENT(CAR(lb->cdr)));
      } else if(lb != NIL && (lb->cdr) == NIL) {
        return get_first_inner_perfectly_nested_loop(STATEMENT(CAR(lb)));
      }
      break;
    }
    case is_instruction_loop: {
      return stat;
    }
    default:
      break;
  }
 
  return statement_undefined;
 
}

References CAR, cons::cdr, continue_statement_p(), instruction_block, instruction_tag, is_instruction_block, is_instruction_loop, NIL, STATEMENT, statement_instruction, and statement_undefined.

Here is the call graph for this function:

index_of_a_loop_p()

bool index_of_a_loop_p	(	Variable	v,
		list	loops
	)

Check if variable v is an index for an enclosing loop.

Parameters

loops

of statements

Definition at line 980 of file loop.c.

{
  bool result = false;
  FOREACH(statement, s, loops) {
    loop l = statement_loop(s);
    pips_debug(5,"Enclosed loop with index : %s\n",entity_name(loop_index(l)));
    if( same_entity_p((entity)v,loop_index(l) ) ) {
      result = true;
    }
  }
 
  if(result) pips_debug(4,"%s is a loop index !\n",entity_name((entity)v));
  else pips_debug(4,"%s is not a loop index !\n",entity_name((entity)v));
 
  return result;
}

References entity_name, FOREACH, loop_index, loops, pips_debug, same_entity_p(), and statement_loop().

Referenced by get_variables_to_remove().

Here is the call graph for this function:

Here is the caller graph for this function:

index_private_p()

bool index_private_p

(

loop

lo

)

returns true if loop lo's index is private for this loop

Parameters

lo

o

Definition at line 240 of file loop.c.

{
    if( lo == loop_undefined ) {
        pips_internal_error("Loop undefined");
    }
 
    return((entity) gen_find_eq(loop_index(lo), loop_locals(lo)) !=
           entity_undefined);
}

References entity_undefined, gen_find_eq(), loop_index, loop_locals, loop_undefined, and pips_internal_error.

Referenced by ConnectedStatements(), and MakeNestOfParallelLoops().

Here is the call graph for this function:

Here is the caller graph for this function:

loop_executed_at_least_once_p()

bool loop_executed_at_least_once_p

(

loop

l

)

Check if loop bound are constant and then if upper >= lower.

Parameters

l	loop to check execution

Returns

true if the loop is always executed at least once

Definition at line 937 of file loop.c.

{
  return range_contains_at_least_one_point_p(loop_range(l));
}

References loop_range, and range_contains_at_least_one_point_p().

Referenced by inout_loop(), live_in_paths_of_loop(), and live_out_paths_from_loop_to_body().

Here is the call graph for this function:

Here is the caller graph for this function:

loop_executed_never_p()

bool loop_executed_never_p

(

loop

l

)

Check if loop bound are constant and then if upper < lower.

Parameters

l	loop to check execution

Returns

true if the loop is never executed if we don't know return false

Definition at line 971 of file loop.c.

{
  return range_contains_nothing_p(loop_range(l));
}

References loop_range, and range_contains_nothing_p().

Referenced by inout_loop(), live_in_paths_of_loop(), and live_out_paths_from_loop_to_body().

Here is the call graph for this function:

Here is the caller graph for this function:

loop_increment_value()

int loop_increment_value

(

loop

l

)

ser_error("loop_increment_value", "increment is not constant");

Definition at line 714 of file loop.c.

                             {
  range r = loop_range(l);
  expression ic = range_increment(r);
  normalized ni;
  int inc;
 
  ni = NORMALIZE_EXPRESSION(ic);
 
  if (! EvalNormalized(ni, &inc)){
    /*user_error("loop_increment_value", "increment is not constant");*/
    debug(8,"loop_increment_value", "increment is not constant");
    return(0);
  }
  return(inc);
}

References debug(), EvalNormalized(), loop_range, NORMALIZE_EXPRESSION, and range_increment.

Referenced by build_and_test_dependence_context(), dependence_system_add_lci_and_di(), gcd_and_constant_dependence_test(), loop_strip_mine(), and make_context_of_loop().

Here is the call graph for this function:

Here is the caller graph for this function:

loop_parallel_p()

bool loop_parallel_p

(

loop

l

)

Test if a loop is parallel.

Parameters

l	is the loop to test

Returns

true if the loop has a parallel execution mode

Definition at line 393 of file loop.c.

                             {
  return execution_parallel_p(loop_execution(l));
}

References execution_parallel_p, and loop_execution.

Referenced by live_in_paths_of_loop(), live_out_paths_from_loop_to_body(), loop_push(), loop_update_statistics(), parallel_loop_statement_p(), and process_reductions_in_loop().

Here is the caller graph for this function:

loop_private_variables_as_entites()

list loop_private_variables_as_entites	(	loop	obj,
		bool	local,
		bool	index
	)

Get the variables local or private to a loop.

The function can also remove from that list all the variables that are localy declared in the loop statement body and the loop index using the apropriate flags.

Parameters

obj,the	loop to look at.
local,set	to true to remove the the variables that are localy declared.
index,set	to true to remove the loop index variable

Returns

a list of entities that are private in the current * context.

Parameters

obj	bj
local	ocal
index	ndex

Definition at line 338 of file loop.c.

                                                                          {
  // List of entities that are private to the loop according to the previous
  // phases. For historical reasons private variables are stored in the
  // locals field of the loop.
  list result = gen_copy_seq (loop_locals(obj));
 
  ifdebug(9) {
    pips_debug (9, "private entites to the loop:\n");
    print_entities (result);
    fprintf (stderr, "\n");
  }
 
  if (local ) {
    // List of localy declared entities that are stored in loop body
    list decl_var = statement_declarations (loop_body (obj));
    ifdebug(9) {
      pips_debug (9, "localy declaed entites:\n");
      print_entities (decl_var);
      fprintf (stderr, "\n");
    }
    gen_list_and_not (&result, decl_var);
  }
 
  if (index ) {
    pips_debug (9, "loop_indexl to remove : %s\n", entity_name (loop_index(obj)));
    gen_remove (&result, loop_index(obj));
  }
 
  sort_list_of_entities(result);
 
  return result;
}

References entity_name, fprintf(), gen_copy_seq(), gen_list_and_not(), gen_remove(), ifdebug, loop_body, loop_index, loop_locals, pips_debug, print_entities(), sort_list_of_entities(), and statement_declarations.

Referenced by loop_private_variables(), and omp_append_private_clause().

Here is the call graph for this function:

Here is the caller graph for this function:

loop_sequential_p()

bool loop_sequential_p

(

loop

l

)

Test if a loop is sequential.

Parameters

l	is the loop to test

Returns

true if the loop has a sequential execution mode

Definition at line 404 of file loop.c.

                               {
  return execution_sequential_p(loop_execution(l));
}

References execution_sequential_p, and loop_execution.

Referenced by gpu_promote_sequential_walker_in().

Here is the caller graph for this function:

loop_sort_locals()

static void loop_sort_locals ( loop  l )

static

of entity

Definition at line 375 of file loop.c.

{
    list /* of entity */ le = loop_locals(l);
    if (le) sort_list_of_entities(le);
}

References loop_locals, and sort_list_of_entities().

Referenced by sort_all_loop_locals().

Here is the call graph for this function:

Here is the caller graph for this function:

loop_update_statistics()

static void loop_update_statistics ( loop  l )

static

Definition at line 763 of file loop.c.

{
  if (loop_parallel_p(l))
    npar++;
  else
    nseq++;
}

References loop_parallel_p(), npar, and nseq.

Referenced by number_of_sequential_and_parallel_loops().

Here is the call graph for this function:

Here is the caller graph for this function:

loops_mapping_of_statement()

statement_mapping loops_mapping_of_statement

(

statement

stat

)

Parameters

stat

tat

Definition at line 155 of file loop.c.

{
    statement_mapping loops_map;
    loops_map = MAKE_STATEMENT_MAPPING();
    Nbrdo = 0;
    rloops_mapping_of_statement(loops_map, NIL, stat);
 
    if (get_debug_level() >= 7) {
      STATEMENT_MAPPING_MAP(stat, loops, {
          fprintf(stderr, "statement %td in loops ",
                  statement_number((statement) stat));
          FOREACH (STATEMENT, s,loops)
            fprintf(stderr, "%td ", statement_number(s));
          fprintf(stderr, "\n");
        }, loops_map)
    }
    return(loops_map);
}

References FOREACH, fprintf(), get_debug_level(), loops, MAKE_STATEMENT_MAPPING, Nbrdo, NIL, rloops_mapping_of_statement(), STATEMENT, STATEMENT_MAPPING_MAP, and statement_number.

Referenced by chains(), outliner_parameters(), prettyprint_dependence_graph_view(), prettyprint_dot_dependence_graph(), rice_dependence_graph(), rice_loop(), and search_parallel_loops().

Here is the call graph for this function:

Here is the caller graph for this function:

make_new_loop_statement()

statement make_new_loop_statement	(	entity	i,
		expression	low,
		expression	up,
		expression	inc,
		statement	b,
		execution	e
	)

This is an ad'hoc function designed for do_loop_unroll_with_epilogue().

The expression and execution parameters are reused directly in the new loop, but the body must be cloned. Compared to make_loop(), this function adds the cloning and the wrapping into an instruction and a statement.

Loop range is created

Create body of the loop, with updated index

"gen_copy_tree returns bad statement\n");

Parameters

low	ow
up	p
inc	nc

Definition at line 839 of file loop.c.

{
  /* Loop range is created */
  range rg = make_range(low, up, inc);
 
  ifdebug(9) {
    pips_assert("new range is consistent", range_consistent_p(rg));
  }
 
  /* Create body of the loop, with updated index */
  clone_context cc = make_clone_context(
      get_current_module_entity(),
      get_current_module_entity(),
      NIL,
      get_current_module_statement() );
  statement body = clone_statement(b, cc);
  free_clone_context(cc);
 
  ifdebug(9) {
    pips_assert("cloned body is consistent", statement_consistent_p(body));
    /* "gen_copy_tree returns bad statement\n"); */
  }
 
  entity label_entity = entity_empty_label();
 
  ifdebug(9) {
    pips_assert("the cloned is consistent",
        statement_consistent_p(body));
  }
 
  instruction inst = make_instruction(is_instruction_loop,
      make_loop(i,
          rg,
          body,
          label_entity,
          e,
          NIL));
 
  ifdebug(9) {
    pips_assert("inst is consistent",
        instruction_consistent_p(inst));
  }
 
  statement stmt = instruction_to_statement(inst);
  return stmt;
}

References clone_statement(), entity_empty_label(), free_clone_context(), get_current_module_entity(), get_current_module_statement(), ifdebug, instruction_consistent_p(), instruction_to_statement(), is_instruction_loop, make_clone_context(), make_instruction(), make_loop(), make_range(), NIL, pips_assert, range_consistent_p(), and statement_consistent_p().

Referenced by do_loop_unroll_with_epilogue(), and promote_statement().

Here is the call graph for this function:

Here is the caller graph for this function:

normal_loop_p()

bool normal_loop_p

(

loop

l

)

Test if a loop does have a 1-increment step.

Definition at line 741 of file loop.c.

                           {
  expression ri;
  entity ent;
 
  pips_debug(7, "doing\n");
 
  if (!constant_step_loop_p(l))
    // No way for a non-constant step to be a 1-constant :-)
    return(false);
 
  ri = range_increment(loop_range(l));
  ent = reference_variable(syntax_reference(expression_syntax(ri)));
  return strcmp(entity_local_name(ent), "1") == 0;
}

References constant_step_loop_p(), entity_local_name(), expression_syntax, loop_range, pips_debug, range_increment, reference_variable, and syntax_reference.

Here is the call graph for this function:

number_of_sequential_and_parallel_loops()

void number_of_sequential_and_parallel_loops	(	statement	stat,
		int *	pseq,
		int *	ppar
	)

Compute the number of parallel and sequential loops found in a statement and update given variables.

Parameters

stat	is the statement to dig into
pseq	point to the variable to update with the number of sequential loops found
ppr	point to the variable to update with the number of parallel loops found

Parameters

stat	tat
pseq	seq
ppar	par

Definition at line 784 of file loop.c.

                                                         {
  nseq=0, npar=0;
  gen_recurse(stat, loop_domain, gen_true, loop_update_statistics);
  *pseq=nseq, *ppar=npar;
}

References gen_recurse, gen_true(), loop_domain, loop_update_statistics(), npar, and nseq.

Referenced by print_number_of_loop_statistics().

Here is the call graph for this function:

Here is the caller graph for this function:

parallel_loop_statement_p()

bool parallel_loop_statement_p

(

statement

s

)

Test if a statement is a parallel loop.

It tests the parallel status of the loop but should test extensions such as OpenMP pragma and so on. TODO...

Parameters

s	is the statement that may own the loop. We need this statement to get the pragma for the loop. instruction with a loop in it.

Returns

true only if the statement is a parallel loop.

Definition at line 420 of file loop.c.

                                            {
  if (statement_loop_p(s)) {
    instruction i = statement_instruction(s);
    loop l = instruction_loop(i);
 
    return loop_parallel_p(l);
  }
  return false;
}

References instruction_loop, loop_parallel_p(), statement_instruction, and statement_loop_p().

Referenced by depth_of_parallel_perfect_loop_nest(), gpu_promote_sequential_on_sequence(), and rice_loop().

Here is the call graph for this function:

Here is the caller graph for this function:

perfectly_nested_loop_index_at_depth()

entity perfectly_nested_loop_index_at_depth	(	statement	s,
		int	depth
	)

Get the index of the loop at a given depth inside a loop-nest.

Parameters

s	is the loop-nest statement to dig into
depth	is the diving depth

Returns

the loop-body found at the given depth

there may be some declarations before

Parameters

depth

epth

Definition at line 694 of file loop.c.

                                                             {
  statement preloop = perfectly_nested_loop_to_body_at_depth(s, depth);
  /* there may be some declarations before */
  while(statement_block_p(preloop)) {
    for(list iter= statement_block(preloop);!ENDP(iter);POP(iter))
      if(declaration_statement_p(STATEMENT(CAR(iter)))) continue;
      else { preloop = STATEMENT(CAR(iter)) ;  break ;}
  }
 
  return loop_index(statement_loop(preloop));
}

References CAR, declaration_statement_p(), depth, ENDP, loop_index, perfectly_nested_loop_to_body_at_depth(), POP, STATEMENT, statement_block(), statement_block_p, and statement_loop().

Referenced by gpu_ify_statement().

Here is the call graph for this function:

Here is the caller graph for this function:

perfectly_nested_loop_p()

bool perfectly_nested_loop_p

(

statement

stat

)

Test if a statement is a perfect loop-nest.

Parameters

stat	is the statement to test

Returns

true if the statement is a perfect loop-nest

biased for WP65

extreme case: empty loop nest

Parameters

stat

tat

Definition at line 543 of file loop.c.

                                        {
  instruction ins = statement_instruction(stat);
  tag t = instruction_tag(ins);
 
  switch( t ) {
  case is_instruction_block: {
    list lb = instruction_block(ins);
 
    if ( lb != NIL && (lb->cdr) != NIL && (lb->cdr)->cdr == NIL
         && ( continue_statement_p(STATEMENT(CAR(lb->cdr))) ) ) {
      if ( assignment_statement_p(STATEMENT(CAR(lb))) )
        return true;
      else
        return(perfectly_nested_loop_p(STATEMENT(CAR(lb))));
    }
    else if ( lb != NIL && (lb->cdr) == NIL )
      return(perfectly_nested_loop_p(STATEMENT(CAR(lb))));
    else if ( lb != NIL ) {
      /* biased for WP65 */
      return assignment_block_p(ins);
    }
    else
      /* extreme case: empty loop nest */
      return true;
    break;
  }
  case is_instruction_loop: {
    loop lo = instruction_loop(ins);
    statement sbody = loop_body(lo);
 
    if ( assignment_statement_p(sbody) )
      return true;
    else
      return(perfectly_nested_loop_p(sbody));
    break;
  }
  default:
    break;
  }
 
  return false;
}

References assignment_block_p(), assignment_statement_p(), CAR, cons::cdr, continue_statement_p(), instruction_block, instruction_loop, instruction_tag, is_instruction_block, is_instruction_loop, loop_body, NIL, STATEMENT, and statement_instruction.

Referenced by simdizer_auto_tile(), and wp65_conform_p().

Here is the call graph for this function:

Here is the caller graph for this function:

perfectly_nested_loop_to_body()

statement perfectly_nested_loop_to_body

(

statement

loop_nest

)

Extract the body of a perfectly nested loop body.

By hypothesis we are in a perfectly nested loop and since it is not a loop, we've reached the loop body:

The loop body is an empty block, such as { } in C:

It is another loop: dig into it to reach the loop body:

just to avoid a warning

Parameters

loop_nest

oop_nest

Definition at line 590 of file loop.c.

                                                   {
  instruction ins = statement_instruction(loop_nest);
 
  switch(instruction_tag(ins)) {
 
  case is_instruction_call:
  case is_instruction_whileloop:
  case is_instruction_test:
    /* By hypothesis we are in a perfectly nested loop and since it is
       not a loop, we've reached the loop body: */
    return loop_nest;
 
  case is_instruction_block: {
    list lb = instruction_block(ins);
    if (lb == NIL)
      /* The loop body is an empty block, such as { } in C: */
      return loop_nest;
    statement first_s = STATEMENT(CAR(lb));
    instruction first_i = statement_instruction(first_s);
 
    if(instruction_call_p(first_i))
      return loop_nest;
    else {
      if(instruction_block_p(first_i))
        return perfectly_nested_loop_to_body(STATEMENT(CAR(instruction_block(first_i))));
      else {
        pips_assert("perfectly_nested_loop_to_body",
                    instruction_loop_p(first_i));
        return perfectly_nested_loop_to_body( first_s);
      }
    }
    break;
  }
  case is_instruction_loop: {
    /* It is another loop: dig into it to reach the loop body: */
    statement sbody = loop_body(instruction_loop(ins));
    return (perfectly_nested_loop_to_body(sbody));
    break;
  }
  default:
    pips_internal_error("illegal tag");
    break;
  }
  return(statement_undefined); /* just to avoid a warning */
}

References CAR, instruction_block, instruction_block_p, instruction_call_p, instruction_loop, instruction_loop_p, instruction_tag, is_instruction_block, is_instruction_call, is_instruction_loop, is_instruction_test, is_instruction_whileloop, loop_body, NIL, pips_assert, pips_internal_error, STATEMENT, statement_instruction, and statement_undefined.

Referenced by loop_nest_to_wp65_code().

Here is the caller graph for this function:

perfectly_nested_loop_to_body_at_depth()

statement perfectly_nested_loop_to_body_at_depth	(	statement	s,
		int	depth
	)

Extract the loop-body of a perfect loop-nest at a given depth.

Parameters

s	is the loop-nest statement to dig into
depth	is the diving depth

Returns

the loop-body found at the given depth

ifdebug(2) {

pips_debug(1, "Look at statement at depth 0:\n");

print_statement(body);

}

ifdebug(2) {

pips_debug(1, "Look at statement at depth %d:\n", i + 1);

print_statement(body);

}

Parameters

depth

epth

Definition at line 646 of file loop.c.

                                                               {
  // To have it working for depth = 0 too:
  statement body = s;
  /* ifdebug(2) { */
  /*   pips_debug(1, "Look at statement at depth 0:\n"); */
  /*   print_statement(body); */
  /* } */
  for(int i = 0; i < depth; i++) {
 
    // We can have blocks and declarations surrounding loops
    while(statement_block_p(body)) {
      for(list iter=statement_block(body);!ENDP(iter);POP(iter)) {
        statement st = STATEMENT(CAR(iter));
        if(declaration_statement_p(st))//ok, skip this
          continue;
        else if(gen_length(iter)!=1) pips_internal_error("should be a perfectly nested loop\n");
        else
          body = st;
        }
    }
 
    pips_assert("The statement is a loop", statement_loop_p(body));
    // Dive into one loop:
    body = loop_body(statement_loop(body));
 
    /* ifdebug(2) { */
    /*   pips_debug(1, "Look at statement at depth %d:\n", i + 1); */
    /*   print_statement(body); */
    /* } */
  }
  // We can have blocks and declarations surrounding loops
  while(statement_block_p(body)&&gen_length(statement_block(body))==1) {
        body=STATEMENT(CAR(statement_block(body)));
  }
 
  return body;
}

References CAR, declaration_statement_p(), depth, ENDP, gen_length(), loop_body, pips_assert, pips_internal_error, POP, STATEMENT, statement_block(), statement_block_p, statement_loop(), and statement_loop_p().

Referenced by gpu_ify_statement(), gpu_memory_apply(), and perfectly_nested_loop_index_at_depth().

Here is the call graph for this function:

Here is the caller graph for this function:

print_number_of_loop_statistics()

void print_number_of_loop_statistics	(	FILE *	out,
		string	msg,
		statement	s
	)

Compute the number of parallel and sequential loops found in a statement and output them on a stream with a message before.

Parameters

out	is the stream to send the information to
msg	is the message to prepend
s	is the statement to dig into

Parameters

out	ut
msg	sg

Definition at line 803 of file loop.c.

                                                  {
  int seq, par;
  number_of_sequential_and_parallel_loops(s, &seq, &par);
  fprintf(out, "%s: %d seq loops, %d par loops\n", msg, seq, par);
}

References fprintf(), number_of_sequential_and_parallel_loops(), and out.

Referenced by print_parallelization_statistics().

Here is the call graph for this function:

Here is the caller graph for this function:

print_parallelization_statistics()

void print_parallelization_statistics	(	const char *	module,
		const char *	msg,
		statement	s
	)

Print out the number of sequential versus parallel loops.

Parameters

module	the module name
msg	an additional message
s	the module statement to consider

Definition at line 814 of file loop.c.

                      {
  if (get_bool_property("PARALLELIZATION_STATISTICS"))
    {
      fprintf(stderr, "%s %s parallelization statistics", module, msg);
      print_number_of_loop_statistics(stderr, "", s);
    }
}

References fprintf(), get_bool_property(), module, and print_number_of_loop_statistics().

Referenced by do_it().

Here is the call graph for this function:

Here is the caller graph for this function:

range_contains_at_least_one_point_p()

bool range_contains_at_least_one_point_p

(

range

r

)

Definition at line 911 of file loop.c.

{
  bool return_val = false;
  expression low = range_lower(r); int i_low;
  expression up = range_upper(r); int i_up;
  expression inc = range_increment(r); int i_inc;
  if(extended_integer_constant_expression_p_to_int(low, &i_low)
     && extended_integer_constant_expression_p_to_int(up, &i_up)
     && extended_integer_constant_expression_p_to_int(inc, &i_inc) ) {
    if (i_inc > 0 && i_up >= i_low) {
      // Increasing case
      return_val = true;
    }
    else if (i_inc < 0 && i_up <= i_low) {
      // Decreasing case
      return_val = true;
    }
  }
  return return_val;
}

References extended_integer_constant_expression_p_to_int(), range_increment, range_lower, and range_upper.

Referenced by loop_executed_at_least_once_p().

Here is the call graph for this function:

Here is the caller graph for this function:

range_contains_nothing_p()

bool range_contains_nothing_p

(

range

r

)

Definition at line 943 of file loop.c.

{
  bool return_val = false;
  expression low = range_lower(r); int i_low;
  expression up = range_upper(r); int i_up;
  expression inc = range_increment(r); int i_inc;
  if(extended_integer_constant_expression_p_to_int(low, &i_low)
     && extended_integer_constant_expression_p_to_int(up, &i_up)
     && extended_integer_constant_expression_p_to_int(inc, &i_inc) ) {
    if (i_inc > 0 && i_up < i_low) {
      // Increasing case
      return_val = true;
    }
    else if (i_inc < 0 && i_up > i_low) {
      // Decreasing case
      return_val = true;
    }
  }
  return return_val;
}

References extended_integer_constant_expression_p_to_int(), range_increment, range_lower, and range_upper.

Referenced by loop_executed_never_p().

Here is the call graph for this function:

Here is the caller graph for this function:

region_of_loop()

set region_of_loop

(

statement

l

)

this function returns the set of all statements belonging to the given loop even if the loop contains test, goto or unstructured control structures

Definition at line 254 of file loop.c.

{
    set r;
 
    pips_assert("distributable_loop", statement_loop_p(l));
 
    r = set_make(set_pointer);
    region_of_statement(l,r);
    return(r);
}

References pips_assert, region_of_statement(), set_make(), set_pointer, and statement_loop_p().

Referenced by rdg_loop(), and search_parallel_loops().

Here is the call graph for this function:

Here is the caller graph for this function:

region_of_statement()

void region_of_statement	(	statement	stat,
		set	region
	)

Should be rewritten with a gen_recurse to deal with the recent RI...

The next statement is added by Y.Q. 12/9.

Parameters

stat	tat
region	egion

Definition at line 269 of file loop.c.

{
  instruction i = statement_instruction(stat);
 
  switch(instruction_tag(i)) {
 
  case is_instruction_block:
      MAPL(ps, {
          region_of_statement(STATEMENT(CAR(ps)),region);
      }, instruction_block(i));
      break;
 
  case is_instruction_loop:{
      region = set_add_element(region, region, (char *) stat);
      region_of_statement(loop_body(instruction_loop(i)),region);
      break;
  }
 
  case is_instruction_call:
  case is_instruction_expression:
      region = set_add_element(region, region, (char *) stat);
      break;
 
  case is_instruction_goto:
      region = set_add_element(region, region, (char *) stat);
      break;
 
  case is_instruction_test:
      /* The next statement is added by Y.Q. 12/9.*/
      region = set_add_element(region, region, (char *) stat);
      region_of_statement(test_true(instruction_test(i)), region);
      region_of_statement(test_false(instruction_test(i)), region);
      break;
 
  case is_instruction_unstructured:{
      unstructured u = instruction_unstructured(i);
      cons *blocs = NIL;
 
      CONTROL_MAP(c, {
          region_of_statement(control_statement(c), region);
      }, unstructured_control(u), blocs) ;
 
      gen_free_list(blocs) ;
      break;
  }
 
  default:
      pips_internal_error("unexpected tag %d", instruction_tag(i));
  }
}

References CAR, CONTROL_MAP, control_statement, gen_free_list(), instruction_block, instruction_loop, instruction_tag, instruction_test, instruction_unstructured, is_instruction_block, is_instruction_call, is_instruction_expression, is_instruction_goto, is_instruction_loop, is_instruction_test, is_instruction_unstructured, loop_body, MAPL, NIL, pips_internal_error, region, set_add_element(), STATEMENT, statement_instruction, test_false, test_true, and unstructured_control.

Referenced by region_of_loop().

Here is the call graph for this function:

Here is the caller graph for this function:

rloops_mapping_of_statement() [1/2]

static void rloops_mapping_of_statement ( )

static

Referenced by loops_mapping_of_statement(), rloops_mapping_of_statement(), and rloops_mapping_of_unstructured().

Here is the caller graph for this function:

rloops_mapping_of_statement() [2/2]

static void rloops_mapping_of_statement ( statement_mapping  m, list  loops, statement  s  )

static

Definition at line 94 of file loop.c.

{
    instruction i = statement_instruction(s);
 
    SET_STATEMENT_MAPPING(m, s, gen_copy_seq(loops));
 
    switch(instruction_tag(i)) {
 
      case is_instruction_block:
        MAP(STATEMENT, s, rloops_mapping_of_statement(m, loops, s),
            instruction_block(i));
        break;
 
      case is_instruction_loop:
      {
          list nl = gen_nconc(gen_copy_seq(loops), CONS(STATEMENT, s, NIL));
          Nbrdo++;
          rloops_mapping_of_statement(m, nl, loop_body(instruction_loop(i)));
          gen_free_list(nl);
          break;
      }
 
      case is_instruction_test:
        rloops_mapping_of_statement(m, loops, test_true(instruction_test(i)));
        rloops_mapping_of_statement(m, loops, test_false(instruction_test(i)));
        break;
 
      case is_instruction_whileloop:
        rloops_mapping_of_statement(m, loops, whileloop_body(instruction_whileloop(i)));
        break;
 
      case is_instruction_call:
        break;
      case is_instruction_expression:
        break;
      case is_instruction_goto:
        pips_internal_error("Go to instruction in CODE internal representation");
        break;
 
      case is_instruction_unstructured: {
          rloops_mapping_of_unstructured(m, loops,instruction_unstructured(i));
          break ;
      }
 
      case is_instruction_forloop: {
        /*
          pips_user_error("Use property FOR_TO_WHILE_LOOP_IN_CONTROLIZER or "
                          "FOR_TO_DO_LOOP_IN_CONTROLIZER to convert for loops into while loops\n");
        */
        rloops_mapping_of_statement(m, loops, forloop_body(instruction_forloop(i)));
        break ;
      }
      default:
        pips_internal_error("unexpected tag %d", instruction_tag(i));
    }
}

References CONS, forloop_body, gen_copy_seq(), gen_free_list(), gen_nconc(), instruction_block, instruction_forloop, instruction_loop, instruction_tag, instruction_test, instruction_unstructured, instruction_whileloop, is_instruction_block, is_instruction_call, is_instruction_expression, is_instruction_forloop, is_instruction_goto, is_instruction_loop, is_instruction_test, is_instruction_unstructured, is_instruction_whileloop, loop_body, loops, MAP, Nbrdo, NIL, pips_internal_error, rloops_mapping_of_statement(), rloops_mapping_of_unstructured(), SET_STATEMENT_MAPPING, STATEMENT, statement_instruction, test_false, test_true, and whileloop_body.

Here is the call graph for this function:

rloops_mapping_of_unstructured()

static void rloops_mapping_of_unstructured ( statement_mapping  m, list  loops, unstructured  u  )

static

Definition at line 80 of file loop.c.

{
    list blocs = NIL ;
 
    CONTROL_MAP(c, rloops_mapping_of_statement(m, loops, control_statement(c)),
                unstructured_control(u), blocs) ;
 
    gen_free_list(blocs) ;
}

References CONTROL_MAP, control_statement, gen_free_list(), loops, NIL, rloops_mapping_of_statement(), and unstructured_control.

Referenced by rloops_mapping_of_statement().

Here is the call graph for this function:

Here is the caller graph for this function:

sort_all_loop_locals()

void sort_all_loop_locals

(

statement

s

)

Definition at line 381 of file loop.c.

{
    gen_multi_recurse(s, loop_domain, gen_true, loop_sort_locals, NULL);
}

References gen_multi_recurse(), gen_true(), loop_domain, and loop_sort_locals().

Here is the call graph for this function:

statement_to_loop_statement_list()

list statement_to_loop_statement_list

(

statement

s

)

If statement s is a perfectly loop nest, return the corresponding loop list.

If not, the list returned is empty.

Definition at line 893 of file loop.c.

{
  list l = NIL;
  statement cs = s;
 
  while(statement_loop_p(cs)) {
    l = gen_nconc(l, CONS(STATEMENT,cs, NIL));
    cs = loop_body(statement_loop(cs));
    if(statement_block_p(cs)) {
      list sl = statement_block(cs);
      if(gen_length(sl)==1)
        cs = STATEMENT(CAR(sl));
    }
  }
 
  return l;
}

References CAR, CONS, gen_length(), gen_nconc(), loop_body, NIL, STATEMENT, statement_block(), statement_block_p, statement_loop(), and statement_loop_p().

Here is the call graph for this function:

Variable Documentation

Nbrdo

int Nbrdo

loop.c

Definition at line 54 of file loop.c.

Referenced by loops_mapping_of_statement(), rice_dependence_graph(), and rloops_mapping_of_statement().

npar

int npar

static

Definition at line 760 of file loop.c.

Referenced by loop_update_statistics(), and number_of_sequential_and_parallel_loops().

nseq

int nseq

static

To store the number of sequential and parallel loops.

Definition at line 760 of file loop.c.

Referenced by loop_update_statistics(), and number_of_sequential_and_parallel_loops().