rice.h File Reference

This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Macros
#define	VERTEX_ENCLOSING_SCC(v)
	Warning! Do not modify this file that is automatically generated! More...
#define	INSERT_AT_END(bl, el, c)    { cons *_insert_ = c; if (bl == NIL) bl = _insert_; else CDR(el) = _insert_; el = _insert_; CDR(el) = NIL; }
	a macro to insert an element at the end of a list. More...

Functions
void	rice_unstructured (unstructured, int, statement(*)(statement, graph, set, int, bool))
statement	rice_statement (statement, int, statement(*)(statement, graph, set, int, bool))
statement	rice_loop (statement, int, statement(*)(statement, graph, set, int, bool))
	Eventually parallelize a do-loop with à la Rice algorithm. More...
bool	do_it (string, bool, string, statement(*)(statement, graph, set, int, bool))
bool	distributer (string)
bool	rice_all_dependence (string)
bool	rice_data_dependence (string)
bool	rice_cray (string)
bool	ignore_this_conflict (vertex, vertex, conflict, int)
	codegen.c More...
statement	find_level_l_loop_statement (scc, int)
	s is a strongly connected component which is analyzed at level l. More...
set	scc_region (scc)
bool	contains_level_l_dependence (scc, set, int)
	s is a strongly connected component for which a DO loop is being produced. More...
bool	strongly_connected_p (scc, int)
	this function returns true if scc s is stronly connected at level l, i.e. More...
statement	MakeNestOfParallelLoops (int, cons *, statement, bool)
	this function creates a nest of parallel loops around an isolated statement whose iterations may execute in parallel. More...
int	statement_imbrication_level (statement)
statement	MakeNestOfStatementList (int, int, list *, list, list *, list *, bool)
statement	CodeGenerate (statement, graph, set, int, bool)
statement	MakeLoopAs (statement, tag, statement)
	This function creates a new loop whose characteristics (index, bounds, ...) are similar to those of old_loop. More...
statement	IsolatedStatement (scc, int, bool)
	If the isolated statement is a CALL and is not a CONTINUE, regenerate the nested loops around it. More...
statement	ConnectedStatements (graph, scc, int, bool)
	BB: ConnectedStatements() is called when s contains more than one vertex or one vertex dependent upon itself. More...
void	set_sccs_drivers (bool(*)(set, vertex), bool(*)(vertex, set, successor, int))
	scc.c More...
void	reset_sccs_drivers (void)
void	LowlinkCompute (graph, set, vertex, int, sccs)
int	IsInStack (vertex)
	this function checks if vertex v is in the stack More...
sccs	FindSccs (graph, set, int)
	FindSccs is the interface function to compute the SCCs of a graph. More...
void	ComputeInDegree (graph, set, int)
list	TopSortSccs (graph, set, int, sccs)
list	FindAndTopSortSccs (graph, set, int)
void	PrintScc (scc)
void	PrintSccs (sccs)
void	dump_sef (statement_effects)
	icm.c More...
void	print_list_entities (list)
bool	invariant_code_motion (const char *)
	Phase that hoists loop invariant code out of loops. More...

Variables
graph	dg
	external variables. More...
bool	rice_distribute_only
	to know if do loop parallelization must be done More...
int	Nbrdoall
int	enclosing
	This is an horrendous hack. More...

Macro Definition Documentation

INSERT_AT_END

#define INSERT_AT_END	(		bl,
			el,
			c
	)		{ cons *_insert_ = c; if (bl == NIL) bl = _insert_; else CDR(el) = _insert_; el = _insert_; CDR(el) = NIL; }

a macro to insert an element at the end of a list.

c is the element to insert. bl and el are pointers to the begining and the end of the list.

Definition at line 42 of file rice.h.

VERTEX_ENCLOSING_SCC

#define VERTEX_ENCLOSING_SCC

(

v

)

Value:

    sccflags_enclosing_scc(dg_vertex_label_sccflags((dg_vertex_label) \
        vertex_vertex_label(v)))

Warning! Do not modify this file that is automatically generated!

Modify src/Libs/rice/rice-local.h instead, to add your own modifications. header file built by cproto rice-local.h macros

Definition at line 33 of file rice.h.

Function Documentation

CodeGenerate()

statement CodeGenerate	(	statement	,
		graph	,
		set	,
		int	,
		bool
	)

ComputeInDegree()

void ComputeInDegree	(	graph	g,
		set	region,
		int	l
	)

Parameters

region

egion

Definition at line 244 of file scc.c.

                                                 {
  FOREACH(VERTEX, v, graph_vertices(g))
  {
    if(!ignore_this_vertex_drv(region, v)) {
      scc sv = VERTEX_ENCLOSING_SCC(v);
      FOREACH(SUCCESSOR, su, vertex_successors(v))
      {
        if(!ignore_this_successor_drv(v, region, su, l)) {
          vertex s = successor_vertex(su);
          scc ss = VERTEX_ENCLOSING_SCC(s);
          if(sv != ss)
            scc_indegree(ss) += 1;
        }
      }
    }
  }
}

References FOREACH, graph_vertices, ignore_this_successor_drv, ignore_this_vertex_drv, region, scc_indegree, SUCCESSOR, successor_vertex, VERTEX, VERTEX_ENCLOSING_SCC, and vertex_successors.

Referenced by FindAndTopSortSccs().

Here is the caller graph for this function:

ConnectedStatements()

statement ConnectedStatements	(	graph	g,
		scc	s,
		int	l,
		bool	task_parallelize_p
	)

BB: ConnectedStatements() is called when s contains more than one vertex or one vertex dependent upon itself.

Thus, vectorization can't occur.

FI: it may not be true if one of the statements is a C declaration.

At most one outer loop parallel

CodeGenerate does not use the first parameter...

big hack

Parameters

task_parallelize_p

ask_parallelize_p

Definition at line 614 of file codegen.c.

                                                                              {
  extern int enclosing;
  statement slo = find_level_l_loop_statement(s, l - enclosing);
  loop lo = statement_loop(slo);
  statement inner_stat;
  set inner_region;
  tag seq_or_par;
  bool task_parallelize_inner;
 
  pips_debug(8, "at level %d:\n",l);
  ifdebug(8)
    PrintScc(s);
 
  inner_region = scc_region(s);
  seq_or_par = (!task_parallelize_p
      || contains_level_l_dependence(s, inner_region, l)
      || !index_private_p(lo)) ? is_execution_sequential
                               : is_execution_parallel;
 
  /* At most one outer loop parallel */
  task_parallelize_inner
      = (seq_or_par == is_execution_parallel
          && !get_bool_property("GENERATE_NESTED_PARALLEL_LOOPS")) ? false
                                                                   : task_parallelize_p;
 
  /* CodeGenerate does not use the first parameter... */
  inner_stat = CodeGenerate(/* big hack */statement_undefined,
                            g,
                            inner_region,
                            l + 1,
                            task_parallelize_inner);
 
  set_free(inner_region);
 
  if(statement_undefined_p(inner_stat))
    return inner_stat;
  else
    return MakeLoopAs(slo, seq_or_par, inner_stat);
}

