PIPS
|
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include "genC.h"
#include "linear.h"
#include "ri.h"
#include "effects.h"
#include "bootstrap.h"
#include "ri-util.h"
#include "effects-util.h"
#include "misc.h"
#include "text-util.h"
#include "properties.h"
#include "effects-generic.h"
#include "effects-simple.h"
#include "points_to_private.h"
#include "points-to.h"
Go to the source code of this file.
Macros | |
#define | _GNU_SOURCE |
For strdup and asprintf: More... | |
Functions | |
void | points_to_forward_translation () |
-----------------------------—Interprocedural Points-to Analysis--------------------— More... | |
void | points_to_backward_translation () |
set | formal_points_to_parameter (cell c) |
We want a recursive descent on the type of the formal parameter, once we found a pointer type we beguin a recursive descent until founding a basic case. More... | |
entity | create_stub_entity (entity e, string fs, type t) |
Allocate a stub entity "stub" for entity "e" and with type "t". More... | |
cell | create_scalar_stub_sink_cell (entity v, type st, type pt, int d, list sl, string fs) |
Create a stub entity "se" for entity "v" with type "t" and return a cell based on a reference to the stub entity "se" with "d" unbounded subscripts to account for the dimension of the source and a zero subscript for implicit array. More... | |
int | points_to_indices_to_array_index_number (list sl) |
Count the number of array indices and ignore the field subscripts. More... | |
void | points_to_indices_to_unbounded_indices (list sl) |
FI: probably a duplicate... More... | |
list | points_to_indices_to_subscript_indices (list ptsl) |
Generate a new subscript list. More... | |
string | reference_to_field_disambiguator (reference r) |
Build an ASCII string to disambiguate the different field paths that may exist in similar references. More... | |
points_to | create_stub_points_to (cell c, type unused_st __attribute__((__unused__)), bool exact_p) |
points_to create_stub_points_to(cell c, bool exact_p) More... | |
points_to | create_advanced_stub_points_to (cell c, type t, bool exact_p) |
Take into account the POINTS_TO_STRICT_POINTER_TYPE to allocate a sink cell of type "t" if the strictness is requested and of type "array of t" if not. More... | |
points_to | create_pointer_to_array_stub_points_to (cell c, type t, bool exact_p) |
To create the points-to stub associated to the formal parameter, the sink name is a concatenation of the formal parmater and the POINTS_TO_MODULE_NAME. More... | |
set | pointer_formal_parameter_to_stub_points_to (type pt, cell c) |
Input : a formal parameter which is a pointer and its type. More... | |
set | derived_formal_parameter_to_stub_points_to (type pt, cell c) |
Input : a formal parameter which has a derived type (FI, I guess). More... | |
set | typedef_formal_parameter_to_stub_points_to (type pt, cell c) |
Input : a formal parameter which is a typedef. More... | |
set | array_formal_parameter_to_stub_points_to (type t, cell c) |
Type "t" is supposed to be a concrete type. More... | |
Variables | |
static int | pointer_index = 1 |
#define _GNU_SOURCE |
For strdup and asprintf:
Definition at line 28 of file points_to_init_analysis.c.
Type "t" is supposed to be a concrete type.
Type "t" may be modified: no.
Cell "c" is copied.
The dimensions of type "t" are forgotten. They are retrieved later from the type of the entity references in cell "c".
Add an artificial dimension for pointer arithmetic
Definition at line 1116 of file points_to_init_analysis.c.
References basic_pointer, basic_pointer_p, cell_any_reference(), CONS, copy_type(), create_stub_points_to(), DIMENSION, get_bool_property(), make_cell_reference(), make_dimension(), make_reference(), make_unbounded_expression(), make_zero_expression(), NIL, points_to_equal_p(), points_to_rank(), ref, reference_consistent_p(), reference_variable, scalar_type_p(), set_add_element(), set_generic_make(), set_private, type_variable, variable_basic, and variable_dimensions.
Referenced by formal_points_to_parameter().
Take into account the POINTS_TO_STRICT_POINTER_TYPE to allocate a sink cell of type "t" if the strictness is requested and of type "array of t" if not.
assume that pointers to scalars always points towards an array of unknown dimension.
exact_p | xact_p |
Definition at line 688 of file points_to_init_analysis.c.
References array_type_p(), create_stub_points_to(), get_bool_property(), pips_internal_error, points_to_undefined, and type_to_array_type().
To create the points-to stub associated to the formal parameter, the sink name is a concatenation of the formal parmater and the POINTS_TO_MODULE_NAME.
exact_p | xact_p |
Definition at line 709 of file points_to_init_analysis.c.
References base, basic_undefined, cell_any_reference(), concatenate(), CONS, copy_basic(), copy_cell(), copy_type(), DIMENSION, dimension_lower, dimension_upper, entity_kind, ENTITY_POINTER_DUMMY_TARGETS_AREA, entity_storage, entity_undefined_p, entity_user_name(), EXPRESSION, expression_undefined, f(), FindOrCreateEntity(), FOREACH, formal_offset, formal_parameter_p(), gen_find_entity(), gen_length(), gen_nconc(), get_bool_property(), get_current_module_entity(), get_current_module_name(), int2a(), int_to_expression(), make_approximation_exact(), make_approximation_may(), make_cell_reference(), make_descriptor_none(), make_dimension(), make_entity, make_points_to(), make_ram(), make_reference(), make_storage_ram(), make_type_variable(), make_unbounded_expression(), make_value_unknown(), make_variable(), MODULE_SEP_STRING, NIL, POINTER_DUMMY_TARGETS_AREA_LOCAL_NAME, pointer_index, reference_undefined, reference_variable, storage_formal, strdup(), type_undefined, type_variable, UNKNOWN_RAM_OFFSET, variable_basic, and variable_dimensions.
Referenced by pointer_formal_parameter_to_stub_points_to().
Create a stub entity "se" for entity "v" with type "t" and return a cell based on a reference to the stub entity "se" with "d" unbounded subscripts to account for the dimension of the source and a zero subscript for implicit array.
Type "pt" is the theoretically expected type for the reference "sink_ref" within the returned cell, "sink_cell". We assert "pt==points_to_cell_to_type(sink_cell)".
Type "t" must account for the extra "d" dimensions.
The type strictness is handled by the caller.
The name of the function is misleading. It should be "create_stub_sink_cell"... but in fact is does not handle the struct case because struct can contain may different pointers, directly or indirectly, depending on fields. This function is ok if v a pointer or an array of pointers, but not if v is a struct.
The function is called four times from create_stub_points_to().
When scalars are used, we should have "d==0" and "td==0" and hence "sl==NIL"
FI: use 0 for all proper target dimensions
FI: adding 0 subscripts is similar to a dereferencing. We do not know at this level if the dereferencing has been requested. See pointer_reference02. The handling fo eval_p must be modified correspondingly by adding 0 subscripts when the source is an array. Or evaluation must be skipped.
st | t |
pt | t |
sl | l |
fs | s |
Definition at line 267 of file points_to_init_analysis.c.
References array_pointer_type_equal_p(), array_type_p(), basic_equal_p(), cell_consistent_p(), CONS, copy_type(), create_stub_entity(), entity_local_name(), entity_user_name(), EXPRESSION, fprintf(), free_type(), gen_nconc(), ifdebug, make_cell_reference(), make_reference(), make_zero_expression(), MakeTypeOverloaded(), NIL, overloaded_type_p(), pips_assert, pips_debug, pips_internal_error, points_to_cell_to_concrete_type(), points_to_reference_to_type(), print_points_to_cell, print_type(), reference_indices, reference_undefined, type_functional_p, type_undefined, type_variable, type_variable_p, type_void_p, variable_basic, and variable_dimension_number().
Referenced by create_stub_points_to().
Allocate a stub entity "stub" for entity "e" and with type "t".
Abort if "stub" already exists.
It seems that type "t" could be derived from "e" since it should be the pointed type of "e"'s type, but it is not at all the case in general. Variable e is used to build a reference and the type pointed by the reference may be different when arrays of structs of arrays of structs are involved.
FI: I assume all unknown offsets defined in ri-util-local.h to be strictly negative.
FI: we could use a 0 as default offset for clarity?
FI: we are in deep trouble because the stub entity has already been created... but we have no idea if it is or not the entity we wanted as it depends on field names in the reference. And the reference is not available from this function.
fs | s |
Definition at line 151 of file points_to_init_analysis.c.
References ABSTRACT_LOCATION, add_C_variable_to_area(), AddEntityToDeclarations(), array_pointer_type_equal_p(), concatenate(), copy_type(), DYNAMIC_RAM_OFFSET, entity_basic_concrete_type(), ENTITY_FORMAL_AREA, entity_initial, entity_kind, entity_local_name(), entity_module_name(), entity_storage, entity_stub_sink_p(), entity_type, entity_undefined_p, entity_user_name(), f(), FindOrCreateEntity(), FORMAL_AREA_LOCAL_NAME, formal_offset, formal_parameter_p(), gen_find_entity(), int2a(), is_type_area, is_value_unknown, make_area(), make_entity, make_ram(), make_storage_ram(), make_storage_rom(), make_type(), make_value(), make_value_unknown(), module_name_to_entity(), MODULE_SEP_STRING, NIL, pips_internal_error, ram_offset, static_global_variable_p(), storage_formal, storage_ram, strdup(), string_undefined, top_level_entity_p(), type_undefined_p, and UU.
Referenced by create_scalar_stub_sink_cell().
points_to create_stub_points_to(cell c, bool exact_p)
To create the points-to arc "pt_to" between a cell "c" containing a constant path reference based on a formal parameter or a global variable or another stub on one hand, and another new points-to stub reference on the other.
Argument "exact_p" specifies the approximation of the generated points-to arc. It is overriden when NULL pointers are distinguished according to property POINTS_TO_NULL_POINTER_INITIALIZATION. This simplifies the semantics of the stub entities: they cannot represent/hide the NULL abstract cell.
The arc approximation itself is another issue as pointed out by Beatrice Creusillet because we may have an approximation on the source node, on the sink node or on the arc. Currently, an exact approximation seems to indicate that no approximation at all is made. This is issue is not currently solved (13 August 2012).
Assumption: the reference in source cell "c" is a constant memory path. So is the new reference hidden in the sink cell.
This function must be consistent with type compatibility checks used in points-to analysis, points_to_cell_types_compatibility(l, r).
The global sink name of the generated stub is a concatenation of the formal parameter, underscore, some number, and POINTS_TO_MODULE_NAME as module name.
The type of cell "c" and the type of the sink cell that is generated must fit in some complicated way:
Here, we needs lots of examples with constant memory path references to prepare a precise specification of the desired function. Let c stands for the reference hidden in cell "c":
The cell "c" is not embedded in the generated points-to "pt_to". A copy is allocated. The output has no sharing with the input parameters.
&& vd==0
You may have a pointer or an unbounded array for source_t...
Take care of void *
Update sink_t to take into account all the dimensions existing in the source
stub_t is same as sink_t, but add a dimension array arithmetic
Definition at line 580 of file points_to_init_analysis.c.
References C_type_to_pointed_type(), cell_any_reference(), cell_undefined, CONS, copy_cell(), copy_type(), create_scalar_stub_sink_cell(), DEFAULT_CHARACTER_TYPE_SIZE, ENDP, ENTITY_STDERR_P, ENTITY_STDIN_P, ENTITY_STDOUT_P, entity_type, EXPRESSION, f(), FindOrCreateEntity(), FOPEN_FUNCTION_NAME, free_type(), gen_full_copy_list(), gen_nconc(), get_bool_property(), int_to_expression(), make_approximation_exact(), make_approximation_may(), make_basic_overloaded(), make_cell_reference(), make_descriptor_none(), make_points_to(), make_reference(), make_scalar_integer_type(), make_type_variable(), make_unbounded_dimensions(), make_variable(), MakeIoFileArray(), NIL, pips_assert, pips_internal_error, pointer_index, points_to_cell_to_concrete_type(), points_to_cell_types_compatibility(), points_to_indices_to_array_index_number(), points_to_indices_to_subscript_indices(), reference_indices, reference_to_field_disambiguator(), reference_variable, STDERR_FILENO, STDIN_FILENO, STDOUT_FILENO, TOP_LEVEL_MODULE_NAME, type_functional_p, type_to_array_type(), type_to_pointed_type(), type_undefined_p, type_variable, type_variable_p, type_void_p, and variable_dimensions.
Referenced by array_formal_parameter_to_stub_points_to(), create_advanced_stub_points_to(), derived_formal_parameter_to_stub_points_to(), pointer_formal_parameter_to_stub_points_to(), and typedef_formal_parameter_to_stub_points_to().
Input : a formal parameter which has a derived type (FI, I guess).
output : a set of points-to where sinks are stub points-to.
FI: a lot of rewrite needed to simplify. Also, do not forget that NULL maybe the received value.
maybe should be removed if we have already called ultimate type in formal_points_to_parameter()
We ignore dimensions for the time being, descriptors are not implemented yet...Amira Mensi
ultimate_type() returns a wrong type for arrays. For example for type int*[10] it returns int*[10] instead of int[10].
In fact, there should be a FOREACH to scan all elements of l_ef
free the spine
pt | t |
Definition at line 952 of file points_to_init_analysis.c.
References array_entity_p(), basic_derived, basic_derived_p, CAR, cell_any_reference(), compute_basic_concrete_type(), create_stub_points_to(), EFFECT, effect_any_reference, effect_undefined, effects_free(), ENTITY, entity_intrinsic(), entity_to_expression(), entity_type, entity_undefined, expression_pointer_p(), FIELD_OPERATOR_NAME, FOREACH, gen_free_list(), generic_effects_reset_all_methods(), generic_proper_effects_of_complex_address_expression(), get_bool_property(), make_cell_reference(), MakeBinaryCall(), NIL, points_to_equal_p(), points_to_rank(), points_to_undefined, reference_undefined, reference_variable, set_add_element(), set_generic_make(), set_methods_for_proper_simple_effects(), set_private, type_struct, type_struct_p, type_to_pointed_type(), type_variable, type_variable_p, ultimate_type(), and variable_basic.
Referenced by formal_points_to_parameter().
We want a recursive descent on the type of the formal parameter, once we found a pointer type we beguin a recursive descent until founding a basic case.
Then we beguin the ascent and the creation gradually of the points_to_stub by calling pointer_formal_parameter_to_stub_points_to().
FI->AM: as I would rather work on-demand, this function should be useless. I fixed it nevertheless because it seems better for EffectsWithPointsTo, which does not seem to allocate the new points-to stubs it needs.
fpt = entity_basic_concrete_type(e);
We ignor dimensions for the time being, descriptors are not implemented yet...Amira Mensi
what about storage
Definition at line 85 of file points_to_init_analysis.c.
References array_formal_parameter_to_stub_points_to(), array_type_p(), basic_tag, cell_reference_to_type(), cell_to_reference(), derived_formal_parameter_to_stub_points_to(), free_type(), is_basic_bit, is_basic_complex, is_basic_derived, is_basic_float, is_basic_int, is_basic_logical, is_basic_overloaded, is_basic_pointer, is_basic_string, is_basic_typedef, pips_internal_error, pointer_formal_parameter_to_stub_points_to(), points_to_equal_p(), points_to_rank(), reference_undefined, set_generic_make(), set_private, set_union(), type_undefined, type_variable, type_variable_p, typedef_formal_parameter_to_stub_points_to(), and variable_basic.
Referenced by init_points_to_analysis().
Input : a formal parameter which is a pointer and its type.
Output : a set of points-to where sinks are stub points-to. we descent recursively until reaching a basic type, then we call create_stub_points_to()to generate the adequate points-to.
FI: I do not know if I want to keep using this function because stubs are not created on demand and because some are certainly not useful for the points-to analysis. But they may be useful for client analysis... However, client analyses will have to create more such stubs...
maybe should be removed if we have already called ultimate type in formal_points_to_parameter()
The pointer may be NULL or undefined. We neglect undefined/nowhere
The pointer may points towards another object (or set of object)
Recursive descent for pointers: the new sink becomes the new source... FI: I do not think this is useful because they will be created on demand...
what about storage
Create a target of unknown type
pt | t |
Definition at line 810 of file points_to_init_analysis.c.
References add_arc_to_simple_pt_map, array_type_p(), basic_tag, copy_cell(), create_pointer_to_array_stub_points_to(), create_stub_points_to(), get_bool_property(), is_basic_bit, is_basic_complex, is_basic_derived, is_basic_float, is_basic_int, is_basic_logical, is_basic_overloaded, is_basic_pointer, is_basic_string, is_basic_typedef, make_approximation_may(), make_descriptor_none(), make_null_pointer_value_cell(), make_points_to(), pips_internal_error, pointer_formal_parameter_to_stub_points_to(), points_to_equal_p(), points_to_rank(), points_to_sink, points_to_undefined, set_add_element(), set_free(), set_generic_make(), set_private, set_union(), type_functional_p, type_to_pointed_type(), type_variable, type_variable_p, type_void_p, and variable_basic.
Referenced by formal_points_to_parameter(), and pointer_formal_parameter_to_stub_points_to().
void points_to_backward_translation | ( | void | ) |
Definition at line 71 of file points_to_init_analysis.c.
void points_to_forward_translation | ( | void | ) |
-----------------------------—Interprocedural Points-to Analysis--------------------—
This package computes the points-to interprocedurally.
See Chapter ? in Amira Mensi's PhD dissertation.
Definition at line 66 of file points_to_init_analysis.c.
Count the number of array indices and ignore the field subscripts.
sl | l |
Definition at line 384 of file points_to_init_analysis.c.
References EXPRESSION, expression_reference_p(), and FOREACH.
Referenced by create_stub_points_to().
Generate a new subscript list.
References to fields are ignored, constant and unbounded expressions are preserved, non-constant expressions are replaced by unbounded expressions.
ptsl | tsl |
Definition at line 425 of file points_to_init_analysis.c.
References CAR, CONS, copy_expression(), ENDP, entity_field_p(), EXPRESSION, expression_reference(), expression_reference_p(), extended_integer_constant_expression_p(), gen_nreverse(), make_unbounded_expression(), NIL, POP, reference_variable, and unbounded_expression_p().
Referenced by create_stub_points_to().
void points_to_indices_to_unbounded_indices | ( | list | sl | ) |
FI: probably a duplicate...
sl | l |
Definition at line 395 of file points_to_init_analysis.c.
References CAR, ENDP, entity_field_p(), EXPRESSION, EXPRESSION_, expression_is_constant_p(), expression_reference(), expression_reference_p(), free_expression(), make_unbounded_expression(), NIL, POP, reference_variable, and unbounded_expression_p().
Build an ASCII string to disambiguate the different field paths that may exist in similar references.
If the variable referenced by "r" is not a struct, returns the empty string.
If it is a struct, derive a string that is unique to a particular combination of fields and subfields.
Definition at line 468 of file points_to_init_analysis.c.
References asprintf, entity_field_p(), entity_field_rank(), EXPRESSION, expression_reference(), expression_reference_p(), f(), FOREACH, free(), reference_indices, reference_variable, strdup(), string_undefined, and string_undefined_p.
Referenced by create_stub_points_to().
Input : a formal parameter which is a typedef.
FI: a formal parameter cannot be a typedef, but it can be typed with a typedefined type.
maybe should be removed if we have already called ultimate type in formal_points_to_parameter()
We ignor dimensions for the being, descriptors are not implemented yet...Amira Mensi
ultimate_type() returns a wrong type for arrays. For example for type int*[10] it returns int*[10] instead of int[10].
l = points_to_init_derived(e, e2);
In fact, there should be a FOREACH to scan all elements of l_ef
free the spine
pt | t |
Definition at line 1033 of file points_to_init_analysis.c.
References array_entity_p(), b2, basic_derived, basic_derived_p, basic_typedef, basic_typedef_p, CAR, cell_any_reference(), create_stub_points_to(), EFFECT, effect_any_reference, effect_undefined, effects_free(), ENTITY, entity_intrinsic(), entity_to_expression(), entity_type, entity_undefined, entity_variable_p, expression_pointer_p(), FIELD_OPERATOR_NAME, FOREACH, gen_free_list(), generic_effects_reset_all_methods(), generic_proper_effects_of_complex_address_expression(), get_bool_property(), make_cell_reference(), MakeBinaryCall(), NIL, points_to_equal_p(), points_to_rank(), points_to_undefined, reference_undefined, reference_variable, set_add_element(), set_generic_make(), set_methods_for_proper_simple_effects(), set_private, type_struct, type_struct_p, type_to_pointed_type(), type_variable, type_variable_p, and variable_basic.
Referenced by formal_points_to_parameter().
|
static |
Definition at line 58 of file points_to_init_analysis.c.
Referenced by create_pointer_to_array_stub_points_to(), and create_stub_points_to().