PIPS
|
#include "local.h"
Go to the source code of this file.
Macros | |
#define | GRAPH_IS_DFG |
Name : adg_graph.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... | |
Functions | |
graph | adg_pure_dfg (graph in_gr) |
====================================================================== More... | |
graph | adg_pure_dfg2 (graph in_gr) |
====================================================================== More... | |
void | adg_print_graph (FILE *fd, statement mod_stat, graph mod_graph) |
====================================================================== More... | |
int | adg_number_to_ordering (int in_nb) |
====================================================================== More... | |
vertex | adg_number_to_vertex (graph in_dfg, int in_nb) |
====================================================================== More... | |
statement | adg_vertex_to_statement (vertex in_ver) |
====================================================================== More... | |
int | adg_vertex_to_ordering (vertex in_ver) |
====================================================================== More... | |
bool | integer_in_list_p (int i, list l) |
=========================================================================== More... | |
void | adg_reorder_statement_number (graph in_dfg) |
====================================================================== More... | |
vertex | adg_same_dfg_vertex_number (list in_l, int in_i) |
====================================================================== More... | |
void | adg_update_dfg (quast in_sou, reference in_ref, vertex in_dest, Ppath in_pa, Psysteme in_context, Psysteme in_test, graph in_gr, list *in_lp) |
====================================================================== More... | |
list | adg_get_exec_domain (static_control stco) |
====================================================================== More... | |
list | adg_same_order_in_dvl (list l, vertex ver) |
====================================================================== More... | |
graph | adg_dup_disjunctive_nodes (graph g, statement_mapping stco_map) |
====================================================================== More... | |
list | adg_write_reference_list (vertex ver, effect reff) |
====================================================================== More... | |
bool | in_effect_list_p (list l, effect eff) |
====================================================================== More... | |
list | read_reference_list (vertex ver, list ent_l1, list ent_l2) |
====================================================================== More... | |
graph | adg_only_call_WR_dependence (graph g) |
====================================================================== More... | |
static effect | effect_dup (effect eff) |
effect effect_dup(effect eff) input : an effect. More... | |
conflict | conflict_dup (conflict conf) |
====================================================================== More... | |
dg_arc_label | dg_arc_label_dup (dg_arc_label dg_al) |
====================================================================== More... | |
dg_vertex_label | dg_vertex_label_dup (dg_vertex_label dg_vl) |
====================================================================== More... | |
vertex | dg_vertex_dup (vertex ver) |
====================================================================== More... | |
list | adg_list_same_order_in_dg (list in_l, vertex in_v) |
====================================================================== More... | |
vertex | adg_same_order_in_dg (list l, vertex v) |
====================================================================== More... | |
graph | adg_reverse_graph (graph g) |
====================================================================== More... | |
Variables | |
int | Gcount_re |
External variables. More... | |
hash_table | Gvertex_number_to_statement |
Global variables. More... | |
hash_table | Gstco_map |
#define GRAPH_IS_DFG |
Name : adg_graph.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 adg_graph.c.
graph adg_dup_disjunctive_nodes | ( | graph | g, |
statement_mapping | stco_map | ||
) |
======================================================================
graph adg_dup_disjunctive_nodes( graph g, statement_mapping stco_map) Input : A dependence graph or a partial one. AL 20/07/93 A static_control mapping on each statement. Output: A graph whose nodes controlled by a disjunctive predicate are duplicated. Labels associated to vertex are dfg_vertex_label whose predicate are set to one of the disjunctive part of the englobing tests. Successors arc-labels are initial dg_arc_label PRIVATE to this pass !!
Do the associated vertices successors exist ?
Does vertex associated to ver exist in the new ver_list ?
Build the new successors list
ssociate a duplicated successor list to each new vertex
Definition at line 581 of file adg_graph.c.
References ADD_ELEMENT_TO_LIST, adg_get_disjunctions(), adg_list_same_order_in_dg(), Ssysteme::base, CAR, copy_dfg_arc_label(), debug(), ENDP, GET_STATEMENT_MAPPING, graph_vertices, int, make_dfg_vertex_label(), make_graph(), make_successor(), make_vertex(), NIL, POP, PREDICATE, predicate_system, predicate_undefined, sc_creer_base(), sccflags_undefined, statement_ordering, static_control_tests, SUCCESSOR, successor_arc_label, successor_vertex, VERTEX, vertex_successors, and vertex_to_statement().
Referenced by array_dfg().
list adg_get_exec_domain | ( | static_control | stco | ) |
======================================================================
list adg_get_exec_domain( static_control stco ) AL 21/07/93 Input : A static_control stco. Output: A list of predicates corresponding to the conditions on enclosing loops combined with enclosing tests. PRIVATE to this pass !!
Get existing predicate for the exec_domain
Definition at line 515 of file adg_graph.c.
References ADD_ELEMENT_TO_LIST, adg_fprint_predicate_list(), adg_get_disjunctions(), adg_get_predicate_of_loops(), adg_make_disjunctions(), debug(), get_debug_level(), make_predicate(), NIL, PREDICATE, predicate_undefined, static_control_loops, and static_control_tests.
======================================================================
list adg_list_same_order_in_dg( (list) in_l, (vertex) in_v ) AL 27/10/93 Input : A list of vertices of a dg and a vertex of this type. Output : All the vertices which associated ordering has same ordering as the one linked to in_v. PRIVATE use !
Definition at line 992 of file adg_graph.c.
References ADD_ELEMENT_TO_LIST, CAR, debug(), ENDP, NIL, POP, statement_ordering, VERTEX, and vertex_to_statement().
Referenced by adg_dup_disjunctive_nodes().
======================================================================
int adg_number_to_ordering( (int) in_nb ) AL 21/10/93 Input : Number of a vertex. Output : The ordering of Statement associated to this vertex. PRIVATE to this pass !!
Definition at line 227 of file adg_graph.c.
References Gvertex_number_to_statement, and hash_get().
Referenced by adg_dataflowgraph(), and adg_number_to_statement().
======================================================================
vertex adg_number_to_vertex( (graph) in_dfg, (int) in_nb ) AL 21/10/93 Input : A graph and a number of a vertex. Output : A vertex which statement number is equal to in_nb. PRIVATE to this pass !!
Definition at line 239 of file adg_graph.c.
References CAR, debug(), dfg_vertex_label_statement, dfg_vertex_label_undefined, ENDP, graph_vertices, POP, VERTEX, vertex_undefined, and vertex_vertex_label.
Referenced by adg_dataflowgraph().
======================================================================
graph adg_only_call_WR_dependence( (graph) g ) AL 06/07/93 Returns a graph from a dependence graph with only Write-Read conflicts and assignements statements.
We only keep call statement
Definition at line 784 of file adg_graph.c.
References action_read_p, action_write_p, ADD_ELEMENT_TO_LIST, adg_same_order_in_dg(), assignment_statement_p(), CAR, CONFLICT, conflict_dup(), conflict_sink, conflict_source, debug(), dfg_vertex_label_statement, dg_arc_label_conflicts, effect_action, ENDP, graph_vertices, make_dg_arc_label(), make_graph(), make_successor(), make_vertex(), NIL, ordering_to_statement(), POP, SUCCESSOR, successor_arc_label, successor_vertex, VERTEX, vertex_successors, vertex_undefined, and vertex_vertex_label.
Referenced by array_dfg().
======================================================================
void adg_print_graph() Prints a dg graph with vertex labels as they are, Do not try to translate vertex label to a statement number.
Definition at line 172 of file adg_graph.c.
References CAR, CDR, cone_generating_system, cone_levels, cone_undefined, CONFLICT, conflict_cone, conflict_sink, conflict_source, dg_arc_label_conflicts, dg_vertex_label_statement, ENDP, entity_local_name(), fprintf(), graph_vertices, INT, MAPL, pl, print_words(), sg_fprint(), SG_UNDEFINED_P, SUCCESSOR, successor_arc_label, successor_vertex, VERTEX, vertex_successors, vertex_vertex_label, and words_effect().
======================================================================
GRAPH FUNCTIONS
====================================================================== ====================================================================== graph adg_pure_dfg( in_gr ) AL 18/02/94
Returns a pure Data Flow Graph : without Entry or Exit Node.
First get entry and exit nodes from in_gr
Then duplicate nodes without exit and entry nodes
If this succ is an extremity, continue
Definition at line 56 of file adg_graph.c.
References ADD_ELEMENT_TO_LIST, adg_same_dfg_vertex_number(), CAR, debug(), dfg_vertex_label_statement, ENDP, ENTRY_ORDER, EXIT_ORDER, graph_vertices, int, make_graph(), make_successor(), make_vertex(), NIL, POP, SUCCESSOR, successor_arc_label, successor_vertex, verlist, VERTEX, vertex_successors, vertex_undefined, and vertex_vertex_label.
Referenced by array_dfg(), prgm_mapping(), print_parallelizedCMF_code(), print_parallelizedCRAFT_code(), scheduling(), and single_assign().
======================================================================
graph adg_pure_dfg2( in_gr ) AL 18/02/94
Returns a pure Data Flow Graph : without Entry or Exit Node.
First remove entry and exit nodes from in_gr
Then remove successors that include exit node
Definition at line 123 of file adg_graph.c.
References ADD_ELEMENT_TO_LIST, CAR, copy_graph(), debug(), dfg_vertex_label_statement, ENDP, ENTRY_ORDER, EXIT_ORDER, gen_remove(), graph_vertices, int, NIL, POP, SUCCESSOR, successor_vertex, VERTEX, vertex_successors, and vertex_vertex_label.
void adg_reorder_statement_number | ( | graph | in_dfg | ) |
======================================================================
void adg_reorder_statement_number( (graph) in_dfg ) AL 21/10/93 Input : A dfg graph with different vertices pointing on the same statement. This is possible due to duplication of vextices whose statement are controled by a disjunction of predicates (See Doc about IF statement). Output : Nothing. Each vertex has a new and distinct number for the statement tag of it dfg_vertex_label tag. PRIVATE to this pass !!
AP, oct 6th 1995: I change the way to choose the new numbers used to reorder
Definition at line 318 of file adg_graph.c.
References BASE_NODE_NUMBER, CAR, CONS, debug(), dfg_vertex_label_statement, dfg_vertex_label_undefined, ENDP, graph_vertices, Gvertex_number_to_statement, hash_int, hash_put(), hash_table_make(), INT, integer_in_list_p(), NIL, num, ordering_to_statement(), POP, statement_number, VERTEX, and vertex_vertex_label.
Referenced by array_dfg().
======================================================================
graph adg_reverse_graph( (graph) g ) AL 29/06/93 This function is used to reverse Pips's graph in order to have all possible sources directly (Feautrier's dependance graph).
Definition at line 1047 of file adg_graph.c.
References ADD_ELEMENT_TO_LIST, adg_same_order_in_dg(), CAR, debug(), dg_arc_label_dup(), graph_vertices, make_graph(), make_successor(), make_vertex(), MAPL, NIL, SUCCESSOR, successor_arc_label, successor_vertex, verlist, VERTEX, vertex_successors, vertex_undefined, and vertex_vertex_label.
Referenced by array_dfg().
======================================================================
vertex adg_same_dfg_vertex_number( (list) in_l, (int) in_i ) AL 27/10/93 Input : A list of vertices and a number in_i. Output : A vertex v in in_l which statement associated to it
has a number equal to in_i. PRIVATE to this pass !!
Definition at line 358 of file adg_graph.c.
References CAR, debug(), dfg_vertex_label_statement, ENDP, POP, VERTEX, vertex_undefined, and vertex_vertex_label.
Referenced by adg_dataflowgraph(), adg_pure_dfg(), and adg_update_dfg().
======================================================================
vertex adg_same_order_in_dg( (list) l, (vertex) v ) AL 30/06/93 Input : A list l of vertices. A vertex v of a dependence graph. Returns vertex_undefined if v is not in list l. Returns v' that has the same statement_ordering than v. COMMON use possible.
Definition at line 1021 of file adg_graph.c.
References CAR, debug(), ENDP, POP, statement_ordering, VERTEX, vertex_to_statement(), and vertex_undefined.
Referenced by adg_only_call_WR_dependence(), and adg_reverse_graph().
======================================================================
list adg_same_order_in_dvl( list l, vertex ver ) AL 21/07/93 Input : A list of vertices, each vertex has an unique ordering according to a statement. A vertex ver of a Data Flow Graph. Its number is not equal to an ordering statement. Output : A list or vertices with same statement ordering as ver. WARNING : Implicitly uses Gvertex_number_to_statement ! PRIVATE to this pass !!
Definition at line 549 of file adg_graph.c.
References ADD_ELEMENT_TO_LIST, adg_vertex_to_ordering(), CAR, debug(), dfg_vertex_label_statement, ENDP, NIL, POP, VERTEX, and vertex_vertex_label.
void adg_update_dfg | ( | quast | in_sou, |
reference | in_ref, | ||
vertex | in_dest, | ||
Ppath | in_pa, | ||
Psysteme | in_context, | ||
Psysteme | in_test, | ||
graph | in_gr, | ||
list* | in_lp | ||
) |
======================================================================
void adg_update_dfg((quast) in_sou,(reference) in_ref, AL 19/10/93 (vertex) in_dest, (Psysteme) in_ps, (list) *in_lp ) Input : A quast, a reference, destination vertex, a predicate representing present control condition, and a list of vertices representing a DFG. Output : Nothing. Just modify the graph *in_lp. See Doc. PRIVATE to this pass !!
Presently, newparms should be empty
if (quast_newparms(in_sou) != NIL)
fprintf(stderr, "\n Newparms list should be presently empty !\n");
Build the new dataflows list of data flow
Update graph
Do pred_v already has in_dest as a successor ?
If not, add to it the correct successor
Definition at line 386 of file adg_graph.c.
References ADD_ELEMENT_TO_LIST, adg_fprint_dataflow(), adg_same_dfg_vertex_number(), adg_sc_update_base(), adg_suppress_2nd_in_1st_ps(), Ssysteme::base, CAR, communication_undefined, conditional_false_quast, conditional_predicate, conditional_true_quast, CONS, DATAFLOW, debug(), dfg_arc_label_dataflows, dfg_vertex_label_exec_domain, dfg_vertex_label_statement, ENDP, ENTRY_ORDER, EXIT_ORDER, gen_nconc(), get_debug_level(), in_dfg_vertex_list(), int, leaf_label_statement, make_dataflow(), make_dfg_arc_label(), make_dfg_vertex_label(), make_predicate(), make_successor(), make_vertex(), NIL, pa_intersect_complement(), pa_intersect_system(), pa_path_to_disjunct, pips_assert, POP, predicate_system, predicate_undefined, Ssyslist::psys, quast_leaf_leaf_label, quast_leaf_solution, quast_quast_value, quast_undefined, quast_value_conditional, quast_value_conditional_p, quast_value_quast_leaf, quast_value_quast_leaf_p, quast_value_undefined, sc_append(), sc_creer_base(), sc_dup(), sc_elim_redund(), sc_empty_p(), sccflags_undefined, Ssyslist::succ, SUCCESSOR, successor_arc_label, successor_vertex, VERTEX, vertex_successors, vertex_undefined, and vertex_vertex_label.
Referenced by adg_dataflowgraph(), and adg_dataflowgraph_with_extremities().
======================================================================
adg_vertex_to_ordering( (vertex) in_ver ) AL 21/10/93 Input : A vertex in_ver Output : ordering of statement associated to in_ver PRIVATE to this pass !!
Definition at line 276 of file adg_graph.c.
References count, debug(), dfg_vertex_label_statement, Gvertex_number_to_statement, hash_get(), int, vertex_undefined, and vertex_vertex_label.
Referenced by adg_same_order_in_dvl(), and adg_vertex_to_statement().
======================================================================
statement adg_vertex_to_statement( (vertex) in_ver ) AL 21/10/93 Input : A vertex in_ver which has been reordered by adg_reorder_statement_number. Output : A statement corresponding to the vertex number. WARNING ! Uses global variable Gvertex_number_to_statement. PRIVATE to this pass !!
Definition at line 266 of file adg_graph.c.
References adg_vertex_to_ordering(), and ordering_to_statement().
Referenced by adg_dataflowgraph(), adg_dataflowgraph_with_extremities(), adg_decreasing_stat_order_sort(), adg_get_read_entity_vertices(), adg_get_write_entity_vertices(), adg_path_possible_source(), and read_reference_list().
======================================================================
list adg_write_reference_list( (vertex) ver, (effect) reff ) AL 08/07/93 Returns a list of vertices whose statement write the read effect reff. Vertex ver is a DG node.
Definition at line 688 of file adg_graph.c.
References ADD_ELEMENT_TO_LIST, CAR, CONFLICT, conflict_sink, debug(), dg_arc_label_conflicts, effect_any_reference, ENDP, NIL, POP, reference_equal_p(), SUCCESSOR, successor_arc_label, successor_vertex, VERTEX, and vertex_successors.
Referenced by adg_dataflowgraph().
======================================================================
conflict conflict_dup( (conflict) conf ) AL 06/07/93 Duplicates a conflict copy_conflict should now be used.
Definition at line 891 of file adg_graph.c.
References ADD_ELEMENT_TO_LIST, CAR, cone_generating_system, cone_levels, cone_undefined, conflict_cone, conflict_sink, conflict_source, debug(), effect_dup(), int, INT, make_cone(), make_conflict(), MAPL, NIL, and sg_dup().
Referenced by adg_only_call_WR_dependence(), and dg_arc_label_dup().
dg_arc_label dg_arc_label_dup | ( | dg_arc_label | dg_al | ) |
======================================================================
dg_arc_label dg_arc_label_dup((dg_arc_label) dg_al) AL 05/07/93 Duplicates the dg_arc_label.
Definition at line 924 of file adg_graph.c.
References ADD_ELEMENT_TO_LIST, CAR, CONFLICT, conflict_dup(), debug(), dg_arc_label_conflicts, make_dg_arc_label(), MAPL, and NIL.
Referenced by adg_reverse_graph(), and dg_vertex_dup().
======================================================================
vertex dg_vertex_dup( (vertex) ver ) AL 05/07/93 duplicates a vertex of the Dependence Graph Be VERY CAREFULL : this code could loop for ever if one successor of 'ver' points on it. PRIVATE use !
Definition at line 960 of file adg_graph.c.
References ADD_ELEMENT_TO_LIST, CAR, copy_dg_vertex_label(), debug(), dg_arc_label_dup(), make_successor(), make_vertex(), MAPL, NIL, statement_number, SUCCESSOR, successor_arc_label, successor_vertex, vertex_successors, vertex_to_statement(), and vertex_vertex_label.
dg_vertex_label dg_vertex_label_dup | ( | dg_vertex_label | dg_vl | ) |
======================================================================
dg_vertex_label dg_vertex_label_dup( AL 05/07/93 Duplicates the dg_vertex_label.
Definition at line 945 of file adg_graph.c.
References debug(), dg_vertex_label_statement, make_dg_vertex_label(), sccflags_undefined, and statement_undefined.
effect effect_dup(effect eff) input : an effect.
output : a copy of the input effect (no sharing). modifies : FI: the meaning of effect_dup() is unclear; should any syntactically correct effect by duplicable? Or this function be restricted to semantically correct effects? I do not understand why SC_UNDEFINED was used instead of transformer_undefined in contexts for scalar variables (8 August 1992)
Definition at line 864 of file adg_graph.c.
References effect_action, effect_approximation, effect_reference, effect_system, make_convex_effect, make_simple_effect, and pips_assert.
Referenced by conflict_dup().
======================================================================
bool in_effect_list_p( (list) l, (effect) eff ) AL 08/07/93 Returns True if the effect list l has an element whose reference is the same as the reference of eff. returns False in other cases.
Definition at line 722 of file adg_graph.c.
References CAR, debug(), EFFECT, effect_any_reference, ENDP, POP, and reference_equal_p().
Referenced by read_reference_list().
===========================================================================
Definition at line 292 of file adg_graph.c.
References CAR, CDR, INT, and NIL.
Referenced by adg_reorder_statement_number().
======================================================================
list read_reference_list( ver, ent_l1, ent_l2 ) AL 18/02/94 Returns a list of read effect for vertex ver. Vertex ver should have dg_arc_label arc_labels. This function should be very simple knowing effects of each statement : we should just scan the read effects of statement vertex.
Current effect
Put in rl effects readen by ver and remove from it effect whose variable are in ent_l1 or in ent_l2.
Definition at line 748 of file adg_graph.c.
References action_read_p, ADD_ELEMENT_TO_LIST, adg_vertex_to_statement(), CAR, debug(), EFFECT, effect_action, effect_any_reference, effect_undefined, ENDP, entity_undefined, in_effect_list_p(), is_entity_in_list_p(), load_proper_rw_effects_list(), NIL, POP, reference_variable, statement_number, and statement_undefined.
Referenced by adg_dataflowgraph().
|
extern |
External variables.
Definition at line 45 of file array_dfg.c.
|
extern |
Definition at line 47 of file array_dfg.c.
hash_table Gvertex_number_to_statement |
Global variables.
Definition at line 42 of file adg_graph.c.
Referenced by adg_dataflowgraph(), adg_dataflowgraph_with_extremities(), adg_number_to_ordering(), adg_reorder_statement_number(), and adg_vertex_to_ordering().