PIPS
|
#include "local.h"
Go to the source code of this file.
Macros | |
#define | GRAPH_IS_DFG |
Name : array_dfg.c Package : array_dfg Author : Arnauld LESERVOT Date : 93/06/27 Modified : Documents: Platonoff's thesis and Leservot's thesis "Dataflow Analysis of Array and Scalar References" P. More... | |
#define | NEXT(cp) (((cp) == NIL) ? NIL : (cp)->cdr) |
Local defines. More... | |
Functions | |
bool | my_sc_faisabilite (Psysteme in_ps) |
graph | adg_dataflowgraph (statement mod_stat, statement_mapping stco_map, graph dup_dg) |
====================================================================== More... | |
boolean | array_dfg (char *mod_name) |
====================================================================== More... | |
Variables | |
hash_table | Gvertex_number_to_statement |
Global variables. More... | |
int | Gcount_re |
External variables. More... | |
int | Gcount_ie |
statement_mapping | Gstco_map |
list | Gstructural_parameters |
int | my_pip_count |
int | my_fai_count |
static hash_table | Gforward_substitute_table |
#define GRAPH_IS_DFG |
Name : array_dfg.c Package : array_dfg Author : Arnauld LESERVOT Date : 93/06/27 Modified : Documents: Platonoff's thesis and Leservot's thesis "Dataflow Analysis of Array and Scalar References" P.
FEAUTRIER Comments :
Definition at line 37 of file array_dfg.c.
Local defines.
Definition at line 41 of file array_dfg.c.
graph adg_dataflowgraph | ( | statement | mod_stat, |
statement_mapping | stco_map, | ||
graph | dup_dg | ||
) |
======================================================================
graph adg_dataflowgraph( (statement) module_statement, (statement_mapping) static_control_map, (graph) reversed_dg ) AL 93/07/01 To compute the Array Data Flow Graph, we need : code, static_control, dependance_graph.
Return dfg graph
Return list of vertices
Initialization to have an entry node
We first put entry node in the return list
We run over each vertex of the input graph
Get destination vertex and information linked to it
We search for all the read effects of vertex dest_ver and try to find the source for each read effect in dest_ver.
For debug purpose
Get the current read_effect of destination
For debug purpose
Search for successors (in fact predecessors : input graph is reversed compared to dg graph !) that write the dest_read_eff and put their vertices in sou_l. Then, order them by decreasing order of stat. number.
No sources : Comes from Entry point
Debugging
Build the source leaf label list sou_lll. This list of leaf labels links a vertex number and a depth.
Explode candidates for each depth and then, build the candidate list cand_l by decreasing order.
we will reuse it after
We run over all possible candidates and compute to see how it could contribute to the source
Get possible source vertex and informations linked to it
If this candidate is not possible, see the next. Two cases : candidate and destination are in the same deepest loop and dest is before candidate ; or candidate is not valid with the present source.
Not a possible source => get the next candidate
will be reuse ?
For debug purpose
Get the f(u) = g(b) psystem We first duplicate arguments expressions, then we rename entities that are at a deeper depth than sou_d and forward subsitute those new entities in the expressions
Rename entities at rank > sou_d and update Gforward_substitute_table
Make corresponding indices equal in source and dest F(u) = g(b) and put it in sou_ps.
Build the sequencing predicate
compute indice1 + indice2 + 1
append at the end p.s. of source to those of dest. Concatenate the three lists to build Psys. according to the order : source-variables,sink-variables,struc.params
Build source Psysteme (IF and DO contraints). Build the context and rename variables .
Get predicate that comes from an IF statement
Get predicate that comes from enclosing DO
Rename entities in the source context system
Append sous_ps (F(u) = g(b) and seq. predicate) with prov_ps (IF and DO constraints).
Compute the new candidate source. We try to call PIP only if necesary.
If there is no condition on source...
Order the psysteme according to ent_l
Find the new source and simplify it
Fill "quast_undefined" part of the source with ENTRY node.
Build the new Data Flow Graph with the new source
Definition at line 70 of file array_dfg.c.
References ADD_ELEMENT_TO_LIST, adg_compact_quast(), adg_decreasing_stat_order_sort(), adg_enrichir(), adg_fill_with_quast(), adg_get_loop_indices(), adg_get_predicate_of_loops(), adg_is_textualy_after_p(), adg_list_to_vect(), adg_merge_entities_lists(), adg_number_of_same_loops(), adg_number_to_ordering(), adg_number_to_statement(), adg_number_to_vertex(), adg_path_max_source(), adg_path_possible_source(), adg_rename_entities(), adg_same_dfg_vertex_number(), adg_sc_dup(), adg_sc_update_base(), adg_suppress_2nd_in_1st_ps(), adg_update_dfg(), adg_vertex_to_statement(), adg_write_reference_list(), Ssysteme::base, call_arguments, CAR, CONS, contrainte_make(), CONTRAINTE_UNDEFINED, copy_expression(), debug(), dfg_vertex_label_exec_domain, dfg_vertex_label_statement, EFFECT, effect_any_reference, ENDP, ENTITY, ENTRY_ORDER, EXPRESSION, EXPRESSION_PVECTEUR, expression_syntax, forward_substitute_in_exp(), fprint_psysteme(), fprintf(), gen_append(), gen_length(), gen_nth(), get_debug_level(), GET_STATEMENT_MAPPING, Gforward_substitute_table, graph_undefined, graph_vertices, Gvertex_number_to_statement, HASH_MAP, hash_pointer, hash_put(), hash_table_free(), hash_table_make(), if(), imprime_special_quast(), instruction_call, is_quast_value_conditional, is_quast_value_quast_leaf, LEAF_LABEL, leaf_label_depth, leaf_label_statement, list_to_base(), make_conditional(), make_dfg_vertex_label(), make_graph(), make_leaf_label(), make_predicate(), make_quast(), make_quast_leaf(), make_quast_value(), make_vertex(), my_pip_count, my_sc_faisabilite(), NIL, pa_empty_p(), pa_full(), PA_UNDEFINED_P, Sposs_source::pat, pip_integer_max(), pips_internal_error, POP, predicate_system, predicate_undefined, predicate_undefined_p, print_effects, print_statement(), Spath::psys, pu_vect_fprint(), Sposs_source::qua, quast_leaf_undefined, quast_undefined, read_reference_list(), reference_indices, reference_variable, sc_append(), sc_dup(), sc_make(), sc_variable_rename(), sccflags_undefined, sort_psysteme(), statement_instruction, statement_number, statement_ordering, static_control_loops, static_control_params, stco_common_loops_of_statements(), syntax_reference, TAKE_LAST, TCST, VALUE_ONE, vect_add(), vect_new(), vect_substract(), VERTEX, vertex_successors, vertex_undefined, and vertex_vertex_label.
Referenced by array_dfg().
boolean array_dfg | ( | char* | mod_name | ) |
======================================================================
void array_dfg( (char*) module_name ) AL 93/06/29
It computes the array data flow graph using Feautrier's algorithm. This kind of graph detects the real dependances between arrays. It could be computed on a static control program. The original code is prepared by the static_controlize package. See its comments for more details.
summary or not ?
Initialize debugging functions
Initialization of the pass
set current_module_entity to ent ...
If the input program is not a static_control one, return
What will we compute ?
We need the dependance graph for a first source approximation. The graph is first reversed to have the possible source statement. Then we take only the WR dependances. At the end : duplicate nodes "a la Redon" for IF statement.
We reorder the statement number linked to each vertex in order to distinguich duplicated vertices
We compute the core of the pass
End of the program
mod_name | odule |
Definition at line 501 of file array_dfg.c.
References adg_dataflowgraph(), adg_dataflowgraph_with_extremities(), adg_dup_disjunctive_nodes(), adg_only_call_WR_dependence(), adg_pure_dfg(), adg_reorder_statement_number(), adg_reverse_graph(), db_get_memory_resource(), DB_PUT_MEMORY_RESOURCE, debug_off, debug_on, dg, fprint_dfg(), Gcount_ie, Gcount_re, get_debug_level(), GET_STATEMENT_MAPPING, Gstco_map, Gstructural_parameters, local_name_to_top_level_entity(), mod_stat, my_fai_count, my_pip_count, pips_user_error, printf(), reset_current_module_entity(), reset_current_module_statement(), reset_proper_rw_effects(), set_current_module_entity(), set_proper_rw_effects(), static_control_params, static_control_yes, strdup(), SUMMARY, and user_log().
Definition at line 55 of file array_dfg.c.
References my_fai_count, NO_OFL_CTRL, and sc_rational_feasibility_ofl_ctrl().
Referenced by adg_dataflowgraph(), and adg_dataflowgraph_with_extremities().
int Gcount_ie |
Definition at line 46 of file array_dfg.c.
Referenced by adg_get_integer_entity(), and array_dfg().
int Gcount_re |
External variables.
Global variables.
Definition at line 45 of file array_dfg.c.
Referenced by adg_rename_entities(), and array_dfg().
|
static |
Definition at line 53 of file array_dfg.c.
Referenced by adg_dataflowgraph().
statement_mapping Gstco_map |
Definition at line 47 of file array_dfg.c.
Referenced by adg_enrichir(), adg_max_of_leaves(), adg_path_max_source(), adg_path_possible_source(), and array_dfg().
list Gstructural_parameters |
Definition at line 48 of file array_dfg.c.
Referenced by adg_dataflowgraph_with_extremities(), and array_dfg().
|
extern |
Global variables.
Definition at line 42 of file adg_graph.c.
Referenced by adg_dataflowgraph(), adg_number_to_ordering(), adg_reorder_statement_number(), and adg_vertex_to_ordering().
int my_fai_count |
Definition at line 51 of file array_dfg.c.
Referenced by array_dfg(), and my_sc_faisabilite().
int my_pip_count |
Definition at line 50 of file array_dfg.c.
Referenced by adg_dataflowgraph(), adg_dataflowgraph_with_extremities(), and array_dfg().