PIPS
|
#include <stdlib.h>
#include <stdio.h>
#include "genC.h"
#include "linear.h"
#include "ri.h"
#include "ri-util.h"
#include "effects.h"
#include "effects-util.h"
#include "misc.h"
#include "properties.h"
#include "points-to.h"
Go to the source code of this file.
Variables | |
static stack | statement_points_to_context = stack_undefined |
The input points-to information of a statement is updated by the analysis of the statement because of the on-demand approach. More... | |
static stack | current_statement_points_to_context = stack_undefined |
void add_arc_to_statement_points_to_context | ( | points_to | pt | ) |
pt | t |
Definition at line 104 of file statement.c.
References add_arc_to_pt_map, consistent_pt_map_p, pips_assert, stack_head(), and statement_points_to_context.
Referenced by add_arc_to_points_to_context(), and dereferencing_subscript_to_points_to().
pt_map any_loop_to_points_to | ( | statement | b, |
expression | init, | ||
expression | c, | ||
expression | inc, | ||
pt_map | pt_in | ||
) |
Perform the same k-limiting scheme for all kinds of loops.
The do while loop must use an external special treatment for the first iteration.
Derived from points_to_forloop() and from Amira's work.
pt_in is modified by side effects.
First, enter or skip the loop: initialization + condition check
Comput pt_out as loop invariant: pt_out holds at the beginning of the loop body.
pt_out(i) = f(pt_out(i-1)) U pt_out(i-1)
prev = pt_out(i-1)
Note: the pt_out variable is also used to carry the loop exit points-to set.
prev receives the current points-to information, pt_out
Depending on the kind of loops, execute the body and then possibly the incrementation and the condition
Merge the previous resut and the current result.
Check convergence
Add the last iteration to obtain the pt_out holding when exiting the loop
FI: I suppose that p[i] is replaced by p[*] and that MAY/MUST information is changed accordingly.
init | nit |
inc | nc |
pt_in | t_in |
Definition at line 653 of file statement.c.
References assign_pt_map, clear_pt_map, condition_to_points_to(), consistent_points_to_graph_p(), expression_to_points_to(), expression_undefined_p, full_copy_pt_map(), get_int_property(), ifdebug, init, merge_points_to_graphs(), new_pt_map, normalize_points_to_graph(), pips_assert, pips_debug, pips_internal_error, points_to_graph_bottom, points_to_graph_set, points_to_independent_store(), print_points_to_set(), remove_unreachable_stub_vertices_in_points_to_graph(), set_equal_p(), statement_to_points_to(), and upgrade_approximations_in_points_to_set().
Referenced by forloop_to_points_to(), loop_to_points_to(), and whileloop_to_points_to().
See points_to_init()
pt_in is modified by side-effects and returned
generate points-to due to the initialisation
AM/FI: abnormal sharing (lhs); the reference may be reused in the cel...
free_expression(lhs);
The initialization expression may use pointers, directly or indirectly via struct and arrays.
Take care of expressions in array sizing (see array12.c)
pt_in | t_in |
Definition at line 262 of file statement.c.
References add_arc_to_pt_map, array_of_pointers_type_p(), array_of_struct_type_p(), array_pointer_type_equal_p(), array_type_p(), assignment_to_points_to(), CAR, CELL, cell_to_nowhere_sink(), char_star_type_p(), clear_pt_map, compute_basic_concrete_type(), DIMENSION, dimension_lower, dimension_upper, ENTITY, entity_basic_concrete_type(), entity_initial, entity_storage, entity_to_expression(), entity_user_name(), expression_to_points_to(), expression_to_type(), expression_undefined_p, FOREACH, free_expression(), integer_type_p(), make_approximation_exact(), make_descriptor_none(), make_null_cell(), make_points_to(), NIL, overloaded_type_p(), pips_debug, pips_user_warning, pointer_type_p(), points_to_context_statement_line_number(), points_to_graph_bottom, statement_declarations, storage_rom_p, string_type_p(), struct_type_p(), type_structurally_equal_p(), type_variable, type_void_star_p(), value_expression, value_expression_p, variable_dimensions, variable_initial_expression(), variable_static_p(), and variable_to_pointer_locations().
Referenced by statement_to_points_to().
void equalize_points_to_domains | ( | points_to_graph | pt_t, |
points_to_graph | pt_f | ||
) |
Make sure that pt_t and pt_f have the same definition domain except if one of them is bottom.
pt_t | t_t |
pt_f | t_f |
Definition at line 479 of file statement.c.
References expand_points_to_domain(), and points_to_graph_bottom.
Referenced by test_to_points_to().
|
static |
expand the domain of pt_f according to the domain of pt_t
Definition at line 450 of file statement.c.
References cell_any_reference(), entity_stub_sink_p(), formal_parameter_p(), pips_internal_error, pointer_assignment_to_points_to(), points_to_cell_equal_p(), points_to_graph_bottom, points_to_graph_set, points_to_source, reference_to_expression(), reference_variable, and SET_FOREACH.
Referenced by equalize_points_to_domains().
fl | l |
pt_in | t_in |
Definition at line 974 of file statement.c.
References any_loop_to_points_to(), forloop_body, forloop_condition, forloop_increment, forloop_initialization, and init.
Referenced by instruction_to_points_to().
in | n |
Definition at line 67 of file statement.c.
References copy_points_to(), new_pt_map, out, pips_assert, points_to_graph_bottom, points_to_graph_domain, points_to_graph_domain_number, points_to_graph_set, set_add_element(), and SET_FOREACH.
Referenced by any_loop_to_points_to(), boolean_intrinsic_call_condition_to_points_to(), init_points_to_context(), intrinsic_call_to_points_to(), new_any_loop_to_points_to(), new_points_to_unstructured(), statement_to_points_to(), ternary_intrinsic_call_to_points_to_sinks(), and test_to_points_to().
FI: short term attempt at providing a deep copy to avoid sharing between sets.
statement.c
If elements are shared, it quickly becomes impossible to deep free any set.
Definition at line 50 of file statement.c.
References copy_points_to(), new_simple_pt_map, out, set_add_element(), and SET_FOREACH.
void init_statement_points_to_context | ( | void | ) |
Definition at line 90 of file statement.c.
References current_statement_points_to_context, pips_assert, points_to_graph_domain, stack_make(), stack_undefined_p, statement_domain, and statement_points_to_context.
Referenced by generic_points_to_analysis().
pt_map instruction_to_points_to | ( | instruction | i, |
pt_map | pt_in | ||
) |
See points_to_statement()
pt_in is modified by side-effects and returned
pt_in | t_in |
Definition at line 370 of file statement.c.
References call_to_points_to(), expression_to_points_to(), forloop_to_points_to(), instruction_call, instruction_expression, instruction_forloop, instruction_loop, instruction_sequence, instruction_tag, instruction_test, instruction_unstructured, instruction_whileloop, is_instruction_call, is_instruction_expression, is_instruction_forloop, is_instruction_goto, is_instruction_loop, is_instruction_multitest, is_instruction_sequence, is_instruction_test, is_instruction_unstructured, is_instruction_whileloop, loop_to_points_to(), NIL, pips_internal_error, points_to_graph_bottom, sequence_to_points_to(), test_to_points_to(), unstructured_to_points_to(), and whileloop_to_points_to().
Referenced by statement_to_points_to().
pt_out | t_out |
Definition at line 912 of file statement.c.
References cell_any_reference(), cell_to_type(), copy_approximation(), free_type(), gen_length(), make_anywhere_cell(), make_descriptor_none(), make_points_to(), points_to_approximation, points_to_equal_p(), points_to_graph_set, points_to_sink, points_to_source, reference_indices, remove_arc_from_pt_map_, and SET_FOREACH.
FI: I assume that pointers and pointer arithmetic cannot appear in a do loop, "do p=q, r, 1" is possible with "p", "q" and "r" pointing towards the same array...
Let's hope the do loop conversion does not catch such cases.
loop range expressions may require some points-to information See for instance Pointers/Mensi.sub/array_init02.c
Side effects might have to be taken into account... But side effects should also prevent PIPS from transforming a for loop into a do loop.
pt_in | t_in |
Definition at line 573 of file statement.c.
References any_loop_to_points_to(), expression_to_points_to(), expression_undefined, init, loop_body, loop_range, range_increment, range_lower, and range_upper.
Referenced by instruction_to_points_to().
mt | t |
pt_in | t_in |
Definition at line 967 of file statement.c.
References pips_internal_error.
pt_map new_any_loop_to_points_to | ( | statement | b, |
expression | init, | ||
expression | c, | ||
expression | inc, | ||
pt_map | pt_in | ||
) |
Perform the same k-limiting scheme for all kinds of loops.
The do while loop must use an external special treatment for the first iteration.
Derived from the initial any_loop_to_points_to(): the iteration scheme is slighlty different but we end up with the same final iteration with all unioned states. Seems problematic at least in the presence of calls to free() because iter() is never normalized and always introduces new vertices and arcs in "pt_out". See list05.c.
pt_in is modified by side effects.
First, enter or skip the loop: initialization + condition check
Compute pt_out as loop invariant: pt_out holds at the beginning of the loop body.
pt_out(i) = pt_out(i-1) U pt_iter(i)
pt_iter(i) = f(pt_iter(i-1))
pt_prev == pt_iter(i-1), pt_out_prev == pt_out(i-1)
Note: the pt_out variable is also used to carry the loop exit points-to set.
prev receives the current points-to information, pt_iter
Depending on the kind of loop, execute the body and then possibly the incrementation and the condition
Merge the previous resut and the current result.
Check convergence
Add the last iteration to obtain the pt_out holding when exiting the loop
FI: I suppose that p[i] is replaced by p[*] and that MAY/MUST information is changed accordingly.
init | nit |
inc | nc |
pt_in | t_in |
Definition at line 792 of file statement.c.
References assign_pt_map, clear_pt_map, condition_to_points_to(), expression_to_points_to(), expression_undefined_p, full_copy_pt_map(), get_int_property(), init, merge_points_to_graphs(), new_pt_map, normalize_points_to_graph(), pips_debug, pips_internal_error, points_to_graph_bottom, points_to_graph_set, points_to_independent_store(), print_points_to_set(), set_equal_p(), and statement_to_points_to().
pt_map points_to_context_statement_in | ( | void | ) |
Definition at line 127 of file statement.c.
References stack_head(), and statement_points_to_context.
Referenced by user_call_to_points_to_interprocedural().
int points_to_context_statement_line_number | ( | void | ) |
Definition at line 120 of file statement.c.
References get_current_statement_from_statement_global_stack(), and statement_number.
Referenced by aliased_translation_p(), binary_intrinsic_call_to_points_to_sinks(), check_type_of_points_to_cells(), declaration_statement_to_points_to(), dereferencing_subscript_to_points_to(), equal_condition_to_points_to(), expression_to_points_to_cells(), filter_formal_context_according_to_actual_context(), freed_list_to_points_to(), freed_pointer_to_points_to(), internal_pointer_assignment_to_points_to(), intrinsic_call_to_points_to(), list_assignment_to_points_to(), memory_leak_to_more_memory_leaks(), new_filter_formal_context_according_to_actual_context(), non_equal_condition_to_points_to(), offset_cell(), offset_points_to_cell(), process_casted_sinks(), process_casted_sources(), reference_dereferencing_to_points_to(), reference_to_points_to_sinks(), source_to_sinks(), subscript_to_points_to_sinks(), subscripted_reference_to_points_to(), and user_call_to_points_to_interprocedural().
pt_map pop_statement_points_to_context | ( | void | ) |
Definition at line 133 of file statement.c.
References current_statement_points_to_context, stack_pop(), and statement_points_to_context.
Referenced by statement_to_points_to().
in | n |
Definition at line 98 of file statement.c.
References current_statement_points_to_context, stack_push(), and statement_points_to_context.
Referenced by statement_to_points_to().
void reset_statement_points_to_context | ( | void | ) |
Definition at line 139 of file statement.c.
References stack_free(), stack_undefined, and statement_points_to_context.
Referenced by generic_points_to_analysis().
seq | eq |
pt_in | t_in |
Definition at line 436 of file statement.c.
References FOREACH, sequence_statements, and statement_to_points_to().
Referenced by instruction_to_points_to().
bool statement_points_to_context_defined_p | ( | void | ) |
Definition at line 145 of file statement.c.
References stack_undefined, and statement_points_to_context.
Referenced by aliased_translation_p(), filter_formal_context_according_to_actual_context(), internal_pointer_assignment_to_points_to(), new_filter_formal_context_according_to_actual_context(), reference_dereferencing_to_points_to(), and reference_to_points_to_sinks().
See points_to_statement()
Process the declarations
Go down recursively, although it is currently useless since a declaration statement is a call to CONTINUE
Get the current version of pt_in, updated by the analysis of s.
Either pt_in or pt_out should be stored in the hash_table
But it might be smarter (or not) to require or not the storage.
Eliminate local information if you exit a block
The statement context is know unknown: it has been popped above. No precise error message in points_to_set_block_projection()
Because arc removals do not update the approximations of the remaining arcs, let's upgrade approximations before the information is passed. Useful for arithmetic02.
Really dangerous here: if pt_map "in" is empty, then pt_map "out" must be empty to...
FI: we have a problem to denote unreachable statement. To associate an empty set to them woud be a way to avoid problems when merging points-to along different control paths. But you might also wish to start with an empty set... And anyway, you can find declarations in dead code...
pt_in | t_in |
Definition at line 154 of file statement.c.
References bound_pt_to_list_p(), consistent_pt_map_p, declaration_statement_p(), declaration_statement_to_points_to(), entity_main_module_p(), fi_points_to_storage(), full_copy_pt_map(), gen_free_list(), gen_full_copy_list(), get_current_module_entity(), get_current_module_statement(), graph_assign_list(), init_heap_model(), instruction_to_points_to(), load_pt_to_list(), merge_points_to_graphs(), new_pt_map, pips_assert, points_to_graph_bottom, points_to_graph_set, points_to_list_list, points_to_set_block_projection(), pop_statement_global_stack(), pop_statement_points_to_context(), push_statement_on_statement_global_stack(), push_statement_points_to_context(), reset_heap_model(), statement_declarations, statement_instruction, statement_sequence_p(), and upgrade_approximations_in_points_to_set().
Referenced by any_loop_to_points_to(), control_to_points_to(), cyclic_graph_to_points_to(), generic_points_to_analysis(), new_any_loop_to_points_to(), new_points_to_unstructured(), sequence_to_points_to(), test_to_points_to(), and whileloop_to_points_to().
Computing the points-to information after a test.
All the relationships are of type MAY, even if the same arc is defined, e.g. "if(c) p = &i; else p=&i;".
Might be refined later by using preconditions.
Make sure the condition is exploited, either because of side effects or simply because of dereferencements.
This cannot be done here because of side-effects.
FI: because the conditions must be evaluated for true and false?
condition's side effect and information are taked into account, e.g.:
"if(p=q)" or "if(*p++)" or "if(p)" which implies p->NULL in the else branch. FI: to be checked with test cases
We must use a common definition domain for both relations in order to obatin a really consistent points-to relation after the merge. This is similar to what is done in semantics for scalar preconditions.
pt_in | t_in |
Definition at line 496 of file statement.c.
References condition_to_points_to(), equalize_points_to_domains(), expression_to_points_to(), free_pt_map, full_copy_pt_map(), merge_points_to_graphs(), pips_assert, points_to_graph_bottom, points_to_graph_consistent_p(), points_to_graph_set, pt_map_undefined, set_clear(), statement_to_points_to(), test_condition, test_false, and test_true.
Referenced by instruction_to_points_to().
pt_map unstructured_to_points_to | ( | unstructured | u, |
pt_map | pt_in | ||
) |
pt_in | t_in |
Definition at line 958 of file statement.c.
References new_points_to_unstructured().
Referenced by instruction_to_points_to().
void update_statement_points_to_context_with_arc | ( | points_to | pt | ) |
pt | t |
Definition at line 112 of file statement.c.
References consistent_pt_map_p, pips_assert, stack_head(), statement_points_to_context, and update_points_to_graph_with_arc().
Referenced by update_points_to_context_with_arc().
Execute the first iteration
wl | l |
pt_in | t_in |
Definition at line 604 of file statement.c.
References any_loop_to_points_to(), consistent_points_to_graph_p(), evaluation_before_p, expression_to_points_to(), expression_undefined, pips_assert, statement_to_points_to(), whileloop_body, whileloop_condition, and whileloop_evaluation.
Referenced by instruction_to_points_to().
|
static |
Definition at line 88 of file statement.c.
Referenced by init_statement_points_to_context(), pop_statement_points_to_context(), and push_statement_points_to_context().
|
static |
The input points-to information of a statement is updated by the analysis of the statement because of the on-demand approach.
The formal context with its stubs is built onloy when necessary.
Definition at line 87 of file statement.c.
Referenced by add_arc_to_statement_points_to_context(), init_statement_points_to_context(), points_to_context_statement_in(), pop_statement_points_to_context(), push_statement_points_to_context(), reset_statement_points_to_context(), statement_points_to_context_defined_p(), and update_statement_points_to_context_with_arc().