References CodeGenerate(), contains_level_l_dependence(), enclosing, find_level_l_loop_statement(), get_bool_property(), ifdebug, index_private_p(), is_execution_parallel, is_execution_sequential, MakeLoopAs(), pips_debug, PrintScc(), scc_region(), set_free(), statement_loop(), statement_undefined, and statement_undefined_p.

Referenced by CodeGenerate().

Here is the call graph for this function:

Here is the caller graph for this function:

contains_level_l_dependence()

bool contains_level_l_dependence	(	scc	s,
		set	region,
		int	level
	)

s is a strongly connected component for which a DO loop is being produced.

this function returns false if s contains no dependences at level l. in this case, the loop will be a DOALL loop.

Parameters

region	egion
level	evel

Definition at line 239 of file codegen.c.

                                                               {
  FOREACH(VERTEX, v, scc_vertices(s)) {
    statement s1 = vertex_to_statement(v);
    FOREACH(SUCCESSOR, su, vertex_successors(v))
    {
      vertex vs = successor_vertex(su);
      statement s2 = vertex_to_statement(vs);
 
      if(!AK_ignore_this_vertex(region, vs)) {
        dg_arc_label dal = (dg_arc_label)successor_arc_label(su);
        FOREACH(CONFLICT, c, dg_arc_label_conflicts(dal))
        {
          if(!ignore_this_conflict(v, vs, c, level)) {
            if(conflict_cone(c) != cone_undefined) {
              FOREACH(int, l, cone_levels(conflict_cone(c)))
              {
                if(l == level) {
                  ifdebug(7) {
                    pips_debug(7, "containing conflit at level %d: ",level);
                    fprintf(stderr,
                            "\t%02td --> %02td ",
                            statement_number(s1),
                            statement_number(s2));
                    fprintf(stderr, "\t\tfrom ");
                    print_effect(conflict_source(c));
                    fprintf(stderr, " to ");
                    print_effect(conflict_sink(c));
                    fprintf(stderr, "\n");
                  }
                  return (true);
                }
              }
            }
          }
        }
      }
    }
  }
 
  return (false);
}

References AK_ignore_this_vertex(), cone_levels, cone_undefined, CONFLICT, conflict_cone, conflict_sink, conflict_source, dg_arc_label_conflicts, FOREACH, fprintf(), ifdebug, ignore_this_conflict(), level, pips_debug, print_effect, region, s1, scc_vertices, statement_number, SUCCESSOR, successor_arc_label, successor_vertex, VERTEX, vertex_successors, and vertex_to_statement().

Referenced by ConnectedStatements().

Here is the call graph for this function:

Here is the caller graph for this function:

distributer()

bool distributer

(

string

mod_name

)

Parameters

mod_name

od_name

Definition at line 354 of file rice.c.

                                  {
  bool success;
 
  debug_on("RICE_DEBUG_LEVEL");
 
  entity module = local_name_to_top_level_entity(mod_name);
  /*
   * For C code, this pass requires that effects are calculated with property
   * MEMORY_EFFECTS_ONLY set to false because we need that the Chains includes
   * arcs for declarations as these latter are separate statements now.
   */
  bool memory_effects_only_p = get_bool_property("MEMORY_EFFECTS_ONLY");
  if(c_module_p(module) && memory_effects_only_p) {
    // user error? internal error?
    pips_user_warning("Distributer should be run with property "
                      "MEMORY_EFFECTS_ONLY set to FALSE.");
    return false; // return to pass manager with a failure code
  }
 
  success = do_it(mod_name, true, DBR_CODE, &CodeGenerate);
 
  debug_off();
 
  return success;
}

References c_module_p(), CodeGenerate(), debug_off, debug_on, do_it(), get_bool_property(), local_name_to_top_level_entity(), module, and pips_user_warning.

Here is the call graph for this function:

do_it()

bool do_it	(	string	mod_name,
		bool	distribute_p,
		string	what,
		statement(*)(statement, graph, set, int, bool)	codegen_fun
	)

In spite of its name, the new statement "mod_parallel_stat" may be sequential if distribute_p is true

Make sure the dependence graph points towards the code copy

Regenerate statement_ordering for the parallel code

FI: This may be parallel or sequential code

Parameters

mod_name	od_name
distribute_p	istribute_p
what	hat

Definition at line 261 of file rice.c.

                                                                      {
  entity module = local_name_to_top_level_entity(mod_name);
  set_current_module_entity(module);
 
  statement mod_stat = statement_undefined;
  /* In spite of its name, the new statement "mod_parallel_stat"
   * may be sequential if distribute_p is true
   */
  statement mod_parallel_stat = statement_undefined;
 
  set_current_module_statement((statement)db_get_memory_resource(DBR_CODE,
                                                                 mod_name,
                                                                 true));
  mod_stat = get_current_module_statement();
 
  debug_on("RICE_DEBUG_LEVEL");
 
  print_parallelization_statistics(mod_name, "ante", mod_stat);
 
  ifdebug(7) {
    pips_debug(7, "\nTesting NewGen consistency for initial code %s:\n",
        mod_name);
    if(statement_consistent_p((statement)mod_stat))
      fprintf(stderr, " NewGen consistent statement\n");
  }
 
  ifdebug(1) {
    debug(1, "do_it", "original sequential code:\n\n");
    print_statement(mod_stat);
  }
 
  mod_parallel_stat = copy_statement(mod_stat);
 
  ifdebug(7) {
    debug(7,
          "do_it",
          "\nTesting NewGen consistency for copy code %s:",
          mod_name);
    if(statement_consistent_p((statement)mod_parallel_stat))
      fprintf(stderr, " NewGen consistent statement copy\n");
  }
 
  ifdebug(1) {
    debug(1, "do_it", "copy of sequential code:\n\n");
    print_statement(mod_stat);
  }
 
  if(graph_undefined_p(dg)) {
    dg = (graph)db_get_memory_resource(DBR_DG, mod_name, true);
  } else {
    pips_internal_error("dg should be undefined");
  }
 
  /* Make sure the dependence graph points towards the code copy */
  set_ordering_to_statement(mod_parallel_stat);
 
  rice_distribute_only = distribute_p;
  enclosing = 0;
  // rice_statement works by side effects, most of the times, but
  // not for loops
  mod_parallel_stat = rice_statement(mod_parallel_stat, 1, codegen_fun);
 
  /* Regenerate statement_ordering for the parallel code */
  reset_ordering_to_statement();
  module_body_reorder(mod_parallel_stat);
  reset_current_module_entity();
 
  (void)update_loops_locals(mod_name, mod_parallel_stat);
 
  ifdebug(7) {
    pips_debug(7, "\nparallelized code for module %s:", mod_name);
    if(statement_consistent_p(mod_parallel_stat))
      fprintf(stderr, " gen consistent\n");
    print_parallel_statement(mod_parallel_stat);
  }
 
  debug_off();
  clean_up_sequences(mod_parallel_stat);
 
  /* FI: This may be parallel or sequential code */DB_PUT_MEMORY_RESOURCE(what, mod_name, mod_parallel_stat);
 
  print_parallelization_statistics(mod_name, "post", mod_parallel_stat);
 
  dg = graph_undefined;
  reset_current_module_statement();
  return true;
}

