PIPS
|
Go to the source code of this file.
Functions | |
static bool | AK_ignore_this_level (dg_arc_label dal, int level) |
static bool | AK_ignore_this_vertex (set region, vertex v) |
static bool | AK_ignore_this_successor (vertex __attribute__((unused)) v, set region, successor su, int level) |
static bool | variable_private_to_loop_p (list loops, entity var) |
Check if a variable is private to loop nest. More... | |
bool | ignore_this_conflict (vertex v1, vertex v2, conflict c, int l) |
This function checks if conflict c between vertices v1 and v2 should be ignored at level l. More... | |
statement | find_level_l_loop_statement (scc s, int l) |
s is a strongly connected component which is analyzed at level l. More... | |
set | scc_region (scc s) |
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. More... | |
bool | strongly_connected_p (scc s, int l) |
this function returns true if scc s is stronly connected at level l, i.e. More... | |
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. More... | |
int | statement_imbrication_level (statement st) |
statement | MakeNestOfStatementList (int l, int nbl, list *lst, list loops, list *block, list *eblock, bool task_parallelize_p) |
statement | CodeGenerate (statement __attribute__((unused)) stat, graph g, set region, int l, bool task_parallelize_p) |
This function implements Allen & Kennedy's algorithm. More... | |
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. More... | |
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. More... | |
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. More... | |
Variables | |
entity | current_module_entity |
FI: I did not know this was still used... More... | |
|
static |
Definition at line 43 of file codegen.c.
References action_read_p, action_write_p, cone_levels, cone_undefined, CONFLICT, conflict_cone, conflict_sink, conflict_source, dg_arc_label_conflicts, effect_action, FOREACH, get_bool_property(), and level.
Referenced by AK_ignore_this_successor(), and strongly_connected_p().
|
static |
Definition at line 82 of file codegen.c.
References AK_ignore_this_level(), AK_ignore_this_vertex(), CONFLICT, conflict_source, dg_arc_label_conflicts, effect_any_reference, FOREACH, get_bool_property(), level, reference_variable, region, successor_arc_label, successor_vertex, and thread_safe_variable_p().
Referenced by CodeGenerate().
Definition at line 70 of file codegen.c.
References dg_vertex_label_statement, ordering_to_statement(), region, set_belong_p(), and vertex_vertex_label.
Referenced by AK_ignore_this_successor(), CodeGenerate(), and contains_level_l_dependence().
statement CodeGenerate | ( | statement __attribute__((unused)) | stat, |
graph | g, | ||
set | region, | ||
int | l, | ||
bool | task_parallelize_p | ||
) |
This function implements Allen & Kennedy's algorithm.
BB (Bruno Baron): task_parallelize_p is true when we want to parallelize the loop, false when we only want to vectorize it. Probably called by "rice_cray", but there is no explicit information about the vectorization facility in PIPS.
This function is also used to perform loop invariant code motion (Julien Zory).
if s contains a single vertex and if this vertex is not dependent upon itself, we generate a doall loop for it, unless it is a continue statement.
statements that are independent are gathered into the same doall loop
set inner_region = scc_region(s); if (contains_level_l_dependence(s,inner_region,l)) { stat = IsolatedStatement(s, l, task_parallelize_p); debug(9, "CodeGenerate", "isolated comp.that contains dep. at Level %d\n", l); } else { vertex v = VERTEX(CAR(scc_vertices(s))); statement st = vertex_to_statement(v); instruction sbody = statement_instruction(st); nbl = statement_imbrication_level(st); if (instruction_call_p(sbody) && !instruction_continue_p(sbody)) if (nbl>=l-1) stat=IsolatedStatement(s, l, task_parallelize_p); else { loops = load_statement_enclosing_loops(st); lst = gen_nconc(lst, CONS(STATEMENT, st, NIL)); } }
In order to preserve the dependences, statements that have been collected should be generated before the isolated statement that has just been detected
Definition at line 393 of file codegen.c.
References AK_ignore_this_successor(), AK_ignore_this_vertex(), ConnectedStatements(), CONS, debug_off, debug_on, FindAndTopSortSccs(), FOREACH, gen_free_list(), gen_length(), get_bool_property(), ifdebug, INSERT_AT_END, IsolatedStatement(), loops, make_block_statement(), MakeNestOfStatementList(), NIL, pips_debug, print_parallel_statement(), print_statement_set(), region, reset_sccs_drivers(), set_sccs_drivers(), STATEMENT, statement_undefined, and strongly_connected_p().
Referenced by ConnectedStatements(), distributer(), icm_codegen(), and rice().
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
task_parallelize_p | ask_parallelize_p |
Definition at line 614 of file codegen.c.
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().
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.
region | egion |
level | evel |
Definition at line 239 of file codegen.c.
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().
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.
References CAR, load_statement_enclosing_loops(), loops, MAPL, pl, scc_vertices, STATEMENT, statement_undefined, VERTEX, and vertex_to_statement().
Referenced by ConnectedStatements().
This function checks if conflict c between vertices v1 and v2 should be ignored at level l.
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
v1 | 1 |
v2 | 2 |
Definition at line 163 of file codegen.c.
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().
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.
task_parallelize_p | ask_parallelize_p |
Definition at line 571 of file codegen.c.
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().
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
old_loop_statement | ld_loop_statement |
seq_or_par | eq_or_par |
body | ody |
Definition at line 517 of file codegen.c.
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().
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
loops | oops |
body | ody |
task_parallelize_p | ask_parallelize_p |
Definition at line 310 of file codegen.c.
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().
statement MakeNestOfStatementList | ( | int | l, |
int | nbl, | ||
list * | lst, | ||
list | loops, | ||
list * | block, | ||
list * | eblock, | ||
bool | task_parallelize_p | ||
) |
nbl | bl |
lst | st |
loops | oops |
block | lock |
eblock | block |
task_parallelize_p | ask_parallelize_p |
Definition at line 350 of file codegen.c.
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().
Definition at line 226 of file codegen.c.
References CAR, MAPL, region, scc_vertices, set_add_element(), set_make(), set_pointer, VERTEX, and vertex_to_statement().
Referenced by ConnectedStatements().
st | t |
Definition at line 345 of file codegen.c.
References gen_length(), load_statement_enclosing_loops(), and loops.
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.
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().
Check if a variable is private to loop nest.
loops | of loop statement |
Definition at line 113 of file codegen.c.
References entity_undefined, FOREACH, fprintf(), gen_find_eq(), ifdebug, instruction_loop, loop_body, loop_locals, loops, NIL, pips_user_warning, print_entities(), print_statement(), STATEMENT, statement_declarations, statement_instruction, and statement_number.
Referenced by ignore_this_conflict().
|
extern |
FI: I did not know this was still used...