PIPS
|
#include <stdio.h>
#include <string.h>
#include "genC.h"
#include "linear.h"
#include "ri.h"
#include "effects.h"
#include "ri-util.h"
#include "prettyprint.h"
#include "effects-util.h"
#include "database.h"
#include "pipsdbm.h"
#include "resources.h"
#include "misc.h"
#include "effects-generic.h"
#include "effects-simple.h"
#include "transformer.h"
#include "semantics.h"
Go to the source code of this file.
Macros | |
#define | DEBUG_PRECONDITION_INTRA_TO_INTER 1 |
#define | PROCESS_CALL_DEBUG_LEVEL 5 |
Variables | |
static entity | current_caller = entity_undefined |
Context to compute summary preconditions. More... | |
static transformer | current_precondition = transformer_undefined |
static entity | current_callee = entity_undefined |
static list | summary_effects_of_callee = list_undefined |
static transformer | current_summary_precondition = transformer_undefined |
static statement | current_statement = statement_undefined |
static int | number_of_call_sites = -1 |
#define DEBUG_PRECONDITION_INTRA_TO_INTER 1 |
#define PROCESS_CALL_DEBUG_LEVEL 5 |
transformer add_formal_to_actual_bindings | ( | call | c, |
transformer | pre, | ||
entity | caller | ||
) |
add_formal_to_actual_bindings(call c, transformer pre, entity caller):
pre := pre U {f = expr } i i for all i such that formal f_i is an analyzable scalar variable and as far as expression expr_i is analyzable and of the same type
let's start a long, long, long MAPL, so long that MAPL is a pain
type checking. You already know that fp is a scalar variable
Do not care about side effects on expressions: this is used to map a caller precondition towards a callee summary precondition.
tmp must be used instead of fp_new because fp_new does not exist in the caller frame
Likely memory leak for the initial pre
ignore assocation
pre | re |
caller | aller |
Definition at line 283 of file interprocedural.c.
References any_expression_to_transformer(), basic_of_expression(), basic_tag, basic_to_string(), call_arguments, call_function, CAR, dump_transformer, ENDP, ENTITY, entity_local_name(), entity_module_p(), entity_storage, entity_type, expression_undefined, external_entity_to_new_value(), f(), find_ith_argument(), formal_offset, free_arguments(), free_transformer(), ifdebug, make_local_temporary_value_entity(), module_local_name(), module_to_formal_analyzable_parameters(), pips_assert, pips_debug, pips_user_error, pips_user_warning, POP, same_basic_p(), storage_formal, transformer_safe_image_intersection(), transformer_safe_value_substitute(), transformer_undefined, type_variable, and variable_basic.
Referenced by call_site_to_module_precondition_text(), and call_to_summary_precondition().
void add_module_call_site_precondition | ( | entity | m, |
transformer | p | ||
) |
module precondition
cons * ef = code_effects(value_code(entity_initial(m)));
p might not be printable; it may (should!) contain formal parameters of module m
keep only the interprocedural part of p that can be easily used by m; this is non optimal because symbolic constants will be lost; this is due to value mappings; new and old values should be added to the mapping using the module precondition
convert global variables in the summary precondition in the local frame as defined by value mappings (FI, 1 February 1994)
p is returned in the callee's frame; there is no need for a translation; the caller's frame should always contain the callee's frame by definition of effects;unfortunately, I do not remember why I added this translation; it was linked to a problem encountered with transformer and "invisible" variables, i.e. global variables which are indirectly changed by a procedure which does not see them; such variables receive an arbitrary existing global name; they may receive different names in different context, because there is no canonical name; each time, summary_precondition and summary_transformer are used, they must be converted in a unique frame, which can only be the frame of the current module.
FI, 9 February 1994
the former precondition represents the entire space : the new precondition must also represent the entire space BC, november 1994.
the former precondition is undefined. The new precondition is defined by the current call site precondition BC, november 1994.
Definition at line 123 of file interprocedural.c.
References DB_PUT_MEMORY_RESOURCE, dump_transformer, entity_module_p(), get_current_module_entity(), get_module_precondition(), ifdebug, load_summary_effects(), module_local_name(), pips_assert, pips_debug, precondition_intra_to_inter(), strdup(), transformer_convex_hull(), transformer_free(), transformer_identity_p(), transformer_undefined, transformer_undefined_p, and translate_global_values().
Referenced by call_to_summary_precondition().
This function does everything needed.
Called by ICFG with many different contexts.
summary effects for the callee
caller preconditions
callee preconditions
load caller preconditions
first, we deal with the caller
create htable for old_values ...
add to preconditions the links to the callee formal params
transform the preconditions to make sense for the callee
translate_global_values(e_caller, call_site_prec);
Now deal with the callee
Set the htable with its variables because now we work in this frame
caller | aller |
callee | allee |
Definition at line 1051 of file interprocedural.c.
References add_formal_to_actual_bindings(), callee, db_get_memory_resource(), free_value_mappings(), load_statement_semantic(), load_summary_effects(), module_local_name(), module_to_value_mappings(), precondition_intra_to_inter(), reset_cumulated_rw_effects(), reset_current_module_entity(), reset_current_module_statement(), reset_semantic_map(), set_cumulated_rw_effects(), set_current_module_entity(), set_current_module_statement(), set_semantic_map(), text_for_a_transformer(), transformer_dup(), transformer_normalize(), and transformer_undefined.
void call_to_summary_precondition | ( | transformer | pre, |
call | c | ||
) |
propagate precondition pre as summary precondition of user functions
propagate precondition pre as summary precondition of user functions
user_warning("call_to_summary_precondition", "call to symbolic %s\n", entity_name(e));
pre | re |
Definition at line 989 of file interprocedural.c.
References add_formal_to_actual_bindings(), add_module_call_site_precondition(), call_arguments, call_function, entity_initial, entity_name, expressions_to_summary_precondition(), get_current_module_entity(), is_value_code, is_value_constant, is_value_intrinsic, is_value_symbolic, is_value_unknown, pips_debug, pips_internal_error, transformer_dup(), transformer_undefined, user_warning, and value_tag.
Referenced by expression_to_summary_precondition().
void expression_to_summary_precondition | ( | transformer | pre, |
expression | e | ||
) |
pre | re |
Definition at line 977 of file interprocedural.c.
References call_to_summary_precondition(), expression_syntax, syntax_call, and syntax_call_p.
Referenced by expressions_to_summary_precondition().
void expressions_to_summary_precondition | ( | transformer | pre, |
list | le | ||
) |
pre | re |
le | e |
Definition at line 966 of file interprocedural.c.
References CAR, EXPRESSION, expression_to_summary_precondition(), and MAPL.
Referenced by call_to_summary_precondition().
int get_call_site_number | ( | void | ) |
Definition at line 1131 of file interprocedural.c.
References number_of_call_sites.
Referenced by summary_precondition(), and summary_total_postcondition().
transformer get_module_precondition | ( | entity | m | ) |
package semantics
interprocedural.c
include <stdlib.h> What follows has to be updated!!!
The SUMMARY_PRECONDITION of a module m is built incrementally when the preconditions of its CALLERS are computed. Each time a call site cs to m is encountered, the precondition for cs is augmented with equations between formal and actual integer arguments. The new precondition so obtained is chained to the other preconditions for m.
In other word, SUMMARY_PRECONDITION is a list of preconditions containing each a relation between formal and actual parameter. Should it be called SUMMARY_PRECONDITIONS?
Before using the list of preconditions for m, each precondition has to:
These steps cannot be performed in the caller because the callee's value mappings are unknown.
Memory management:
Note: illegal request are made to pipsdbm()
FI: this does not work because the summary preconditions is reset each time it should be accumulated
Definition at line 92 of file interprocedural.c.
References db_get_memory_resource(), db_resource_p(), entity_module_p(), module_local_name(), pips_assert, and transformer_undefined.
Referenced by add_module_call_site_precondition().
Each time a statement is entered, its precondition is memorized.
There may be or not a precondition associated to this statement, depending on an intermediate disk storage. However, if the ordering of statement s is undefined, statement s is not reachable and the corresponding call site should be ignored, as well as call sites in statements controlled by s
FI: probably a memory leak is started here
Definition at line 1137 of file interprocedural.c.
References current_precondition, current_statement, declaration_statement_p(), load_statement_semantic(), pips_assert, propagate_preconditions_in_declarations(), push_statement_on_statement_global_stack(), statement_declarations, statement_ordering, STATEMENT_ORDERING_UNDEFINED, transformer_range(), transformer_undefined, and update_summary_precondition_in_declaration().
Referenced by update_precondition_with_call_site_preconditions().
returns a module's parameter's list
get unsorted list of formal analyzable parameters for f by declaration filtering; these parameters may not be used by the callee's semantics analysis, but we have no way to know it because value mappings are not available
Definition at line 232 of file interprocedural.c.
References analyzable_scalar_entity_p(), CAR, code_declarations, CONS, ENTITY, entity_code(), entity_module_p(), entity_storage, f(), list_undefined, MAPL, NIL, pips_assert, and storage_formal_p.
Referenced by add_formal_to_actual_bindings(), and fortran_user_call_to_transformer().
transformer new_add_formal_to_actual_bindings | ( | call | c, |
transformer | pre, | ||
entity | caller | ||
) |
Take side effects into account:
pre := (t(expr )...(t_expr ))(pre) U {f = expr } n 1 i i for all i such that formal f_i is an analyzable scalar variable and as far as expression expr_i is analyzable and of the same type.
The algorithmic structure has to be different from the previous one.
pre is modified by side effects.
pre | re |
caller | aller |
Definition at line 375 of file interprocedural.c.
References any_user_call_site_to_transformer(), call_arguments, call_function, dump_transformer, f(), free_transformer(), ifdebug, module_local_name(), NIL, pips_debug, and transformer_apply().
Referenced by process_call_for_summary_precondition().
transformer precondition_intra_to_inter | ( | entity | callee, |
transformer | pre, | ||
list | le | ||
) |
precondition cannot be printed because equations linking formal parameters have been added to the real precondition
make sure you do not export a (potentially) meaningless old value
Thru DATA statements, old values of other modules may appear
get rid of old_values
sc_elim_redund
no_elim
get rid of pre's variables that do not appear in effects le
we should not have to know about these internal objects, Psysteme and Pvecteur!
build a list of values to suppress
get rid of variables that are not referenced, directly or indirectly, by the callee; translate what you can
For clarity, all cases are presented
No need to substitute or eliminate this value
This is a short term improvement for partial_eval01-02 that works only for values local to the callee not for values updated indirectedly by callees of "callee".
It resulted in many core dumps in array privatization
no conflicts
list of conflicting entities
case 1: only one entity
case 1.1: one conflicting integer entity
Type mismatch
case 1.22: one conflicting non analyzable scalar entity
case 2: at least 2 conflicting entities
case 2.1: all entities have the same type, according to mapping_values the subtitution is made with the first list element e_callee
case 2.2: all entities do not have the same type
Get rid of variables local to the caller
Get rid of unused or untouched variables, even though they may appear as global variables or formal parameters
This happens with automatically generated modules and for routine XERCLT in KIVA (Renault) because it has been emptied.
No information but feasibility can be preserved
Get rid of the basis and arguments to define the empty set
No information: the all value space is OK
sc_elim_redund
no_elim
free the temporary list of entities
get rid of arguments because they are meaningless for a module precondition: v_new == v_old by definition
callee | allee |
pre | re |
le | e |
Definition at line 395 of file interprocedural.c.
References analyzable_scalar_entity_p(), arguments_add_entity(), arguments_difference(), Ssysteme::base, base_contains_variable_p(), c_language_module_p(), callee, CAR, concrete_effects_entities_which_may_conflict_with_scalar_entity(), DEBUG_PRECONDITION_INTRA_TO_INTER, dump_arguments(), dump_transformer, ENDP, ENTITY, entity_constant_p, entity_module_name(), entity_name, entity_to_old_value(), entity_type, fortran_language_module_p(), free_transformer(), gen_free_list(), gen_length(), get_current_module_entity(), ifdebug, local_entity_of_module_p(), module_local_name(), NIL, pips_debug, POP, predicate_system, print_effects, same_analyzable_type_scalar_entity_list_p(), same_string_p, sc_safe_normalize(), Svecteur::succ, transformer_arguments, transformer_empty(), transformer_empty_p(), transformer_identity(), transformer_projection_with_redundancy_elimination(), transformer_relation, transformer_value_substitute(), translate_global_values(), type_equal_p(), and vecteur_var.
Referenced by add_module_call_site_precondition(), call_site_to_module_precondition_text(), and process_call_for_summary_precondition().
Update the current_summary_precondition, if necessary.
p might not be printable; it may (should!) contain formal parameters of module m
p might not be printable; it may (should!) contain formal parameters of module m
add to call site preconditions the links to the callee formal params
caller_prec should not be printable; it should contain formal parameters of module callee
transform the preconditions to make sense for the callee
Beware: call_site_prec and caller_prec are synonymous
Provoque initialization with an undefined transformer...
ips_assert("process_call", !transformer_undefined_p(call_site_prec));
convert global variables in the summary precondition in the caller's frame as defined by value mappings (FI, 1 February 1994)
p is returned in the callee's frame; there is no need for a translation; the caller's frame should always contain the callee's frame by definition of effects;
Unfortunately, I do not remember why I added this translation; It was linked to a problem encountered with transformer and "invisible" variables, i.e. global variables which are indirectly changed by a procedure which does not see them; such variables receive an arbitrary existing global name; they may receive different names in different context, because there is no canonical name; each time, summary_precondition and summary_transformer are used, they must be converted in a unique frame, which can only be the frame of the current module. In other words, you have to be in the same environment to be allowed to combine preconditions.
FI, 9 February 1994
This may be now useless...
the former precondition represents the entire space : the new precondition must also represent the entire space BC, november 1994.
the former precondition is undefined. The new precondition is defined by the current call site precondition BC, november 1994.
FI: Let's put the summary_precondition in the callee's frame.. Well, it's an illusion because translate_global_values() is not symmetrical. It only can import global values. The summary precondition is left in the last caller's frame. It will have to be translated in callee's frame when used.
Definition at line 1176 of file interprocedural.c.
References call_arguments, call_function, constant_path_analyzed_p(), current_callee, current_caller, current_precondition, current_statement, current_summary_precondition, dump_transformer, ifdebug, module_local_name(), new_add_formal_to_actual_bindings(), NIL, number_of_call_sites, pips_assert, pips_debug, precondition_intra_to_inter(), PROCESS_CALL_DEBUG_LEVEL, substitute_formal_array_elements_in_precondition(), substitute_stubs_in_transformer(), summary_effects_of_callee, transformer_convex_hull(), transformer_dup(), transformer_free(), transformer_identity_p(), transformer_undefined, transformer_undefined_p, and translate_global_values().
Referenced by update_precondition_with_call_site_preconditions(), and update_summary_precondition_in_declaration().
void reset_call_site_number | ( | void | ) |
Definition at line 1126 of file interprocedural.c.
References number_of_call_sites.
Referenced by ordinary_summary_precondition(), and summary_total_postcondition().
Definition at line 255 of file interprocedural.c.
References analyzable_scalar_entity_p(), CAR, CDR, ENDP, ENTITY, entity_type, MAP, and type_equal_p().
Referenced by precondition_intra_to_inter().
void translate_global_value | ( | entity | m, |
transformer | tf, | ||
entity | v | ||
) |
Try to convert an value on a non-local variable into an value on a local variable using a guessed name (instead of a location identity: M and N declared as COMMON/FOO/M and COMMON/FOO/N are not identified as a unique variable/location).
Mo more true: It might also fail to translate variable C:M into A:M if C is indirectly called from A thru B and if M is not defined in B.
This routine is not too safe. It accepts non-translatable variable as input and does not refuse them, most of the time.
Filter out constant and values local to the current module
FI: to be modified to account for global values that have a name but that should nevertheless be translated on their canonical representant; this occurs for non-visible global variables
FI: to be completed later... 3 December 1993 entity var = value_to_variable(v);
pips_debug(7, "%s is translated into %s\n", entity_name(v), entity_name(e)); transformer_value_substitute(tf, v, e);
Filter out old values: they are translated when the new value is encountered, and the new value has to appear if the old value does appear.
Instead, old values could be translated into new values and processing could go on...
FI, 26 October 1994
Should it be projected? No, this should occur later for xxxx::init variables when the xxxx is translated. Or before if xxxx has been translated
must be a common; dynamic and static area must have been filtered out before
try to find an equivalent entity by its name (whereas we should use locations)
no equivalent name found, get rid of v
transformer_projection(tf, CONS(ENTITY, v_old, NIL));
no equivalent location found, get rid of v
no equivalent location found, get rid of v
e has already been introduced and v eliminated; this happens when a COMMON variable is also passed as real argument
FI: v may still appear in the constraints as in spice.f (Perfect Club) and spice01.f (Validation)
this cannot happen when the summary transformer of a called procedure is translated because the write effect in the callee that is implied by v_init existence must have been passed upwards and must have led to the creation of e_init
this should not happen when a caller precondition at a call site is transformed into a piece of a summary precondition for the callee because v_init becomes meaningless; at the callee's entry point, by definition, e == e_init; v_init should have been projected before
forget e_init: there is no v_init in tf
there is no v_init to worry about; v is not changed in the caller (or its subtree of callees)
this value does not need to be translated
tf | f |
Definition at line 657 of file interprocedural.c.
References arguments_add_entity(), base_contains_variable_p(), BASE_UNDEFINED, concatenate(), CONS, contrainte_make(), CONTRAINTE_UNDEFINED, dump_transformer, ENTITY, entity_constant_p, entity_domain, entity_is_argument_p(), entity_local_name(), entity_module_name(), entity_name, entity_storage, entity_type, entity_undefined, eq, gen_find_tabulated(), gen_free_list(), global_new_value_to_global_old_value(), global_old_value_p(), ifdebug, language_c_p, module_language, module_local_name(), MODULE_SEP_STRING, NIL, OLD_VALUE_SUFFIX, pips_debug, pips_internal_error, pips_user_error, predicate_system, ram_function, ram_section, ram_undefined, same_scalar_location_p(), sc_add_egalite(), sc_equation_add(), storage_formal_p, storage_ram, storage_ram_p, storage_return_p, storage_rom_p, storage_tag, storage_undefined, strdup(), top_level_entity_p(), transformer_arguments, transformer_filter(), transformer_projection(), transformer_relation, transformer_value_substitutable_p(), transformer_value_substitute(), type_equal_p(), type_to_string(), user_warning, value_alias(), value_entity_p(), vect_add_elem(), and vect_new().
Referenced by translate_global_values().
void translate_global_values | ( | entity | m, |
transformer | tf | ||
) |
a copy of sc_base(s) is needed because translate_global_value() modifies it at the same time
tf | f |
Definition at line 625 of file interprocedural.c.
References base_rm, dump_value_name(), ifdebug, pips_debug, predicate_system, sc_fprint(), Svecteur::succ, transformer_relation, translate_global_value(), vect_dup(), and vecteur_var.
Referenced by add_module_call_site_precondition(), fortran_user_call_to_transformer(), get_semantic_text(), load_summary_precondition(), module_name_to_total_preconditions(), precondition_intra_to_inter(), process_call_for_summary_precondition(), and program_precondition().
transformer update_precondition_with_call_site_preconditions | ( | transformer | t, |
entity | caller, | ||
entity | callee | ||
) |
Update precondition t for callee with preconditions of call sites to callee in caller.
Call sites are found in the statement of caller, but also in its declarations. Return the updated precondition t.
summary effects for the callee
calls hidden in dimension declarations are not caught because entities are not traversed by gen_recurse().
This normalization seems pretty uneffective for fraer01.tpips
caller | aller |
callee | allee |
Definition at line 1371 of file interprocedural.c.
References call_domain, callee, current_callee, current_caller, current_precondition, current_summary_precondition, db_get_memory_resource(), entity_name, entity_undefined, free_value_mappings(), gen_multi_recurse(), gen_null(), get_current_module_entity(), get_current_module_statement(), list_undefined, load_summary_effects(), memorize_precondition_for_summary_precondition(), module_local_name(), module_to_value_mappings(), pips_assert, pips_user_error, pop_statement_global_stack(), process_call_for_summary_precondition(), reset_cumulated_rw_effects(), reset_current_module_entity(), reset_current_module_statement(), reset_proper_rw_effects(), reset_pt_to_list(), reset_semantic_map(), set_cumulated_rw_effects(), set_current_module_entity(), set_current_module_statement(), set_proper_rw_effects(), set_pt_to_list(), set_semantic_map(), statement_domain, summary_effects_of_callee, transformer_defined_p(), transformer_normalize(), transformer_undefined, and use_points_to_p().
Referenced by ordinary_summary_precondition(), and summary_total_postcondition().
void update_summary_precondition_in_declaration | ( | expression | e, |
transformer | pre | ||
) |
This function is called to deal with call sites located in initialization expressions carried by declarations.
pre | re |
Definition at line 1356 of file interprocedural.c.
References call_domain, current_precondition, gen_null(), gen_recurse, and process_call_for_summary_precondition().
Referenced by memorize_precondition_for_summary_precondition().
transformer value_passing_summary_transformer | ( | entity | f, |
transformer | tf | ||
) |
With value passing, writes on formal parameters are not effective interprocedurally unless an array is passed as parameter.
All new values corresponding to formal arguments of f must be projected out and removed from the arguments list.
Performed by side-effect on tf.
The old values cannot be renamed directly after projection, because the transformer projection opearator detects an inconsistency.
Rename old values as temporary values in the caller frame.
Updates the argument list after the projections
Rename tmp values as new values in the caller frame.
oav renamed oav1 because of FOREACH macro implementation
tf | f |
Definition at line 1471 of file interprocedural.c.
References CAR, CONS, ENTITY, entity_storage, entity_to_new_value(), entity_to_old_value(), entity_type, f(), FOREACH, formal_function, gen_free_list(), gen_nreverse(), location_entity_p(), make_local_temporary_value_entity(), NIL, POP, storage_formal, storage_formal_p, transformer_arguments, transformer_projection(), transformer_value_substitute(), ultimate_type(), and value_to_variable().
Referenced by generic_module_name_to_transformers().
|
static |
Definition at line 1120 of file interprocedural.c.
Referenced by process_call_for_summary_precondition(), and update_precondition_with_call_site_preconditions().
|
static |
Context to compute summary preconditions.
Definition at line 1117 of file interprocedural.c.
Referenced by process_call_for_summary_precondition(), and update_precondition_with_call_site_preconditions().
|
static |
Definition at line 1118 of file interprocedural.c.
Referenced by convex_cell_preceding_p(), convex_cell_reference_preceding_p(), eval_convex_cell_with_points_to(), generic_effect_find_aliases_with_simple_pointer_values(), generic_eval_cell_with_points_to(), generic_reference_to_points_to_matching_list(), memorize_precondition_for_summary_precondition(), path_preceding_p(), process_call_for_summary_precondition(), simple_cell_preceding_p(), update_precondition_with_call_site_preconditions(), and update_summary_precondition_in_declaration().
|
static |
Definition at line 1123 of file interprocedural.c.
Referenced by memorize_precondition_for_summary_precondition(), and process_call_for_summary_precondition().
|
static |
Definition at line 1122 of file interprocedural.c.
Referenced by process_call_for_summary_precondition(), and update_precondition_with_call_site_preconditions().
|
static |
Definition at line 1124 of file interprocedural.c.
Referenced by get_call_site_number(), process_call_for_summary_precondition(), and reset_call_site_number().
|
static |
Definition at line 1121 of file interprocedural.c.
Referenced by process_call_for_summary_precondition(), and update_precondition_with_call_site_preconditions().