PIPS
|
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 |
Some generic methods about loops and list of loops.
There are many things elsewhere that should be factored out into here (static controlize...).
void clean_enclosing_loops | ( | void | ) |
warning: there are shared lists...
Definition at line 58 of file loop.c.
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().
Test if a loop has a constant step loop.
Definition at line 733 of file loop.c.
References expression_constant_p(), loop_range, pips_debug, and range_increment.
Referenced by normal_loop_p(), and static_controlize_loop().
Duplicate a loop list.
ll | l |
Definition at line 826 of file loop.c.
References gen_full_copy_list().
Referenced by static_controlize_call().
Compute the depth of a parallel perfect loop-nest.
No parallel loop found here
Definition at line 436 of file loop.c.
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().
Compute the depth of a perfect loop-nest.
No loop found here
Definition at line 476 of file loop.c.
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().
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.
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().
just to avoid a gcc warning
Definition at line 176 of file loop.c.
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().
Return the inner loop in a perfect loop-nest.
stat | is the statement to test |
stat | tat |
Definition at line 508 of file loop.c.
References CAR, cons::cdr, continue_statement_p(), instruction_block, instruction_tag, is_instruction_block, is_instruction_loop, NIL, STATEMENT, statement_instruction, and statement_undefined.
Check if variable v is an index for an enclosing loop.
loops | of statements |
Definition at line 980 of file loop.c.
References entity_name, FOREACH, loop_index, loops, pips_debug, same_entity_p(), and statement_loop().
Referenced by get_variables_to_remove().
returns true if loop lo's index is private for this loop
lo | o |
Definition at line 240 of file loop.c.
References entity_undefined, gen_find_eq(), loop_index, loop_locals, loop_undefined, and pips_internal_error.
Referenced by ConnectedStatements(), and MakeNestOfParallelLoops().
Check if loop bound are constant and then if upper >= lower.
l | loop to check execution |
Definition at line 937 of file loop.c.
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().
Check if loop bound are constant and then if upper < lower.
l | loop to check execution |
Definition at line 971 of file loop.c.
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().
ser_error("loop_increment_value", "increment is not constant");
Definition at line 714 of file loop.c.
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().
Test if a loop is parallel.
l | is the loop to test |
Definition at line 393 of file loop.c.
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().
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.
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 |
obj | bj |
local | ocal |
index | ndex |
Definition at line 338 of file loop.c.
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().
Test if a loop is sequential.
l | is the loop to test |
Definition at line 404 of file loop.c.
References execution_sequential_p, and loop_execution.
Referenced by gpu_promote_sequential_walker_in().
|
static |
of entity
Definition at line 375 of file loop.c.
References loop_locals, and sort_list_of_entities().
Referenced by sort_all_loop_locals().
|
static |
Definition at line 763 of file loop.c.
References loop_parallel_p(), npar, and nseq.
Referenced by number_of_sequential_and_parallel_loops().
statement_mapping loops_mapping_of_statement | ( | statement | stat | ) |
stat | tat |
Definition at line 155 of file loop.c.
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().
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");
low | ow |
up | p |
inc | nc |
Definition at line 839 of file loop.c.
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().
Test if a loop does have a 1-increment step.
Definition at line 741 of file loop.c.
References constant_step_loop_p(), entity_local_name(), expression_syntax, loop_range, pips_debug, range_increment, reference_variable, and syntax_reference.
Compute the number of parallel and sequential loops found in a statement and update given variables.
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 |
stat | tat |
pseq | seq |
ppar | par |
Definition at line 784 of file loop.c.
References gen_recurse, gen_true(), loop_domain, loop_update_statistics(), npar, and nseq.
Referenced by print_number_of_loop_statistics().
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...
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. |
Definition at line 420 of file loop.c.
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().
Get the index of the loop at a given depth inside a loop-nest.
s | is the loop-nest statement to dig into |
depth | is the diving depth |
there may be some declarations before
depth | epth |
Definition at line 694 of file loop.c.
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().
Test if a statement is a perfect loop-nest.
stat | is the statement to test |
biased for WP65
extreme case: empty loop nest
stat | tat |
Definition at line 543 of file loop.c.
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().
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
loop_nest | oop_nest |
Definition at line 590 of file loop.c.
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().
Extract the loop-body of a perfect loop-nest at a given depth.
s | is the loop-nest statement to dig into |
depth | is the diving depth |
pips_debug(1, "Look at statement at depth 0:\n");
print_statement(body);
}
pips_debug(1, "Look at statement at depth %d:\n", i + 1);
print_statement(body);
}
depth | epth |
Definition at line 646 of file loop.c.
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().
Compute the number of parallel and sequential loops found in a statement and output them on a stream with a message before.
out | is the stream to send the information to |
msg | is the message to prepend |
s | is the statement to dig into |
out | ut |
msg | sg |
Definition at line 803 of file loop.c.
References fprintf(), number_of_sequential_and_parallel_loops(), and out.
Referenced by print_parallelization_statistics().
void print_parallelization_statistics | ( | const char * | module, |
const char * | msg, | ||
statement | s | ||
) |
Print out the number of sequential versus parallel loops.
module | the module name |
msg | an additional message |
s | the module statement to consider |
Definition at line 814 of file loop.c.
References fprintf(), get_bool_property(), module, and print_number_of_loop_statistics().
Referenced by do_it().
Definition at line 911 of file loop.c.
References extended_integer_constant_expression_p_to_int(), range_increment, range_lower, and range_upper.
Referenced by loop_executed_at_least_once_p().
Definition at line 943 of file loop.c.
References extended_integer_constant_expression_p_to_int(), range_increment, range_lower, and range_upper.
Referenced by loop_executed_never_p().
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.
References pips_assert, region_of_statement(), set_make(), set_pointer, and statement_loop_p().
Referenced by rdg_loop(), and search_parallel_loops().
Should be rewritten with a gen_recurse to deal with the recent RI...
The next statement is added by Y.Q. 12/9.
stat | tat |
region | egion |
Definition at line 269 of file loop.c.
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().
|
static |
Referenced by loops_mapping_of_statement(), rloops_mapping_of_statement(), and rloops_mapping_of_unstructured().
|
static |
Definition at line 94 of file loop.c.
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.
|
static |
Definition at line 80 of file loop.c.
References CONTROL_MAP, control_statement, gen_free_list(), loops, NIL, rloops_mapping_of_statement(), and unstructured_control.
Referenced by rloops_mapping_of_statement().
void sort_all_loop_locals | ( | statement | s | ) |
Definition at line 381 of file loop.c.
References gen_multi_recurse(), gen_true(), loop_domain, and loop_sort_locals().
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.
References CAR, CONS, gen_length(), gen_nconc(), loop_body, NIL, STATEMENT, statement_block(), statement_block_p, statement_loop(), and statement_loop_p().
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().
|
static |
Definition at line 760 of file loop.c.
Referenced by loop_update_statistics(), and number_of_sequential_and_parallel_loops().
|
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().