PIPS
|
#include <stdlib.h>
#include <stdio.h>
#include <math.h>
#include <limits.h>
#include <string.h>
#include "genC.h"
#include "misc.h"
#include "linear.h"
#include "ri.h"
#include "effects.h"
#include "dg.h"
#include "graph.h"
#include "ri-util.h"
#include "prettyprint.h"
#include "effects-util.h"
#include "text-util.h"
#include "effects-generic.h"
#include "effects-convex.h"
#include "arithmetique.h"
#include "matrice.h"
#include "tiling.h"
#include "wp65.h"
Go to the source code of this file.
Typedefs | |
typedef dg_arc_label | arc_label |
Code Generation for Distributed Memory Machines. More... | |
typedef dg_vertex_label | vertex_label |
typedef dg_arc_label arc_label |
Code Generation for Distributed Memory Machines.
Define and allocate local variables as well as emulated shared variables
File: variable.c
PUMA, ESPRIT contract 2701
Francois Irigoin, Corinne Ancourt, Lei Zhou 1991
Definition at line 54 of file variable.c.
typedef dg_vertex_label vertex_label |
Definition at line 55 of file variable.c.
entity find_or_create_emulated_shared_variable | ( | entity | v, |
entity | memory_module, | ||
hash_table | v_to_esv, | ||
int | bn, | ||
int | ls | ||
) |
nothing to do
memory_module | emory_module |
v_to_esv | _to_esv |
bn | n |
ls | s |
Definition at line 284 of file variable.c.
References concatenate(), EMULATED_SHARED_MEMORY_PREFIX, entity_domain, entity_local_name(), entity_undefined, gen_find_tabulated(), hash_put(), make_emulated_shared_variable(), and MODULE_SEP_STRING.
Referenced by loop_nest_to_local_variables().
void loop_nest_to_local_variables | ( | entity | initial_module, |
entity | compute_module, | ||
entity | memory_module, | ||
hash_table | llv_to_lcr, | ||
hash_table | r_to_llv, | ||
hash_table | v_to_lllv, | ||
hash_table | r_to_ud, | ||
hash_table | v_to_esv, | ||
hash_table | v_to_nlv, | ||
list | lpv, | ||
statement | body, | ||
Pbase | indices, | ||
graph | dg, | ||
int | bn, | ||
int | ls, | ||
int | pd, | ||
tiling | tile | ||
) |
for the phi variable
variable.c
loop_nest_to_local_variables():
Key function allocating local copies according to interferences between references. It also gather information about references (which is also indirectly available in the effect information), allocate emulated shared variables, and create different mappings between local variables and references.
pips_assert("loop_nest_to_local_variables", instruction_block_p(instr));
first reference in statement s
there are only two expressions to loop over: the lhs and the rhs
FI: local variable dimensions should be set later by the caller so as to use the clustering performed here to compute space complexity, to use space complexity to define the tiling and to use the tiling to define the dimensions
initial_module | nitial_module |
compute_module | loop_nest_to_local_variables(): |
Key function allocating local copies according to interferences between references. It also gather information about references (which is also indirectly available in the effect information), allocate emulated shared variables, and create different mappings between local variables and references. initial module: achtung, this arg. is not used!?!
memory_module | loop_nest_to_local_variables(): |
Key function allocating local copies according to interferences between references. It also gather information about references (which is also indirectly available in the effect information), allocate emulated shared variables, and create different mappings between local variables and references. compute module
llv_to_lcr | loop_nest_to_local_variables(): |
Key function allocating local copies according to interferences between references. It also gather information about references (which is also indirectly available in the effect information), allocate emulated shared variables, and create different mappings between local variables and references. memory module
r_to_llv | loop_nest_to_local_variables(): |
Key function allocating local copies according to interferences between references. It also gather information about references (which is also indirectly available in the effect information), allocate emulated shared variables, and create different mappings between local variables and references. local variable to list of conflicting references
v_to_lllv | loop_nest_to_local_variables(): |
Key function allocating local copies according to interferences between references. It also gather information about references (which is also indirectly available in the effect information), allocate emulated shared variables, and create different mappings between local variables and references. reference to list of local variables
r_to_ud | loop_nest_to_local_variables(): |
Key function allocating local copies according to interferences between references. It also gather information about references (which is also indirectly available in the effect information), allocate emulated shared variables, and create different mappings between local variables and references. variable to list of lists of local variables
v_to_esv | loop_nest_to_local_variables(): |
Key function allocating local copies according to interferences between references. It also gather information about references (which is also indirectly available in the effect information), allocate emulated shared variables, and create different mappings between local variables and references. reference to use def
v_to_nlv | loop_nest_to_local_variables(): |
Key function allocating local copies according to interferences between references. It also gather information about references (which is also indirectly available in the effect information), allocate emulated shared variables, and create different mappings between local variables and references. variable to emulated shared variable
lpv | loop_nest_to_local_variables(): |
Key function allocating local copies according to interferences between references. It also gather information about references (which is also indirectly available in the effect information), allocate emulated shared variables, and create different mappings between local variables and references. variable to number of associated local variables (local to this procedure)
body | loop_nest_to_local_variables(): |
Key function allocating local copies according to interferences between references. It also gather information about references (which is also indirectly available in the effect information), allocate emulated shared variables, and create different mappings between local variables and references. private variables
indices | ndices |
dg | g |
bn | n |
ls | s |
pd | d |
tile | ile |
Definition at line 80 of file variable.c.
References assignment_statement_p(), bool_to_string(), call_arguments, CAR, CONS, debug(), dg, ENDP, entity_is_argument_p(), entity_local_name(), EXPRESSION, expression_to_reference_list(), find_or_create_emulated_shared_variable(), fprintf(), gen_free_list(), hash_get(), hash_put(), HASH_UNDEFINED_VALUE, ifdebug, indices, instruction_block, instruction_call, instruction_call_p, intptr_t, is_action_read, is_action_write, make_new_local_variables(), NIL, pips_assert, POP, print_entities(), print_reference_list(), REFERENCE, reference_conflicting_test_and_update(), reference_indices, reference_variable, set_dimensions_of_local_variables(), STATEMENT, and statement_instruction.
Referenced by loop_nest_to_wp65_code().
filled in the following
filled in the following
generate the proper type; basic is preserved but the array is made two dimensional
In two sprintf , -1 is added once seperately by LZ make_expression_1 takes the place of the make_expression_1 12/11/91
FI->CA, LZ: what should we do with scalar variables? Put a copy on each memory bank? Take into account memory bank conflicts shown in thresholding (PUMA WP 6.1 and 6.7)
memory_module | emory_module |
bn | n |
ls | s |
Definition at line 195 of file variable.c.
References add_variable_to_area(), AddEntityToDeclarations(), CAR, concatenate(), CONS, copy_basic(), debug(), DIMENSION, dimension_size(), dimension_undefined, DYNAMIC_AREA_LOCAL_NAME, EMULATED_SHARED_MEMORY_PREFIX, ENDP, entity_domain, entity_initial, entity_local_name(), entity_name, entity_storage, entity_type, entity_undefined, FindEntity(), fprintf(), gen_find_tabulated(), ifdebug, int_to_expression(), is_storage_ram, make_dimension(), make_entity, make_ram(), make_storage(), make_value_unknown(), MakeTypeVariable(), module_local_name(), MODULE_SEP_STRING, NIL, number_of_elements(), pips_assert, POP, print_sentence(), Sentence_Variable(), storage_undefined, strdup(), type_undefined, type_variable, type_variable_p, value_undefined, variable_basic, and variable_dimensions.
Referenced by find_or_create_emulated_shared_variable().
list make_new_local_variables | ( | entity | v, |
entity | compute_module, | ||
int | number, | ||
int | pd, | ||
hash_table | v_to_lllv | ||
) |
Local variables cannot be immediately dimensionned because this will depend on all associated references.
To avoid a possible "fusion" between references connected in the dg, local variable declarations should be delayed to that point.
concatenate cannot be used (directly) because of n and s conversions
a new btv is necessary for each variable because CONS cannot be shared under NewGen rules
FI->LZ: the type should be v's type, except for the dimensions, the storage should be RAM and allocated in the dynamic area of module_name, and the value is undefined; the actual dimensions will be updated later
update v_to_lllv by side effect
compute_module | ompute_module |
number | umber |
pd | local copy number |
v_to_lllv | pipeline depth |
Definition at line 310 of file variable.c.
References add_variable_to_area(), AddEntityToDeclarations(), asprintf, CONS, copy_basic(), debug(), DYNAMIC_AREA_LOCAL_NAME, ENTITY, entity_local_name(), entity_name, entity_storage, entity_type, entity_undefined_p, FindEntity(), gen_nconc(), hash_get(), hash_put(), HASH_UNDEFINED_VALUE, is_storage_ram, LIST, LOCAL_MEMORY_PREFIX, LOCAL_MEMORY_SEPARATOR, make_entity, make_ram(), make_storage(), MakeTypeVariable(), module_local_name(), MODULE_SEP_STRING, NIL, pips_assert, storage_undefined, type_variable, value_undefined, and variable_basic.
Referenced by loop_nest_to_local_variables().
Psysteme make_tile_constraints(P, b):
convert a partitioning matrice into a system of linear constraints for a tile whose origin is 0, i.e. generate constraints over local indices:
-> -1 -> -—> 0 <= k P b <= (k-1)
where k is the denominator of P inverse.
FI: such functions should be put together in a file, linear.c
pips_assert("make_tile_constraints", k > 1);
Definition at line 591 of file variable.c.
References ACCESS, base_dimension, contrainte_chg_sgn(), contrainte_dup(), contrainte_new(), contrainte_vecteur, debug(), DENOMINATOR, entity_local_name(), fprintf(), ifdebug, matrice_fprint(), matrice_free, matrice_general_inversion(), matrice_new, matrice_normalize(), pips_assert, sc_add_inegalite(), sc_creer_base(), sc_fprint(), sc_new(), tc, TCST, value_minus, VALUE_ONE, value_one_p, value_uminus, variable_of_rank(), and vect_add_elem().
Referenced by set_dimensions_of_local_variables().
r1 | 1 |
r2 | 2 |
dg | g |
Definition at line 513 of file variable.c.
References CAR, CONFLICT, conflict_sink, conflict_source, debug(), dg, dg_arc_label_conflicts, effect_any_reference, fprintf(), graph_vertices, ifdebug, MAPL, print_reference(), reference_equal_p(), SUCCESSOR, successor_arc_label, VERTEX, and vertex_successors.
Referenced by reference_conflicting_test_and_update().
bool reference_conflicting_test_and_update | ( | reference | r, |
graph | dg, | ||
hash_table | v_to_lllv, | ||
hash_table | llv_to_lcr, | ||
hash_table | r_to_llv, | ||
hash_table | r_to_ud | ||
) |
reference_conflicting_test_and_update():
Build, incrementally, connected component in the dependence graph. Input dependences should be used to save local memory space. Mappings are updated.
Too many local variables might be created if two connected components had to be fused. This is not likely to happen with real code. In that case, the function would stop with pips_error().
referenced variable
short cut for identical references; not necessarily a good idea for the body translation process; design to save time in transfer code generation
should go one step forwards and take care of use-def, easier by introducing a "use and def" value or by adding the new reference directly
we need to remember there is a use and a def
this is very clumsy as we may keep a large number of identical def after one use and vice-versa; we need a use-and-def value or we have to keep all references and filter them for data movements
update llv_to_lcr by side-effect
should not happen too often: the regions associated with two references do not intersect together but each of them intersect a third one on which we bump afterwards; the two initial llv's should be merged...
update llv_to_lcr by side-effect
save current_llv for a future (?) merge
no need to study conflicts with other references in the same connected component
dg | g |
v_to_lllv | _to_lllv |
llv_to_lcr | lv_to_lcr |
r_to_llv | _to_llv |
r_to_ud | _to_ud |
Definition at line 401 of file variable.c.
References CAR, CONS, debug(), dg, ENDP, entity_local_name(), fprintf(), gen_nconc(), hash_get(), hash_put(), HASH_UNDEFINED_VALUE, ifdebug, LIST, list_undefined, NIL, pips_assert, pips_internal_error, POP, print_reference(), REFERENCE, reference_conflicting_p(), reference_equal_p(), and reference_variable.
Referenced by loop_nest_to_local_variables().
void set_dimensions_of_local_variable_family | ( | list | llv, |
Psysteme | tc, | ||
list | lr, | ||
tiling | tile, | ||
int | dimn | ||
) |
void set_dimensions_of_local_variable_family(llv, tc, lr):
The algorithm used is not general; references are assumed equal up to a translation;
A general algorithm, as would be necessary for instance if a dependence was detected in the transposition algorithm between M(I,J) and M(J,I), would preserve some translation information for each reference in lr so as to generate proper new references to the local variable.
let's use the first reference to find out the number of dimensions
referenced variable
referenced variable type
referenced variable dimension list
dimension number
dimensions for the local variables
computation of the initial bounds of Entity rv
pips_assert("set_dimensions_of_local_variable_family",
pour tenir compte des offsets numeriques dans les fonctions d'acces
parameter ==> min = max = 1
ips_internal_error("unbounded domain for phi, %s", "check tile bounds and subscript expressions");
update types
sharing is not legal under NewGen rules; to avoid it lvd is duplicated at the CONS level, except the first time
llv | lv |
tc | The algorithm used is not general; references are assumed equal up to a translation; |
A general algorithm, as would be necessary for instance if a dependence was detected in the transposition algorithm between M(I,J) and M(J,I), would preserve some translation information for each reference in lr so as to generate proper new references to the local variable. list of local variables with same dimensions used at different pipeline stages
lr | r |
tile | The algorithm used is not general; references are assumed equal up to a translation; |
A general algorithm, as would be necessary for instance if a dependence was detected in the transposition algorithm between M(I,J) and M(J,I), would preserve some translation information for each reference in lr so as to generate proper new references to the local variable. non-empty list of associated references
dimn | imn |
Definition at line 689 of file variable.c.
References ACCESS, CAR, CONS, contrainte_make(), debug(), DIMENSION, dimension_lower, dimension_undefined, dimension_upper, ENDP, ENTITY, entity_local_name(), entity_name, entity_type, find_ith_expression(), fprintf(), gen_copy_seq(), gen_nconc(), ifdebug, int_to_expression(), list_undefined, make_dimension(), make_phi_entity(), MAPL, max, min, NIL, NORMALIZE_EXPRESSION, normalized_linear, normalized_linear_p, pips_debug, pips_internal_error, POP, print_sentence(), REFERENCE, reference_indices, reference_variable, sc_add_egalite(), sc_dup(), sc_fprint(), sc_minmax_of_variable(), sc_normalize(), Sentence_Variable(), tc, TCST, tiling_tile, type_variable, value_addto, VALUE_CONST, value_decrement, value_div, value_gt, value_lt, VALUE_MAX, value_max, value_max_p, VALUE_MIN, value_min, value_min_p, VALUE_MONE, VALUE_ONE, value_pos_p, VALUE_TO_INT, VALUE_ZERO, variable_dimensions, vect_add_elem(), vect_add_variable(), vect_coeff(), and vect_dup().
Referenced by set_dimensions_of_local_variables().
void set_dimensions_of_local_variables | ( | hash_table | v_to_lllv, |
Pbase | basis, | ||
tiling | tile, | ||
hash_table | llv_to_lcr | ||
) |
v_to_lllv | _to_lllv |
basis | asis |
tile | ile |
llv_to_lcr | lv_to_lcr |
Definition at line 652 of file variable.c.
References CAR, debug(), ENDP, hash_get(), HASH_MAP, LIST, make_tile_constraints(), POP, sc_rm(), set_dimensions_of_local_variable_family(), tc, tiling_tile, and vect_size().
Referenced by loop_nest_to_local_variables().