References clean_up_sequences(), copy_statement(), db_get_memory_resource(), DB_PUT_MEMORY_RESOURCE, debug(), debug_off, debug_on, dg, enclosing, fprintf(), get_current_module_statement(), graph_undefined, graph_undefined_p, ifdebug, local_name_to_top_level_entity(), mod_stat, module, module_body_reorder(), pips_debug, pips_internal_error, print_parallel_statement(), print_parallelization_statistics(), print_statement(), reset_current_module_entity(), reset_current_module_statement(), reset_ordering_to_statement(), rice_distribute_only, rice_statement(), set_current_module_entity(), set_current_module_statement(), set_ordering_to_statement(), statement_consistent_p(), statement_undefined, and update_loops_locals().

Referenced by distributer(), and rice().

Here is the call graph for this function:

Here is the caller graph for this function:

dump_sef()

void dump_sef

(

statement_effects

se

)

icm.c

Parameters

se

e

Definition at line 75 of file icm.c.

{
    fprintf(stderr, "\n");
    STATEMENT_EFFECTS_MAP(s, e, {
        fprintf(stderr, 
                "%02td (%p) -> (%td) : ", 
                statement_number(s), 
                s,
                gen_length(effects_effects(e)));
 
        MAP(EFFECT, e, { 
            print_words(stderr, words_effect(e));
            fprintf(stderr, "(%p), ", e);
        }, effects_effects(e));
        
        fprintf(stderr, "\n");
    }, se);
}

References EFFECT, effects_effects, fprintf(), gen_length(), MAP, print_words(), STATEMENT_EFFECTS_MAP, statement_number, and words_effect().

Here is the call graph for this function:

find_level_l_loop_statement()

statement find_level_l_loop_statement	(	scc	s,
		int	l
	)

s is a strongly connected component which is analyzed at level l.

Its vertices are enclosed in at least l loops. This gives us a solution to retrieve the level l loop enclosing a scc: to take its first vertex and retrieve the l-th loop around this vertex.

Definition at line 213 of file codegen.c.

                                                    {
  vertex v = VERTEX(CAR(scc_vertices(s)));
  statement st = vertex_to_statement(v);
  list loops = load_statement_enclosing_loops(st);
 
  if(l > 0)
    MAPL(pl, {
          if (l-- == 1)
          return(STATEMENT(CAR(pl)));
        }, loops);
  return (statement_undefined);
}

References CAR, load_statement_enclosing_loops(), loops, MAPL, pl, scc_vertices, STATEMENT, statement_undefined, VERTEX, and vertex_to_statement().

Referenced by ConnectedStatements().

Here is the call graph for this function:

Here is the caller graph for this function:

FindAndTopSortSccs()

list FindAndTopSortSccs	(	graph	g,
		set	region,
		int	l
	)

Parameters

region

egion

Definition at line 317 of file scc.c.

                                                    {
  list lsccs;
  sccs Components;
 
  ifdebug(8) {
    pips_debug(8, "Dependence graph:\n");
    prettyprint_dependence_graph(stderr, statement_undefined, g);
  }
 
  pips_debug(3, "computing sccs ...\n");
 
  Components = FindSccs(g, region, l);
 
  pips_debug(3, "computing in degrees ...\n");
 
  ComputeInDegree(g, region, l);
 
  pips_debug(3, "topological sort ...\n");
 
  lsccs = TopSortSccs(g, region, l,Components);
 
//  free_sccs(Components);
  gen_free_list(sccs_sccs(Components));
  free(Components);
 
 
  return (lsccs);
}

References Components, ComputeInDegree(), FindSccs(), free(), gen_free_list(), ifdebug, pips_debug, prettyprint_dependence_graph(), region, sccs_sccs, statement_undefined, and TopSortSccs().

Referenced by CodeGenerate(), SimplifyGraph(), and SupressDependances().

Here is the call graph for this function:

Here is the caller graph for this function:

FindSccs()

sccs FindSccs	(	graph	g,
		set	region,
		int	level
	)

FindSccs is the interface function to compute the SCCs of a graph.

It marks all nodes as 'not visited' and then apply the main function LowlinkCompute on all vertices.

A vertex is processed only if it belongs to region. Later, successors will be processed if they can be reached through arcs whose level is greater or equal to level.

g is a graph

region and level define a sub-graph of g

Bug FOREACH

Parameters

region	egion
level	evel

Definition at line 206 of file scc.c.

                                              {
  list vertices = graph_vertices(g);
  sccs Components;
 
  Count = 1;
  StackPointer = 0;
  Stack = (vertex *)malloc(sizeof(vertex) * gen_length(vertices));
  Components = make_sccs(NIL);
  FOREACH(VERTEX, v, vertices) {
    if(!ignore_this_vertex_drv(region, v)) {
      dg_vertex_label lv = (dg_vertex_label)vertex_vertex_label(v);
      sccflags fv = dg_vertex_label_sccflags(lv);
      if(fv == sccflags_undefined) {
        pips_debug (7, "fv has not been set so far");
        fv = make_sccflags(scc_undefined, 0, 0, 0);
        dg_vertex_label_sccflags(lv) = fv;
      }
      sccflags_mark(fv) = NEW_MARK;
    }
  }
  /* Bug FOREACH */FOREACH(VERTEX, v1, vertices) {
    if(!ignore_this_vertex_drv(region, v1))
      if(MARKED_NEW_P(v1)) {
        LowlinkCompute(g, region, v1, level, Components);
      }
  }
 
  free(Stack);
 
  ifdebug(3) {
    pips_debug(3, "Strongly connected components:\n");
    PrintSccs(Components);
    pips_debug(3, "End\n");
  }
 
  return (Components);
}

References Components, Count, dg_vertex_label_sccflags, FOREACH, free(), gen_length(), graph_vertices, ifdebug, ignore_this_vertex_drv, level, LowlinkCompute(), make_sccflags(), make_sccs(), malloc(), MARKED_NEW_P, NEW_MARK, NIL, pips_debug, PrintSccs(), region, scc_undefined, sccflags_mark, sccflags_undefined, Stack, StackPointer, VERTEX, and vertex_vertex_label.

Referenced by FindAndTopSortSccs().

Here is the call graph for this function:

Here is the caller graph for this function:

ignore_this_conflict()

bool ignore_this_conflict	(	vertex	v1,
		vertex	v2,
		conflict	c,
		int	l
	)

codegen.c

codegen.c

A conflict is to be ignored if the variable that creates the conflict is local to one of the enclosing loops.

