PIPS
|
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... | |
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... | |
#define VERTEX_ENCLOSING_SCC | ( | 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
region | egion |
Definition at line 244 of file scc.c.
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().
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().
mod_name | od_name |
Definition at line 354 of file rice.c.
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.
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
mod_name | od_name |
distribute_p | istribute_p |
what | hat |
Definition at line 261 of file rice.c.
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().
void dump_sef | ( | statement_effects | se | ) |
se | e |
Definition at line 75 of file icm.c.
References EFFECT, effects_effects, fprintf(), gen_length(), MAP, print_words(), STATEMENT_EFFECTS_MAP, statement_number, and words_effect().
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().
region | egion |
Definition at line 317 of file scc.c.
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().
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
region | egion |
level | evel |
Definition at line 206 of file scc.c.
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().
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
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().
bool invariant_code_motion | ( | const char * | module_name | ) |
Phase that hoists loop invariant code out of loops.
[in] | module_name |
Prepare some stuffs and call icm_codegen...
module_name | odule_name |
Definition at line 1495 of file icm.c.
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.
this function checks if vertex v is in the stack
Definition at line 183 of file scc.c.
References Stack, and StackPointer.
Referenced by LowlinkCompute().
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().
region | egion |
level | evel |
Components | omponents |
Definition at line 115 of file scc.c.
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().
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().
void print_list_entities | ( | list | l | ) |
l | of entity |
Definition at line 151 of file icm.c.
References ENTITY, entity_name, fprintf(), and MAP.
Referenced by statement_depend_of_indices_p().
void PrintScc | ( | scc | s | ) |
Definition at line 346 of file scc.c.
References FOREACH, fprintf(), scc_indegree, scc_vertices, statement_number, VERTEX, and vertex_to_statement().
Referenced by ConnectedStatements(), and PrintSccs().
void PrintSccs | ( | sccs | ss | ) |
ss | s |
Definition at line 356 of file scc.c.
References CAR, ENDP, fprintf(), MAPL, PrintScc(), SCC, and sccs_sccs.
Referenced by FindSccs().
void reset_sccs_drivers | ( | void | ) |
Definition at line 98 of file scc.c.
References ignore_this_successor_drv, ignore_this_vertex_drv, and pips_assert.
Referenced by CodeGenerate(), SimplifyGraph(), and SupressDependances().
mod_name | od_name |
Definition at line 400 of file rice.c.
References rice(), and set_bool_property().
mod_name | od_name |
Definition at line 413 of file rice.c.
References rice(), and set_bool_property().
mod_name | od_name |
Definition at line 406 of file rice.c.
References pips_user_warning, rice(), and set_bool_property().
statement rice_loop | ( | statement | stat, |
int | l, | ||
statement(*)(statement, graph, set, int, bool) | codegen_fun | ||
) |
Eventually parallelize a do-loop with à la Rice algorithm.
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:
stat | tat |
Definition at line 160 of file rice.c.
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().
statement rice_statement | ( | statement | stat, |
int | l, | ||
statement(*)(statement, graph, set, int, bool) | codegen_fun | ||
) |
stat | tat |
Definition at line 82 of file rice.c.
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().
void rice_unstructured | ( | unstructured | u, |
int | l, | ||
statement(*)(statement, graph, set, int, bool) | codegen_fun | ||
) |
Definition at line 69 of file rice.c.
References CONTROL_MAP, control_statement, gen_free_list(), NIL, rice_statement(), and unstructured_control.
Referenced by rice_statement().
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().
Referenced by CodeGenerate(), SimplifyGraph(), and SupressDependances().
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().
|
extern |
external variables.
cproto-generated files
see declarations in kennedy.c
external variables.
Modifications:
Definition at line 52 of file rice.h.
Referenced by do_it(), and rice_loop().
|
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().
|
extern |