PIPS
|
#include <stdio.h>
#include <string.h>
#include "genC.h"
#include "linear.h"
#include "ri.h"
#include "effects.h"
#include "ri-util.h"
#include "workspace-util.h"
#include "effects-util.h"
#include "control.h"
#include "effects-generic.h"
#include "effects-simple.h"
#include "misc.h"
#include "properties.h"
#include "ray_dte.h"
#include "sommet.h"
#include "sg.h"
#include "polyedre.h"
#include "transformer.h"
#include "semantics.h"
Go to the source code of this file.
Macros | |
#define | DEBUG_TEST_TO_POSTCONDITION 7 |
Variables | |
static list | module_global_arguments = NIL |
semantical analysis More... | |
#define DEBUG_TEST_TO_POSTCONDITION 7 |
|
static |
Assume that all references are legal.
Assume that variables used in array declarations are not modified in the module.
This assert is too strong in argument lists in Fortran and everywhere in C
Definition at line 623 of file ri_to_preconditions.c.
References basic_pointer_p, CAR, DIMENSION, dimension_lower, dimension_upper, EFFECT, effect_any_reference, ENDP, entity_type, EXPRESSION, FOREACH, gen_length(), load_proper_rw_effects_list(), NIL, NORMALIZE_EXPRESSION, normalized_linear, normalized_linear_p, pips_assert, POP, reference_indices, reference_variable, TCST, transformer_inequality_add(), type_variable, type_variable_p, ultimate_type(), upwards_vect_rename(), value_mappings_compatible_vector_p(), variable_basic, variable_dimensions, vect_coeff(), vect_constant_p(), vect_rm(), and vect_substract().
Referenced by precondition_add_reference_information(), and transformer_add_reference_information().
transformer all_data_to_precondition | ( | entity | m | ) |
any variable is included.
FI: it would be nice, if only for debugging, to pass a more restricted list...
This assumes the all variables declared in a statement is also declared at the module level.
Definition at line 536 of file ri_to_preconditions.c.
References data_to_prec_for_variables(), gen_free_list(), and module_to_all_declarations().
Referenced by initial_precondition().
|
static |
The first statement of the block must receive a copy of the block precondition to avoid data sharing
to avoid accumulating equivalence equalities
the precondition has been allocated as post
Definition at line 111 of file ri_to_preconditions.c.
References CAR, debug(), ENDP, pips_debug, POP, STATEMENT, statement_to_postcondition(), transformer_dup(), transformer_normalize(), and transformer_undefined.
Referenced by instruction_to_postcondition().
|
static |
look for static entities with an initial value.
e may not have values but its initialization expression may refer other variables which have values, however they are not likely to be static initializations.
any_expression_to_transformer may end up with an undefined transformer ...
le | of entity |
Definition at line 453 of file ri_to_preconditions.c.
References any_expression_to_transformer(), dump_transformer, ENTITY, entity_has_values_p(), entity_name, expression_undefined_p, FOREACH, free_transformer(), ifdebug, module_local_name(), pips_debug, transformer_combine(), transformer_identity(), transformer_range(), transformer_safe_normalize(), transformer_temporary_value_projection(), transformer_undefined, transformer_undefined_p, variable_initial_expression(), and variable_static_p().
Referenced by data_to_prec_for_variables().
|
static |
there is room for improvement because assign is now the only well handled intrinsic
impedance problem: build an expression from call c
propagate precondition pre as summary precondition of user functions
FI: don't! Summary preconditions are computed independently
Declared in preprocessor.h
This cannot occur in Fortran, but is possible in C.
Definition at line 281 of file ri_to_preconditions.c.
References c_module_p(), call_arguments, call_function, call_undefined, ENTITY_ASSIGN_P, entity_initial, entity_name, expression_syntax, expression_to_proper_constant_path_effects(), f(), free_expression(), free_transformer(), get_bool_property(), get_current_module_entity(), intrinsic_to_transformer(), is_syntax_call, is_value_code, is_value_constant, is_value_intrinsic, is_value_symbolic, is_value_unknown, make_expression(), make_syntax(), normalized_undefined, pips_debug, pips_internal_error, SEMANTICS_INTERPROCEDURAL, syntax_call, transformer_apply(), transformer_range(), transformer_undefined, and value_tag.
Referenced by instruction_to_postcondition().
|
static |
le | of entity |
Definition at line 499 of file ri_to_preconditions.c.
References c_data_to_prec_for_variables(), c_language_module_p(), fortran95_language_module_p(), fortran_data_to_prec_for_variables(), fortran_language_module_p(), pips_internal_error, and transformer_undefined.
Referenced by all_data_to_precondition(), and data_to_precondition().
transformer data_to_precondition | ( | entity | m | ) |
restricted to variables with effects.
Definition at line 526 of file ri_to_preconditions.c.
References data_to_prec_for_variables(), effects_to_entity_list(), gen_free_list(), and load_module_intraprocedural_effects().
Referenced by generic_module_name_to_transformers().
returns an allocated list of entities that appear in lef.
an entity may appear several times.
lef | ef |
Definition at line 516 of file ri_to_preconditions.c.
References CONS, EFFECT, effect_any_reference, ENTITY, gen_nreverse(), MAP, NIL, and reference_variable.
Referenced by data_to_precondition().
|
static |
Wild guess. See what should be done in call_to_postcondition()
Definition at line 260 of file ri_to_preconditions.c.
References exp, expression_to_proper_constant_path_effects(), expression_to_transformer(), free_transformer(), get_bool_property(), transformer_apply(), and transformer_undefined.
Referenced by instruction_to_postcondition().
|
static |
a remake that works in all cases.
FC. Isn'it a bit presumptuous? FI.
This function works for C as well as Fortran. Its name should be initial_value_to_preconditions.
FI: It remains to be enhanced to handle more cases for non-integer types. EvalExpression() should be extended to non-integer types. The new fields of data structure "constant" should be exploited.
already seen
look for entities with an initial value.
le | of entity |
Definition at line 383 of file ri_to_preconditions.c.
References basic_float_p, basic_logical_p, basic_string_p, boolean_analyzed_p(), constant_call, constant_call_p, constant_int, constant_int_p, dump_transformer, ENTITY, entity_has_values_p(), entity_initial, entity_name, entity_type, f(), float_analyzed_p(), FOREACH, free_transformer(), functional_result, ifdebug, int_to_value, linear_hashtable_free(), linear_hashtable_isin(), linear_hashtable_make(), linear_hashtable_put_once(), module_local_name(), pips_assert, pips_debug, safe_any_expression_to_transformer(), string_analyzed_p(), TCST, transformer_combine(), transformer_equality_add(), transformer_identity(), transformer_range(), transformer_safe_normalize(), transformer_temporary_value_projection(), transformer_undefined, type_functional, type_variable, value_constant, value_constant_p, value_expression, value_expression_p, VALUE_MONE, VALUE_ONE, VALUE_ZERO, variable_basic, vect_make(), and VECTEUR_NUL.
Referenced by data_to_prec_for_variables().
list get_module_global_arguments | ( | void | ) |
Definition at line 98 of file ri_to_preconditions.c.
References module_global_arguments.
Referenced by statement_to_postcondition(), and statement_to_total_precondition().
|
static |
never reached: post = pre;
Definition at line 554 of file ri_to_preconditions.c.
References block_to_postcondition(), call_to_postcondition(), evaluation_before_p, exp, expression_to_postcondition(), forloop_to_postcondition(), ifdebug, instruction_block, instruction_call, instruction_expression, 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_multitest, is_instruction_test, is_instruction_unstructured, is_instruction_whileloop, loop_to_postcondition(), pips_debug, pips_internal_error, print_transformer, repeatloop_to_postcondition(), test_to_postcondition(), transformer_undefined, unstructured_to_postcondition(), whileloop_evaluation, and whileloop_to_postcondition().
Referenced by statement_to_postcondition().
void precondition_add_reference_information | ( | transformer | pre, |
statement | s | ||
) |
pre | re |
Definition at line 695 of file ri_to_preconditions.c.
References add_reference_information().
Referenced by statement_to_postcondition().
void precondition_add_type_information | ( | transformer | pre | ) |
pre | re |
Definition at line 705 of file ri_to_preconditions.c.
References transformer_add_type_information().
transformer propagate_preconditions_in_declarations | ( | list | dl, |
transformer | pre, | ||
void(*)(expression, transformer) | process_initial_expression | ||
) |
This function is mostly copied from declarations_to_transformer().
It is used to recompute intermediate preconditions and to process the initialization expressions with the proper precondition. For instance, in:
int i = 10, j = i+1, a[i], k = foo(i);
you need to collect information about i's value to initialize j, dimension a and compute the summary precondition of function foo().
We assume that the precondition does not change within the expression as in:
int k = i++ + foo(i);
I do not remember if the standard prohibits this or not, but it may well forbid such expressions or state that the result is undefined.
But you can also have:
int a[i++][foo(i)];
or
int a[i++][j=foo(i)];
and the intermediate steps are overlooked by declaration_to_transformer() but can be checked with a proper process_dimensions() function.
This function can be called from ri_to_preconditions.c to propagate preconditions or from interprocedural.c to compute summary preconditions. In the second case, the necessary side effects are provided by the two functional parameters.
post = transformer_safe_normalize(post, 4);
post = transformer_safe_normalize(post, 4);
btf = transformer_normalize(btf, 4);
dl | l |
pre | re |
Definition at line 977 of file ri_to_preconditions.c.
References CAR, copy_transformer(), declaration_to_transformer(), ENDP, ENTITY, expression_undefined_p, free_expression(), free_transformer(), ifdebug, pips_assert, pips_debug, POP, stf(), transformer_combine(), transformer_consistency_p(), transformer_dup(), transformer_normalize(), transformer_safe_apply(), transformer_safe_normalize(), transformer_undefined, transformer_undefined_p, and variable_initial_expression().
Referenced by memorize_precondition_for_summary_precondition().
void set_module_global_arguments | ( | list | args | ) |
args | rgs |
Definition at line 103 of file ri_to_preconditions.c.
References module_global_arguments.
Referenced by module_name_to_preconditions(), and module_name_to_total_preconditions().
transformer statement_to_postcondition | ( | transformer | pre, |
statement | s | ||
) |
end of the non recursive section
Refine the precondition pre of s using side effects and compute its postcondition post.
Postcondition post is returned.
FI: if the statement s is a loop, the transformer tf is not the statement transformer but the transformer T* which maps the precondition pre onto the loop body precondition. The real statement transformer is obtained by executing the loop till it is exited. See complete_any_loop_transformer()
ACHTUNG! "pre" is likely to be misused! FI, Sept. 3, 1990
To provide information for warnings
FC: if the code is not reachable (thanks to STOP or GOTO), which is a structural information, the precondition is just empty.
keep only global initial scalar integer values; else, you might end up giving the same xxx::old name to two different local values
FI: OK, to be fixed when the declaration representation is frozen.
add array references information
add type information
Add information from declarations when useful
FI: it might be better to have another function, declarations_to_postconditions(), which might be slightly more accurate? Note that declarations_to_transformer() does compute the postcondition, but free it before returning the transformer
Remove information when leaving a block
add equivalence equalities
eliminate redundancy, rational redundancy but not integer redundancy.
FI: nice... but time consuming!
Version 3 is OK. Equations are over-used and make inequalities uselessly conplex
pre = transformer_normalize(pre, 3);
pre = transformer_normalize(pre, 6);
pre = transformer_normalize(pre, 7);
The double normalization could be avoided with a non-heuristics approach. For ocean, its overhead is 34s out of 782.97 to give 816.62s: 5 %. The double normalization is also useful for some exit conditions of WHILE loops (w05, w06, w07). It is not powerful enough for preconditions containing equations with three or more variables such as fraer01,...
BC: pre = transformer_normalize(pre, 4);
FI->BC: why keep a first normalization before the next one? FI: Because a level 2 normalization does things that a level 4 does not perform! Although level 2 is much faster...
pre = transformer_normalize(pre, 2);
Do not keep too many initial variables in the preconditions: not so smart? invariance01.c: information is lost... Since C passes values, it is usually useless to keep track of the initial values of arguments because programmers usually do not modify them. However, when they do modify the formal parameter, information is lost.
See character01.c, but other counter examples above about non_initial_values.
FI: redundancy possibly added. See asopt02. Maybe this should be moved up before the normalization step.
store the precondition in the ri
pre = statement_precondition(s);
post = instruction_to_postcondition(pre, i, tf);
pre | re |
s | postcondition of predecessor |
Definition at line 712 of file ri_to_preconditions.c.
References arguments_difference(), CAR, declaration_statement_p(), declarations_to_transformer(), empty_transformer(), ENDP, ENTITY, ENTITY_, entity_to_old_value(), fprintf(), gen_free_list(), get_bool_property(), get_int_property(), get_module_global_arguments(), ifdebug, instruction_identification(), instruction_to_postcondition(), load_statement_precondition(), load_statement_transformer(), loop_index, MAPL, NIL, ORDERING_NUMBER, ORDERING_STATEMENT, pips_assert, pips_debug, pips_internal_error, pips_user_warning, pop_statement_global_stack(), precondition_add_reference_information(), print_transformer, push_statement_on_statement_global_stack(), safe_transformer_projection(), statement_block_p, statement_declarations, statement_instruction, statement_loop(), statement_loop_p(), statement_number, statement_ordering, statement_reachable_p(), store_statement_precondition(), tf_equivalence_equalities_add(), transformer_add_type_information(), transformer_apply(), transformer_arguments, transformer_consistency_p(), transformer_filter(), transformer_normalize(), transformer_undefined, variable_to_values(), and variables_to_values().
Referenced by any_loop_to_postcondition(), block_to_postcondition(), dag_to_flow_sensitive_preconditions(), loop_to_postcondition(), module_name_to_preconditions(), process_unreachable_node(), test_to_postcondition(), unstructured_to_postcondition(), unstructured_to_postconditions(), whileloop_to_postcondition(), and whileloop_to_total_precondition().
|
static |
there are three levels of flow sensitivity and we have only a bool flag! FI
test conditions are assumed to have no side effects; it might be somewhere in the standard since functions called in an expression e cannot (should not) modify any variable used in e
&& !transformer_identity_p(tf)
convex hull might avoided if it is not required or if it is certainly useless but test information should always be propagated
True and false condition transformers. The nest three variables should be freed.
To obtain the best results, transformer_normalize(x,7) should be applied to subtransformers generated by precondition_add_condition_information() in case of equality condition and in case of string or float analysis.
"strong" transformer normalization to detect dead code generated by the test condition
A normalization of degree 3 is fine
transformer_normalize(pret, 3);
Just to get a stronger normalization with sc_safe_normalize()... which is sc_normalize(), a weak normalization function. FI: I do not understand what's going on.
FI, CA: the following "optimization" was added to avoid a call to Chernikova convex hull that core dumps:-(. 8 September 1993
From a theoretical point of view, pref could always be computed.
FI: removed because it is mathematically wrong in many cases; the negation of the test condition is lost! I keep the structure just in case another core dump occurs (25 April 1997).
To obtain the best results, transformer_normalize(x,7) should be applied to subtransformers generated by precondition_add_condition_information() in case of equality condition and in case of string or float analysis.
transformer_normalize(pref, 3);
Just to get a stronger normalization with sc_safe_normalize()
do not try to compute a refined precondition for an empty block keep the current precondition to store in the precondition statement mapping
Be careful, pre is updated by statement_to_postcondition!
Definition at line 147 of file ri_to_preconditions.c.
References condition_to_transformer(), debug(), DEBUG_TEST_TO_POSTCONDITION, empty_statement_p(), free_transformer(), ifdebug, pips_debug, pips_flag_p, print_transformer, SEMANTICS_FLOW_SENSITIVE, statement_to_postcondition(), test_condition, test_false, test_true, transformer_apply(), transformer_convex_hull(), transformer_dup(), transformer_normalize(), transformer_temporary_value_projection(), and transformer_undefined.
Referenced by instruction_to_postcondition().
void transformer_add_reference_information | ( | transformer | tf, |
statement | s | ||
) |
tf | f |
Definition at line 700 of file ri_to_preconditions.c.
References add_reference_information().
Referenced by statement_to_transformer(), and statement_to_transformer_list().
semantical analysis
phasis 2: propagate preconditions from statement to sub-statement, starting from the module 1st statement
For (simple) interprocedural analysis, this phasis should be performed top-down on the call tree.
Most functions are called xxx_to_postcondition although the purpose is to compute preconditions. However transformer are applied to preconditions to produce postconditions. Thus these modules store the preconditions and then compute an independent (i.e. no sharing) postcondition which is returned to be used by the caller.
Preconditions are NEVER shared. Sharing would introduce desastrous side effects when they are updated as for equivalenced variables and would make freeing them impossible. Thus on a recursive path from statement_to_postcondition() to itself the precondition must have been reallocated even when its value is not changed as between a block precondition and the first statement of the block precondition. In the same way statement_to_postcondition() should never returned a postcondition aliased with its precondition argument. Somewhere in the recursive call down the data structures towards call_to_postcondition() some allocation must take place even if the statement as no effect on preconditions.
Preconditions can be used to evaluate sub-expressions because Fortran standard prohibit side effects within an expression. For instance, in: J = I + F(I) function F cannot modify I.
Ambiguity: the type "transformer" is used to abstract statement effects as well as effects combined from the beginning of the module to just before the current statement (precondition) to just after the current statement (postcondition). This is because it was not realized that preconditions could advantageously be seen as transformers of the initial state when designing the ri. include <stdlib.h> another non recursive section used to filter out preconditions
Definition at line 95 of file ri_to_preconditions.c.
Referenced by get_module_global_arguments(), and set_module_global_arguments().