FI: this should be extended to variables declared within the last loop body for C code?

Note: The loops around every statement got by load_statement_loops(statement) here are just these after taking off the loops on which the Kennedy's algo. can't be applied. (YY)

FI: I do not understand the note above.

equivalences do not deserve more cpu cycles

Parameters

v1	1
v2	2

Definition at line 163 of file codegen.c.

                                                                   {
  extern int enclosing;
  effect e1 = conflict_source(c);
  reference r1 = effect_any_reference(e1);
  entity var1 = reference_variable(r1);
  statement s1 = vertex_to_statement(v1);
  list loops1 = load_statement_enclosing_loops(s1);
 
  effect e2 = conflict_sink(c);
  reference r2 = effect_any_reference( e2 );
  entity var2 = reference_variable(r2);
  statement s2 = vertex_to_statement(v2);
  list loops2 = load_statement_enclosing_loops(s2);
  register int i;
 
  if(var1 != var2) {
    /* equivalences do not deserve more cpu cycles */
    return (false);
  }
  for (i = 1; i < l - enclosing; i++) {
    if(!ENDP(loops1)) {
      loops1 = CDR(loops1);
    }
    if(!ENDP(loops2)) {
      loops2 = CDR(loops2);
    }
  }
  ifdebug(8) {
    pips_debug(8, "verifying the following conflit at level %d: \n",l);
    fprintf(stderr,
            "\t%02td --> %02td ",
            statement_number(s1),
            statement_number(s2));
    fprintf(stderr, "\t\tfrom ");
    print_effect(conflict_source(c));
 
    fprintf(stderr, " to ");
    print_effect(conflict_sink(c));
    fprintf(stderr, "\n");
  }
 
  return variable_private_to_loop_p(loops1, var1)
      || variable_private_to_loop_p(loops2, var2);
}

References CDR, conflict_sink, conflict_source, effect_any_reference, enclosing, ENDP, fprintf(), ifdebug, load_statement_enclosing_loops(), pips_debug, print_effect, reference_variable, s1, statement_number, variable_private_to_loop_p(), and vertex_to_statement().

Referenced by contains_level_l_dependence(), prettyprint_dependence_graph_view(), prettyprint_dot_dependence_graph(), and search_parallel_loops().

Here is the call graph for this function:

Here is the caller graph for this function:

invariant_code_motion()

bool invariant_code_motion

(

const char *

module_name

)

Phase that hoists loop invariant code out of loops.

Parameters

[in]

module_name

Returns

true because everything should go fine

Prepare some stuffs and call icm_codegen...

Parameters

module_name

odule_name

Definition at line 1495 of file icm.c.

{
  entity module = local_name_to_top_level_entity(module_name);
  statement mod_stat = statement_undefined;
  set_current_module_entity(module);
 
  set_bool_property( "GENERATE_NESTED_PARALLEL_LOOPS", true );
  set_bool_property( "RICE_DATAFLOW_DEPENDENCE_ONLY", false );
 
  set_current_module_statement((statement)
      db_get_memory_resource(DBR_CODE,
          module_name,
          true));
 
  mod_stat = get_current_module_statement();
 
  set_ordering_to_statement(mod_stat);
 
  debug_on("ICM_DEBUG_LEVEL");
 
  ifdebug(7)
  {
    fprintf(stderr,
        "\nTesting NewGen consistency for initial code %s:\n",
        module_name);
    if (statement_consistent_p((statement)mod_stat))
      fprintf(stderr," NewGen consistent statement\n");
  }
 
  ifdebug(1) {
    pips_debug(1, "original sequential code:\n\n");
    print_statement(mod_stat);
  }
 
  if (graph_undefined_p(dg)) {
    dg = (graph) db_get_memory_resource(DBR_DG, module_name, true);
  }
  else {
    pips_internal_error("dg should be undefined");
  }
 
  enclosing = 0;
  rice_statement(mod_stat, 1, &icm_codegen);
 
  ifdebug(7) {
    fprintf(stderr, "\ntransformed code %s:",module_name);
    if (statement_consistent_p((statement)mod_stat))
      fprintf(stderr," gen consistent ");
  }
 
  // Uselessly reinitialize ordering_to_statement, even if it not set...
  clean_up_sequences(mod_stat);
  module_reorder(mod_stat);
 
  DB_PUT_MEMORY_RESOURCE(DBR_CODE, module_name, mod_stat);
 
  dg = graph_undefined;
  reset_current_module_statement();
  reset_current_module_entity();
  reset_ordering_to_statement();
 
  debug_off();
  return true;
}

References clean_up_sequences(), db_get_memory_resource(), DB_PUT_MEMORY_RESOURCE, debug_off, debug_on, dg, enclosing, fprintf(), get_current_module_statement(), graph_undefined, graph_undefined_p, icm_codegen(), ifdebug, local_name_to_top_level_entity(), mod_stat, module, module_name(), module_reorder(), pips_debug, pips_internal_error, print_statement(), reset_current_module_entity(), reset_current_module_statement(), reset_ordering_to_statement(), rice_statement(), set_bool_property(), set_current_module_entity(), set_current_module_statement(), set_ordering_to_statement(), statement_consistent_p(), and statement_undefined.

Here is the call graph for this function:

IsInStack()

int IsInStack

(

vertex

v

)

this function checks if vertex v is in the stack

Definition at line 183 of file scc.c.

                        {
  int i;
 
  for (i = 0; i < StackPointer; i++)
    if(Stack[i] == v)
      return (true);
 
  return (false);
}

References Stack, and StackPointer.

Referenced by LowlinkCompute().

Here is the caller graph for this function:

IsolatedStatement()

statement IsolatedStatement	(	scc	s,
		int	l,
		bool	task_parallelize_p
	)

If the isolated statement is a CALL and is not a CONTINUE, regenerate the nested loops around it.

Otherwise, returns an undefined statement.

continue statements are ignored.

I: But they should not be isolated statements if the contain declarations...

FI: we are likely to end up in trouble here because C allows expressions as instructions...

FI: if the statement is any kind of loop or a test, do not go down.

Parameters

task_parallelize_p

ask_parallelize_p

Definition at line 571 of file codegen.c.

                                                                   {
  vertex v = VERTEX(CAR(scc_vertices(s)));
  statement st = vertex_to_statement(v);
  statement rst = statement_undefined;
  list loops = load_statement_enclosing_loops(st);
  instruction sbody = statement_instruction(st);
  extern int enclosing;
 
  pips_debug(8, "Input statement %" PRIdPTR "\n", statement_number(st));
 
  /* continue statements are ignored. */
  /*FI: But they should not be isolated statements if the contain
   declarations... */
  //if(declaration_statement_p(st))
  //pips_internal_error("Declaration statement is junked.");
 
  if(!instruction_call_p(sbody) || (continue_statement_p(st)
      && !declaration_statement_p(st)))
    ;
  /* FI: we are likely to end up in trouble here because C allows
   expressions as instructions... */
  /* FI: if the statement is any kind of loop or a test, do not go
   down.*/
  else
    rst = MakeNestOfParallelLoops(l - 1 - enclosing,
                                  loops,
                                  st,
                                  task_parallelize_p);
 
  ifdebug(8) {
    pips_debug(8, "Returned statement:\n");
    safe_print_statement(rst);
  }
 
  return (rst);
}

