PIPS
|
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "genC.h"
#include "linear.h"
#include "ri.h"
#include "effects.h"
#include "alias_private.h"
#include "ri-util.h"
#include "prettyprint.h"
#include "effects-util.h"
#include "database.h"
#include "pipsdbm.h"
#include "resources.h"
#include "misc.h"
#include "properties.h"
#include "transformer.h"
#include "instrumentation.h"
#include "text-util.h"
#include "transformations.h"
#include "callgraph.h"
#include "alias-classes.h"
Go to the source code of this file.
Macros | |
#define | ALIAS_SECTION "ALIAS_SECTION" |
Aliasing occurs when two or more variables refer to the same storage location at the same program point. More... | |
Functions | |
static void | display_alias_propagation_statistics () |
Special alias section counter. More... | |
expression | translate_to_module_frame (entity mod1, entity mod2, expression e1, call c) |
This function translates an expression e1 from the frame of module 1 to the frame of module 2 1.If e1 is a reference: 1.1. More... | |
static void | ram_variable_add_aliases (call c, call_site cs, entity actual_var, entity formal_var, expression subval) |
static bool | common_is_visible_p (entity sec, entity mod) |
This function tests if a common com (TOP_LEVEL:~FOO) is visible in the module mod or in at least one callee (direct and indirect) of this module. More... | |
static bool | same_section_formal_variable_in_list_p (entity actual_var, entity sec, list actual_path, list l, list l_aliases) |
static bool | same_section_common_variable_in_list_p (entity sec, list l) |
static void | formal_variable_add_aliases (call c, call_site cs, entity actual_var, entity formal_var, expression subval, list l_actuals) |
static list | list_of_same_or_equivalence_arguments (entity e, list l) |
static void | same_or_equivalence_argument_add_aliases (list l, call c, call_site cs, list l_actual, bool equiv) |
Add alias_association for each formal variable whose offset is in the list l. More... | |
static bool | add_aliases_for_current_call_site (call c) |
static void | add_aliases_for_current_caller () |
static list | alias_propagation_callers (list l_callers) |
bool | alias_propagation (char *module_name) |
Variables | |
static entity | current_mod = entity_undefined |
Define a static stack and related functions to remember the current statement. More... | |
static entity | current_caller = entity_undefined |
static const char * | caller_name |
static list | l_current_aliases = NIL |
static list | l_traversed = NIL |
static int | number_of_alias_associations = 0 |
static int | number_of_unknown_offsets = 0 |
static int | number_of_known_offsets = 0 |
static int | number_of_processed_modules = 0 |
static int | unique_section_number = 0 |
#define ALIAS_SECTION "ALIAS_SECTION" |
Aliasing occurs when two or more variables refer to the same storage location at the same program point.
This phase tries to compute as precise as possible the interprocedural alias information in a whole program.
In Fortran 77, there are several ways to create aliases:
The basic idea for computing interprocedural aliases is to follow all possible chains of argument-parameters and nonlocal variable-parameter bindings at all call sites. The call graph of program is traversed in invocation order, and alias information is accumulated incrementally.
We use the newgen structure alias_association = (formal_parameter,section, offset, call_path) to store alias information for each formal parameter of each module. Call_path = list of call_sites, call_site = (caller, ordering of the call site) (this is the only current way to store the location of a call site).
Let ai be the considering actual argument in the current call site, by separating the treatment of formal parameters from the treatment of global variables, we only have to treat the following case:
1.1 Alias created by only one call:
Case 1. ai is a common variable and is visible in the current module or in at least one callee (direct and indirect) of this module => add alias association for fi with section of the common : TOP-LEVEL:~FOO
1.2 Alias created through chain of calls:
Case 2. ai is a formal variable with a common section and this common is visible in the current module or in at least one callee (direct and indirect) of this module => add alias association for fi with section of the common : TOP-LEVEL:~FOO and path = path(formal ai) + (C,ordering)
=> useless tests between fi and other variables in the same common block with ai, if not take into account the size of ai (assumption: no [interprocedural] array bound violation), because the section is not enough (unique)
2.1 Alias created by only one call:
Case 3. An actual argument is bound to different formal parameters or there are
different actual arguments but equivalent. So for a call site, we can divide the argument list into groups of same actual or equivalence arguments. For example: EQUIVALENCE (V1(1,1),V2(5)) EQUIVALENCE (U,W) CALL FOO(V1,A,B(TR(I)),C,B(TR(K)),B(H),V1(I,J),V2(K),C,A,M,U,W) SUBROUTINE FOO(F1,F2,F3,F4,F5,F6,F7,F8,F9,F10,F11,F12,F13) => (F1,F7,F8), (F2,F10), (F3,F5,F6),(F4,F9), (F12,F13)
We add alias associations for these formal parameters, all parameters in a same group have same and unique section, path = {(C,ordering)}. The difference among the group (F1,F7,F8), (F12,F13) and the others is that we need to know the initial offsets of F1, F7, F8 and F12, F13 because they can be different variables, and their sections are ram section. For the other cases, we can use section = ALIAS_SPECIAL_i, initial_off = 0.
=> useless tests ??? Not for same variables because the section is unique but useless tests for equivalence variables, as U and V1 have the same section => test between F8,F12, ...
2.2 Alias created through chain of calls
Case 4. Actual arguments are formal variables of the caller and have same section from two included call paths. ai, aj : formal variables, same section, call_path(ai) (is) include(s/d) call_path(aj); add alias association for fi with call_path = path_formal(ai)
Case 5. Actual argument is a formal variable that has same section with other actual argument that is a common variable:
5.1 If ai is the formal variable => add alias association for fi with call_path = path_formal(ai) + (C,ordering)
5.2 If ai is the common variable => add alias association for fi with call_path = (C,ordering)
To compute the offset, we do not use preconditions that may be corrupted by alias violation
Definition at line 158 of file alias_propagation.c.
Correspond to different cases of alias, we make the following groups and order : Case 3. list_of_same_or_equivalence_arguments Case 1 + Case 5.2. common variable Case 2 + Case 4 + Case 5.1. formal variable
To distinguish between equivalence or same argument cases
Definition at line 794 of file alias_propagation.c.
References alias_associations_list, call_arguments, call_function, call_site_consistent_p(), caller_name, common_is_visible_p(), CONS, current_caller, current_mod, db_get_memory_resource(), ENTITY, entity_storage, EXPRESSION, expression_reference(), expression_reference_p(), find_ith_formal_parameter(), FOREACH, formal_variable_add_aliases(), fprintf(), gen_free_list(), gen_full_copy_list(), gen_length(), ifdebug, INT, l_traversed, list_of_same_or_equivalence_arguments(), make_call_site(), MAP, message_assert, NIL, pips_debug, print_statement(), ram_section, ram_variable_add_aliases(), reference_indices, reference_variable, same_or_equivalence_argument_add_aliases(), same_section_formal_variable_in_list_p(), statement_ordering, storage_formal_p, storage_ram, subscript_value_stride(), variable_in_common_p(), and variable_in_list_p().
Referenced by add_aliases_for_current_caller().
|
static |
Definition at line 870 of file alias_propagation.c.
References add_aliases_for_current_call_site(), call_domain, caller_name, db_get_memory_resource(), gen_multi_recurse(), gen_null(), reset_ordering_to_statement(), set_ordering_to_statement(), and statement_domain.
Referenced by alias_propagation_callers().
bool alias_propagation | ( | char * | module_name | ) |
No alias for main program
If the current module is never called by the main program => don't need to compute aliases for this module
search for formal parameters in the declaration list
if there is no formal parameter, do nothing
Take the list of callers, if there is no caller, do nothing
The module has no caller => don't need to compute aliases for this module
save to resource
module_name | odule_name |
Definition at line 903 of file alias_propagation.c.
References alias_propagation_callers(), callees_callees, caller_name, code_declarations, CONS, current_mod, db_get_memory_resource(), DB_PUT_MEMORY_RESOURCE, debug_off, debug_on, display_alias_propagation_statistics(), ENTITY, entity_code(), entity_main_module_p(), entity_undefined, formal_parameter_p(), fprintf(), gen_nconc(), get_bool_property(), ifdebug, local_name_to_top_level_entity(), make_alias_associations(), MAP, module_is_called_by_main_program_p(), module_name(), NIL, number_of_processed_modules, pips_debug, pips_user_warning, print_entities(), reset_current_module_entity(), set_current_module_entity(), and STRING.
Traverse each caller and add aliases to the list of aliases (l_current_aliases)
If the current caller is never called by the main program => no need to follow this caller
Definition at line 884 of file alias_propagation.c.
References add_aliases_for_current_caller(), caller_name, current_caller, get_bool_property(), l_current_aliases, local_name_to_top_level_entity(), MAP, module_is_called_by_main_program_p(), module_local_name(), NIL, pips_user_warning, and STRING.
Referenced by alias_propagation().
This function tests if a common com (TOP_LEVEL:~FOO) is visible in the module mod or in at least one callee (direct and indirect) of this module.
search for the common declaration in the list
search for the common declaration in the callees
Definition at line 466 of file alias_propagation.c.
References callees_callees, code_declarations, current_callee, db_get_memory_resource(), ENTITY, entity_code(), entity_main_module_p(), entity_storage, local_name_to_top_level_entity(), MAP, module_local_name(), ram_section, same_entity_p(), storage_ram, storage_ram_p, and STRING.
Referenced by add_aliases_for_current_call_site(), and formal_variable_add_aliases().
|
static |
Special alias section counter.
Definition at line 176 of file alias_propagation.c.
References number_of_alias_associations, number_of_known_offsets, number_of_processed_modules, number_of_unknown_offsets, and user_log().
Referenced by alias_propagation().
|
static |
a gen_full_copy_list here is to copy the list and its contain without this : gen_write => gen_trav ....=> bug unknown type 1 because the CDR of path point to a newgen data in the caller which is freed before , no more in the memory
To be modified : init_off = lower_offset ...
If offset of aa is not expression_undefined, we must translate it to the module's frame by using binding information
We must translate the subscript value from current caller to the current module's frame by using binding information. This value must be multiplied by the size of array element (number of numerical/character storage units, according to Fortran standard, in PIPS 1 storage unit=1 byte)
init_off <= off <= init_off + SizeOfArray - SizeOfElement (no bound violation ;-))
Definition at line 583 of file alias_propagation.c.
References ALIAS_ASSOCIATION, alias_association_call_chain, alias_association_consistent_p(), alias_association_offset, alias_association_section, alias_association_undefined, alias_association_variable, alias_associations_list, array_entity_p(), binary_intrinsic_expression, CALL_SITE, caller_name, common_is_visible_p(), CONS, copy_expression(), current_caller, current_mod, db_get_memory_resource(), entity_name, entity_special_area_p(), entity_type, expression_constant_p(), expression_equal_integer_p(), expression_to_int(), expression_undefined, expression_undefined_p, fprintf(), gen_full_copy_list(), gen_nconc(), ifdebug, l_current_aliases, make_alias_association(), MAP, message_assert, NIL, number_of_alias_associations, number_of_known_offsets, number_of_unknown_offsets, pips_debug, PLUS_OPERATOR_NAME, print_alias_association(), print_expression(), same_entity_p(), same_section_common_variable_in_list_p(), same_section_formal_variable_in_list_p(), SizeOfArray(), SizeOfElements(), translate_to_module_frame(), type_variable, and variable_basic.
Referenced by add_aliases_for_current_call_site().
Definition at line 693 of file alias_propagation.c.
References CONS, entities_may_conflict_p(), ENTITY, exp, expression_reference(), expression_reference_p(), find_ith_argument(), gen_length(), int, INT, l_traversed, NIL, ref, reference_variable, same_entity_p(), and variable_in_common_p().
Referenced by add_aliases_for_current_call_site().
|
static |
The offset of actual variable is an integer that can always be translated into the module's frame
We must translate the subscript value from current caller to the current module's frame by using binding information. This value must be multiplied by the size of array element (number of numerical/character storage units, according to Fortran standard, in PIPS 1 storage unit=1 byte)
subval is translated to the module's frame
Attention: normalization of an expression equal to 0 returns a Pvecteur null
initial_off <= off <= initial_off + SizeOfArray - SizeOfElement (no bound violation ;-))
Definition at line 394 of file alias_propagation.c.
References ALIAS_ASSOCIATION, alias_association_consistent_p(), alias_association_undefined, array_entity_p(), binary_intrinsic_expression, CALL_SITE, CONS, copy_expression(), current_caller, current_mod, entity_name, entity_storage, entity_type, expression_equal_integer_p(), expression_undefined, expression_undefined_p, fprintf(), gen_nconc(), ifdebug, int_to_expression(), l_current_aliases, make_alias_association(), message_assert, NIL, number_of_alias_associations, number_of_known_offsets, number_of_unknown_offsets, PLUS_OPERATOR_NAME, print_alias_association(), print_expression(), ram_offset, ram_section, SizeOfArray(), SizeOfElements(), storage_ram, translate_to_module_frame(), type_variable, and variable_basic.
Referenced by add_aliases_for_current_call_site(), and same_or_equivalence_argument_add_aliases().
|
static |
Add alias_association for each formal variable whose offset is in the list l.
The offset of the actual variable is an integer that can always be translated into the module's frame
0 <= off <= 0 + array_size_stride (no bound violation ;-))
Definition at line 719 of file alias_propagation.c.
References ALIAS_ASSOCIATION, alias_association_consistent_p(), alias_association_undefined, ALIAS_SECTION, array_entity_p(), CALL_SITE, concatenate(), CONS, current_caller, current_mod, entity_type, expression_equal_integer_p(), expression_reference(), expression_undefined, expression_undefined_p, find_ith_argument(), find_ith_formal_parameter(), FindOrCreateEntity(), fprintf(), free(), gen_nconc(), ifdebug, INT, int2a(), int_to_expression(), l_current_aliases, make_alias_association(), MAP, message_assert, NIL, number_of_alias_associations, number_of_known_offsets, number_of_unknown_offsets, print_alias_association(), print_expression(), ram_variable_add_aliases(), reference_indices, reference_variable, SizeOfArray(), SizeOfElements(), strdup(), subscript_value_stride(), TOP_LEVEL_MODULE_NAME, translate_to_module_frame(), type_variable, unique_section_number, and variable_basic.
Referenced by add_aliases_for_current_call_site().
Definition at line 547 of file alias_propagation.c.
References entity_storage, exp, EXPRESSION, expression_reference(), expression_reference_p(), MAP, pips_debug, ram_section, ref, reference_variable, same_entity_p(), storage_ram, and variable_in_common_p().
Referenced by formal_variable_add_aliases().
|
static |
INCLUDED CALL CHAIN ????????
Definition at line 504 of file alias_propagation.c.
References ALIAS_ASSOCIATION, alias_association_call_chain, alias_association_section, alias_association_variable, entity_storage, exp, EXPRESSION, expression_reference(), expression_reference_p(), included_call_chain_p(), MAP, pips_debug, ref, reference_variable, same_entity_p(), and storage_formal_p.
Referenced by add_aliases_for_current_call_site(), and formal_variable_add_aliases().
expression translate_to_module_frame | ( | entity | mod1, |
entity | mod2, | ||
expression | e1, | ||
call | c | ||
) |
This function translates an expression e1 from the frame of module 1 to the frame of module 2 1.If e1 is a reference:
1.1.
Common variable in mod1 => return corresponding common variable e2 in mod2 1.2. Special case : e1 is a formal parameter in mod1, mod2 is caller of mod1 => take corresponding actual argument e2 in call c 1.3. From the association information, if we have e1 = e2 where e2 is constant or contains variables of the mod2 => return e2 2.If e1 is a call : 2.1. Storage rom : numerical constant or symbolic value (PARAMETER) => return e1 2.2. Recursive : e1 = ex1 * ey1 ex2 = translate_to_module_frame(mod1,mod2,ex1,c) ey2 = translate_to_module_frame(mod1,mod2,ey1,c)
=> return e2=ex2*ey2 3.If e1 is a range : error
Return expression_undefined if we can not translate
Check if the common variable is also declared in the mod2 or not We can use ram_shared which contains a list of aliased variables with en but it does not work ????
Another way : looking for a variable in the declaration of the mod2 that has the same offset in the same common block
ATTENTION : enti may be an array, such as A(2): COMMON C1,C2,C3,C4,C5 COMMON C1,A(2,2) we must return A(1,1), not A
Special case : e1 is a formal parameter in mod1, mod2 is caller of mod1 miss a check : mod2 = caller of mod1 => can be wrong !!!
Use the association of the call site: Take only the equalities. Project all variables belonging to mod1 , except the current variable e1 there are 2 cases :
Look for equality that contain e1 Delete e1 from the vector Check if the remaining of the vectors contains only constant (TCTS) or variables of mod2 => return
Attention : here the transformer binding_context is consistent but not the system ps_tmp. I do not understand why ? fprintf(stderr, "consistent psystem ps_tmp before"); pips_assert("consistent psystem ps_tmp", sc_consistent_p(ps_tmp));
Take only the equations of the system
he coefficient of e is 1 or -1. Check if the remaining vector contains only constant or variavbles of mod2
Numerical constant or symbolic value (PARAMETER)
e1 is a call, not a constant Recursive : with the arguments of the call As our generated expression e1 is a call with operators : +,-,* only, we treat only these cases
mod1 | od1 |
mod2 | od2 |
e1 | 1 |
Definition at line 202 of file alias_propagation.c.
References array_entity_p(), Ssysteme::base, base_contains_variable_p(), call_arguments, call_function, CAR, CDR, clean_all_normalized(), code_declarations, contraintes_free(), Ssysteme::egalites, ENTITY, entity_code(), entity_local_name(), entity_module_name(), entity_storage, entity_to_expression(), entity_type, EXPRESSION, expression_equal_integer_p(), expression_syntax, expression_undefined, expression_undefined_p, find_ith_argument(), formal_and_actual_parameters_association(), formal_offset, gen_length(), ifdebug, Ssysteme::inegalites, is_syntax_call, is_syntax_reference, make_list_of_constant(), make_reference(), MakeBinaryCall(), MakeUnaryCall(), MAP, module_local_name(), Ssysteme::nb_ineq, NIL, NORMALIZE_EXPRESSION, normalized_linear, normalized_linear_p, pips_debug, pips_internal_error, predicate_system, print_expression(), Pvecteur_to_expression(), ref, reference_to_expression(), reference_variable, same_entity_p(), same_scalar_location_p(), sc_dup(), sc_rm(), storage_formal, Scontrainte::succ, Svecteur::succ, syntax_call, syntax_reference, syntax_tag, TCST, transformer_identity(), transformer_relation, type_variable, value_mone_p, VALUE_ONE, value_one_p, Svecteur::var, var_of, variable_dimensions, variable_in_common_p(), variable_is_a_module_formal_parameter_p(), vect_add_elem(), vect_chg_sgn(), vect_coeff(), vect_contains_variable_p(), vect_del_var(), vect_rm(), Scontrainte::vecteur, VECTEUR_NUL, VECTEUR_NUL_P, VECTEUR_UNDEFINED, VECTEUR_UNDEFINED_P, and vecteur_var.
Referenced by alias_check_array_and_scalar_variable_in_caller_flt(), alias_check_array_variable_in_caller_flt(), alias_check_scalar_and_array_variables_in_caller(), alias_check_two_array_variables_in_caller(), formal_variable_add_aliases(), interprocedural_abc_arrays(), ram_variable_add_aliases(), and same_or_equivalence_argument_add_aliases().
|
static |
Definition at line 167 of file alias_propagation.c.
Referenced by add_aliases_for_current_call_site(), add_aliases_for_current_caller(), alias_propagation(), alias_propagation_callers(), and formal_variable_add_aliases().
|
static |
Definition at line 166 of file alias_propagation.c.
Referenced by add_aliases_for_current_call_site(), alias_propagation_callers(), formal_variable_add_aliases(), ram_variable_add_aliases(), and same_or_equivalence_argument_add_aliases().
|
static |
Define a static stack and related functions to remember the current statement.
Definition at line 165 of file alias_propagation.c.
Referenced by add_aliases_for_current_call_site(), alias_propagation(), formal_variable_add_aliases(), ram_variable_add_aliases(), and same_or_equivalence_argument_add_aliases().
Definition at line 168 of file alias_propagation.c.
Referenced by alias_propagation_callers(), formal_variable_add_aliases(), ram_variable_add_aliases(), and same_or_equivalence_argument_add_aliases().
Definition at line 169 of file alias_propagation.c.
Referenced by add_aliases_for_current_call_site(), and list_of_same_or_equivalence_arguments().
|
static |
Definition at line 170 of file alias_propagation.c.
Referenced by display_alias_propagation_statistics(), formal_variable_add_aliases(), ram_variable_add_aliases(), and same_or_equivalence_argument_add_aliases().
|
static |
Definition at line 172 of file alias_propagation.c.
Referenced by display_alias_propagation_statistics(), formal_variable_add_aliases(), ram_variable_add_aliases(), and same_or_equivalence_argument_add_aliases().
|
static |
Definition at line 173 of file alias_propagation.c.
Referenced by alias_propagation(), and display_alias_propagation_statistics().
|
static |
Definition at line 171 of file alias_propagation.c.
Referenced by display_alias_propagation_statistics(), formal_variable_add_aliases(), ram_variable_add_aliases(), and same_or_equivalence_argument_add_aliases().
|
static |
Definition at line 174 of file alias_propagation.c.
Referenced by same_or_equivalence_argument_add_aliases().