PIPS
|
#include <stdio.h>
#include <string.h>
#include "genC.h"
#include "linear.h"
#include "ri.h"
#include "effects.h"
#include "database.h"
#include "misc.h"
#include "ri-util.h"
#include "effects-util.h"
#include "constants.h"
#include "text-util.h"
#include "text.h"
#include "properties.h"
#include "pipsdbm.h"
#include "resources.h"
#include "pointer_values.h"
#include "effects-generic.h"
#include "prettyprint.h"
Go to the source code of this file.
Data Structures | |
struct | live_paths_analysis_context |
struct | live_out_summary_engine_context |
|
static |
Definition at line 108 of file liveness_analysis_engine.c.
References effects_store_effects(), live_paths_analysis_context::memory_effects_only, and live_paths_analysis_context::memory_in_out_effects_only.
Referenced by live_in_paths_of_statement(), live_out_paths_from_forloop_to_body(), live_out_paths_from_loop_to_body(), live_out_paths_from_unstructured_to_nodes(), and live_out_paths_from_whileloop_to_body().
|
static |
Definition at line 92 of file liveness_analysis_engine.c.
References effects_store_effects(), and live_paths_analysis_context::memory_effects_only.
Referenced by live_in_paths_of_loop(), live_in_paths_of_statement(), live_in_paths_of_whileloop(), live_out_paths_from_forloop_to_body(), live_out_paths_from_loop_to_body(), and live_out_paths_from_whileloop_to_body().
For each statement store the new live_out_regions.
Definition at line 1339 of file liveness_analysis_engine.c.
References CONS, copy_action(), copy_approximation(), copy_cell(), descriptor_convex, descriptor_tag, EFFECT, effect_action, effect_any_reference, effect_approximation, effect_cell, effect_descriptor, effect_dup_func, FOREACH, ifdebug, is_descriptor_convex, is_descriptor_convexunion, is_descriptor_none, load_live_in_paths_list(), load_live_out_paths_list(), load_statement_out_regions(), make_descriptor_convex(), make_effect(), new_system_with_only_live_variable(), NIL, pips_debug, pips_internal_error, print_statement(), and store_live_out_regions_list().
Referenced by live_out_region_engine().
|
static |
Definition at line 67 of file liveness_analysis_engine.c.
References get_bool_property(), live_paths_analysis_context::memory_effects_only, live_paths_analysis_context::memory_in_out_effects_only, live_paths_analysis_context::representation, and set_bool_property().
Referenced by live_paths_engine().
|
static |
The live in paths of a loop statement are the live in paths of its header plus the live in paths of its first iteration if it is exectuted
If the loop belongs to a sequence of statements, which is generally the case, its live in paths have already been computed. I don't yet know if they may be much more precisely computed here. For performance reasons, I don't try to recompute them if they are already available. The code below is likely to be seldom executed; however, it has been tested on small cases.
Live in effects of header
We assume that there is no side effect in the loop header; thus the live in effects of the header are similar to its proper read effects
Live in effects of first iteration if it exists minus read effects on the loop index, which are masked by its initialization in the header, and read effects on loop locals if the loop is parallel;
beware: potential sharing with loop_locals(l)
free l_masked_vars: beware of the potential sharing with loop_locals
put them together
Definition at line 952 of file liveness_analysis_engine.c.
References bound_live_in_paths_p(), CDR, CONS, convert_rw_effects(), current_stmt, effects_dup_without_variables(), effects_read_effects_dup(), effects_same_action_p(), effects_to_may_effects(), ENDP, ENTITY, gen_free_list(), gen_full_free_list(), gen_get_ancestor(), load_live_in_paths_list(), load_proper_rw_effects_list(), loop_body, loop_descriptor_make_func, loop_executed_at_least_once_p(), loop_executed_never_p(), loop_index, loop_locals, loop_parallel_p(), loop_range, loop_undefined_descriptor_make(), NIL, normalizable_and_linear_loop_p(), pips_debug, pips_debug_effects, pips_internal_error, proper_to_summary_effects(), reset_converted_rw_effects(), statement_domain, and store_live_in_paths_list().
Referenced by live_paths_of_module_statement().
|
static |
live in paths may have already been computed, for instance for sequences
First, we get the live out paths of the statement
Live_in(S) = (live_out(S) o T(S) - W(S)) U IN (S)
first take care of declarations
Definition at line 361 of file liveness_analysis_engine.c.
References bound_live_in_paths_p(), c_module_p(), convert_in_effects(), convert_rw_effects(), declaration_statement_p(), effects_dup(), effects_same_action_p(), effects_write_effects_dup(), ENTITY, entity_storage, filter_effects_with_declaration(), FOREACH, get_current_module_entity(), load_in_effects_list(), load_live_out_paths_list(), load_rw_effects_list(), pips_debug, pips_debug_effects, r_w_combinable_p(), ram_section, reset_converted_in_effects(), reset_converted_rw_effects(), statement_declarations, statement_number, statement_ordering, static_area_p(), storage_ram, storage_ram_p, and store_live_in_paths_list().
Referenced by live_paths_from_block_to_statements(), and live_paths_of_module_statement().
|
static |
If the loop belongs to a sequence of statements, which is generally the case, its live in paths have already been computed. I don't yet know if they may be much more precisely computed here. For performance reasons, I don't try to recompute them if they are already available. see also the comment inside the else branch of if (!before_p) about the way of computing live in paths. The code below is likely to be seldom executed; however, it has been tested on small cases.
the live in paths of the loop are either those of the first iteration if there is one, or the live out paths of the whole loop is there is no iteration; we must remove the write effects and add the in effects of the condition evaluation
As we currently only compute simple live paths, I wonder if there is a difference with the live out paths of the loop body...
Get the live out paths of the whole loop
It may be executed...
...or the first iteration of the loop body
Take into account the effects of the condition
We don't have the in effects of the condition evaluation we safely approximate them by its may read proper effects if there are write effects during its evaluation
Definition at line 725 of file liveness_analysis_engine.c.
References bound_live_in_paths_p(), convert_rw_effects(), current_stmt, effects_dup(), effects_read_effects_dup(), effects_same_action_p(), effects_to_may_effects(), effects_write_effects_dup(), ENDP, evaluation_before_p, gen_get_ancestor(), load_live_in_paths_list(), load_live_out_paths_list(), load_proper_rw_effects_list(), NIL, pips_debug, pips_debug_effects, proper_to_summary_effects(), r_w_combinable_p(), reset_converted_rw_effects(), statement_domain, store_live_in_paths_list(), whileloop_body, and whileloop_evaluation.
Referenced by live_paths_of_module_statement().
bool live_in_summary_paths_engine | ( | const char * | module_name | ) |
module_name | odule_name |
Definition at line 130 of file liveness_analysis_engine.c.
References db_get_live_in_paths_func, db_get_memory_resource(), get_current_module_statement(), load_live_in_paths_list(), module_name(), module_name_to_entity(), NIL, reset_current_module_entity(), reset_current_module_statement(), reset_live_in_paths(), set_current_module_entity(), set_current_module_statement(), and set_live_in_paths().
|
static |
there is a problem here because the context is in the store preceding the statement whereas live_out_paths hold after the statement. So I think I must apply the transformer to get the post-condition. That's ok for simple paths since they are store independent. BC.
There may also be a problem here in C, because calls may be anywhere inside an expression, and not solely as standalone statements. It may be better to call this function during the intraprocedural analysis of callers and not during a standalone phase which would have to deal with calls in sub-expressions, and thus also with store/pointers modifications. BC.
Definition at line 209 of file liveness_analysis_engine.c.
References call_arguments, call_function, live_out_summary_engine_context::current_callee, current_stmt, entity_name, gen_get_ancestor(), generic_effects_forward_translation(), load_live_out_paths_list(), pips_debug, pips_debug_effects, statement_domain, and update_live_out_summary_engine_context_paths().
Referenced by live_out_paths_from_caller_to_callee().
|
static |
All we need to perform the translation
Definition at line 256 of file liveness_analysis_engine.c.
References call_domain, callee, caller_name, live_out_summary_engine_context::current_callee, db_get_live_out_paths_func, db_get_memory_resource(), entity_name, free_statement_global_stack(), gen_context_multi_recurse(), gen_null(), get_current_module_statement(), live_out_paths_from_call_site_to_callee(), live_out_summary_paths_stmt_filter(), make_statement_global_stack(), module_local_name(), pips_debug, reset_current_module_entity(), reset_current_module_statement(), reset_live_out_paths(), set_current_module_entity(), set_current_module_statement(), set_live_out_paths(), and statement_domain.
Referenced by live_out_summary_paths_engine().
|
static |
The live out paths of an iteration are the paths that
First, we get the live out paths of the whole loop
It may be executed...
...or another next iteration of the loop body
Take into account the effects of the header
We don't have the in effects of the header evaluation we safely approximate them by its may read proper effects if there are write effects during its evaluation We could be much more precise here by distinguishing the three different components and re-computing their effects. However, for loops are generally converted to loops or while loops by the controlizer, so I leave this as it is for the time being.
Definition at line 532 of file liveness_analysis_engine.c.
References convert_in_effects(), convert_rw_effects(), current_stmt, effects_dup(), effects_read_effects_dup(), effects_same_action_p(), effects_to_may_effects(), effects_write_effects_dup(), ENDP, forloop_body, gen_get_ancestor(), load_invariant_in_effects_list(), load_live_out_paths_list(), load_proper_rw_effects_list(), pips_debug, pips_debug_effects, proper_to_summary_effects(), r_w_combinable_p(), reset_converted_in_effects(), reset_converted_rw_effects(), statement_domain, and store_live_out_paths_list().
Referenced by live_paths_of_module_statement().
|
static |
First, we get the live out paths of the statement corresponding to the whole loop
We then compute the live out paths of the loop body
The live out paths of an iteration are the paths that
Definition at line 845 of file liveness_analysis_engine.c.
References CONS, convert_in_effects(), convert_rw_effects(), current_stmt, EFFECT, effects_dup(), effects_dup_without_variables(), effects_read_effects_dup(), effects_same_action_p(), effects_to_may_effects(), effects_write_effects_dup(), gen_full_free_list(), gen_get_ancestor(), load_invariant_in_effects_list(), load_live_out_paths_list(), load_proper_rw_effects_list(), load_rw_effects_list(), loop_body, loop_executed_at_least_once_p(), loop_executed_never_p(), loop_index, loop_locals, loop_parallel_p(), make_action_read_memory(), make_reference(), NIL, pips_debug, pips_debug_effects, proper_to_summary_effects(), r_w_combinable_p(), reference_to_effect_func, reset_converted_in_effects(), reset_converted_rw_effects(), statement_domain, and store_live_out_paths_list().
Referenced by live_paths_of_module_statement().
|
static |
First, we get the live out paths of the statement corresponding to the test
The live out paths for each branch are the live_out_paths of the test
The live in paths of the test are computed with the surrounding sequence live paths computation.
Definition at line 1052 of file liveness_analysis_engine.c.
References current_stmt, effects_dup(), gen_get_ancestor(), load_live_out_paths_list(), pips_debug, statement_domain, store_live_out_paths_list(), test_false, and test_true.
Referenced by live_paths_of_module_statement().
|
static |
Adopt a very conservative strategy: live_out(node)= live_out(unstructured)*may U (U_{n \in nodes} IN(nodes)) If convex paths were to be computed, transformers should be taken into account.
The exit node is a particular case: its live_out paths are the live_out paths of the unstructured.
there is only one statement in u;
It may be executed...
be sure live_out paths are not stored twice, in particular for the exit node
Definition at line 439 of file liveness_analysis_engine.c.
References bound_live_out_paths_p(), CONTROL, control_predecessors, control_statement, control_successors, convert_in_effects(), current_stmt, effects_dup(), effects_same_action_p(), effects_to_may_effects(), FOREACH, gen_get_ancestor(), load_in_effects_list(), load_live_out_paths_list(), NIL, pips_debug, pips_debug_effects, reset_converted_in_effects(), statement_domain, statement_number, statement_ordering, store_live_out_paths_list(), UNSTRUCTURED_CONTROL_MAP, and unstructured_exit.
Referenced by live_paths_of_module_statement().
|
static |
The live out paths of an iteration are the paths that
First, we get the live out paths of the whole loop
It may be executed...
...or another next iteration of the loop body
Take into account the effects of the condition
We don't have the in effects of the condition evaluation we safely approximate them by its may read proper effects if there are write effects during its evaluation
Definition at line 631 of file liveness_analysis_engine.c.
References convert_in_effects(), convert_rw_effects(), current_stmt, effects_dup(), effects_read_effects_dup(), effects_same_action_p(), effects_to_may_effects(), effects_write_effects_dup(), ENDP, gen_get_ancestor(), load_invariant_in_effects_list(), load_live_out_paths_list(), load_proper_rw_effects_list(), pips_debug, pips_debug_effects, proper_to_summary_effects(), r_w_combinable_p(), reset_converted_in_effects(), reset_converted_rw_effects(), statement_domain, store_live_out_paths_list(), and whileloop_body.
Referenced by live_paths_of_module_statement().
bool live_out_region_engine | ( | const char * | module_name, |
__attribute__((unused)) effects_representation_val | representation | ||
) |
Definition at line 1394 of file liveness_analysis_engine.c.
References db_get_memory_resource(), DB_PUT_MEMORY_RESOURCE, debug_off, debug_on, filter_live_out_regions_statement(), gen_null(), gen_recurse, get_current_module_statement(), get_live_out_regions(), init_live_out_regions(), module_name(), module_name_to_entity(), module_statement, pips_assert, pips_debug, reset_current_module_entity(), reset_current_module_statement(), reset_live_in_paths(), reset_live_out_paths(), reset_live_out_regions(), reset_out_effects(), set_current_module_entity(), set_current_module_statement(), set_live_in_paths(), set_live_out_paths(), set_out_effects(), statement_consistent_p(), and statement_domain.
bool live_out_summary_paths_engine | ( | const char * | module_name | ) |
Look for all call sites in the callers
module_name | odule_name |
Definition at line 304 of file liveness_analysis_engine.c.
References callee, callees_callees, caller_name, db_get_memory_resource(), debug_off, debug_on, FOREACH, fprintf(), free_effects_private_current_context_stack(), gen_length(), ifdebug, live_out_summary_engine_context::l_current_paths, list_undefined_p, live_out_paths_from_caller_to_callee(), make_effects_private_current_context_stack(), module_local_name(), module_name(), module_name_to_entity(), NIL, pips_debug, reset_current_module_entity(), reset_current_module_statement(), reset_live_out_summary_engine_context(), set_current_module_entity(), set_current_module_statement(), set_live_out_summary_engine_context(), and STRING.
|
static |
Definition at line 248 of file liveness_analysis_engine.c.
References pips_debug, and statement_number.
Referenced by live_out_paths_from_caller_to_callee().
bool live_paths_engine | ( | const char * | module_name, |
effects_representation_val | representation | ||
) |
Get the code of the module.
Get the various effects and in_effects of the module.
Initialize the map for live_out and live_int paths
Get the live_out_summary_paths of the current module
And stores them as the live out paths of the module statement
Compute the live paths of the module.
module_name | odule_name |
representation | epresentation |
Definition at line 1178 of file liveness_analysis_engine.c.
References db_get_cumulated_in_effects_func, db_get_in_effects_func, db_get_invariant_in_effects_func, db_get_invariant_rw_effects_func, db_get_memory_resource(), db_get_proper_rw_effects_func, db_get_rw_effects_func, debug_off, debug_on, effects_dup(), free_effects_private_current_context_stack(), get_current_module_statement(), get_live_in_paths(), get_live_out_paths(), init_live_in_paths(), init_live_out_paths(), init_live_paths_context(), live_paths_of_module_statement(), make_effects_private_current_context_stack(), module_name(), module_name_to_entity(), module_statement, pips_debug, reset_cumulated_in_effects(), reset_current_module_entity(), reset_current_module_statement(), reset_in_effects(), reset_invariant_in_effects(), reset_invariant_rw_effects(), reset_live_in_paths(), reset_live_out_paths(), reset_live_paths_context(), reset_proper_rw_effects(), reset_rw_effects(), set_cumulated_in_effects(), set_current_module_entity(), set_current_module_statement(), set_in_effects(), set_invariant_in_effects(), set_invariant_rw_effects(), set_proper_rw_effects(), set_rw_effects(), and store_live_out_paths_list().
|
static |
reversed version of the sequence to avoid recursion
the live out paths of the current statement are the live in paths of the next statement (or the live out of the while block if last statement)
Now let us compute the live in paths
The block live in paths are the live in paths of the first statement which is the last visited statement. However, in case of nested sequences, which may be the case when there are macros for instance, the live_in paths may have already been computed. It's not yet clear if the effects we have just computed are more precise or not.
Definition at line 1080 of file liveness_analysis_engine.c.
References bound_live_in_paths_p(), CONS, effects_dup(), ENDP, FOREACH, gen_free_list(), gen_get_ancestor(), get_bool_property(), live_in_paths_of_statement(), load_live_in_paths_list(), load_live_out_paths_list(), NIL, pips_debug, pips_debug_effects, pips_user_warning, sequence_statements, STATEMENT, statement_domain, statement_number, statement_ordering, store_live_in_paths_list(), and store_live_out_paths_list().
Referenced by live_paths_of_module_statement().
|
static |
for expression instructions solely, equivalent to gen_true otherwise
Stop on these nodes:
calls are treated in another phase
Definition at line 1155 of file liveness_analysis_engine.c.
References call_domain, expression_domain, forloop_domain, gen_context_multi_recurse(), gen_false(), gen_null(), gen_true(), live_in_paths_of_loop(), live_in_paths_of_statement(), live_in_paths_of_whileloop(), live_out_paths_from_forloop_to_body(), live_out_paths_from_loop_to_body(), live_out_paths_from_test_to_branches(), live_out_paths_from_unstructured_to_nodes(), live_out_paths_from_whileloop_to_body(), live_paths_from_block_to_statements(), loop_domain, sequence_domain, statement_domain, test_domain, unstructured_domain, and whileloop_domain.
Referenced by live_paths_engine().
|
static |
Create a new nsc system from the sc system of a region.
On this new nsc system only keep live variable. /param sc constraint system of the region /param ref reference variable that the region carry, have to keep on the new system of constraints /param llivein list of live in effect, variables to keep /param lliveout list of live out effect, variables to keep /return a new system of constraint for the region that only keep live variable
Definition at line 1264 of file liveness_analysis_engine.c.
References base_add_variable(), base_contains_variable_p(), base_copy(), BASE_FOREACH, CATCH, default_variable_to_string(), EFFECT, effect_any_reference, entity_name, EXPRESSION, expression_to_entity(), FOREACH, FWD_OFL_CTRL, ifdebug, keep, overflow_error, pips_debug, pips_user_warning, ref, reference_indices, reference_variable, sc_base_remove_variable(), sc_dup(), sc_free(), sc_normalize(), sc_print(), TRY, UNCATCH, vect_erase_var(), and vect_fprint().
Referenced by filter_live_out_regions_statement().
|
static |
Definition at line 118 of file liveness_analysis_engine.c.
References gen_free_list(), live_paths_analysis_context::memory_effects_only, live_paths_analysis_context::memory_in_out_effects_only, and NIL.
Referenced by live_in_paths_of_statement(), live_out_paths_from_forloop_to_body(), live_out_paths_from_loop_to_body(), live_out_paths_from_unstructured_to_nodes(), and live_out_paths_from_whileloop_to_body().
|
static |
Definition at line 101 of file liveness_analysis_engine.c.
References gen_free_list(), live_paths_analysis_context::memory_effects_only, and NIL.
Referenced by live_in_paths_of_loop(), live_in_paths_of_statement(), live_in_paths_of_whileloop(), live_out_paths_from_forloop_to_body(), live_out_paths_from_loop_to_body(), and live_out_paths_from_whileloop_to_body().
|
static |
Definition at line 185 of file liveness_analysis_engine.c.
References live_out_summary_engine_context::current_callee, entity_undefined, live_out_summary_engine_context::l_current_paths, and list_undefined.
Referenced by live_out_summary_paths_engine().
|
static |
Definition at line 81 of file liveness_analysis_engine.c.
References live_paths_analysis_context::memory_effects_only, live_paths_analysis_context::memory_in_out_effects_only, and set_bool_property().
Referenced by live_paths_engine().
|
static |
Definition at line 178 of file liveness_analysis_engine.c.
References callee, live_out_summary_engine_context::current_callee, live_out_summary_engine_context::l_current_paths, and list_undefined.
Referenced by live_out_summary_paths_engine().
|
static |
Definition at line 192 of file liveness_analysis_engine.c.
References effects_same_action_p(), live_out_summary_engine_context::l_current_paths, list_undefined_p, and pips_debug_effects.
Referenced by live_out_paths_from_call_site_to_callee().