References CAR, continue_statement_p(), declaration_statement_p(), enclosing, ifdebug, instruction_call_p, load_statement_enclosing_loops(), loops, MakeNestOfParallelLoops(), pips_debug, safe_print_statement(), scc_vertices, statement_instruction, statement_number, statement_undefined, VERTEX, and vertex_to_statement().

Referenced by CodeGenerate().

Here is the call graph for this function:

Here is the caller graph for this function:

LowlinkCompute()

void LowlinkCompute	(	graph	g,
		set	region,
		vertex	v,
		int	level,
		sccs	Components
	)

Parameters

region	egion
level	evel
Components	omponents

Definition at line 115 of file scc.c.

                                                                               {
  dg_vertex_label dvl = (dg_vertex_label)vertex_vertex_label(v);
  sccflags fv = dg_vertex_label_sccflags(dvl);
  statement sv = ordering_to_statement(dg_vertex_label_statement(dvl));
 
  pips_debug(7, "vertex is %zd (%zd %zd %zd)\n", statement_number(sv),
      sccflags_mark(fv), sccflags_lowlink(fv), sccflags_dfnumber(fv));
 
  MARK_OLD(v);
 
  sccflags_lowlink(fv) = Count;
  sccflags_dfnumber(fv) = Count;
 
  Count++;
 
  Stack[StackPointer++] = v;
  FOREACH(SUCCESSOR, su, vertex_successors(v)) {
 
    if(!ignore_this_successor_drv(v, region, su, level)) {
      vertex s = successor_vertex(su);
 
      if(!ignore_this_vertex_drv(region, s)) {
        dg_vertex_label dsl = (dg_vertex_label)vertex_vertex_label(s);
        sccflags fs = dg_vertex_label_sccflags(dsl);
        statement ss = ordering_to_statement(dg_vertex_label_statement(dsl));
 
        pips_debug(7, "successor before is %zd (%zd %zd %zd)\n",
            statement_number(ss), sccflags_mark(fs),
            sccflags_lowlink(fs), sccflags_dfnumber(fs));
 
        if(MARKED_NEW_P(s)) {
          LowlinkCompute(g, region, s, level, Components);
          pips_debug(7, "successor after is %zd (%zd %zd %zd)\n",
              statement_number(ss), sccflags_mark(fs),
              sccflags_lowlink(fs), sccflags_dfnumber(fs));
          sccflags_lowlink(fv) = MIN(sccflags_lowlink(fv),
              sccflags_lowlink(fs));
        } else {
          if((sccflags_dfnumber(fs) < sccflags_dfnumber(fv)) && IsInStack(s)) {
            sccflags_lowlink(fv) = MIN(sccflags_dfnumber(fs),
                sccflags_lowlink(fv));
          }
        }
      }
    }
  }
 
  if(sccflags_lowlink(fv) == sccflags_dfnumber(fv)) {
    scc ns = make_scc(NIL, 0);
    vertex p;
    sccflags fp;
    cons *pv = NIL;
 
    do {
      p = Stack[--StackPointer];
      fp = dg_vertex_label_sccflags((dg_vertex_label)
          vertex_vertex_label(p));
      sccflags_enclosing_scc(fp) = ns;
      pv = gen_nconc(pv, CONS(VERTEX, p, NIL));
    } while(v != p);
 
    scc_vertices(ns) = pv;
    sccs_sccs(Components)
        = gen_nconc(sccs_sccs(Components), CONS(SCC, ns, NIL));
  }
}

References Components, CONS, Count, dg_vertex_label_sccflags, dg_vertex_label_statement, FOREACH, gen_nconc(), ignore_this_successor_drv, ignore_this_vertex_drv, IsInStack(), level, LowlinkCompute(), make_scc(), MARK_OLD, MARKED_NEW_P, MIN, NIL, ordering_to_statement(), pips_debug, region, SCC, scc_vertices, sccflags_dfnumber, sccflags_enclosing_scc, sccflags_lowlink, sccflags_mark, sccs_sccs, Stack, StackPointer, statement_number, SUCCESSOR, successor_vertex, VERTEX, vertex_successors, and vertex_vertex_label.

Referenced by FindSccs(), and LowlinkCompute().

Here is the call graph for this function:

Here is the caller graph for this function:

MakeLoopAs()

statement MakeLoopAs	(	statement	old_loop_statement,
		tag	seq_or_par,
		statement	body
	)

This function creates a new loop whose characteristics (index, bounds, ...) are similar to those of old_loop.

The body and the execution type are different between the old and the new loop.

fixed bug about private variable without effects, FC 22/09/93

avoid sharing

Parameters

old_loop_statement	ld_loop_statement
seq_or_par	eq_or_par
body	ody

Definition at line 517 of file codegen.c.

                                     {
  loop old_loop = statement_loop(old_loop_statement);
  loop new_loop;
  statement new_loop_s;
  statement old_body = loop_body (old_loop);
  list new_locals = gen_copy_seq(loop_locals(old_loop));
 
  if(rice_distribute_only)
    seq_or_par = is_execution_sequential;
 
  // copy declaration from old body to new body
  if((statement_decls_text (old_body) != string_undefined)
      && (statement_decls_text (old_body) != NULL)) {
    if(!statement_block_p(body))
      body = make_block_statement(CONS(STATEMENT,body,NIL));
    statement_decls_text (body) = copy_string (statement_decls_text (old_body));
  }
  if((statement_declarations (old_body) != list_undefined)
      && (statement_declarations (old_body) != NULL)) {
    if(!statement_block_p(body))
      body = make_block_statement(CONS(STATEMENT,body,NIL));
    statement_declarations (body)
        = gen_copy_seq(statement_declarations (old_body));
  }
 
  new_loop = make_loop(loop_index(old_loop), copy_range(loop_range(old_loop)), /* avoid sharing */
  body, entity_empty_label(), make_execution(seq_or_par, UU), new_locals);
 
  new_loop_s
      = make_statement(entity_empty_label(),
                       statement_number(old_loop_statement),
                       STATEMENT_ORDERING_UNDEFINED,
                       string_undefined,
                       make_instruction(is_instruction_loop, new_loop),
                       NIL,
                       NULL,
                       copy_extensions(statement_extensions(old_loop_statement)), make_synchronization_none());
 
  ifdebug(8) {
    pips_assert("Execution is either parallel or sequential",
        seq_or_par==is_execution_sequential || seq_or_par==is_execution_parallel);
    pips_debug(8, "New %s loop\n",
        seq_or_par==is_execution_sequential? "sequential" : "parallel");
    print_parallel_statement(new_loop_s);
  }
 
  return (new_loop_s);
}

