PIPS
|
#include <stdlib.h>
#include <stdio.h>
#include "genC.h"
#include "linear.h"
#include "ri.h"
#include "effects.h"
#include "ri-util.h"
#include "effects-util.h"
#include "misc.h"
#include "properties.h"
#include "text-util.h"
#include "prettyprint.h"
#include "points-to.h"
#include "semantics.h"
Go to the source code of this file.
Macros | |
#define | LESS_THAN 0 |
See if you can decide that the addresses linked to c1 are xxx than the addresses linked to c2. More... | |
#define | LESS_THAN_OR_EQUAL_TO 1 |
#define | GREATER_THAN 2 |
#define | GREATER_THAN_OR_EQUAL_TO 3 |
Functions | |
void | subscripted_reference_to_points_to (reference r, list sl, pt_map pt_in) |
FI: what is this function supposed to do? Just update "pt_in" to make sure that "r" can be dereferenced? And then recursively, with the different subscripts? More... | |
pt_map | expression_to_points_to (expression e, pt_map pt_in, bool side_effect_p) |
Update pt_in and pt_out according to expression e. More... | |
pt_map | expressions_to_points_to (list el, pt_map pt_in, bool side_effect_p) |
Compute the points-to information pt_out that results from the evaluation of a possibly empty list of expression. More... | |
pt_map | reference_to_points_to (reference r, pt_map pt_in, bool side_effect_p) |
The subscript expressions may impact the points-to information. More... | |
pt_map | range_to_points_to (range r, pt_map pt_in, bool side_effect_p) |
pt_map | call_to_points_to (call c, pt_map pt_in, list el, bool side_effect_p) |
Three different kinds of calls are distinguished: More... | |
pt_map | constant_call_to_points_to (call c __attribute__((unused)), pt_map pt_in) |
FI: this should not generate any points-to update. More... | |
pt_map | intrinsic_call_to_points_to (call c, pt_map pt_in, bool side_effect_p) |
pt_map | pointer_arithmetic_to_points_to (expression lhs, expression delta, pt_map pt_in) |
Update the sink locations associated to the source "lhs" under points-to information pt_map by "delta". More... | |
void | offset_array_reference (reference r, expression delta, type et) |
Side effect on reference "r". More... | |
void | offset_cells (cell source, list sinks, expression delta, type et, pt_map in) |
Each cell in sinks is replaced by a cell located "delta" elements further up in the memory. More... | |
points_to | offset_cell (points_to pt, expression delta, type et) |
Allocate and return a new points-to "npt", copy of "pt", with an offset of "delta" on the sink. More... | |
void | offset_points_to_cells (list sinks, expression delta, type t) |
Each cell in sinks is replaced by a cell located "delta" elements further up in the memory. More... | |
void | offset_points_to_cell (cell sink, expression delta, type t, bool unique_p __attribute__((__unused__))) |
FI: offset_cell() has been derived from this function. More... | |
pt_map | assignment_to_points_to (expression lhs, expression rhs, pt_map pt_in) |
void | check_type_of_points_to_cells (list sinks, type ct, bool eval_p) |
Check that all cells in list "sinks" are compatible with type "ct" if "eval_p" is false, and with the type pointed by "st" if eval_p is true. More... | |
void | check_rhs_value_types (expression lhs, expression rhs __attribute__((unused)), list sinks) |
Check that the cells in list "sinks" have types compatible with the expression on the left-hand side, lhs. More... | |
pt_map | internal_pointer_assignment_to_points_to (expression lhs, expression rhs, pt_map pt_in) |
Any abstract location of the lhs in L is going to point to any sink of any abstract location of the rhs in R. More... | |
pt_map | pointer_assignment_to_points_to (expression lhs, expression rhs, pt_map pt_in) |
list | freeable_points_to_cells (list R) |
Remove from points-to cell list R cells that certainly cannot be freed. More... | |
pt_map | freed_list_to_points_to (expression lhs, list L, list R, pt_map pt_in) |
Error detections on "L" and "R" have already been performed. More... | |
pt_map | freed_pointer_to_points_to (expression lhs, pt_map pt_in, bool side_effect_p) |
Any abstract location of the lhs in L is going to point to nowhere, maybe. More... | |
cell | reduce_cell_to_pointer_type (cell c) |
Remove last subscripts of cell c till its type becomes a scalar pointer. More... | |
list | reduce_cells_to_pointer_type (list cl) |
Undo the extra eval performed when stubs are generated: 0 subscripts are added when arrays are involved. More... | |
static list | generic_points_to_cell_to_useful_pointer_cells (cell c, set pts) |
Returns a list of cells of pointer type which are included in cell "c". More... | |
list | points_to_cell_to_pointer_cells (cell c) |
list | points_to_cell_to_useful_pointer_cells (cell c, set pts) |
list | points_to_cells_to_pointer_cells (list pl) |
Convert cells in l into derived pointer cells when possible. More... | |
pt_map | memory_leak_to_more_memory_leaks (cell l, pt_map in) |
Cell "l" has been memory leaked for sure and is not referenced any more in "in". More... | |
pt_map | list_assignment_to_points_to (list L, list R, pt_map pt_out) |
Update "pt_out" when any element of L can be assigned any element of R. More... | |
pt_map | struct_initialization_to_points_to (expression lhs, expression rhs, pt_map in) |
pt_map | struct_assignment_to_points_to (expression lhs, expression rhs, pt_map pt_in) |
pt_in is modified by side-effects and returned as pt_out More... | |
pt_map | application_to_points_to (application a, pt_map pt_in, bool side_effect_p) |
pt_map | condition_to_points_to (expression c, pt_map in, bool true_p) |
Update points-to set "in" according to the content of the expression using side effects. More... | |
pt_map | reference_condition_to_points_to (reference r, pt_map in, bool true_p) |
Handle conditions such as "if(p)". More... | |
pt_map | call_condition_to_points_to (call c, pt_map in, list el, bool true_p) |
Handle any condition that is a call such as "if(p!=q)", "if(*p)", "if(foo(p=q))"... More... | |
pt_map | intrinsic_call_condition_to_points_to (call c, pt_map in, bool true_p) |
We can break down the intrinsics according to their arity or according to their kinds... More... | |
pt_map | user_call_condition_to_points_to (call c, pt_map in, list el, bool true_p) |
pt_map | boolean_intrinsic_call_condition_to_points_to (call c, pt_map in, bool true_p) |
Deal with "!", "&&", "||" etc. More... | |
static bool | cell_is_xxx_p (cell c1, cell c2, int xxx) |
bool | cell_is_less_than_or_equal_to_p (cell c1, cell c2) |
See if you can decide that the addresses linked to c1 are smaller than the addresses linked to c2. More... | |
bool | cell_is_less_than_p (cell c1, cell c2) |
bool | cell_is_greater_than_or_equal_to_p (cell c1, cell c2) |
bool | cell_is_greater_than_p (cell c1, cell c2) |
pt_map | null_equal_condition_to_points_to (expression e, pt_map in) |
The condition is e==NULL. More... | |
pt_map | null_non_equal_condition_to_points_to (expression e, pt_map in) |
The condition is e!=NULL. More... | |
pt_map | equal_condition_to_points_to (list al, pt_map in) |
The expression list "al" contains exactly two arguments, "lhs" and "rhs". More... | |
pt_map | non_equal_condition_to_points_to (list al, pt_map in) |
The expression list "al" contains exactly two arguments. More... | |
pt_map | order_condition_to_points_to (entity f, list al, bool true_p, pt_map in) |
The expression list "al" contains exactly two arguments. More... | |
pt_map | relational_intrinsic_call_condition_to_points_to (call c, pt_map in, bool true_p) |
Update the points-to information "in" according to the validity of the condition. More... | |
#define GREATER_THAN 2 |
Definition at line 2739 of file expression.c.
#define GREATER_THAN_OR_EQUAL_TO 3 |
Definition at line 2740 of file expression.c.
#define LESS_THAN 0 |
See if you can decide that the addresses linked to c1 are xxx than the addresses linked to c2.
True is returned when a decision can be made.
False is returned when no decision can be made.
Definition at line 2737 of file expression.c.
#define LESS_THAN_OR_EQUAL_TO 1 |
Definition at line 2738 of file expression.c.
pt_map application_to_points_to | ( | application | a, |
pt_map | pt_in, | ||
bool | side_effect_p | ||
) |
FI: We should also identify the possibly called functions and update the points-to according to the possible call sites.
pt_in | t_in |
side_effect_p | ide_effect_p |
Definition at line 2490 of file expression.c.
References application_arguments, application_function, expression_to_points_to(), expressions_to_points_to(), f(), and pips_internal_error.
Referenced by expression_to_points_to().
pt_map assignment_to_points_to | ( | expression | lhs, |
expression | rhs, | ||
pt_map | pt_in | ||
) |
It is not obvious that you are allowed to evaluate this before the sink of lhs, but the standard probably forbid stupid side effects.
Can occur in a declaration
When more precision is needed, the BRACE_INTRINSIC arguments will have to be analyzed...
lhs | hs |
rhs | hs |
pt_in | t_in |
Definition at line 1163 of file expression.c.
References add_arc_to_pt_map_(), array_of_pointers_type_p(), array_of_struct_type_p(), basic_pointer, compute_basic_concrete_type(), copy_reference(), ENDP, expression_reference(), expression_reference_p(), free_type(), make_anywhere_points_to_cell(), make_approximation_may(), make_cell_reference(), make_descriptor_none(), make_points_to(), pips_assert, pips_internal_error, pointer_assignment_to_points_to(), pointer_type_p(), points_to_cell_add_unbounded_subscripts(), points_to_expression_to_type(), reference_indices, struct_assignment_to_points_to(), struct_type_p(), type_variable, and variable_basic.
Referenced by compute_points_to_binded_set(), declaration_statement_to_points_to(), intrinsic_call_to_points_to(), struct_assignment_to_points_to(), and struct_initialization_to_points_to().
Deal with "!", "&&", "||" etc.
Combine the conditions
Merge the results of the different conditions...
in | n |
true_p | rue_p |
Definition at line 2695 of file expression.c.
References call_arguments, call_function, CAR, CDR, clear_pt_map, condition_to_points_to(), ENTITY_AND_P, entity_local_name(), ENTITY_NOT_P, ENTITY_OR_P, EXPRESSION, f(), free_pt_map, full_copy_pt_map(), merge_points_to_graphs(), out, out2, pips_assert, pips_internal_error, and points_to_graph_consistent_p().
Referenced by intrinsic_call_condition_to_points_to().
Handle any condition that is a call such as "if(p!=q)", "if(*p)", "if(foo(p=q))"...
in | n |
el | l |
true_p | rue_p |
Definition at line 2595 of file expression.c.
References call_function, entity_initial, f(), intrinsic_call_condition_to_points_to(), out, pips_assert, pips_internal_error, points_to_graph_consistent_p(), user_call_condition_to_points_to(), value_code_p, value_constant_p, and value_intrinsic_p.
Referenced by condition_to_points_to().
Three different kinds of calls are distinguished:
"el" is the effect list associated to the call site
points-to updates due to arguments
Must be a pointer to a function
I do not know if nft must be freed later
points-to updates due to arguments
pt_in | t_in |
el | l |
side_effect_p | ide_effect_p |
Definition at line 306 of file expression.c.
References call_arguments, call_function, CAR, ENTITY_CONDITIONAL_P, entity_initial, entity_name, entity_type, EXPRESSION, expression_to_points_to(), expressions_to_points_to(), f(), functional_result, intrinsic_call_to_points_to(), is_value_code, is_value_constant, is_value_expression, is_value_intrinsic, is_value_symbolic, is_value_unknown, pips_assert, pips_internal_error, pointer_type_p(), points_to_graph_bottom, points_to_graph_consistent_p(), points_to_graph_undefined_p, symbolic_expression, type_functional, type_functional_p, type_to_pointed_type(), type_undefined, type_variable_p, type_void_p, user_call_to_points_to(), value_code_p, value_expression, value_symbolic, and value_tag.
Referenced by dereferencing_to_points_to(), expression_to_points_to(), and instruction_to_points_to().
c1 | 1 |
c2 | 2 |
Definition at line 2830 of file expression.c.
References cell_is_xxx_p(), and GREATER_THAN_OR_EQUAL_TO.
Referenced by order_condition_to_points_to().
c1 | 1 |
c2 | 2 |
Definition at line 2835 of file expression.c.
References cell_is_xxx_p(), and GREATER_THAN.
Referenced by order_condition_to_points_to().
See if you can decide that the addresses linked to c1 are smaller than the addresses linked to c2.
True is returned when a decision can be made.
False is returned when no decision can be made.
c1 | 1 |
c2 | 2 |
Definition at line 2820 of file expression.c.
References cell_is_xxx_p(), and LESS_THAN_OR_EQUAL_TO.
Referenced by order_condition_to_points_to().
c1 | 1 |
c2 | 2 |
Definition at line 2825 of file expression.c.
References cell_is_xxx_p(), and LESS_THAN.
Referenced by order_condition_to_points_to().
You must compare the subscript expressions lexicographically
Definition at line 2742 of file expression.c.
References CAR, CDR, cell_any_reference(), constant_int, constant_int_p, ENDP, EvalExpression(), EXPRESSION, GREATER_THAN, GREATER_THAN_OR_EQUAL_TO, LESS_THAN, LESS_THAN_OR_EQUAL_TO, pips_internal_error, pips_user_error, reference_indices, reference_to_string(), reference_variable, s1, unbounded_expression_p(), value_constant, and value_constant_p.
Referenced by cell_is_greater_than_or_equal_to_p(), cell_is_greater_than_p(), cell_is_less_than_or_equal_to_p(), and cell_is_less_than_p().
void check_rhs_value_types | ( | expression | lhs, |
expression rhs | __attribute__(unused), | ||
list | sinks | ||
) |
Check that the cells in list "sinks" have types compatible with the expression on the left-hand side, lhs.
List "sinks" is assumed to have been derived from the "rhs" expression.
At least for the NULL pointer...
Definition at line 1277 of file expression.c.
References array_type_p(), array_type_to_element_type(), check_type_of_points_to_cells(), compute_basic_concrete_type(), free_type(), pips_internal_error, pointer_type_p(), points_to_expression_to_type(), scalar_integer_type_p(), type_to_pointed_type(), type_undefined, and type_void_star_p().
Referenced by internal_pointer_assignment_to_points_to().
Check that all cells in list "sinks" are compatible with type "ct" if "eval_p" is false, and with the type pointed by "st" if eval_p is true.
Adding the zero subscripts may muddle the type issue because "&a[0]" has not the same type as "a" although we normalize every cell into "a[0]".
Take care of the constant strings like "hello"
Take care of void
sinks | inks |
ct | t |
eval_p | val_p |
Definition at line 1214 of file expression.c.
References anywhere_cell_p(), array_pointer_type_equal_p(), array_type_p(), array_type_to_sub_array_type(), CELL, cell_any_reference(), cell_typed_anywhere_locations_p(), char_star_constant_function_type_p(), char_type_p(), compute_basic_concrete_type(), copy_type(), effect_reference_to_string(), ENDP, FOREACH, nowhere_cell_p(), null_cell_p(), overloaded_type_p(), pips_internal_error, pips_user_error, pips_user_warning, pointer_type_p(), points_to_cell_to_type(), points_to_context_statement_line_number(), string_of_type(), type_structurally_equal_p(), type_to_pointed_type(), type_undefined, and type_void_p.
Referenced by check_rhs_value_types(), reference_to_points_to_sinks(), and subscript_to_points_to_sinks().
pt_map condition_to_points_to | ( | expression | c, |
pt_map | in, | ||
bool | true_p | ||
) |
Update points-to set "in" according to the content of the expression using side effects.
Use "true_p" to know if the condition must be met or not.
FI: the side effects should not be taken into account because this function is often called twice, once for the true branch and once for the false branch of a test.
For instance, C short cut "if(p)" for "if(p!=NULL)"
in | n |
true_p | rue_p |
Definition at line 2512 of file expression.c.
References call_condition_to_points_to(), expression_syntax, NIL, out, pips_assert, pips_internal_error, points_to_graph_bottom, points_to_graph_consistent_p(), reference_condition_to_points_to(), syntax_call, syntax_call_p, syntax_reference, and syntax_reference_p.
Referenced by any_loop_to_points_to(), boolean_intrinsic_call_condition_to_points_to(), intrinsic_call_condition_to_points_to(), intrinsic_call_to_points_to(), new_any_loop_to_points_to(), ternary_intrinsic_call_to_points_to_sinks(), and test_to_points_to().
FI: this should not generate any points-to update.
it would be better not to go down here
Definition at line 404 of file expression.c.
The expression list "al" contains exactly two arguments, "lhs" and "rhs".
Check if "lhs==rhs" may return true.
If these expressions are pointers, "in" is modified by removing arcs that are not compatible with the equality. If no arc is left, a bottom "out" is returned.
If one of these two expressions cannot be evaluated according to the C standard, i.e. its value is undefined, a bottom graph is returned.
"out" is "in", modified by side-effects.
This function has many commonalities with non_equal_condition_to_points_to(). They were developped independently to avoid mistakes when dealing with negations of quantifiers. They could now be unified.
Is it impossible to evaluate lhs?
The check is too low. The message will be emitted twice because conditions are often evaluated as true and false.
Is it impossible to evaluate rhs?
Is the condition feasible?
al | l |
in | n |
Definition at line 2986 of file expression.c.
References add_arc_to_pt_map, atomic_points_to_cell_p(), CAR, CDR, CELL, cell_undefined, cell_undefined_p, clear_pt_map, copy_cell(), EXPRESSION, expression_null_p(), expression_to_points_to_sinks(), expression_to_points_to_sources(), expression_to_string(), expression_to_type(), FOREACH, free_type(), gen_length(), int, list_undefined, make_approximation_exact(), make_descriptor_none(), make_points_to(), nowhere_cell_p(), null_equal_condition_to_points_to(), out, pips_user_warning, pointer_type_p(), points_to_cell_source_projection(), points_to_cells_intersect_p(), points_to_context_statement_line_number(), and points_to_graph_bottom.
Referenced by relational_intrinsic_call_condition_to_points_to().
pt_map expression_to_points_to | ( | expression | e, |
pt_map | pt_in, | ||
bool | side_effect_p | ||
) |
Update pt_in and pt_out according to expression e.
Ignore side effects due to pointer arithmetic and assignment and function calls if side_effet_p is not set. This may be useful when conditions are evaluated twice, once for true and once for false.
Some idea, but points-to information should rather be used
list el = expression_to_proper_constant_path_effects(e);
Also, this would be computed before we know if it is useful because we need an expression and not a call to have a function to compute effects. And we do not know if we want an inter or an intraprocedural points-to analysis.
The alternative is too always compute points-to information interprocedurally, which makes sense as it is done for for memory effects and since points-to information is at a lower level than memory effects...
a cannot evaluate to null or undefined
FI: we may need a special case for stubs...
pt_in | t_in |
side_effect_p | ide_effect_p |
Definition at line 115 of file expression.c.
References application_to_points_to(), array_of_pointers_type_p(), call_to_points_to(), CAR, cast_expression, dereferencing_to_points_to(), ENDP, entity_basic_concrete_type(), expression_syntax, expressions_to_points_to(), gen_full_free_list(), gen_length(), int, is_syntax_application, is_syntax_call, is_syntax_cast, is_syntax_range, is_syntax_reference, is_syntax_sizeofexpression, is_syntax_subscript, is_syntax_va_arg, make_reference(), NIL, pips_assert, pips_internal_error, pointer_type_p(), points_to_graph_bottom, points_to_graph_consistent_p(), points_to_graph_undefined_p, range_to_points_to(), reference_indices, reference_to_points_to(), reference_variable, SIZEOFEXPRESSION, sizeofexpression_expression, sizeofexpression_type_p, subscript_array, subscript_indices, subscripted_reference_to_points_to(), syntax_application, syntax_call, syntax_cast, syntax_range, syntax_reference, syntax_sizeofexpression, syntax_subscript, syntax_tag, syntax_va_arg, and type_depth().
Referenced by any_loop_to_points_to(), application_to_points_to(), call_to_points_to(), declaration_statement_to_points_to(), dereferencing_subscript_to_points_to(), expressions_to_points_to(), freed_pointer_to_points_to(), instruction_to_points_to(), intrinsic_call_to_points_to(), loop_to_points_to(), new_any_loop_to_points_to(), pointer_reference_dereferencing_to_points_to(), range_to_points_to(), test_to_points_to(), and whileloop_to_points_to().
Compute the points-to information pt_out that results from the evaluation of a possibly empty list of expression.
A new data structure is allocated.
Ignore side-effects unless side_effect_p is set to true.
The result is correct only if you are sure that all expressions in "el" are always evaluated.
el | l |
pt_in | t_in |
side_effect_p | ide_effect_p |
Definition at line 243 of file expression.c.
References EXPRESSION, expression_to_points_to(), FOREACH, and points_to_graph_bottom.
Referenced by application_to_points_to(), call_to_points_to(), dereferencing_subscript_to_points_to(), dereferencing_to_points_to(), expression_to_points_to(), reference_condition_to_points_to(), and reference_to_points_to().
Remove from points-to cell list R cells that certainly cannot be freed.
if c is a heap location with indices other than zero then we have bumped into a non-legal free
Definition at line 1457 of file expression.c.
References CAR, CELL, cell_any_reference(), cell_typed_anywhere_locations_p(), CONS, ENDP, EXPRESSION, expression_null_p(), FOREACH, gen_free_list(), gen_list_and_not(), heap_cell_p(), NIL, reference_indices, and stub_points_to_cell_p().
Referenced by freed_pointer_to_points_to().
pt_map freed_list_to_points_to | ( | expression | lhs, |
list | L, | ||
list | R, | ||
pt_map | pt_in | ||
) |
Error detections on "L" and "R" have already been performed.
R only contains heap locations or stub locations, i.e. potential heap locations. Neither L nor R are empty. "lhs" is provided for other error messages.
First level memory leaks
Build a nowhere cell - Should we check a property to type it or not?
Remove Kill_1 if it is not empty by definition
Memory leak detection... Must be computed early, before pt_out has been (too?) modified. Transitive closure not performed... If one cell has been freed and if it has become unreachable, then arcs starting from it have become useless and other cells that were pointed by it may also have become unreachable.
Add Gen_2, which is not conditionned by gen_length(R) or atomicity.
Compute and add Gen_2
Do not notify the user that the source of the new nowhere points to relation is a dangling pointer because it is only a may information. Exact alias information or a more precise heap model would be necessary to have exact information about dangling pointers.
Remove Kill_2 if it is not empty by definition... which it is if heap(r) is true, but not if stub(r). Has to be done after Gen_2, or modification of pt_out should be delayed, which would avoid the internal modification of pt_out_s and make the code easier to understand...
Remove Kill_3 if it is not empty by definition: with the current heap model, it is always empty. Unreachable cells are dealt somewhere else. They can be tested with points_to_sink_to_sources().
FI: Must be placed after gen_1 in case the assignment makes the cell reachable? Nonsense?
Add Gen_1 - Not too late since pt_out has aready been modified?
Add Gen_2: useless, already performed by Kill_2
More memory leaks?
Clean up the resulting graph
lhs | hs |
pt_in | t_in |
Definition at line 1489 of file expression.c.
References add_arc_to_pt_map, anywhere_cell_p(), array_of_pointers_type_p(), array_of_struct_type_p(), atomic_points_to_cell_p(), CAR, CELL, cell_any_reference(), compute_basic_concrete_type(), CONS, copy_approximation(), copy_cell(), ENDP, entity_name, entity_user_name(), FOREACH, gen_free_list(), gen_length(), generic_atomic_points_to_cell_p(), heap_cell_p(), list_assignment_to_points_to(), make_descriptor_none(), make_points_to(), make_typed_nowhere_cell(), memory_leak_to_more_memory_leaks(), NIL, nowhere_cell_p(), null_cell_p(), pips_assert, pips_user_warning, pointer_type_p(), points_to_approximation, points_to_cell_equal_p(), points_to_cell_in_list_p(), points_to_cell_to_concrete_type(), points_to_context_statement_line_number(), points_to_expression_to_concrete_type(), points_to_graph_set, points_to_sink, points_to_sink_to_sources(), points_to_source, reference_variable, related_points_to_cell_in_list_p(), remove_arc_from_pt_map, SET_FOREACH, struct_type_p(), stub_points_to_cell_p(), type_to_pointed_type(), unreachable_points_to_cell_p(), and variable_to_sinks().
Referenced by freed_pointer_to_points_to().
pt_map freed_pointer_to_points_to | ( | expression | lhs, |
pt_map | pt_in, | ||
bool | side_effect_p | ||
) |
Any abstract location of the lhs in L is going to point to nowhere, maybe.
Any source in pt_in pointing towards any location in lhs may or Must now points towards nowhere (malloc07).
New points-to information must be added when a formal parameter is dereferenced.
Equations for "free(e);":
Let L = expression_to_sources(e,in)
and R_1 = (expression_to_sinks(e,in) ^ (HEAP U STUBS)) - {undefined}
where ^ denotes the set intersection.
If R_1 is empty, an execution error must occur.
If R_1={NULL}, nothing happens. Let R=R_1-{NULL}.
Any location "l" corresponding to "e" can now point to nowhere/undefined:
Gen_1 = {pts=(l,nowhere,a) | l in L}
Any location source that pointed to a location r in the heap, pointed to by some l by definition, can now point to nowhere/undefined also:
Gen_2 = {pts=(source,nowhere,a) | exists r in R && r in Heap or Stubs && exists pts'=(source,r,a') in in}
If e corresponds to a unique (non-abstract?) location l, any arc starting from l can be removed:
Kill_1 = {pts=(l,r,a) in in | l in L && |L|=1 && atomic(l)}
If the freed location r is precisely known, any arc pointing towards it can be removed:
Kill_2 = {pts=(l,r,a) in in | r in R && |R|=1 && atomic(r)}
If the freed location r is precisely known or if it can no longer be reached, any arc pointing from it can be removed:
Kill_3 = {pts=(r,d,a) in in | r in R && |R|=1 && (atomic(r) v unreachable_p(r, in)}
Then the set PML = { d | heap(d) ^ (r,d,a) in Kill_3} becomes a set of potential meory leaks. They are leaked if they become unreachable in the new points-to relation out (see below) and they generate recursively new potential memory leaks and an updated points-to relation.
Since our current heap model only use abstract locations and since we do not keep any alias information, the predicate atomic should always return false and the sets Kill_2 and Kill_3 should always be empty, except if a stub is freed: locally the stub is atomic.
So, after the execution of "free(e);", the points-to relation is:
out = (in - Kill_1 - Kill_2 - Kill_3) U Gen_1 U Gen_2
Warnings for potential dangling pointers:
DP = {r|exists pts=(r,l,a) in Gen_2} // To be checked
No warning is issued as those are only potential.
Memory leaks: the freed bucket may be the only bucket containing pointers towards another bucket:
PML = {source_to_sinks(r)|r in R} ML = {m|m in PML && heap_cell_p(m) && !reachable(m, out)}
Note: for DP and ML, we could compute may and must/exact sets. We only compute must/exact sets to avoid swamping the log file with false alarms.
FI->FC: it might be better to split the problem according to |R|. If |R|=1, you know which bucket is destroyed, unless it is an abstract bucket... which we do not really know even at the intraprocedural level. In that case, you could remove all edges starting from r and then substitute r by nowhere/undefined.
If |R| is greater than 1, then a new node nowhere/undefined must be added and any arc ending up in R must be duplicated with a similar arc ending up in the new node.
The cardinal of |L| does not seem to have an impact: it does, see Kill_1
Remove cells from R_1 that do not belong to Heap: they cannot be freed
A execution error is certain
Free(NULL) has no effect
Remove from R locations that cannot be freed
We have bumped into a non-legal free such as free(p[10]). See test case malloc10.c
lhs | hs |
pt_in | t_in |
side_effect_p | ide_effect_p |
Definition at line 1741 of file expression.c.
References anywhere_cell_p(), CAR, CELL, cell_typed_anywhere_locations_p(), clear_pt_map, CONS, ENDP, expression_to_points_to(), expression_to_points_to_sinks(), expression_to_points_to_sources(), expression_to_string(), FOREACH, freeable_points_to_cells(), freed_list_to_points_to(), gen_free_list(), gen_full_free_list(), gen_length(), heap_cell_p(), NIL, null_cell_p(), pips_assert, pips_user_warning, points_to_context_statement_line_number(), points_to_graph_bottom, and stub_points_to_cell_p().
Referenced by intrinsic_call_to_points_to().
Returns a list of cells of pointer type which are included in cell "c".
Useful when "c" is a struct or an array of structs or pointers. Returns a list with cell "c" if it denotes a pointer.
If set "pt" is defined, make sure that each cell in the returned list, "pcl" appears in "pt".
Look for pointer and struct and array of pointers or struct fields
transformer
Definition at line 1862 of file expression.c.
References array_of_pointers_type_p(), array_of_struct_type_p(), CELL, cell_in_points_to_set_p(), CONS, copy_cell(), ENTITY, entity_basic_concrete_type(), f(), FOREACH, gen_nconc(), NIL, pointer_type_p(), points_to_cell_add_field_dimension(), points_to_cell_add_unbounded_subscripts(), points_to_cell_to_concrete_type(), struct_type_p(), and struct_type_to_fields().
Referenced by points_to_cell_to_pointer_cells(), and points_to_cell_to_useful_pointer_cells().
pt_map internal_pointer_assignment_to_points_to | ( | expression | lhs, |
expression | rhs, | ||
pt_map | pt_in | ||
) |
Any abstract location of the lhs in L is going to point to any sink of any abstract location of the rhs in R.
New points-to information must be added when a formal parameter is dereferenced.
Store independence must be checked.
Beware of points-to cell lattice: e.g. add a[*] to a[1]
This is not the right place to take the lattice into account. As a result, a[1] woud not kill a[1] anymore. The problem must be taken care of by the equations used in list_assignment_to_points_to().
Make sure all cells in L are pointers: l may be an array of pointers
FI: I am not sure it is useful here because the conversion to an array due to property POINTS_TO_STRICT_POINTER_TYPES may not have occured yet
Retrieve the memory locations that might be reached by the rhs
Update the real "pt_in", the calling context, and "pt_out" by adding new stubs linked directly or indirectly to the formal parameters and global variables if necessary.
We must be in a dead-code portion. If not pleased, adjust properties...
The C99 standard does not preclude the propagation of indeterminate values. It is often used in our test cases when structs are assigned.
clear_pt_map(pt_out); points_to_graph_bottom(pt_out) = true;
lhs | hs |
rhs | hs |
pt_in | t_in |
Definition at line 1315 of file expression.c.
References array_type_p(), CAR, CELL, check_rhs_value_types(), clear_pt_map, CONS, consistent_points_to_graph_p(), copy_cell(), ENDP, expression_to_points_to_sinks(), expression_to_points_to_sources(), expression_to_string(), FOREACH, free_type(), gen_free_list(), gen_length(), int, list_assignment_to_points_to(), NIL, nowhere_cell_p(), pips_assert, pips_user_warning, points_to_cell_add_unbounded_subscripts(), points_to_cell_add_zero_subscripts(), points_to_cell_to_type(), points_to_context_statement_line_number(), points_to_graph_bottom, source_to_sinks(), and statement_points_to_context_defined_p().
Referenced by pointer_assignment_to_points_to().
We can break down the intrinsics according to their arity or according to their kinds...
or according to both conditions...
Make sure that all dereferencements are possible? Might be included in intrinsic_call_to_points_to()...
in | n |
true_p | rue_p |
Definition at line 2618 of file expression.c.
References boolean_intrinsic_call_condition_to_points_to(), call_arguments, call_function, CAR, CDR, cells_may_not_point_to_null_p(), cells_must_point_to_null_p(), clear_pt_map, condition_to_points_to(), dereferencing_to_points_to(), ENTITY_ASSIGN_P, ENTITY_DEREFERENCING_P, ENTITY_LOGICAL_OPERATOR_P, ENTITY_POINT_TO_P, ENTITY_POST_DECREMENT_P, ENTITY_POST_INCREMENT_P, ENTITY_PRE_DECREMENT_P, ENTITY_PRE_INCREMENT_P, ENTITY_RELATIONAL_OPERATOR_P, EXPRESSION, expression_to_points_to_sinks(), f(), gen_free_list(), intrinsic_call_to_points_to(), out, pips_assert, pips_user_warning, pointer_type_p(), points_to_expression_to_concrete_type(), points_to_graph_bottom, points_to_graph_consistent_p(), and relational_intrinsic_call_condition_to_points_to().
Referenced by call_condition_to_points_to().
Is the dereferenced pointer null or undefined?
Is the dereferenced pointer null or undefined?
|| ENTITY_ASSERT_FAIL_SYSTEM_P(f)
Check the FILE * parameter, when it exists, and the char * format parameter, as well as the char * other actual arguments since they may be dereferenced or not, depending on the format content. With a p, the pointer is not referenced, with a s, it is.
attempt at using an undefined value
Expression a may be dereferenced or not depending on the corresponding format specification, s or p.
We could try to analyze the format when it is available to decide if a dereferencing must occur with s or not.
possible attempt at using an undefined value
it is assumed that only one return is present in any module code because internal returns are replaced by gotos
pt_in | t_in |
side_effect_p | ide_effect_p |
Definition at line 411 of file expression.c.
References assignment_to_points_to(), C_pointer_type_p(), call_arguments, call_function, CAR, CDR, CELL, char_star_type_p(), clear_pt_map, condition_to_points_to(), CONS, copy_expression(), copy_points_to_graph(), DEREFERENCING_OPERATOR_NAME, dereferencing_to_points_to(), ENDP, ENTITY_ABORT_SYSTEM_P, ENTITY_ASSERT_FAIL_SYSTEM_P, ENTITY_ASSIGN_P, ENTITY_C_RETURN_P, ENTITY_CLEARERR_P, ENTITY_CONDITIONAL_P, ENTITY_DEREFERENCING_P, ENTITY_EXIT_SYSTEM_P, ENTITY_FCLOSE_P, ENTITY_FDOPEN_P, ENTITY_FEOF_P, ENTITY_FERROR_P, ENTITY_FILENO_P, ENTITY_FOPEN_P, ENTITY_FPRINTF_P, ENTITY_FREAD_P, ENTITY_FREE_SYSTEM_P, ENTITY_FREOPEN_P, ENTITY_FSCANF_P, ENTITY_FWRITE_P, ENTITY_ISOC99_FSCANF_P, ENTITY_ISOC99_SCANF_P, ENTITY_ISOC99_SSCANF_P, ENTITY_MINUS_C_P, ENTITY_MINUS_UPDATE_P, entity_name, ENTITY_PLUS_C_P, ENTITY_PLUS_UPDATE_P, ENTITY_POINT_TO_P, ENTITY_POST_DECREMENT_P, ENTITY_POST_INCREMENT_P, ENTITY_PRE_DECREMENT_P, ENTITY_PRE_INCREMENT_P, ENTITY_PRINTF_P, ENTITY_SCANF_P, ENTITY_SPRINTF_P, ENTITY_SSCANF_P, ENTITY_STOP_P, ENTITY_STRCAT_SYSTEM_P, ENTITY_STRCMP_SYSTEM_P, ENTITY_STRNCAT_SYSTEM_P, ENTITY_STRNCMP_SYSTEM_P, entity_to_expression(), entity_user_name(), EXPRESSION, expression_reference_p(), expression_to_points_to(), expression_to_points_to_sinks(), expression_to_points_to_sources(), expression_to_string(), expression_to_type(), f(), FindOrCreateTopLevelEntity(), FOREACH, free_expression(), free_pt_map, free_type(), freed_pointer_to_points_to(), full_copy_pt_map(), function_to_return_value(), gen_free_list(), gen_length(), get_current_module_entity(), int_to_expression(), list_assignment_to_points_to(), make_nowhere_cell(), MakeUnaryCall(), merge_points_to_graphs(), NIL, nowhere_cell_p(), pips_assert, pips_debug, pips_user_error, pips_user_warning, pointer_arithmetic_to_points_to(), pointer_type_p(), points_to_context_statement_line_number(), points_to_expression_to_concrete_type(), points_to_graph_bottom, points_to_graph_consistent_p(), points_to_graph_set, points_to_graph_undefined_p, pt_map_undefined, set_clear(), struct_type_p(), type_to_full_string_definition(), unary_intrinsic_expression, and UNARY_MINUS_OPERATOR_NAME.
Referenced by call_to_points_to(), and intrinsic_call_condition_to_points_to().
Update "pt_out" when any element of L can be assigned any element of R.
FI->AM: Potential and sure memory leaks are not (yet) detected.
FI->AM: the distinction between may and must sets used in the implementation seem useless.
Old description by Amira:
KILL_MAY = kill_may_set() KILL_MUST= kill_must_set()
GEN_MAY = gen_may_set() GEN_MUST= gen_must_set()
KILL = KILL_MAY U KILL_MUST GEN = GEN_MAY U GEN_MUST PT_OUT = (PT_OUT - KILL) U GEN
This function is used to model a C pointer assignment "e1 = e2;"
Let L = expression_to_sources(e1) and R = expression_to_sinks(e2).
Let "in" be the points-to relation before executing the assignment.
Gen(L,R) = {pts| exist l in L exists r in R s.t. pts=(l,r,|L|=1)
Kill(L,in) = {pts=(l,sink,must)| l in L}
Let K=Kill(L,in) and out = (in-K) U gen(L,R)
For memory leaks, let
ML(K,out) = {c in Heap | exists pts=(l,c,a) in K && !(exists pts'=(l',c,a') in out)}
For error dereferencing, such as nowhere/undefined and NULL, check the content of L.
This function is described in Amira Mensi's dissertation.
Test cases designed to check the behavior of this function: ?!?
Check possible dereferencing errors
For arrays, an extra eval has been applied by adding 0 subscripts
What do we want to do when the left hand side is NULL or UNDEFINED?
The code cannot be executed
Compute the data-flow equation for the may and the must edges...
out = (in - kill) U gen ?
Extract MAY/MUST points to relations from the input set "pt_out"
Check kill_must for potential memory leaks
FI: this error message may be wrong in case of a call to realloc(); see Pointers/hyantes02.c, hyantes03.c
FI: this error message may deal with a bucket that does not really exist because its allocation was conditional.
To make things worse, the warning is emitted in an iterative loop analysis.
Look for a chain of memory leaks. Since they are also "related" to "d", this must be done before the next step.
Look for related lost arcs. See Pointers/malloc18.c
en_must,
kill,
pt_out | t_out |
Definition at line 2029 of file expression.c.
References add_arc_to_pt_map, approximation_exact_p, C_pointer_type_p(), CAR, CELL, cell_any_reference(), clear_pt_map, CONS, consistent_points_to_graph_p(), consistent_points_to_set(), copy_cell(), copy_descriptor(), effect_reference_to_string(), ENDP, entity_type, FOREACH, fprintf(), free_cell(), gen(), gen_free_list(), gen_length(), gen_list_and_not(), gen_may_set(), generic_atomic_points_to_cell_p(), get_bool_property(), heap_cell_p(), kill_may_set(), kill_must_set(), make_anywhere_points_to_cell(), make_approximation_may(), make_points_to(), memory_leak_to_more_memory_leaks(), new_simple_pt_map, NIL, nowhere_cell_p(), null_cell_p(), overloaded_type_p(), pips_assert, pips_internal_error, pips_user_warning, POINTS_TO, points_to_anywhere(), points_to_anywhere_typed(), points_to_approximation, points_to_cell_to_concrete_type(), points_to_cell_to_string(), points_to_context_statement_line_number(), points_to_descriptor, points_to_graph_bottom, points_to_graph_set, points_to_may_filter(), points_to_must_filter(), points_to_sink, points_to_source, print_points_to_cell, reduce_cell_to_pointer_type(), reference_variable, remove_arc_from_pt_map, set_assign(), set_difference(), set_empty_p(), SET_FOREACH, set_size(), set_union(), sets_free(), and unreachable_points_to_cell_p().
Referenced by freed_list_to_points_to(), internal_pointer_assignment_to_points_to(), and intrinsic_call_to_points_to().
Cell "l" has been memory leaked for sure and is not referenced any more in "in".
Its successors may be leaked too.
Remove useless unreachable arcs
Look for a chain of memory leaks
in | n |
Definition at line 1929 of file expression.c.
References CELL, CONS, FOREACH, gen_free_list(), heap_cell_p(), NIL, out, pips_user_warning, POINTS_TO, points_to_cell_equal_p(), points_to_cell_to_pointer_cells(), points_to_cell_to_string(), points_to_context_statement_line_number(), points_to_graph_set, points_to_sink, points_to_source, remove_arc_from_pt_map, SET_FOREACH, and unreachable_points_to_cell_p().
Referenced by freed_list_to_points_to(), list_assignment_to_points_to(), and points_to_set_block_projection().
The expression list "al" contains exactly two arguments.
If these expressions are pointers, "in" is modified by removing arcs that are not compatible with the equality. If no arc is left, a bottom "in" is returned.
"out" is "in", modified by side-effects.
Is the condition lhs!=rhs certainly impossible to evaluate? If not, is it always false?
al | l |
in | n |
Definition at line 3086 of file expression.c.
References atomic_points_to_cell_p(), CAR, CDR, CELL, cell_undefined, cell_undefined_p, clear_pt_map, copy_cell(), EXPRESSION, expression_null_p(), expression_to_points_to_sinks(), expression_to_points_to_sources(), expression_to_string(), expression_to_type(), free_type(), gen_length(), int, list_undefined, make_approximation_may(), make_descriptor_none(), make_points_to(), nowhere_cell_p(), null_non_equal_condition_to_points_to(), out, pips_assert, pips_user_warning, pointer_type_p(), points_to_cell_equal_p(), points_to_context_statement_line_number(), points_to_graph_bottom, and remove_arc_from_pt_map.
Referenced by relational_intrinsic_call_condition_to_points_to().
pt_map null_equal_condition_to_points_to | ( | expression | e, |
pt_map | in | ||
) |
The condition is e==NULL.
e==NULL may be true if exists c in sinks(e) s.t. {NULL} is included in c. else e==NULL must be false.
Some arcs in in may be removed: forall c in sources(e):
out = in - {pt=(a,b) in in | a in sources(e) and b=NULL}
May the condition be true under "in"?
If NULL initialization is not performed, a stub can represent a NULL.
Remove arcs incompatible with the condition e==NULL and add the arc e->NULL
All arcs starting from fc can be removed and replaced by one arc from fc to NULL.
in | n |
Definition at line 2849 of file expression.c.
References add_arc_to_pt_map, anywhere_cell_p(), atomic_points_to_cell_p(), CAR, CELL, cell_in_list_p(), cell_typed_anywhere_locations_p(), clear_pt_map, copy_cell(), ENDP, expression_to_points_to_sinks(), expression_to_points_to_sources(), expression_to_type(), FOREACH, gen_free_list(), gen_length(), get_bool_property(), int, make_approximation_exact(), make_descriptor_none(), make_null_cell(), make_points_to(), null_cell_p(), out, pips_assert, pips_internal_error, pointer_type_p(), points_to_cell_source_projection(), points_to_graph_bottom, points_to_graph_set, points_to_sink, points_to_source, remove_arc_from_pt_map_, SET_FOREACH, and stub_points_to_cell_p().
Referenced by equal_condition_to_points_to().
pt_map null_non_equal_condition_to_points_to | ( | expression | e, |
pt_map | in | ||
) |
The condition is e!=NULL.
e!=NULL may be true if exists c in sinks(e) s.t. c != {NULL}
e!=NULL is false if forall c in sinks(e) c is included in {NULL}
Arcs that can be removed:
FI: I decided not to merge this function with the previous one till they are both fully defined and tested.
May the condition be true under "in"?
Remove arcs incompatible with the condition e!=NULL
in | n |
Definition at line 2927 of file expression.c.
References CELL, cell_in_list_p(), clear_pt_map, ENDP, expression_to_points_to_sinks(), expression_to_points_to_sources(), expression_to_type(), FOREACH, null_cell_p(), out, pips_internal_error, pointer_type_p(), points_to_graph_bottom, points_to_graph_set, points_to_sink, points_to_source, remove_arc_from_pt_map_, and SET_FOREACH.
Referenced by non_equal_condition_to_points_to().
void offset_array_reference | ( | reference | r, |
expression | delta, | ||
type | et | ||
) |
Side effect on reference "r".
r is assumed to be a reference to an array.
The offset is applied to the last suscript.
delta | elta |
et | t |
Definition at line 802 of file expression.c.
References CAR, CONS, constant_int, constant_int_p, ENDP, EvalExpression(), EXPRESSION, EXPRESSION_, free_expression(), get_int_property(), int_to_expression(), make_unbounded_expression(), NIL, points_to_reference_to_typed_index(), reference_indices, value_constant, and value_constant_p.
Referenced by offset_cell().
points_to offset_cell | ( | points_to | pt, |
expression | delta, | ||
type | et | ||
) |
Allocate and return a new points-to "npt", copy of "pt", with an offset of "delta" on the sink.
"et" is used to determine which index should be offseted.
Some kind of k-limiting should be performed here to avoid creating too many new nodes in the points-to graph, such as t[0], t[1],... A fix point t[*] should be used when too may nodes already exist.
Since "sink" is used to compute the key in the hash table used to represent set "in", it is not possible to perform a side effect on "sink" without removing and reinserting the corresponding arc.
FI: I am not sure we have the necessary information to know which subscript must be updated when more than one is available. This is bad for multidimensional arrays and worse for references to stub that may include fields (or not) as subscript as well as lots of articificial dimensions due to the source.
I assumed gen_last() to start with, but it is unlikely in general!
"&a[i]" should be transformed into "&a[i+eval(delta)]" when "delta" can be statically evaluated
| !get_bool_property("POINTS_TO_STRICT_POINTER_TYPES")
pt | t |
delta | elta |
et | t |
Definition at line 937 of file expression.c.
References anywhere_cell_p(), array_pointer_type_equal_p(), array_type_p(), cell_any_reference(), char_star_constant_function_type_p(), compute_basic_concrete_type(), copy_points_to(), effect_reference_to_string(), entity_basic_concrete_type(), entity_user_name(), free_type(), get_bool_property(), nowhere_cell_p(), null_cell_p(), offset_array_reference(), pips_user_error, points_to_cell_to_type(), points_to_context_statement_line_number(), points_to_sink, points_to_source, reference_variable, struct_type_p(), and type_to_pointed_type().
Referenced by offset_cells().
void offset_cells | ( | cell | source, |
list | sinks, | ||
expression | delta, | ||
type | et, | ||
pt_map | in | ||
) |
Each cell in sinks is replaced by a cell located "delta" elements further up in the memory.
In some cases, the same points-to are removed and added. For instance, t[0],t[1] -> t[1],t[2] because of a p++, and t[1] is removed and added.
If the source may point to null, the corresponding arc is removed. If the source points only to null, the resulting graph is bottom.
This procedure must be used when cells in "sinks" are components of points-to arcs stored in a points-to set.
source | ource |
sinks | inks |
delta | elta |
et | t |
in | n |
Definition at line 869 of file expression.c.
References add_arc_to_pt_map, anywhere_cell_p(), CELL, cell_typed_anywhere_locations_p(), copy_cell(), difference_of_pt_maps, find_arc_in_points_to_set(), FOREACH, gen_length(), make_approximation_may(), make_descriptor_none(), make_points_to(), new_pt_map, null_cell_p(), offset_cell(), points_to_cell_to_string(), points_to_graph_bottom, points_to_undefined_p, semantics_user_warning, and union_of_pt_maps.
Referenced by pointer_arithmetic_to_points_to().
void offset_points_to_cell | ( | cell | sink, |
expression | delta, | ||
type | t, | ||
bool unique_p | __attribute__(__unused__) | ||
) |
FI: offset_cell() has been derived from this function.
Some factoring out should be performed.
The naming is all wrong: offset_points_to_cell() can operate on a cell, while offset_cell() is designed to operate on a cell component of a points-to.
Type "t" is used to decide which subscript should be updated by delta.
"&a[i]" should be transformed into "&a[i+eval(delta)]" when "delta" can be statically evaluated
No subscript is possible, but 0 and it does not need to appear
dereferencing18.c: a scalar was malloced
We might use unique_p and the value of delta to detect an error or to warn the user about a possible error
Definition at line 1036 of file expression.c.
References anywhere_cell_p(), CAR, cell_any_reference(), cell_typed_anywhere_locations_p(), CONS, constant_int, constant_int_p, ENDP, entity_array_p(), entity_user_name(), EvalExpression(), EXPRESSION, EXPRESSION_, find_points_to_subscript_for_type(), free_expression(), get_bool_property(), get_int_property(), int_to_expression(), make_unbounded_expression(), NIL, nowhere_cell_p(), null_cell_p(), pips_user_error, points_to_context_statement_line_number(), reference_indices, reference_variable, value_constant, value_constant_p, and zero_expression_p().
Referenced by offset_points_to_cells().
void offset_points_to_cells | ( | list | sinks, |
expression | delta, | ||
type | t | ||
) |
Each cell in sinks is replaced by a cell located "delta" elements further up in the memory.
Similar to offset_cells(), but, in spite of the name, cannot be used with points-to cells that are part of a points-to belonging to a points-to set.
sinks | inks |
delta | elta |
Definition at line 1020 of file expression.c.
References CDR, CELL, ENDP, FOREACH, and offset_points_to_cell().
Referenced by expression_to_points_to_sinks_with_offset(), and unary_intrinsic_call_to_points_to_sinks().
The expression list "al" contains exactly two arguments.
If these expressions are pointers, "in" is modified by removing arcs that are not compatible with the equality. If no arc is left, a bottom "in" is returned.
"out" is "in", modified by side-effects.
The condition cannot violate an exact arc.
The condition cannot violate an exact arc.
al | l |
true_p | rue_p |
in | n |
Definition at line 3176 of file expression.c.
References approximation_exact_p, CAR, CDR, CELL, cell_in_list_p(), cell_is_greater_than_or_equal_to_p(), cell_is_greater_than_p(), cell_is_less_than_or_equal_to_p(), cell_is_less_than_p(), ENTITY_GREATER_OR_EQUAL_P, ENTITY_GREATER_THAN_P, ENTITY_LESS_OR_EQUAL_P, ENTITY_LESS_THAN_P, EXPRESSION, expression_to_points_to_sinks(), expression_to_points_to_sources(), expression_to_type(), f(), free_type(), gen_length(), out, pips_internal_error, pointer_type_p(), points_to_approximation, points_to_graph_bottom, points_to_graph_set, points_to_sink, points_to_source, remove_arc_from_pt_map, RR, set_clear(), and SET_FOREACH.
Referenced by relational_intrinsic_call_condition_to_points_to().
pt_map pointer_arithmetic_to_points_to | ( | expression | lhs, |
expression | delta, | ||
pt_map | pt_in | ||
) |
Update the sink locations associated to the source "lhs" under points-to information pt_map by "delta".
C standard guarantees that the sink objects is unchanged by pointer arithmetic.
Property POINTS_TO_STRICT_POINTER_TYPES is used to be more or less flexible about formal parameters and local variables such as "int * p"
lhs | hs |
delta | elta |
pt_in | t_in |
Definition at line 760 of file expression.c.
References CELL, cell_any_reference(), clear_pt_map, ENDP, entity_user_name(), expression_to_points_to_sources(), FOREACH, gen_length(), nowhere_cell_p(), null_cell_p(), offset_cells(), pips_user_warning, points_to_expression_to_type(), reference_variable, remove_points_to_arcs(), and source_to_sinks().
Referenced by intrinsic_call_to_points_to().
pt_map pointer_assignment_to_points_to | ( | expression | lhs, |
expression | rhs, | ||
pt_map | pt_in | ||
) |
FI: this is a crazy idea to avoid problems in balancing test branches. It should only be useful when the formal context has to be expanded by this assignment. lhs = lhs;
Of course, it is a catastrophy when expression lhs has side effects...
And it does not work because the current "in" of the test is modified by side-effect no seen when the false branch is analyzed.
lhs | hs |
rhs | hs |
pt_in | t_in |
Definition at line 1437 of file expression.c.
References internal_pointer_assignment_to_points_to().
Referenced by assignment_to_points_to(), and expand_points_to_domain().
Definition at line 1900 of file expression.c.
References generic_points_to_cell_to_useful_pointer_cells(), and set_undefined.
Referenced by memory_leak_to_more_memory_leaks(), and points_to_cells_to_pointer_cells().
pts | ts |
Definition at line 1905 of file expression.c.
References generic_points_to_cell_to_useful_pointer_cells().
Referenced by filter_formal_context_according_to_actual_context(), and recursive_filter_formal_context_according_to_actual_context().
Convert cells in l into derived pointer cells when possible.
The elements of list pl are reused in list l
pl | l |
Definition at line 1917 of file expression.c.
References CELL, FOREACH, gen_nconc(), NIL, pl, and points_to_cell_to_pointer_cells().
Referenced by recursive_filter_formal_context_according_to_actual_context().
pt_in | t_in |
side_effect_p | ide_effect_p |
Definition at line 284 of file expression.c.
References expression_to_points_to(), range_increment, range_lower, and range_upper.
Referenced by expression_to_points_to().
Remove last subscripts of cell c till its type becomes a scalar pointer.
This of course may fail.
Remove the last subscript, hopefully 0
Definition at line 1809 of file expression.c.
References C_pointer_type_p(), CAR, cell_any_reference(), ENDP, EXPRESSION, field_reference_expression_p(), free_type(), gen_last(), gen_list_and_not(), pointer_type_p(), points_to_cell_to_type(), and reference_indices.
Referenced by list_assignment_to_points_to(), and reduce_cells_to_pointer_type().
Undo the extra eval performed when stubs are generated: 0 subscripts are added when arrays are involved.
cl | l |
Definition at line 1844 of file expression.c.
References CELL, FOREACH, null_cell_p(), and reduce_cell_to_pointer_type().
Handle conditions such as "if(p)".
Do not take care of side effects in references...
are we dealing with a pointer?
if p points to NULL, the condition is not feasible. If not, remove any arc from p to NULL
Make a points-to NULL and remove the arc from the current out
remove any arc from v to anything and add an arc from p to NULL
Make a points-to NULL and remove the arc from the current out
This condition is always false
in | n |
true_p | rue_p |
Definition at line 2538 of file expression.c.
References add_arc_to_pt_map, clear_pt_map, copy_reference(), entity_basic_concrete_type(), expressions_to_points_to(), free_points_to(), make_approximation_exact(), make_approximation_may(), make_cell_reference(), make_descriptor_none(), make_null_pointer_value_cell(), make_points_to(), out, pips_user_warning, pointer_type_p(), points_to_graph_bottom, points_to_graph_set, points_to_source_projection(), reference_indices, reference_may_points_to_null_p(), reference_must_points_to_null_p(), reference_variable, and remove_arc_from_pt_map.
Referenced by condition_to_points_to().
The subscript expressions may impact the points-to information.
E.g. a[*(p++)]
FI: I'm surprised that pointers can be indexed instead of being subscripted... This is linked to the parser in expression_to_points_to().
pt_in | t_in |
side_effect_p | ide_effect_p |
Definition at line 262 of file expression.c.
References dereferencing_to_points_to(), ENDP, entity_basic_concrete_type(), entity_stub_sink_p(), entity_to_expression(), expressions_to_points_to(), formal_parameter_p(), free_expression(), pointer_type_p(), points_to_graph_bottom, reference_indices, and reference_variable.
Referenced by expression_to_points_to().
Update the points-to information "in" according to the validity of the condition.
We can remove the arcs that violate the condition or decide that the condition cannot be true.
in | n |
true_p | rue_p |
Definition at line 3274 of file expression.c.
References call_arguments, call_function, ENTITY_EQUAL_P, ENTITY_GREATER_OR_EQUAL_P, ENTITY_GREATER_THAN_P, ENTITY_LESS_OR_EQUAL_P, ENTITY_LESS_THAN_P, ENTITY_NON_EQUAL_P, equal_condition_to_points_to(), f(), non_equal_condition_to_points_to(), order_condition_to_points_to(), out, pips_assert, pips_internal_error, and points_to_graph_consistent_p().
Referenced by intrinsic_call_condition_to_points_to().
pt_map struct_assignment_to_points_to | ( | expression | lhs, |
expression | rhs, | ||
pt_map | pt_in | ||
) |
pt_in is modified by side-effects and returned as pt_out
This function is also used for declarations, although the syntax for declarations is reacher than the syntax for assignments which can use BRACE_INTRINSIC.
Current arc list (cal): the new arc may be conflicting with an existing must arc
We may have an implicit array of struct in the right or left hand side
rray_type_p(ft) ||
FI: conditionally add zero subscripts necessary to move from an array "a" to its first element, e.g. a[0][0][0]
lhs | hs |
rhs | hs |
pt_in | t_in |
Definition at line 2319 of file expression.c.
References add_arc_to_pt_map, approximation_exact_p, array_of_pointers_type_p(), array_of_struct_type_p(), array_type_p(), assignment_to_points_to(), basic_derived, basic_equal_p(), C_initialization_expression_p(), CELL, cell_any_reference(), cell_to_type(), CONS, copy_cell(), copy_reference(), ENTITY, entity_abstract_location_p(), entity_basic_concrete_type(), entity_type, EXPRESSION, expression_to_points_to_sources(), f(), FOREACH, gen_free_list(), gen_nconc(), make_anywhere_cell(), make_approximation_may(), make_cell_reference(), make_descriptor_none(), make_points_to(), make_unbounded_expression(), NIL, pips_assert, pips_internal_error, pointer_type_p(), POINTS_TO, points_to_approximation, points_to_sink, points_to_source, points_to_source_to_arcs(), reference_add_field_dimension(), reference_add_zero_subscripts(), reference_indices, reference_to_expression(), reference_variable, remove_arc_from_pt_map, simple_reference_add_field_dimension(), struct_initialization_to_points_to(), struct_type_p(), type_struct, type_to_pointed_type(), type_variable, and variable_basic.
Referenced by assignment_to_points_to().
pt_map struct_initialization_to_points_to | ( | expression | lhs, |
expression | rhs, | ||
pt_map | in | ||
) |
Temporary implementation: use anywhere as default initialization
We must assign to each relevant field its initial value
lhs | hs |
rhs | hs |
in | n |
Definition at line 2262 of file expression.c.
References add_arc_to_pt_map, assignment_to_points_to(), CAR, CELL, cell_any_reference(), compute_basic_concrete_type(), CONS, ENDP, ENTITY, entity_to_expression(), EXPRESSION, expression_to_points_to_sources(), f(), FOREACH, free_type(), gen_length(), make_anywhere_cell(), make_approximation_exact(), make_descriptor_none(), make_points_to(), make_reference(), NIL, out, pips_assert, points_to_cell_to_type(), POP, reference_indices, reference_to_expression(), reference_variable, struct_initialization_expression_to_expressions(), struct_variable_to_fields(), type_to_pointed_type(), and variable_to_pointer_locations().
Referenced by struct_assignment_to_points_to().
FI: what is this function supposed to do? Just update "pt_in" to make sure that "r" can be dereferenced? And then recursively, with the different subscripts?
expression.c
FI: we have to find the right location for the subscript to update. Some dimensions are due to the dimension of the source in pt_in, one dimension is due to the fact that we are dealing with a pointer, some dimensions are due to the fact that an array is pointed. The dimension to update may be the first one, the last one, or one in the middle.
This also depends on strict typing...
See for instance, Pointers/pointer20.c
sl | l |
pt_in | t_in |
Definition at line 57 of file expression.c.
References adapt_reference_to_type(), array_of_pointers_type_p(), CAR, CDR, CELL, cell_any_reference(), CONS, copy_expression(), ENDP, EXPRESSION, FOREACH, NIL, pips_internal_error, pointer_type_p(), points_to_cell_update_last_subscript(), points_to_context_statement_line_number(), points_to_reference_to_concrete_type(), reference_indices, reference_to_points_to_sinks(), and remove_impossible_arcs_to_null().
Referenced by expression_to_points_to().
in | n |
el | l |
true_p | rue_p |
Definition at line 2679 of file expression.c.
References out, and user_call_to_points_to().
Referenced by call_condition_to_points_to().