PIPS
|
#include "local.h"
Go to the source code of this file.
Macros | |
#define | GRAPH_IS_DG |
Name : adg_utils.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 | |
void | adg_fill_with_quast (quast *in_pq, quast in_q) |
====================================================================== More... | |
entity | adg_get_integer_entity (int in_i) |
====================================================================== More... | |
quast | adg_compact_quast (quast in_q) |
====================================================================== More... | |
bool | adg_quast_equal_p (quast in_q1, quast in_q2) |
====================================================================== More... | |
bool | adg_quast_value_equal_p (quast_value in_qv1, quast_value in_qv2) |
====================================================================== More... | |
bool | adg_quast_leaf_equal_p (quast_leaf in_ql1, quast_leaf in_ql2) |
====================================================================== More... | |
bool | adg_quast_leaf_label_equal_p (quast in_q1, quast in_q2) |
====================================================================== More... | |
bool | adg_quast_leaf_solution_equal_p (quast in_q1, quast in_q2) |
====================================================================== More... | |
Psysteme | adg_sc_dup (Psysteme in_ps) |
====================================================================== More... | |
bool | adg_is_textualy_after_p (statement in_s1, statement in_s2) |
====================================================================== More... | |
void | adg_sc_update_base (Psysteme *in_pps) |
====================================================================== More... | |
Psysteme | adg_suppress_2nd_in_1st_ps (Psysteme in_ps1, Psysteme in_ps2) |
====================================================================== More... | |
int | adg_number_of_same_loops (list in_l1, list in_l2) |
====================================================================== More... | |
statement | adg_number_to_statement (int in_nb) |
====================================================================== More... | |
void | adg_enrichir (quast in_qu, leaf_label in_ll) |
====================================================================== More... | |
predicate | predicate_dup (predicate in_pred) |
====================================================================== More... | |
dfg_vertex_label | dfg_vertex_label_dup (dfg_vertex_label in_dvl) |
====================================================================== More... | |
bool | adg_simple_ineg_p (Psysteme in_ps) |
====================================================================== More... | |
quast | adg_max_of_leaves (quast *tsou, quast tsou2, int in_i, Ppath in_pa, bool take_last) |
====================================================================== More... | |
quast | adg_path_max_source (quast *tsou, quast *tsou2, Ppath in_pa, list psl, boolean take_last) |
====================================================================== More... | |
Pvecteur | adg_list_to_vect (list in_list, bool with_tcst) |
====================================================================== More... | |
Psysteme | adg_build_Psysteme (predicate in_pred, list in_list) |
====================================================================== More... | |
Pposs_source | adg_path_possible_source (quast *in_tsou, vertex in_ver, int in_dep, Ppath in_pa, bool take_last) |
====================================================================== More... | |
list | adg_increasing_stat_order_sort (list in_list) |
====================================================================== More... | |
list | adg_decreasing_stat_order_sort (list in_list) |
====================================================================== More... | |
list | adg_merge_entities_lists (list l1, list l2) |
====================================================================== More... | |
list | adg_rename_entities (list le, hash_table fst) |
====================================================================== More... | |
list | adg_get_loop_indices (list ll) |
====================================================================== More... | |
Variables | |
int | Gcount_re |
Global variables. More... | |
statement_mapping | Gstco_map |
boolean | PATH_METHOD |
#define GRAPH_IS_DG |
Name : adg_utils.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_utils.c.
======================================================================
Psysteme adg_build_Psysteme( predicate in_pred, list in_list ) Input : A predicate in_pred. AL 29/07/93 A list of entities in_list. Output : A Psysteme from in_pred ordered according to the list in_list. PUBLIC use.
Call a sort function
Definition at line 895 of file adg_utils.c.
References adg_list_to_vect(), debug(), NIL, pips_internal_error, predicate_system, predicate_undefined, and sort_psysteme().
======================================================================
quast adg_compact_quast( in_q ) AL 1/12/93 Compact a quast with a lot of undefined leaves. Could be costly extended to more general cases. Usefull to compact a quast provided by PIP.
Definition at line 129 of file adg_utils.c.
References adg_quast_equal_p(), Ssysteme::base, conditional_false_quast, conditional_predicate, conditional_true_quast, debug(), free_quast(), is_quast_value_conditional, make_conditional(), make_predicate(), make_quast(), make_quast_value(), predicate_system, quast_newparms, quast_quast_value, quast_undefined, quast_value_conditional, quast_value_conditional_p, quast_value_quast_leaf_p, quast_value_undefined, sc_append(), sc_creer_base(), and sc_dup().
Referenced by adg_dataflowgraph(), and adg_dataflowgraph_with_extremities().
======================================================================
list adg_decreasing_stat_order_sort( list in_list ) AL 28/07/93 Input : A list of vertices in_list. Output : A list of vertices sorted by decreasing order of statement_ordering attached to each vertex ret_list. Method : We scan in_list. For each vertex ver of in_list, we scan ret_list with l1. l2 points on predecessor of l1. According to the order of ver compared to the order of v1 and v2, we insert (or not) ver between l2 and l1. PRIVATE use.
ret_list is presently empty : we initialize it with the new vertex ver
We are at the end of ret_list : we add the new vertex at the end of our list
Core of the pass : compares new input vertex ver
Definition at line 1028 of file adg_utils.c.
References ADD_ELEMENT_TO_LIST, adg_vertex_to_statement(), CAR, cons::cdr, debug(), ENDP, gen_length(), NIL, POP, statement_number, and VERTEX.
Referenced by adg_dataflowgraph(), adg_dataflowgraph_with_extremities(), and adg_increasing_stat_order_sort().
void adg_enrichir | ( | quast | in_qu, |
leaf_label | in_ll | ||
) |
======================================================================
void adg_enrichir( (quast) in_qu, (leaf_label) in_ll ) AL 21/10/93 Input : A quast and a leaf label. Output : Nothing. Just put each leaf_label of quast in_qu equal to in_ll and update the solution. WARNING ! Using global variable : Gstco_map. PRIVATE use !
We get the indices of statement linked to in_ll
Get the dep first indices and put them in prov_l
Add to prov_l the solutions of quast
Definition at line 474 of file adg_utils.c.
References ADD_ELEMENT_TO_LIST, adg_get_loop_indices(), adg_number_to_statement(), CAR, conditional_false_quast, conditional_true_quast, conditional_undefined, count, debug(), ENDP, ENTITY, entity_to_expression(), exp, EXPRESSION, GET_STATEMENT_MAPPING, Gstco_map, leaf_label_depth, leaf_label_statement, make_quast_leaf(), NIL, POP, quast_leaf_solution, quast_leaf_undefined, quast_quast_value, quast_undefined, quast_value_conditional, quast_value_conditional_p, quast_value_quast_leaf, quast_value_quast_leaf_p, quast_value_undefined, and static_control_loops.
Referenced by adg_dataflowgraph(), and adg_dataflowgraph_with_extremities().
======================================================================
USEFULL FUNCTIONS
====================================================================== ====================================================================== void adg_fill_with_quast( in_pq, in_q ) AL 17/02/94
Definition at line 52 of file adg_utils.c.
References conditional_false_quast, conditional_true_quast, debug(), fprintf(), get_debug_level(), imprime_special_quast(), quast_quast_value, quast_undefined, quast_value_conditional, and quast_value_conditional_p.
Referenced by adg_dataflowgraph(), and adg_dataflowgraph_with_extremities().
======================================================================
AL 94/02/14
If a Renamed Entity already exists, we use it ; else, we make a new one and increment Gcount_re.
Definition at line 83 of file adg_utils.c.
References ADFG_MODULE_NAME, concatenate(), debug(), entity_local_name(), FindOrCreateEntity(), fprintf(), free(), Gcount_ie, get_current_module_entity(), get_debug_level(), int2a(), is_basic_int, is_storage_ram, is_type_variable, is_value_unknown, make_basic(), make_entity, make_storage(), make_type(), make_value(), make_variable(), mod_ent, MODULE_SEP_STRING, NIL, num, ram_undefined, strdup(), UU, and UUINT.
Referenced by adg_dataflowgraph_with_extremities().
======================================================================
list adg_get_loop_indices( list ll ) AL 22/07/93 Input : A list of loops ll. Output : A list of entities representing indices of loops in ll. PUBLIC use.
Definition at line 1186 of file adg_utils.c.
References ADD_ELEMENT_TO_LIST, CAR, ENDP, ENTITY, LOOP, loop_index, NIL, and POP.
Referenced by adg_dataflowgraph(), adg_dataflowgraph_with_extremities(), and adg_enrichir().
======================================================================
list adg_increasing_stat_order_sort( list in_list ) AL 28/07/93 Input : A list of vertices in_list. Output : A list of vertices sorted by decreasing order PRIVATE use.
Definition at line 1013 of file adg_utils.c.
References adg_decreasing_stat_order_sort(), and gen_nreverse().
Referenced by adg_dataflowgraph_with_extremities().
======================================================================
bool adg_is_textualy_after_p( (statement) in_s1, (statement) in_s2 ) Input : Two statements in_s1 and in_s2. AL 08/11/93 Output : True if in_s1 is before in_s2 in the text program. WARNING: This function compares the statement number of the two statements => these numbers should already be ordered.
Definition at line 373 of file adg_utils.c.
References statement_number.
Referenced by adg_dataflowgraph().
======================================================================
Pvecteur adg_list_to_vect(list in_list, bool with_tcst) AL 07/10/93 Input : A list of entities and a boolean. Output : A Pvecteur sorted by the in_list order. TCST is added at the end if with_tcst is set to TRUE. PUBLIC use.
Build a Pvecteur according to the reverse order of the in_list
Add the TCST var or not
Reverse the vecteur to recover the order of the input list
Definition at line 865 of file adg_utils.c.
References CAR, debug(), ENDP, ENTITY, POP, TCST, VALUE_ONE, vect_add_elem(), vect_reversal(), and VECTEUR_NUL.
Referenced by adg_build_Psysteme(), adg_dataflowgraph(), and adg_dataflowgraph_with_extremities().
======================================================================
quast adg_max_of_leaves( tsou, tsou2, in_i, in_pa, take_last) Compute max of two quasts. in_i is the order to ta ... PRIVATE use.
he two leaves are at the same depth : we have three cases
If we are in the deepest position : take textual order
Take the in_i element of solutions
f *tsou and tsou2 distances to the source could be equal
See if tsou2 could be after *tsou
See if *tsou could be after tsou2
Only one of the two is after the other.
Both quast could be a source: look at a deeper stage.
!after1 or !after2
only after1 holds
only after2 holds
!after1 and !after2
Definition at line 578 of file adg_utils.c.
References adg_number_to_statement(), contrainte_make(), CONTRAINTE_UNDEFINED, copy_quast(), copy_quast_value(), debug(), EXPRESSION, EXPRESSION_PVECTEUR, gen_nth(), Gstco_map, is_quast_value_conditional, leaf_label_depth, leaf_label_statement, leaf_label_undefined, make_conditional(), make_predicate(), make_quast(), make_quast_value(), NIL, pa_faisabilite, pa_intersect_system(), pips_internal_error, quast_leaf_leaf_label, quast_leaf_solution, quast_quast_value, quast_undefined, quast_value_quast_leaf, RETURN, sc_make(), statement_number, stco_common_loops_of_statements(), TCST, VALUE_ONE, vect_add(), vect_chg_sgn(), vect_new(), and vect_substract().
Referenced by adg_path_max_source().
======================================================================
list adg_merge_entities_lists( list l1, list l2 ) AL 23/07/93 Input : Two lists of entities. Output : A list of entities, union of the l1 and l2. Append the new entities of l2 after list l1. PUBLIC use.
Definition at line 1093 of file adg_utils.c.
References ADD_ELEMENT_TO_LIST, CAR, chunk_undefined, debug(), ENDP, ENTITY, gen_find_eq(), NIL, and POP.
Referenced by adg_dataflowgraph().
======================================================================
int adg_number_of_same_loops( (list) in_l1, (list) in_l2 ) AL 28/10/93 Input : Two lists of loops in_l1 and in_l2. Output : Number of loops in the two lists that have the same statement ordering. PUBLIC use possible.
Definition at line 438 of file adg_utils.c.
References CAR, count, debug(), ENDP, LOOP, loop_body, POP, and statement_ordering.
Referenced by adg_dataflowgraph().
======================================================================
statement adg_number_to_statement( (int) in_nb ) AL 25/10/93 Input : Number of a vertex. Output : A statement associated to this vertex. PRIVATE use !
Definition at line 461 of file adg_utils.c.
References adg_number_to_ordering(), and ordering_to_statement().
Referenced by adg_dataflowgraph(), adg_enrichir(), adg_max_of_leaves(), adg_path_max_source(), adg_path_possible_source(), broadcast_conditions(), broadcast_of_dataflow(), cmf_layout_align(), craft_layout_align(), cutting_conditions(), dims_of_nest(), edge_weight(), fprint_bdt_with_stat(), get_list_of_all_param(), include_parameters_in_sc(), include_trans_in_poly(), is_not_trivial_p(), mapping_on_broadcast(), partial_broadcast_coefficients(), plc_make_dim(), plc_make_distance(), plc_make_min_dim(), plc_make_proto(), prepare_reindexing(), re_do_it(), sa_do_it(), simplify_bdt(), sort_dfg_node(), and valuer().
======================================================================
quast adg_path_max_source( quast *tsou, quast *tsou2, list psl, Ppath in_pa, bool take_last ) AL 04/08/93
Trivial cases
Case the quast of *tsou is a conditional
quast qt = conditional_true_quast( qvcond ); quast qf = conditional_false_quast( qvcond );
Case the quast of *tsou is a leaf and *tsou2 a conditional
The two quasts are leaves
The two statement have the same depth dep
Definition at line 726 of file adg_utils.c.
References adg_max_of_leaves(), adg_number_to_statement(), adg_quast_leaf_solution_equal_p(), Ssysteme::base, conditional_false_quast, conditional_predicate, conditional_true_quast, copy_quast(), copy_quast_value(), debug(), gen_concatenate(), Gstco_map, is_quast_value_conditional, leaf_label_depth, leaf_label_statement, leaf_label_undefined, make_conditional(), make_quast(), make_quast_value(), pa_faisabilite, pa_intersect_complement(), pa_intersect_system(), pips_internal_error, predicate_system, quast_leaf_leaf_label, quast_newparms, quast_quast_value, quast_undefined, quast_value_conditional, quast_value_conditional_p, quast_value_quast_leaf, quast_value_quast_leaf_p, quast_value_undefined, RETURN, sc_creer_base(), statement_number, and stco_common_loops_of_statements().
Referenced by adg_dataflowgraph(), and adg_dataflowgraph_with_extremities().
Pposs_source adg_path_possible_source | ( | quast * | in_tsou, |
vertex | in_ver, | ||
int | in_dep, | ||
Ppath | in_pa, | ||
bool | take_last | ||
) |
======================================================================
Pposs_source adg_path_possible_source( quast in_tsou, vertex in_ver, int in_dep, Psysteme in_ps ) Input : The present solution source in_tsou AL 29/07/93 the vertex in_ver to examine and its depth in_dep. and the candidate context in_ps. If take_last is true, we select leaves according to the sequential order (the last one wins). If it is false, the first one wins. Output : Node of quast in_tsou under which we could find a source. PRIVATE use.
The last wins. General usage.
The first wins. Used to compute summary read effects
This vertex is not a possible source
Definition at line 929 of file adg_utils.c.
References adg_number_to_statement(), adg_sc_update_base(), adg_vertex_to_statement(), conditional_false_quast, conditional_predicate, conditional_true_quast, debug(), Gstco_map, leaf_label_depth, leaf_label_statement, malloc(), nesting, pa_empty(), pa_empty_p(), pa_intersect_complement(), pa_intersect_system(), Sposs_source::pat, predicate_system, Sposs_source::qua, quast_leaf_leaf_label, quast_quast_value, quast_undefined, quast_value_conditional, quast_value_conditional_p, quast_value_quast_leaf, quast_value_quast_leaf_p, quast_value_undefined, RETURN, statement_number, and stco_common_loops_of_statements().
Referenced by adg_dataflowgraph(), and adg_dataflowgraph_with_extremities().
======================================================================
bool adg_quast_equal_p() AL 1/12/93 Returns true if the 2 input quasts are equal to quast_undefined. Could be extented.
Definition at line 192 of file adg_utils.c.
References quast_undefined.
Referenced by adg_compact_quast(), and adg_quast_value_equal_p().
bool adg_quast_leaf_equal_p | ( | quast_leaf | in_ql1, |
quast_leaf | in_ql2 | ||
) |
======================================================================
bool adg_quast_leaf_equal_p() AL 1/12/93 NOT used, NOT tested.
Definition at line 226 of file adg_utils.c.
References leaf_label_depth, leaf_label_statement, leaf_label_undefined, quast_leaf_leaf_label, and quast_leaf_undefined.
Referenced by adg_quast_value_equal_p().
======================================================================
bool adg_quast_leaves_equal_p( (quast) in_q1, (quast) in_q2 ) Returns True if the Two input quast have same leaf-labels.
Definition at line 254 of file adg_utils.c.
References debug(), leaf_label_depth, leaf_label_statement, leaf_label_undefined, quast_leaf_leaf_label, quast_leaf_undefined, quast_quast_value, quast_undefined, quast_value_conditional_p, quast_value_quast_leaf, and quast_value_undefined.
======================================================================
Definition at line 290 of file adg_utils.c.
References CAR, debug(), ENDP, EXPRESSION, EXPRESSION_PVECTEUR, gen_length(), POP, quast_leaf_solution, quast_leaf_undefined, quast_quast_value, quast_undefined, quast_value_conditional_p, quast_value_quast_leaf, quast_value_undefined, and vect_equal().
Referenced by adg_path_max_source().
bool adg_quast_value_equal_p | ( | quast_value | in_qv1, |
quast_value | in_qv2 | ||
) |
======================================================================
bool adg_quast_value_equal_p() AL 1/12/93 NOT used, NOT tested.
Definition at line 201 of file adg_utils.c.
References adg_quast_equal_p(), adg_quast_leaf_equal_p(), adg_suppress_2nd_in_1st_ps(), conditional_false_quast, conditional_predicate, conditional_true_quast, predicate_system, quast_value_conditional, quast_value_quast_leaf, quast_value_quast_leaf_p, and quast_value_undefined.
list adg_rename_entities | ( | list | le, |
hash_table | fst | ||
) |
======================================================================
list adg_rename_entities( list le, hash_table fst) AL 22/07/93 Input : A list of entities le and a hash table fst.
Output : A list of entities with names RE1 RE2 RE3 ... according to a global counter Gcount_re. If we already have created enough amount of new entities, we reuse them; else, we create new ones. Gcount_re is the total number of such entities. The corresponding changes are kept in the hash_table Gforward_substitute_table ("fst") given in argument. PRIVATE use.
If a Renamed Entity already exists, we use it ; else, we make a new one and increment Gcount_re.
Definition at line 1125 of file adg_utils.c.
References ADD_ELEMENT_TO_LIST, ADFG_MODULE_NAME, CAR, concatenate(), debug(), ENDP, ENTITY, entity_local_name(), entity_to_expression(), FindOrCreateEntity(), fprintf(), free(), Gcount_re, get_current_module_entity(), get_debug_level(), hash_put(), int2a(), is_basic_int, is_storage_ram, is_type_variable, is_value_unknown, make_basic(), make_entity, make_storage(), make_type(), make_value(), make_variable(), mod_ent, MODULE_SEP_STRING, NIL, num, POP, ram_undefined, strdup(), UU, and UUINT.
Referenced by adg_dataflowgraph().
======================================================================
Psysteme adg_sc_dup( (Psysteme) in_ps ) AL 09/11/93 Input : A Psysteme in_ps. Output : A duplicated Psysteme. Smooth version of sc_dup : We avoid any verificatio on the contraintes. PRIVATE use !
Definition at line 331 of file adg_utils.c.
References base_reversal(), contrainte_new(), contrainte_vecteur, cp, debug(), eq, sc_add_egalite(), sc_add_inegalite(), sc_new(), Scontrainte::succ, vect_dup(), and VECTEUR_UNDEFINED.
Referenced by adg_dataflowgraph(), and adg_dataflowgraph_with_extremities().
void adg_sc_update_base | ( | Psysteme* | in_pps | ) |
======================================================================
void adg_sc_update_base( (Psysteme*) in_pps ) AL 05/11/93 Input : A pointer on Psysteme in_pps. Done : Update base of in_ps. PRIVATE use !
Definition at line 384 of file adg_utils.c.
References Ssysteme::base, Ssysteme::nb_eq, Ssysteme::nb_ineq, and sc_creer_base().
Referenced by adg_dataflowgraph(), adg_path_possible_source(), and adg_update_dfg().
======================================================================
bool adg_simple_ineg_p( (Psysteme) in_ps ) AL 22/10/93 Input : A psysteme in_ps Output : true if in_ps has only one inegality in it. FALSE otherwhise. PUBLIC use.
Definition at line 568 of file adg_utils.c.
======================================================================
Psysteme adg_suppress_2nd_in_1st_ps( (Psysteme) in_ps1, (Psysteme) in_ps2 ) AL 03/11/93 Input : 2 Psystemes. Output : Psysteme : Scan in_ps1 and remove from it Pcontraintes in in_ps2. No sharing, No remove input object. PUBLIC use possible.
Definition at line 403 of file adg_utils.c.
References contrainte_make(), CONTRAINTE_UNDEFINED, debug(), ok, RETURN, sc_append(), sc_make(), Scontrainte::succ, vect_equal(), and Scontrainte::vecteur.
Referenced by adg_dataflowgraph(), adg_dataflowgraph_with_extremities(), adg_quast_value_equal_p(), and adg_update_dfg().
dfg_vertex_label dfg_vertex_label_dup | ( | dfg_vertex_label | in_dvl | ) |
======================================================================
dfg_vertex_label_dup( (dfg_vertex_label) in_dvl ) AL 18/10/93 Input : A dfg_vertex_label in_dvl Output : A duplicated dfg_vertex_label. WARNING: tag sccflags is always put to sccflags_undefined !! Should not be used anymore : copy_dfg_vertex_label exists ! PRIVATE use .
Definition at line 545 of file adg_utils.c.
References debug(), dfg_vertex_label_exec_domain, dfg_vertex_label_statement, dfg_vertex_label_undefined, make_dfg_vertex_label(), predicate_dup(), and sccflags_undefined.
======================================================================
predicate predicate_dup( (predicate) in_pred ) AL 18/10/93 Input : A predicate in_pred. Output : A duplicated predicate ret_pred. PUBLIC use possible.
Definition at line 529 of file adg_utils.c.
References make_predicate(), predicate_system, predicate_undefined, and sc_dup().
Referenced by dfg_vertex_label_dup().
|
extern |
Global variables.
Global variables.
Definition at line 45 of file array_dfg.c.
Referenced by adg_rename_entities(), and array_dfg().
|
extern |
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().
|
extern |