References CONS, copy_extensions(), copy_range(), copy_string, entity_empty_label(), gen_copy_seq(), ifdebug, is_execution_parallel, is_execution_sequential, is_instruction_loop, list_undefined, loop_body, loop_index, loop_locals, loop_range, make_block_statement(), make_execution(), make_instruction(), make_loop(), make_statement(), make_synchronization_none(), NIL, pips_assert, pips_debug, print_parallel_statement(), rice_distribute_only, STATEMENT, statement_block_p, statement_declarations, statement_decls_text, statement_extensions, statement_loop(), statement_number, STATEMENT_ORDERING_UNDEFINED, string_undefined, and UU.

Referenced by ConnectedStatements(), and MakeNestOfParallelLoops().

Here is the call graph for this function:

Here is the caller graph for this function:

MakeNestOfParallelLoops()

statement MakeNestOfParallelLoops	(	int	l,
		cons *	loops,
		statement	body,
		bool	task_parallelize_p
	)

this function creates a nest of parallel loops around an isolated statement whose iterations may execute in parallel.

loops is the loop nest that was around body in the original program. l is the current level; it tells us how many loops have already been processed.

At most one outer loop parallel

Parameters

loops	oops
body	ody
task_parallelize_p	ask_parallelize_p

Definition at line 310 of file codegen.c.

                                                           {
  statement s;
  pips_debug(3, " at level %d ...\n",l);
 
  if(loops == NIL)
    s = body;
  else if(l > 0)
    s = MakeNestOfParallelLoops(l - 1, CDR(loops), body, task_parallelize_p);
  else {
    statement slo = STATEMENT(CAR(loops));
    loop lo = statement_loop(slo);
    tag seq_or_par = ((CDR(loops) == NIL || task_parallelize_p)
        && index_private_p(lo)) ? is_execution_parallel
                                : is_execution_sequential;
 
    /* At most one outer loop parallel */
    bool
        task_parallelize_inner =
            (seq_or_par == is_execution_parallel
                && !get_bool_property("GENERATE_NESTED_PARALLEL_LOOPS")) ? false
                                                                         : task_parallelize_p;
 
    s = MakeLoopAs(slo,
                   seq_or_par,
                   MakeNestOfParallelLoops(0,
                                           CDR(loops),
                                           body,
                                           task_parallelize_inner));
  }
  return (s);
}

References CAR, CDR, get_bool_property(), index_private_p(), is_execution_parallel, is_execution_sequential, loops, MakeLoopAs(), NIL, pips_debug, STATEMENT, and statement_loop().

Referenced by IsolatedStatement(), and MakeNestOfStatementList().

Here is the call graph for this function:

Here is the caller graph for this function:

MakeNestOfStatementList()

statement MakeNestOfStatementList	(	int	l,
		int	nbl,
		list *	lst,
		list	loops,
		list *	block,
		list *	eblock,
		bool	task_parallelize_p
	)

Parameters

nbl	bl
lst	st
loops	oops
block	lock
eblock	block
task_parallelize_p	ask_parallelize_p

Definition at line 350 of file codegen.c.

                                                           {
  statement stat = statement_undefined;
  statement rst = statement_undefined;
  extern int enclosing;
 
  debug_on("RICE_DEBUG_LEVEL");
 
  if(*lst != NIL && nbl) {
    if(gen_length(*lst) == 1)
      rst = (STATEMENT(CAR(*lst)));
    else
      rst = make_block_statement(*lst);
    if(nbl >= l - 1)
      stat = MakeNestOfParallelLoops(l - 1 - enclosing,
                                     loops,
                                     rst,
                                     task_parallelize_p);
    else
      stat = rst;
    *lst = NIL;
    INSERT_AT_END(*block, *eblock, CONS(STATEMENT, stat, NIL));
  }
 
  debug_off();
  return (stat);
}

References CAR, CONS, debug_off, debug_on, enclosing, gen_length(), INSERT_AT_END, loops, make_block_statement(), MakeNestOfParallelLoops(), NIL, STATEMENT, and statement_undefined.

Referenced by CodeGenerate().

Here is the call graph for this function:

Here is the caller graph for this function:

print_list_entities()

void print_list_entities

(

list

l

)

Parameters

l

of entity

Definition at line 151 of file icm.c.

{
    MAP(ENTITY, e, { 
        fprintf(stderr, "%s ", entity_name(e));
    }, l);
}

References ENTITY, entity_name, fprintf(), and MAP.

Referenced by statement_depend_of_indices_p().

Here is the call graph for this function:

Here is the caller graph for this function:

PrintScc()

void PrintScc

(

scc

s

)

Definition at line 346 of file scc.c.

                     {
  fprintf(stderr, "Scc's statements : ");
  FOREACH(VERTEX, v, scc_vertices(s)) {
    statement st = vertex_to_statement(v);
 
    fprintf(stderr, "%02td ", statement_number(st));
  }
  fprintf(stderr, " -  in degree : %td\n", scc_indegree(s));
}

References FOREACH, fprintf(), scc_indegree, scc_vertices, statement_number, VERTEX, and vertex_to_statement().

Referenced by ConnectedStatements(), and PrintSccs().

Here is the call graph for this function:

Here is the caller graph for this function:

PrintSccs()

void PrintSccs

(

sccs

ss

)

Parameters

ss

s

Definition at line 356 of file scc.c.

                        {
  fprintf(stderr, "Strongly connected components:\n");
  if(!ENDP(sccs_sccs(ss))) {
    MAPL(ps, {PrintScc(SCC(CAR(ps)));}, sccs_sccs(ss));
  } else {
    fprintf(stderr, "Empty list of scc\n");
  }
}

References CAR, ENDP, fprintf(), MAPL, PrintScc(), SCC, and sccs_sccs.

Referenced by FindSccs().

Here is the call graph for this function:

Here is the caller graph for this function:

reset_sccs_drivers()

void reset_sccs_drivers

(

void

)

Definition at line 98 of file scc.c.

                          {
  pips_assert( "ignore_this_vertex_drv is not set", ignore_this_vertex_drv != 0 );
  pips_assert( "ignore_this_successor_drv is not set", ignore_this_successor_drv != 0 );
  ignore_this_vertex_drv = 0;
  ignore_this_successor_drv = 0;
}

References ignore_this_successor_drv, ignore_this_vertex_drv, and pips_assert.

Referenced by CodeGenerate(), SimplifyGraph(), and SupressDependances().

Here is the caller graph for this function:

rice_all_dependence()

bool rice_all_dependence

(

string

mod_name

)

Parameters

mod_name

od_name

Definition at line 400 of file rice.c.

                                          {
  set_bool_property("GENERATE_NESTED_PARALLEL_LOOPS", true);
  set_bool_property("RICE_DATAFLOW_DEPENDENCE_ONLY", false);
  return rice(mod_name);
}

References rice(), and set_bool_property().

