PIPS
|
#include <stdio.h>
#include <string.h>
#include "genC.h"
#include "database.h"
#include "linear.h"
#include "ri.h"
#include "effects.h"
#include "text.h"
#include "text-util.h"
#include "ri-util.h"
#include "prettyprint.h"
#include "effects-util.h"
#include "constants.h"
#include "effects-generic.h"
#include "effects-simple.h"
#include "misc.h"
#include "properties.h"
#include "transformer.h"
#include "semantics.h"
Go to the source code of this file.
Functions | |
list | declaration_to_transformer_list (entity v, transformer pre) |
Postpone convex hulls by keeping transformer lists instead. More... | |
list | declarations_to_transformer_list (list dl, transformer pre) |
For C declarations. More... | |
static list | block_to_transformer_list (list b, transformer pre) |
Generate all possible linear control paths. More... | |
static list | test_to_transformer_list (test t, transformer pre, list ef) |
effects of t More... | |
list | intrinsic_to_transformer_list (entity e, list pc, transformer pre, list ef) |
because of the conditional and the comma C intrinsics at least More... | |
list | assigned_expression_to_transformer_list (entity v, expression expr, transformer pre) |
transformer assigned_expression_to_transformer(entity e, expression expr, list ef): returns a transformer abstracting the effect of assignment "e = expr" when possible, transformer_undefined otherwise. More... | |
list | safe_assigned_expression_to_transformer_list (entity v, expression expr, transformer pre) |
Always returns a fully defined transformer. More... | |
list | integer_assign_to_transformer_list (expression lhs, expression rhs, transformer pre, list ef) |
This function never returns an undefined transformer. More... | |
list | any_scalar_assign_to_transformer_list (entity v, expression rhs, list ef, transformer pre) |
precondition More... | |
list | any_assign_to_transformer_list (list args, list ef, transformer pre) |
precondition More... | |
list | any_update_to_transformer_list (entity op, list args, list ef, transformer pre) |
precondition More... | |
list | any_basic_update_to_transformer_list (entity op, list args, list ef, transformer pre) |
precondition More... | |
static list | instruction_to_transformer_list (instruction i, transformer tf, transformer pre, list e) |
effects associated to instruction i More... | |
list | statement_to_transformer_list (statement s, transformer spre) |
A transformer is already available for statement s, but it is going to be refined into a list of transformers to isolate at least the identity transformer from effective transformers. More... | |
list any_assign_to_transformer_list | ( | list | args, |
list | ef, | ||
transformer | pre | ||
) |
precondition
The lhs must be a scalar reference to perform an interesting analysis
if some condition was not met and transformer derivation failed
args | rgs |
ef | arguments for assign |
pre | effects of assign |
Definition at line 777 of file ri_to_transformer_lists.c.
References any_scalar_assign_to_transformer(), CAR, CDR, effects_to_transformer(), ENDP, EXPRESSION, expression_syntax, ifdebug, NIL, pips_assert, pips_debug, pips_internal_error, print_transformers(), reference_indices, reference_variable, syntax_reference, syntax_reference_p, and transformer_undefined.
list any_basic_update_to_transformer_list | ( | entity | op, |
list | args, | ||
list | ef, | ||
transformer | pre | ||
) |
precondition
The lhs must be a scalar reference to perform an interesting analysis
if some condition was not met and transformer derivation failed
op | p |
args | rgs |
ef | arguments for update |
pre | effects of assign |
Definition at line 849 of file ri_to_transformer_lists.c.
References any_scalar_assign_to_transformer(), CAR, CDR, copy_expression(), effects_to_transformer(), ENDP, entity_intrinsic(), ENTITY_POST_INCREMENT_P, ENTITY_PRE_INCREMENT_P, EXPRESSION, expression_syntax, expression_undefined, free_expression(), ifdebug, int_to_expression(), MakeBinaryCall(), NIL, pips_assert, pips_debug, pips_internal_error, PLUS_C_OPERATOR_NAME, print_transformers(), reference_indices, reference_variable, syntax_reference, syntax_reference_p, and transformer_undefined.
list any_scalar_assign_to_transformer_list | ( | entity | v, |
expression | rhs, | ||
list | ef, | ||
transformer | pre | ||
) |
precondition
Is it standard compliant? The assigned variable is modified by the rhs.
Take care of aliasing
tf = transformer_value_substitute(tf, v_new, v_old);
rhs | hs |
ef | f |
pre | effects of assign |
Definition at line 709 of file ri_to_transformer_lists.c.
References any_expression_to_transformer(), dump_transformer, effects_to_transformer(), entity_has_values_p(), entity_is_argument_p(), entity_local_name(), entity_to_new_value(), entity_to_old_value(), entity_type, entity_user_name(), expression_to_string(), free(), free_transformer(), ifdebug, make_local_temporary_value_entity(), NIL, pips_debug, pips_internal_error, reset_temporary_value_counter(), semantics_user_warning, simple_equality_to_transformer(), transformer_add_modified_variable(), transformer_arguments, transformer_combine(), transformer_temporary_value_projection(), transformer_undefined, transformer_undefined_p, transformer_value_substitute(), ultimate_type(), and value_to_variable().
list any_update_to_transformer_list | ( | entity | op, |
list | args, | ||
list | ef, | ||
transformer | pre | ||
) |
precondition
The lhs must be a scalar reference to perform an interesting analysis
if some condition was not met and transformer derivation failed
op | p |
args | rgs |
ef | arguments for update |
pre | effects of assign |
Definition at line 810 of file ri_to_transformer_lists.c.
References any_scalar_assign_to_transformer(), CAR, CDR, copy_expression(), effects_to_transformer(), ENDP, entity_to_expression(), EXPRESSION, expression_syntax, free_expression(), ifdebug, MakeBinaryCall(), NIL, pips_assert, pips_debug, pips_internal_error, print_transformers(), reference_indices, reference_variable, syntax_reference, syntax_reference_p, transformer_undefined, and update_operator_to_regular_operator().
list assigned_expression_to_transformer_list | ( | entity | v, |
expression | expr, | ||
transformer | pre | ||
) |
transformer assigned_expression_to_transformer(entity e, expression expr, list ef): returns a transformer abstracting the effect of assignment "e = expr" when possible, transformer_undefined otherwise.
Note: it might be better to distinguish further between e and expr and to return a transformer stating that e is modified when e is accepted for semantics analysis.
if the assigned variable is also assigned by the expression as in i = (i = 2) + 1, transformer_value_substitute() cannot be used right away. The previous store must be projected out.
v must be assigned
subcase of previous aternative
vect_rm(ve);
expr | xpr |
pre | re |
Definition at line 551 of file ri_to_transformer_lists.c.
References any_expression_to_transformer(), entity_has_values_p(), entity_is_argument_p(), entity_to_new_value(), entity_to_old_value(), entity_type, free_transformer(), make_local_temporary_value_entity(), NIL, pips_debug, pips_internal_error, simple_equality_to_transformer(), transformer_add_value_update(), transformer_arguments, transformer_combine(), transformer_temporary_value_projection(), transformer_undefined, transformer_undefined_p, and transformer_value_substitute().
|
static |
Generate all possible linear control paths.
We start with a unique precondition.
For each statement, we start with a transformer list btfl_i-1 and with a postcondition list postl_i-1
To each statement s_i, we associate a transformer list stfl_i.
For each transformer stf_j in stfl_i, for each transformer btf_k and postcondition post_k in btfl_i-1 and postl_i-1, we compute a new transformer nbtf_j,k=stf_j o btf_k and a new postcondition npost_j,k=stf_j(post_k).
btfl_i = {nbtf_j,k} and postl_i = {npost_j,k}
The first statement must be handled in a specific way or btfl_0 be initialized to a singleton list with the identity transformer and postl_0 be initialized as a singleton list with a single element {pre}.
The number of transformers returned increase exponentially with the block size n. Assume that each statement returns two transformers: 2**n transformers are returned by this function.
More thinking about memory management probably useful. Also postconditions are automatically available in the transformers. The simultaneous computation of postconditions seem redundant.
Handle the first statement
For the next statements
Now, switch from btfl and postl to nbtfl and npostl
Postconditions are discarded
Clean up the transformer list: reduce identity transformers to one if any and move it ahead of the list
Definition at line 292 of file ri_to_transformer_lists.c.
References CAR, clean_up_transformer_list(), CONS, copy_transformer(), ENDP, FOREACH, free_transformer(), gen_full_free_list(), gen_length(), gen_nconc(), ifdebug, NIL, pips_assert, pips_debug, POP, print_transformers(), STATEMENT, statement_to_transformer_list(), stf(), TRANSFORMER, transformer_combine(), transformer_consistency_p(), transformer_empty_p(), transformer_normalize(), transformer_range(), transformer_safe_apply(), transformer_safe_normalize(), transformer_undefined, transformer_undefined_p, transformers_range(), transformers_safe_apply(), and transformers_safe_normalize().
Referenced by instruction_to_transformer_list().
list declaration_to_transformer_list | ( | entity | v, |
transformer | pre | ||
) |
Postpone convex hulls by keeping transformer lists instead.
This development was prompted by the last example found in the paper by Schrammel and Jeannet at NSAD 2010. See test cases schrammel04, 05 and 06. The minimal goal is to avoid the indentity transformer when performing the convex hull of several transformers.
This could also be useful to automatize the handling of tests within a loop using the technique presented at NSAD 2010 by Ancourt & al. The control structure
"while(c) if(t) T; else F;"
is replaced by
"while(c) {while(c&&t) T; while(c&& !t) F;}".
This replacement could be performed on the equations instead of requiring a program transformation. semantical analysis
phasis 3: compute transformer lists from statements and statement transformers
For refined precondition analysis. Keep track of all control paths within sequences
Francois Irigoin, September 2010 include <stdlib.h> Note: initializations of static variables are not used as transformers but to initialize the program precondition. It is not assumed that entity_has_values_p(v)==true A write effect on the declared variable is assumed as required by Beatrice Creusillet for region computation.
FI: the initialization expression might have relevant side-effects? This could ba handled by generalizing variable_to_initial_expression() and by returning expression_undefined incase of failure instead of aborting.
Use the dimension expressions and the initial value
FI: I preserve the code below in case I have problems with integer typing in the future
pre | re |
Definition at line 100 of file ri_to_transformer_lists.c.
References dimensions_to_transformer(), entity_has_values_p(), entity_name, free_expression(), get_bool_property(), ifdebug, NIL, pips_assert, pips_debug, pips_internal_error, print_transformers(), safe_assigned_expression_to_transformer(), transformer_apply(), transformer_combine(), transformer_identity(), transformer_range(), transformer_undefined, transformer_undefined_p, variable_initial_expression(), and variable_static_p().
list declarations_to_transformer_list | ( | list | dl, |
transformer | pre | ||
) |
For C declarations.
Very close to a block_to_transformer() as declarations can be seen as a sequence of assignments.
Note: initialization of static variables are not taken into account. They must be used for summary preconditions.
post = transformer_safe_normalize(post, 4);
post = transformer_safe_normalize(post, 4);
btf = transformer_normalize(btf, 4);
dl | l |
pre | re |
Definition at line 212 of file ri_to_transformer_lists.c.
References CAR, declaration_to_transformer(), ENDP, ENTITY, entity_undefined, free_transformer(), ifdebug, list_undefined, pips_assert, pips_debug, pips_internal_error, POP, stf(), transformer_combine(), transformer_consistency_p(), transformer_dup(), transformer_identity(), transformer_normalize(), transformer_range(), transformer_safe_apply(), transformer_safe_normalize(), transformer_undefined, and transformer_undefined_p.
|
static |
effects associated to instruction i
Nothing fancy yet in spite of the C ? and , operators
Bourdoncle's to be replaced
Nothing fancy yet in spite of the C ? and , operators
Definition at line 894 of file ri_to_transformer_lists.c.
References block_to_transformer_list(), call_to_transformer(), complete_forloop_transformer_list(), complete_loop_transformer_list(), complete_whileloop_transformer_list(), CONS, fprintf(), ifdebug, instruction_block, instruction_call, instruction_forloop, instruction_loop, instruction_tag, instruction_test, 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, list_undefined, list_undefined_p, NIL, pips_debug, pips_internal_error, print_transformers(), test_to_transformer_list(), TRANSFORMER, and transformer_empty_p().
Referenced by statement_to_transformer_list().
list integer_assign_to_transformer_list | ( | expression | lhs, |
expression | rhs, | ||
transformer | pre, | ||
list | ef | ||
) |
This function never returns an undefined transformer.
It is used for an assignment statement, not for an assignment operation. effects of assign
algorithm: if lhs and rhs are linear expressions on scalar integer variables, build the corresponding equation; else, use effects ef
should be extended to cope with constant integer division as in N2 = N/2 because it is used in real program; inequalities should be generated in that case 2*N2 <= N <= 2*N2+1
same remark for MOD operator
implementation: part of this function should be moved into transformer.c
&& integer_scalar_entity_p(e)
FI: the initial version was conservative because only affine scalar integer assignments were processed precisely. But non-affine operators and calls to user defined functions can also bring some information as soon as some integer read or write effect exists
check that all read effects are on integer scalar entities
Check that some read or write effects are on integer scalar entities. This is almost always true... Let's hope assigned_expression_to_transformer() returns quickly for array expressions used to initialize a scalar integer entity.
if some condition was not met and transformer derivation failed
lhs | hs |
rhs | hs |
pre | re |
ef | f |
Definition at line 645 of file ri_to_transformer_lists.c.
References assigned_expression_to_transformer(), effects_to_transformer(), entity_has_values_p(), ifdebug, NIL, NORMALIZE_EXPRESSION, normalized_linear, normalized_linear_p, pips_debug, pips_internal_error, print_transformers(), some_integer_scalar_read_or_write_effects_p(), transformer_undefined, and vecteur_var.
list intrinsic_to_transformer_list | ( | entity | e, |
list | pc, | ||
transformer | pre, | ||
list | ef | ||
) |
because of the conditional and the comma C intrinsics at least
effects of intrinsic call
FI: this may happen, for instance with the macro definition of assert() or because the programmer writes "i>1? (i = 2): (i = 3);" instead of "i = i>1? 2 : 3;"
FI: the condition should be evaluated and considered true on exit, but this is sometimes captured by a macro definition and the code below is then useless
pc | c |
pre | re |
ef | f |
Definition at line 480 of file ri_to_transformer_lists.c.
References any_assign_to_transformer(), any_basic_update_to_transformer(), any_update_to_transformer(), c_return_to_transformer(), CAR, CDR, condition_to_transformer(), conditional_to_transformer(), CONS, effects_to_transformer(), ENTITY_ABORT_SYSTEM_P, ENTITY_ASSERT_FAIL_SYSTEM_P, ENTITY_ASSERT_SYSTEM_P, ENTITY_ASSIGN_P, ENTITY_BITWISE_AND_UPDATE_P, ENTITY_BITWISE_OR_UPDATE_P, ENTITY_BITWISE_XOR_UPDATE_P, ENTITY_C_RETURN_P, ENTITY_COMMA_P, ENTITY_CONDITIONAL_P, ENTITY_DIVIDE_UPDATE_P, ENTITY_EXIT_SYSTEM_P, ENTITY_LEFT_SHIFT_UPDATE_P, ENTITY_MINUS_UPDATE_P, ENTITY_MODULO_UPDATE_P, ENTITY_MULTIPLY_UPDATE_P, ENTITY_PLUS_UPDATE_P, ENTITY_POST_DECREMENT_P, ENTITY_POST_INCREMENT_P, ENTITY_PRE_DECREMENT_P, ENTITY_PRE_INCREMENT_P, ENTITY_RIGHT_SHIFT_UPDATE_P, ENTITY_STOP_P, EXPRESSION, expressions_to_transformer(), NIL, pips_debug, pips_internal_error, TRANSFORMER, transformer_empty(), and transformer_undefined.
list safe_assigned_expression_to_transformer_list | ( | entity | v, |
expression | expr, | ||
transformer | pre | ||
) |
Always returns a fully defined transformer.
FI: The property to compute transformers in context is not taken into account to add information from pre within tf. pre is used to evaluate expr, but is not made part of tf.
expr | xpr |
pre | re |
Definition at line 610 of file ri_to_transformer_lists.c.
References assigned_expression_to_transformer(), entity_has_values_p(), expression_undefined_p, get_bool_property(), NIL, pips_assert, pips_internal_error, transformer_add_modified_variable_entity(), transformer_identity(), transformer_range(), transformer_undefined, transformer_undefined_p, and transformers_consistency_p().
list statement_to_transformer_list | ( | statement | s, |
transformer | spre | ||
) |
A transformer is already available for statement s, but it is going to be refined into a list of transformers to isolate at least the identity transformer from effective transformers.
stmt precondition
Transformation REFINE_TRANSFORMERS is being executed: add information available from the statement precondition
it would be nicer to control warning_on_redefinition
FI: an empty tl means that s does not return. An undefined tl means that instruction_to_transformer() is not implemented in a satisfactory way. So the existing transformer is used by default.
add array references information using proper effects
nt = transformer_normalize(nt, 0);
When we leave a block the local stack allocated variables disappear
Get rid of the dynamic and stack variables declared in this block statement. No stack variable should be analyzed as the stack area is used only for dependent types.
nt = transformer_normalize(nt, 7);
nt = transformer_normalize(nt, 4);
(void) print_transformer(load_statement_transformer(s));
The transformer returned for the statement is not always the transformer stored for the statement. This happens for loops and for context sensitive transformers for replicated statements in CFG/unstructured. See comments in loop.c
spre | pre |
Definition at line 978 of file ri_to_transformer_lists.c.
References all_statements_defined_p(), CONS, copy_transformer(), declaration_statement_p(), declarations_to_transformer(), dump_transformer, dynamic_variables_to_values(), ENDP, FOREACH, fprintf(), free_transformer(), gen_length(), get_bool_property(), get_int_property(), ifdebug, instruction_to_transformer_list(), list_undefined_p, load_cumulated_rw_effects_list(), load_statement_precondition(), load_statement_transformer(), NIL, ORDERING_NUMBER, ORDERING_STATEMENT, pips_assert, pips_debug, pips_internal_error, print_transformer, print_transformers(), refine_transformers_p, safe_transformer_projection(), semantics_user_warning, statement_block_p, statement_declarations, statement_instruction, statement_number, statement_ordering, store_statement_transformer(), TRANSFORMER, transformer_add_reference_information(), transformer_consistency_p(), transformer_consistent_p(), transformer_convex_hull(), transformer_domain_intersection(), transformer_free(), transformer_identity(), transformer_internal_consistency_p(), transformer_normalize(), transformer_range(), transformer_undefined, transformer_undefined_p, and update_statement_transformer().
Referenced by block_to_transformer_list(), test_to_transformer_list(), and whileloop_to_postcondition().
|
static |
effects of t
EXPRESSION_TO_TRANSFORMER() SHOULD BE USED MORE EFFECTIVELY
Clearly, this must be true for transformer list to be computed. However, if test_to_transformer_list() is more general than test_to_transformer(), the later should disappear and be merged here, with a convex hull to reduce the list
Ideally, they should be initialized with the current best precondition, intraprocedural if nothing else better is available. This function's profile as well as most function profiles in ri_to_transformers should be modifed.
True condition transformer, TCT
False condition transformer, FCT
tffwc = precondition_add_condition_information(tffwc, e, context, false);
Definition at line 380 of file ri_to_transformer_lists.c.
References condition_to_transformer(), CONS, effects_to_transformer(), free_arguments(), free_transformer(), ifdebug, merge_transformer_lists(), NIL, pips_debug, pips_flag_p, precondition_to_abstract_store(), print_transformer, print_transformers(), reset_temporary_value_counter(), SEMANTICS_FLOW_SENSITIVE, statement_to_transformer(), statement_to_transformer_list(), test_condition, test_false, test_true, TRANSFORMER, transformer_apply(), transformer_apply_map(), transformer_dup(), transformer_free(), transformer_identity(), transformer_temporary_value_projection(), and transformer_undefined_p.
Referenced by instruction_to_transformer_list().