Here is the call graph for this function:

rice_cray()

bool rice_cray

(

string

mod_name

)

Parameters

mod_name

od_name

Definition at line 413 of file rice.c.

                                {
  set_bool_property("GENERATE_NESTED_PARALLEL_LOOPS", false);
  set_bool_property("RICE_DATAFLOW_DEPENDENCE_ONLY", false);
  return rice(mod_name);
}

References rice(), and set_bool_property().

Here is the call graph for this function:

rice_data_dependence()

bool rice_data_dependence

(

string

mod_name

)

Parameters

mod_name

od_name

Definition at line 406 of file rice.c.

                                           {
  set_bool_property("GENERATE_NESTED_PARALLEL_LOOPS", true);
  set_bool_property("RICE_DATAFLOW_DEPENDENCE_ONLY", true);
  pips_user_warning("This phase is designed for experimental purposes only. The generated code is most likely to be illegal, especially if a privatization phase was performed before.\n");
  return rice(mod_name);
}

References pips_user_warning, rice(), and set_bool_property().

Here is the call graph for this function:

rice_loop()

statement rice_loop	(	statement	stat,
		int	l,
		statement(*)(statement, graph, set, int, bool)	codegen_fun
	)

Eventually parallelize a do-loop with à la Rice algorithm.

Returns

a statement with the same loop (not parallelized), a statement with a parallelized do-loop or an empty statement (the loop body was empty so it is trivially parallelized in this way).

Well the loop is already parallel and we are asked not to do the job again that may lead to less optimal code for the target:

The code generation did not generate anything, probably because the loop body was empty ("CONTINUE"/";", "{ }"), so no loop is generated:

FI: I'd rather not return a block when a unique loop statement has to be wrapped.

try to keep label

Do not forget to move forbidden information associated with block:

StatementToContext should be freed here. but it is not easy.

Skip the parallelization of this loop but go on recursion for eventual loops in this loop body:

Parameters

stat

tat

Definition at line 160 of file rice.c.

                                                                               {
  statement nstat;
  instruction istat = statement_instruction(stat);
  loop lstat = instruction_loop(istat);
  set region;
  //statement b = statement_undefined;
  ifdebug(1) {
    pips_debug(1, "original nest of loops:\n\n");
    print_statement(stat);
  }
 
  if((region = distributable_loop(stat)) == set_undefined) {
    int so = statement_ordering(stat);
    user_warning("rice_loop",
                 "Cannot apply Allen & Kennedy's algorithm on "
                   "loop %s with index %s at Statement %d (%d, %d)"
                   " because it contains either tests or goto statements"
                   " which prohibit loop distribution. You could activate the"
                   " coarse_grain_parallelization rule.\n",
                 label_local_name(loop_label(instruction_loop(istat))),
                 entity_local_name(loop_index(instruction_loop(istat))),
                 statement_number(stat),
                 ORDERING_NUMBER(so),
                 ORDERING_STATEMENT(so));
    goto skip_parallelization_of_this_loop;
  }
 
  if(!get_bool_property("PARALLELIZE_AGAIN_PARALLEL_CODE")
      && parallel_loop_statement_p(stat))
    /* Well the loop is already parallel and we are asked not to do the
     job again that may lead to less optimal code for the target: */
    goto skip_parallelization_of_this_loop;
 
  ifdebug(2) {
    debug(2, "rice_loop", "applied on region:\n");
    print_statement_set(stderr, region);
  }
 
  set_enclosing_loops_map(loops_mapping_of_statement(stat));
  nstat = codegen_fun(stat, dg, region, l, true);
 
  ifdebug(7) {
    pips_debug(7, "consistency checking for CodeGenerate output: ");
    if(statement_consistent_p(nstat))
      fprintf(stderr, " gen consistent\n");
  }
 
  if(nstat == statement_undefined)
    /* The code generation did not generate anything, probably because the
     loop body was empty ("CONTINUE"/";", "{ }"), so no loop is
     generated: */
    nstat = make_empty_statement();
 
  /* FI: I'd rather not return a block when a unique loop statement has to
   * be wrapped.
   */pips_assert("block or loop",
      instruction_block_p(statement_instruction(nstat)) ||
      instruction_loop_p(statement_instruction(nstat)));
  /* try to keep label */
  if(statement_loop_p(nstat))
    statement_label(nstat) = statement_label(stat);
  else {
    FOREACH(STATEMENT,s,statement_block(nstat))
      if(statement_loop_p(s)) {
        statement_label(s) = statement_label(stat);
        break;
      }
  }
  statement_number(nstat)
      = (statement_block_p(nstat) ? STATEMENT_NUMBER_UNDEFINED
                                  : statement_number(stat));
  statement_ordering(nstat) = statement_ordering(stat);
  statement_comments(nstat) = statement_comments(stat);
  /* Do not forget to move forbidden information associated with
   block: */
  fix_statement_attributes_if_sequence(nstat);
  ifdebug(1) {
    fprintf(stderr, "final nest of loops:\n\n");
    print_parallel_statement(nstat);
  }
 
  /* StatementToContext should be freed here. but it is not easy. */
  set_free(region);
 
  clean_enclosing_loops();
 
  return nstat;
 
  /* Skip the parallelization of this loop but go on recursion for
   eventual loops in this loop body: */
  skip_parallelization_of_this_loop: enclosing++;
  loop_body(lstat) = rice_statement(loop_body(lstat), l + 1, codegen_fun);
  enclosing--;
  return (stat);
}

References clean_enclosing_loops(), debug(), dg, distributable_loop(), enclosing, entity_local_name(), fix_statement_attributes_if_sequence(), FOREACH, fprintf(), get_bool_property(), ifdebug, instruction_block_p, instruction_loop, instruction_loop_p, label_local_name(), loop_body, loop_index, loop_label, loops_mapping_of_statement(), make_empty_statement, ORDERING_NUMBER, ORDERING_STATEMENT, parallel_loop_statement_p(), pips_assert, pips_debug, print_parallel_statement(), print_statement(), print_statement_set(), region, rice_statement(), set_enclosing_loops_map(), set_free(), set_undefined, STATEMENT, statement_block(), statement_block_p, statement_comments, statement_consistent_p(), statement_instruction, statement_label, statement_loop_p(), statement_number, STATEMENT_NUMBER_UNDEFINED, statement_ordering, statement_undefined, and user_warning.

Referenced by rice_statement().

Here is the call graph for this function:

Here is the caller graph for this function:

rice_statement()

statement rice_statement	(	statement	stat,
		int	l,
		statement(*)(statement, graph, set, int, bool)	codegen_fun
	)

Parameters

stat

tat

Definition at line 82 of file rice.c.

                                                        {
  instruction istat = statement_instruction(stat);
  statement new_stat = stat; // Most statements are modified by side effects
 
  switch(instruction_tag(istat)) {
    case is_instruction_block: {
      MAPL(pc, {
            statement st = STATEMENT(CAR(pc));
            STATEMENT_(CAR(pc)) = rice_statement(st,l,codegen_fun);
          }, instruction_block(istat));
      break;
    }
    case is_instruction_test: {
      test obj_test = instruction_test(istat);
      test_true(obj_test) = rice_statement(test_true(obj_test), l, codegen_fun);
      test_false(obj_test) = rice_statement(test_false(obj_test),
                                            l,
                                            codegen_fun);
      break;
    }
    case is_instruction_loop: {
      new_stat = rice_loop(stat, l, codegen_fun);
      ifdebug(7) {
        if(statement_loop_p(new_stat))
          pips_debug(7, "regenerated loop is %s:",
              execution_sequential_p(loop_execution(instruction_loop(statement_instruction(new_stat))))?
              "sequential" : "parallel");
        else
          pips_debug(7, "regenerated code:");
        if(statement_consistent_p(new_stat))
          fprintf(stderr, " consistent\n");
        print_parallel_statement(new_stat);
      }
      break;
    }
    case is_instruction_whileloop: {
      whileloop wl = instruction_whileloop(istat);
 
      whileloop_body(wl) = rice_statement(whileloop_body(wl), l, codegen_fun);
      break;
    }
    case is_instruction_forloop: {
      forloop wl = instruction_forloop(istat);
 
      forloop_body(wl) = rice_statement(forloop_body(wl), l, codegen_fun);
      break;
    }
    case is_instruction_goto:
      pips_internal_error("Unexpected go to instruction in parsed code");
      break;
    case is_instruction_call:
    case is_instruction_expression:
      break;
    case is_instruction_unstructured: {
      unstructured obj_unstructured = instruction_unstructured(istat);
      rice_unstructured(obj_unstructured, l, codegen_fun);
      break;
    }
    default:
      pips_internal_error("default case reached with tag %d",
          instruction_tag(istat));
  }
 
  return (new_stat);
}

References CAR, execution_sequential_p, forloop_body, fprintf(), ifdebug, 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_execution, MAPL, pips_debug, pips_internal_error, print_parallel_statement(), rice_loop(), rice_unstructured(), STATEMENT, STATEMENT_, statement_consistent_p(), statement_instruction, statement_loop_p(), test_false, test_true, and whileloop_body.

Referenced by do_it(), invariant_code_motion(), rice_loop(), and rice_unstructured().

Here is the call graph for this function:

Here is the caller graph for this function:

rice_unstructured()

void rice_unstructured	(	unstructured	u,
		int	l,
		statement(*)(statement, graph, set, int, bool)	codegen_fun
	)

Definition at line 69 of file rice.c.

                                                                              {
  cons *blocs = NIL;
 
  CONTROL_MAP(c, {
        statement st = rice_statement(control_statement(c),l,codegen_fun);
        control_statement(c) = st;
      }, unstructured_control(u), blocs);
 
  gen_free_list(blocs);
}

References CONTROL_MAP, control_statement, gen_free_list(), NIL, rice_statement(), and unstructured_control.

Referenced by rice_statement().

Here is the call graph for this function:

Here is the caller graph for this function:

scc_region()

set scc_region

(

scc

s

)

Definition at line 226 of file codegen.c.

                      {
  set region = set_make(set_pointer);
  MAPL(pv, {
        set_add_element(region, region,
            (char *) vertex_to_statement(VERTEX(CAR(pv))));
      }, scc_vertices(s));
  return (region);
}

References CAR, MAPL, region, scc_vertices, set_add_element(), set_make(), set_pointer, VERTEX, and vertex_to_statement().

Referenced by ConnectedStatements().

Here is the call graph for this function:

Here is the caller graph for this function:

set_sccs_drivers()

void set_sccs_drivers	(	bool(*)(set, vertex)	,
		bool(*)(vertex, set, successor, int)
	)

scc.c

Referenced by CodeGenerate(), SimplifyGraph(), and SupressDependances().

Here is the caller graph for this function:

statement_imbrication_level()

int statement_imbrication_level

(

statement

st

)

Parameters

st

t

Definition at line 345 of file codegen.c.

                                              {
  list loops = load_statement_enclosing_loops(st);
  return (gen_length(loops));
}

References gen_length(), load_statement_enclosing_loops(), and loops.

Here is the call graph for this function:

strongly_connected_p()

bool strongly_connected_p	(	scc	s,
		int	l
	)

this function returns true if scc s is stronly connected at level l, i.e.

dependence arcs at level l or greater form at least one cycle

if s contains more than one vertex, it is strongly connected

if there is a dependence from v to v, s is strongly connected

s is not strongly connected

Definition at line 284 of file codegen.c.

                                        {
  cons *pv = scc_vertices(s);
  vertex v = VERTEX(CAR(pv));
 
  /* if s contains more than one vertex, it is strongly connected */
  if(CDR(pv) != NIL)
    return (true);
  /* if there is a dependence from v to v, s is strongly connected */
  FOREACH(SUCCESSOR, s, vertex_successors(v)) {
    if(!AK_ignore_this_level((dg_arc_label)successor_arc_label(s), l)
        && successor_vertex(s) == v)
      return (true);
  }
 
  /* s is not strongly connected */
  return (false);
}

References AK_ignore_this_level(), CAR, CDR, FOREACH, NIL, scc_vertices, SUCCESSOR, successor_arc_label, successor_vertex, VERTEX, and vertex_successors.

Referenced by CodeGenerate(), and SimplifyGraph().

Here is the call graph for this function:

Here is the caller graph for this function:

TopSortSccs()

list TopSortSccs	(	graph	,
		set	,
		int	,
		sccs
	)

Variable Documentation

dg

graph dg

extern

external variables.

cproto-generated files

see declarations in kennedy.c

rice.c

external variables.

Modifications:

• Bruno Baron:
• Francois Irigoin: I do not understand why regions of statements are implemented as set of statements instead of set of statement orderings since the dependence graph refers to statement orderings.
• Francois Irigoin: use a copy of the code statement to generate the parallel code, instead of using side effects on the sequential code statement. This works because the dependence graph uses persistent pointers towards statement, statement_ordeging, and because the references are the same in the sequential code and in its copy. So references are still accessible, although it may be useless for parallelization. FI: I want misc.h and I end up with the other ones as well? the dependence graph of the current loop nest

Definition at line 52 of file rice.h.

Referenced by do_it(), and rice_loop().

enclosing

int enclosing

extern

This is an horrendous hack.

ENCLOSING should be passed as an argument, but I don't have the courage to make the changes .

Definition at line 67 of file rice.c.

Referenced by ConnectedStatements(), do_it(), glc_call(), glc_cast(), glc_ref(), ignore_this_conflict(), invariant_code_motion(), IsolatedStatement(), MakeNestOfStatementList(), and rice_loop().

Nbrdoall

int Nbrdoall

extern

rice_distribute_only

bool rice_distribute_only

extern

to know if do loop parallelization must be done

Definition at line 53 of file rice.h.

Referenced by do_it().