PIPS
|
Go to the source code of this file.
Macros | |
#define | INFAISABLE 0 |
Warning! Do not modify this file that is automatically generated! More... | |
#define | FAISABLE 1 |
#define | MAXDEPTH 9 |
maximun number of nested loops More... | |
#define | MAXSV 1024 |
maximum number of scalar variables More... | |
#define | FLOW_DEPENDANCE 1 |
Definition for the dependance_verticies_p function. More... | |
#define | ANTI_DEPENDANCE 2 |
#define | OUTPUT_DEPENDANCE 4 |
#define | INPUT_DEPENDANCE 8 |
Variables | |
int | NbrArrayDepInit |
he variables for the statistics of test of dependence and parallelization More... | |
int | NbrIndepFind |
int | NbrAllEquals |
int | NbrDepCnst |
int | NbrDepExact |
int | NbrDepInexactEq |
int | NbrDepInexactFM |
int | NbrDepInexactEFM |
int | NbrScalDep |
int | NbrIndexDep |
int | deptype [5][3] |
int | constdep [5][3] |
int | NbrTestCnst |
int | NbrTestGcd |
int | NbrTestSimple |
int | NbrTestDiCnst |
by sc_normalize() More... | |
int | NbrTestProjEqDi |
int | NbrTestProjFMDi |
int | NbrTestProjEq |
int | NbrTestProjFM |
int | NbrTestDiVar |
int | NbrProjFMTotal |
int | NbrFMSystNonAug |
int | FMComp [18] |
bool | is_test_exact |
or counting the number of F-M complexity less than 16. More... | |
bool | is_test_inexact_eq |
bool | is_test_inexact_fm |
bool | is_dep_cnst |
bool | is_test_Di |
bool | Finds2s1 |
int | Nbrdo |
loop.c More... | |
entity | DiVars [9] |
testdep_util.c More... | |
entity | LiVars [9] |
entity | DsiVars [1024] |
int | NbrTestExact |
#define FLOW_DEPENDANCE 1 |
#define INFAISABLE 0 |
Warning! Do not modify this file that is automatically generated!
Modify src/Libs/ricedg/ricedg-local.h instead, to add your own modifications. header file built by cproto ricedg-local.h
Check to see if there is a directed way between 2 statements in the graph specified.
s1 | 1 |
s2 | 2 |
Definition at line 290 of file impact_check.c.
References ADD_ELEMENT_TO_LIST, CAR, ENDP, gen_in_list_p(), MAP, NIL, POP, s1, statement_equal_p(), statement_to_vertex(), SUCCESSOR, successor_vertex, VERTEX, vertex_successors, and vertex_to_statement().
int compare_vertex | ( | const void * | v0, |
const void * | v1 | ||
) |
compare two vertices based on their ordering
v0 | 0 |
v1 | 1 |
Definition at line 58 of file util.c.
References vertex_ordering().
Referenced by do_scalar_renaming_in_graph().
chains | hains |
Definition at line 2363 of file ricedg.c.
References chains(), compute_dg_on_statement_from_chains_in_place(), copy_graph(), and dg.
chains | hains |
Definition at line 2342 of file ricedg.c.
References chains(), constdep, debug_off, debug_on, deptype, dg, DG_FAST, dg_type, memset(), quick_privatize_graph(), and rdg_statement().
Referenced by compute_dg_on_statement_from_chains().
hash_table compute_ordering_to_dg_mapping | ( | graph | dependance_graph | ) |
Define a mapping from the statement ordering to the dependence graph vertices:
dependance_graph | ependance_graph |
Definition at line 70 of file util.c.
References dg_vertex_label_statement, FOREACH, graph_vertices, hash_int, hash_put(), hash_table_make(), pips_debug, VERTEX, vertex_successors, and vertex_vertex_label.
This is a callback for qsort function, it compares two conflicts.
c1 | 1 |
c2 | 2 |
Definition at line 126 of file util.c.
References concatenate(), conflict_sink, conflict_source, effect_action, effect_any_reference, effect_words_reference(), free(), full_action_to_short_string(), s1, strdup(), and words_to_string().
Referenced by prettyprint_dependence_graph(), prettyprint_dependence_graph_view(), and xml_Chain_Graph().
bool context_map_undefined_p | ( | void | ) |
statement_mapping contexts_mapping_of_nest | ( | statement | stat | ) |
stat | tat |
Definition at line 162 of file contexts.c.
References contexts_mapping_of_statement(), entity_local_name(), fprintf(), ifdebug, MAKE_STATEMENT_MAPPING, pips_assert, sc_fprint(), statement_call_p(), statement_loop_p(), STATEMENT_MAPPING_MAP, and statement_number.
Referenced by rice_update_dependence_graph().
void delete_statement_context | ( | statement | ) |
int dep_type(action ac1,action ac2) This function test the type of the dependence.
ac1, ac2 are the action of two references.The representations of the result are as follows. 0 -— def-use dependence 1 -— use-def dependence 2 -— def-def dependence 3 -— use-use dependence (added in 20/01/92) FI->YY: we also have use-use dependence (also called input dependence); there is no reason to abort here; input dependences should just be ignored for parallelization, but not for tiling or cache optimization
to please gcc
ac1 | c1 |
ac2 | c2 |
Definition at line 378 of file testdep_util.c.
References action_read_p, action_write_p, and pips_internal_error.
Referenced by insert_impact_description_as_comment(), and TestCoupleOfReferences().
this function returns the nesting level of a given di variable e.
Definition at line 185 of file testdep_util.c.
References DiVars, and MAXDEPTH.
Referenced by sc_proj_on_di(), sc_proj_optim_on_di_ofl(), and TestDependence().
bool find_covering_reference_path | ( | set | arcs_processed_set, |
statement | s_src, | ||
action | act_src, | ||
entity | ent_src, | ||
statement | s_dest, | ||
action | act_dest, | ||
entity | ent_dest | ||
) |
arcs_processed_set | rcs_processed_set |
s_src | _src |
act_src | ct_src |
ent_src | nt_src |
s_dest | _dest |
act_dest | ct_dest |
ent_dest | nt_dest |
Definition at line 238 of file impact_check.c.
References action_read_p, action_write_p, CONFLICT, conflict_sink, conflict_source, dg, dg_arc_label_conflicts, effect_action, effect_any_reference, entities_may_conflict_p(), MAP, reference_variable, set_add_element(), set_belong_p(), set_make(), set_pointer, statement_equal_p(), statement_to_vertex(), SUCCESSOR, successor_arc_label, successor_vertex, vertex_successors, and vertex_to_statement().
Referenced by check_for_effected_statement().
n1 | 1 |
n2 | 2 |
Definition at line 307 of file testdep_util.c.
References CAR, CDR, LOOP, and NIL.
Referenced by prettyprint_dependence_graph_view(), prettyprint_dot_dependence_graph(), search_parallel_loops(), TestCoupleOfReferences(), and TestDependence().
void free_context_map | ( | void | ) |
statement_mapping get_context_map | ( | void | ) |
in_l | n_l |
in_s | n_s |
Definition at line 35 of file trace.c.
References MAP, same_string_p, VERTEX, vertex_undefined, and vertex_vertex_label.
Referenced by make_filtered_dg_or_dvdg().
This functions looks up a di variable of nesting level l in table DiVars.
di variables are created if they do not exist.
Definition at line 79 of file testdep_util.c.
References DiVars, MakeDiVar(), MAXDEPTH, and user_error.
Referenced by dependence_system_add_lci_and_di(), gcd_and_constant_dependence_test(), MakeDibaseinorder(), sc_add_di(), TestDiCnst(), and TestDiVariables().
Definition at line 164 of file testdep_util.c.
References DsiVars, MakeDsiVar(), MAXSV, and user_error.
Referenced by gcd_and_constant_dependence_test(), and sc_add_dsi().
Definition at line 121 of file testdep_util.c.
References LiVars, MakeLiVar(), MAXDEPTH, and user_error.
Referenced by build_and_test_dependence_context(), dependence_system_add_lci_and_di(), and gcd_and_constant_dependence_test().
bool impact_check | ( | char * | module_name | ) |
ash_table control_to_set_of_dominators = hash_table_make(hash_pointer, 0);
ull_control_graph(module_name);
omputing_dominators(control_to_set_of_dominators, load_ctrl_graph(mod_stat));
set_precondition_map((statement_mapping) db_get_memory_resource(DBR_PRECONDITIONS, module_name, true));
Looking for another formal variable in the list of alias associations that has same section and included call path. If this variable is checked dynamically with e1 => no need to continue
Looking for common variables in module or callee of modules to check for alias impact ...
formal parameter has a same section with other common variable
If u1 is defined (different to -1) and u1<l2, there is no alias impact The same for: l1 is defined (different to -1) and u2<l1
The common variable always have a good offset off2
ash_table_free(control_to_set_of_dominators);
lean_ctrl_graph();
eset_precondition_map();
module_name | odule_name |
Definition at line 1242 of file impact_check.c.
References ALIAS_ASSOCIATION, alias_association_call_chain, alias_association_lower_offset, alias_association_offset, alias_association_section, alias_association_upper_offset, alias_association_variable, alias_associations_list, array_entity_p(), CAR, CDR, code_declarations, current_mod, db_get_memory_resource(), DB_PUT_MEMORY_RESOURCE, debug_off, debug_on, dg, display_impact_alias_statistics(), dynamic_checked_p(), ENDP, ENTITY, entity_code(), entity_storage, entity_type, entity_undefined, gen_length(), impact_check_two_variables(), included_call_chain_p(), init_dynamic_check_list(), int_to_expression(), l_dynamic_check, l_module_aliases, local_name_to_top_level_entity(), MAP, mod_stat, module_name(), NIL, number_of_processed_modules, ram_offset, ram_section, reset_current_module_entity(), reset_ordering_to_statement(), same_entity_p(), set_current_module_entity(), set_ordering_to_statement(), SizeOfArray(), SizeOfElements(), statement_undefined, storage_ram, type_variable, user_log(), variable_basic, and variable_in_common_p().
void make_context_map | ( | void | ) |
for computing the line numbers of statements
Additional information for EDF prettyprint. Instruction calls are given with statement numbers
mod_stat | od_stat |
mod_graph | od_graph |
Definition at line 101 of file trace.c.
References action_read_p, ADD_ELEMENT_TO_LIST, apply_persistant_statement_to_int(), call_function, CAR, cone_levels, cone_undefined, CONFLICT, conflict_cone, conflict_sink, conflict_source, dg_arc_label_conflicts, effect_action, effect_any_reference, effect_words_reference(), entity_local_name(), free_persistant_statement_to_int(), gen_free_list(), gen_in_list_p(), get_bool_property(), get_current_module_entity(), get_list_of_variable_to_filter(), get_vertex_in_list(), graph_vertices, instruction_call, instruction_call_p, INT, make_successor(), make_vertex(), malloc(), MAP, MAPL, memset(), mod_stat, module_to_declaration_length(), NIL, persistant_statement_to_int_undefined, pl, reference_variable, s1, statement_instruction, statement_number, statement_to_line_number(), statement_undefined_p, SUCCESSOR, successor_arc_label, successor_vertex, verlist, VERTEX, vertex_successors, vertex_to_statement(), vertex_undefined_p, and words_to_string().
Referenced by print_filtered_dg_or_dvdg().
Pbase MakeDibaseinorder(int n) make a base of D#1 ...
D::n in order of D#1-> D#2, ...-> D::n.
Definition at line 296 of file testdep_util.c.
References BASE_NULLE, GetDiVar(), and vect_add_variable().
Referenced by TestDependence().
This function creates di variables.
There are MAXDEPTH di variables which means that programs with more than MAXDEPTH nested loops cannot be parallelized by pips.
l | is the nesting level of the variable to create |
Create a variable of this format: "d#X"
Definition at line 63 of file testdep_util.c.
References asprintf, DI_VAR_MODULE_NAME, entity_domain, entity_undefined, free(), gen_find_tabulated(), make_entity, MODULE_SEP_STRING, storage_undefined, type_undefined, and value_undefined.
Referenced by GetDiVar().
This function creates dsi variables.
There are MAXSV dsi variables which means that programs with more than MAXSV scalar variables cannot be parallelized by PIPS.
l | means to create Dsi[l] variable |
Create a variable of this format: "ds#XXXX"
Definition at line 146 of file testdep_util.c.
References asprintf, DI_VAR_MODULE_NAME, entity_domain, entity_undefined, free(), gen_find_tabulated(), make_entity, MODULE_SEP_STRING, storage_undefined, type_undefined, and value_undefined.
Referenced by GetDsiVar().
This function creates li variables(thee ith loop index variable).
There are MAXDEPTH li variables which means that programs with more than MAXDEPTH nested loops cannot be parallelized by pips.
l | is the nesting level of the variable to create |
Create a variable of this format: "l#X"
Definition at line 103 of file testdep_util.c.
References asprintf, DI_VAR_MODULE_NAME, entity_domain, entity_undefined, free(), gen_find_tabulated(), make_entity, MODULE_SEP_STRING, storage_undefined, type_undefined, and value_undefined.
Referenced by GetLiVar().
entity MakeLoopCounter | ( | void | ) |
Create a new loop counter variable.
Create a variable of this format: "lc#XXXXXX"
Try a new free one:
Definition at line 334 of file testdep_util.c.
References asprintf, entity_domain, entity_undefined, free(), gen_find_tabulated(), ilc, ILCMAX, LOOP_COUNTER_MODULE_NAME, make_entity, MODULE_SEP_STRING, pips_debug, pips_internal_error, storage_undefined, strdup(), type_undefined, and value_undefined.
Referenced by dependence_system_add_lci_and_di().
Print all edges and arcs.
There is no guarantee that the ordering_to_statement() hash table is the proper one
compute line numbers for statements
If we have zero printable conflicts, move on.
If we have more than one conflict, let's sort them !
FI: the number of conflicts should take into account the filtering due to PRETTYPRINT_MEMORY_EFFECTS_ONLY
Modification at revision 12484 because statement numbers were not initialized by C parser, with no validation of ricedg available at that time
factorize line numbers
FI: I should use another property, specific to the use-def chains, but this is quite close
if (!entity_scalar_p(reference_variable (effect_any_reference(conflict_source(c))))) {
Additional information for EDF prettyprint. Instruction calls are given with statement numbers
uniform dependence
sg_fprint(fd,gs,entity_local_name);
FI: almost print_dependence_cone:-(
fd | d |
mod_stat | od_stat |
mod_graph | od_graph |
Definition at line 177 of file util.c.
References apply_persistant_statement_to_int(), type_sg::base, call_function, CAR, CDR, cone_generating_system, cone_levels, cone_undefined, CONFLICT, conflict_cone, conflict_sink, conflict_source, conflicts_sort_callback(), CONS, debug_off, debug_on, dependence_graph_banner, dg_arc_label_conflicts, effect_action, effect_any_reference, effect_words_reference(), ENDP, entity_local_name(), FOREACH, fprint_lsom_as_dense(), fprintf(), free_persistant_statement_to_int(), full_action_to_short_string(), GEN_ARRAY_FOREACH, gen_array_free(), gen_array_make(), gen_array_nitems(), gen_array_pointer(), gen_length(), gen_sort_list(), get_bool_property(), get_current_module_entity(), graph_vertices, ifdebug, instruction_call, instruction_call_p, INT, list_to_array(), MAPL, mod_stat, module_to_declaration_length(), NIL, persistant_statement_to_int_undefined, pl, print_ordering_to_statement(), print_words(), s1, sc_fprint(), sc_new(), sg_fprint_as_ddv(), sg_fprint_as_dense(), sg_nbre_droites, sg_nbre_rayons, sg_nbre_sommets, sg_sommets, sg_to_sc_chernikova(), SG_UNDEFINED_P, statement_instruction, statement_number, statement_to_line_number(), statement_undefined_p, store_effect_p(), SUCCESSOR, successor_arc_label, successor_sort_callback(), successor_vertex, VERTEX, vertex_sort_callback(), vertex_successors, vertex_to_statement(), and words_effect().
Referenced by chains(), FindAndTopSortSccs(), icm_codegen(), print_dependence_or_chains_graph(), rice_dependence_graph(), and rice_update_dependence_graph().
Do not print vertices and arcs ignored by the parallelization algorithms.
At least, hopefully...
f (! entity_scalar_p(reference_variable (effect_any_reference(conflict_source(c))))) {
sg_fprint(fd,gs,entity_local_name);
fd | d |
mod_stat | od_stat |
mod_graph | od_graph |
Definition at line 833 of file util.c.
References type_sg::base, CAR, CDR, clean_enclosing_loops(), cone_generating_system, cone_levels, cone_undefined, CONFLICT, conflict_cone, conflict_sink, conflict_source, conflicts_sort_callback(), CONS, debug_off, debug_on, dependence_graph_banner, dg_arc_label_conflicts, ENDP, entity_local_name(), prettyprint_dot_context::fd, FindMaximumCommonLevel(), fprintf(), GEN_ARRAY_FOREACH, gen_array_free(), gen_array_make(), gen_array_nitems(), gen_array_pointer(), gen_length(), gen_nconc(), get_bool_property(), graph_vertices, ifdebug, ignore_this_conflict(), INT, level, list_to_array(), load_statement_enclosing_loops(), loops_mapping_of_statement(), MAPL, mod_stat, NIL, pl, print_words(), s1, sc_fprint(), sc_new(), set_enclosing_loops_map(), sg_fprint_as_dense(), sg_to_sc_chernikova(), SG_UNDEFINED_P, statement_number, SUCCESSOR, successor_arc_label, successor_vertex, VERTEX, vertex_successors, vertex_to_statement(), and words_effect().
Referenced by print_dependence_or_chains_graph().
Output dependence graph in a file in graphviz dot format.
fd | is the file descriptor where to output |
mod_stat | is the module statement (not necessary module, it can be a block statement for instance |
graph | is the dependence graph to print |
There is no guarantee that the ordering_to_statement() hash table is the proper one
graph style
Nodes style
uniform dependence
fd | d |
mod_stat | od_stat |
mod_graph | od_graph |
Definition at line 583 of file util.c.
References action_read_p, action_write_p, type_sg::base, CAR, cone_generating_system, cone_levels, cone_undefined, conflict_cone, conflict_sink, conflict_source, prettyprint_dot_context::current, debug_off, debug_on, dg_arc_label_conflicts, effect_action, effect_any_reference, effect_words_reference(), prettyprint_dot_context::fd, FindMaximumCommonLevel(), FOREACH, fprint_lsom_as_dense(), fprintf(), full_action_to_short_string(), gen_context_recurse, gen_null2(), get_bool_property(), get_string_property(), graph_vertices, ifdebug, ignore_this_conflict(), INT, level, load_statement_enclosing_loops(), loops_mapping_of_statement(), MAPL, mod_stat, prettyprint_dot_context::ordered, pl, prettyprint_dot_nodes(), prettyprint_dot_context::previous_ordering, print_ordering_to_statement(), print_statement(), prettyprint_dot_context::print_statement, print_words(), reset_enclosing_loops_map(), s1, same_string_p, set_enclosing_loops_map(), sg_fprint_as_ddv(), sg_nbre_droites, sg_nbre_rayons, sg_nbre_sommets, sg_sommets, SG_UNDEFINED_P, statement_domain, statement_ordering, successor_arc_label, successor_vertex, vertex_successors, and vertex_to_statement().
Referenced by do_simplify_dg(), and print_dot_dependence_or_chains_graph().
void prettyprint_graph_daVinci | ( | FILE * | out_f, |
list | l_of_vers | ||
) |
print a graph to daVinci format, each label of successor is represented by a circular node, each vertex is represented by a square node
To match the call to the free() at the end:
out_f | ut_f |
l_of_vers | _of_vers |
Definition at line 63 of file trace.c.
References concatenate(), fprintf(), free(), MAP, strdup(), SUCCESSOR, successor_arc_label, successor_vertex, VERTEX, vertex_successors, and vertex_vertex_label.
Referenced by print_filtered_dg_or_dvdg().
void prettyprint_graph_text | ( | FILE * | out_f, |
list | l_of_vers | ||
) |
print a graph to text format
out_f | ut_f |
l_of_vers | _of_vers |
Definition at line 46 of file trace.c.
References FOREACH, fprintf(), SUCCESSOR, successor_arc_label, successor_vertex, VERTEX, vertex_successors, and vertex_vertex_label.
Referenced by print_filtered_dg_or_dvdg().
name | ame |
Definition at line 131 of file prettyprint.c.
References print_dependence_or_chains_graph().
fd | d |
dc | c |
basis | asis |
Definition at line 974 of file util.c.
References base_fprint(), typ_som::denominateur, prettyprint_dot_context::fd, fprint_string_Value(), fprintf(), print_vect_in_vertice_val(), safe_entity_name(), sg_droites, sg_nbre_droites, sg_nbre_rayons, sg_nbre_sommets, sg_rayons, sg_sommets, SG_UNDEFINED_P, rdte::succ, typ_som::succ, rdte::vecteur, and typ_som::vecteur.
Referenced by dependence_cone_positive(), and TestDependence().
name | ame |
Definition at line 126 of file prettyprint.c.
References print_dependence_or_chains_graph().
Referenced by print_effective_dependence_graph(), print_loop_carried_dependence_graph(), and print_whole_dependence_graph().
This pipmake pass output the chains in a file usable by the graphviz tool dot.
name | is the name of the module, given by pipsmake |
name | ame |
Definition at line 200 of file prettyprint.c.
References print_dot_dependence_or_chains_graph().
This pipmake pass output the DG in a file usable by graphviz tool dot.
name | is the name of the module, given by pipsmake |
name | ame |
Definition at line 210 of file prettyprint.c.
References print_dot_dependence_or_chains_graph().
bool print_effective_dependence_graph | ( | const | string | ) |
string | od_name |
Definition at line 59 of file prettyprint.c.
References print_dependence_graph(), and set_bool_property().
bool print_filtered_dependence_daVinci_graph | ( | const | string | ) |
string | od_name |
Definition at line 52 of file prettyprint.c.
References print_filtered_dg_or_dvdg(), and set_bool_property().
bool print_filtered_dependence_graph | ( | const | string | ) |
string | od_name |
Definition at line 45 of file prettyprint.c.
References print_filtered_dg_or_dvdg(), and set_bool_property().
mod_name | od_name |
is_dv | s_dv |
Definition at line 202 of file trace.c.
References concatenate(), db_build_file_resource_name(), db_get_current_workspace_directory(), db_get_memory_resource(), DB_PUT_FILE_RESOURCE, debug_off, debug_on, dg, free(), gen_free_list(), get_current_module_statement(), local_name_to_top_level_entity(), make_filtered_dg_or_dvdg(), mod_stat, prettyprint_graph_daVinci(), prettyprint_graph_text(), reset_current_module_entity(), reset_current_module_statement(), reset_ordering_to_statement(), safe_fclose(), safe_fopen(), set_current_module_entity(), set_current_module_statement(), set_ordering_to_statement(), and strdup().
Referenced by print_filtered_dependence_daVinci_graph(), and print_filtered_dependence_graph().
bool print_loop_carried_dependence_graph | ( | const | string | ) |
string | od_name |
Definition at line 70 of file prettyprint.c.
References print_dependence_graph(), and set_bool_property().
bool print_loopnest_dependence_cone | ( | const char * | module_name | ) |
Get the loop label from the user
module_name | odule_name |
Definition at line 274 of file trace.c.
References type_sg::base, base_fprint(), concatenate(), cone_generating_system, cone_undefined, CONFLICT, conflict_cone, db_build_file_resource_name(), db_get_current_workspace_directory(), db_get_memory_resource(), DB_PUT_FILE_RESOURCE, debug_off, debug_on, dg, dg_arc_label_conflicts, entity_undefined_p, find_label_entity(), find_loop_from_label(), FOREACH, fprintf(), free(), gen_recurse, gen_true(), get_current_module_statement(), get_string_property(), graph_vertices, local_name_to_top_level_entity(), mod_stat, module_name(), pips_user_warning, print_cone_vecteur(), reset_current_module_entity(), reset_current_module_statement(), reset_ordering_to_statement(), safe_entity_name(), safe_fclose(), safe_fopen(), selected_label, set_current_module_entity(), set_current_module_statement(), set_ordering_to_statement(), sg_droites, sg_nbre_droites, sg_nbre_rayons, sg_nbre_sommets, sg_rayons, sg_sommets, SG_UNDEFINED_P, statement_domain, statement_in_loopnest(), statement_in_loopnest_p, strdup(), string_undefined_p, SUCCESSOR, successor_arc_label, successor_vertex, test_statement_of_reference, vect_chg_sgn(), vect_copy(), vect_rm(), VERTEX, vertex_successors, and vertex_to_statement().
fd | d |
Definition at line 959 of file util.c.
References prettyprint_dot_context::fd, fprint_string_Value(), fprintf(), Svecteur::succ, Svecteur::var, and vect_coeff().
Referenced by print_dependence_cone().
prettyprint.c
prettyprint.c
mod_name | od_name |
Definition at line 34 of file prettyprint.c.
References print_dependence_graph(), and set_bool_property().
void quick_privatize_graph | ( | graph | dep_graph | ) |
we analyze arcs exiting from loop statements
dep_graph | ep_graph |
Definition at line 38 of file quick_privatize.c.
References CONS, dep_graph, ENTITY, entity_undefined, FOREACH, gen_find_eq(), graph_vertices, loop_index, loop_locals, pips_debug, quick_privatize_loop(), s1, statement_loop(), statement_loop_p(), statement_number, successors(), VERTEX, vertex_successors, and vertex_to_statement().
Referenced by compute_dg_on_statement_from_chains_in_place(), and rice_dependence_graph().
void reset_context_map | ( | void | ) |
void ResetLoopCounter | ( | void | ) |
Definition at line 329 of file testdep_util.c.
References ilc.
Referenced by rice_dependence_graph().
bool rice_fast_dependence_graph | ( | char * | mod_name | ) |
mod_name | od_name |
Definition at line 139 of file ricedg.c.
References DG_FAST, dg_type, and rice_dependence_graph().
bool rice_full_dependence_graph | ( | char * | mod_name | ) |
mod_name | od_name |
Definition at line 144 of file ricedg.c.
References DG_FULL, dg_type, and rice_dependence_graph().
bool rice_regions_dependence_graph | ( | char * | mod_name | ) |
mod_name | od_name |
Definition at line 154 of file ricedg.c.
References DG_FAST, dg_type, find_rule_by_resource(), pips_user_warning, rice_dependence_graph(), rule_phase, and same_string_p.
bool rice_semantics_dependence_graph | ( | char * | mod_name | ) |
mod_name | od_name |
Definition at line 149 of file ricedg.c.
References DG_SEMANTICS, dg_type, and rice_dependence_graph().
li | i |
Definition at line 209 of file testdep_util.c.
References Ssysteme::egalites, GetDiVar(), Ssysteme::inegalites, int_to_value, Scontrainte::succ, value_product, vect_add_elem(), vect_coeff(), and Scontrainte::vecteur.
Referenced by build_and_test_dependence_context().
Definition at line 238 of file testdep_util.c.
References Ssysteme::egalites, GetDsiVar(), Ssysteme::inegalites, Scontrainte::succ, vect_add_elem(), vect_coeff(), and Scontrainte::vecteur.
Referenced by build_and_test_dependence_context().
bool sc_faisabilite_optim (Psysteme sc) :
Test system sc feasibility by successive projections along all variables in its basis.
carry out the projection with function sc_projection_optim_along_vecteur().
sc_normalize() is called here before the projection, which means that sc may be deallocated
result :
boolean : true if system is faisable false else
Modification:
Automatic variables read in a CATCH block need to be declared volatile as specified by the documentation
sc | c |
Definition at line 484 of file testdep_util.c.
References Ssysteme::base, base_dup(), base_rm, CATCH, debug(), is_test_Di, overflow_error, pips_debug, sc_dup(), sc_empty_p(), sc_normalize(), sc_projection_optim_along_vecteur_ofl(), sc_rm(), TRY, and UNCATCH.
Referenced by TestDependence().
Psysteme sc_invers(Psysteme ps): calcul un systeme des contraintes qui est l'invers du systeme initial.
pour chaque element b dans le base initial, remplace b par -b dans le systeme initial.
ps | s |
Definition at line 1060 of file testdep_util.c.
References eq, Scontrainte::succ, Svecteur::succ, vect_chg_var_sign(), Scontrainte::vecteur, VECTEUR_NUL_P, and vecteur_var.
Referenced by TestDependence().
void sc_minmax_of_variable_optim(Psysteme ps, Variable var, Value *pmin, *pmax): examine un systeme pour trouver le minimum et le maximum d'une variable apparaissant dans ce systeme par projection a la Fourier-Motzkin.
la procedure retourne la valeur false si le systeme est infaisable et true sinon
le systeme ps est detruit.
projection sur toutes les variables sauf var
cette contrainte nous donne une borne max
cette contrainte nous donne une borne min
ps | s |
var | ar |
pmin | min |
pmax | max |
Definition at line 975 of file testdep_util.c.
References CATCH, debug(), overflow_error, sc_empty_p(), sc_normalize(), sc_projection_optim_along_vecteur_ofl(), sc_rm(), sc_value_of_variable(), Scontrainte::succ, Svecteur::succ, TCST, TRY, UNCATCH, value_gt, value_lt, VALUE_MAX, VALUE_MIN, value_neg_p, value_pdiv, value_pos_p, value_uminus, vect_add_elem(), vect_coeff(), vect_rm(), Scontrainte::vecteur, VECTEUR_NUL_P, and vecteur_var.
Referenced by TestDiVariables().
cl | l |
Definition at line 267 of file testdep_util.c.
References Ssysteme::base, debug(), DiVarLevel(), entity_local_name(), Svecteur::succ, VECTEUR_NUL_P, and vecteur_var.
int sc_proj_optim_on_di_ofl(cl, sc)
This function projects a system onto a set of di variables. This set is defined by cl, the common nesting level of the two array references being tested: only di variables whose nesting level is less than or equal to cl are kept in the projected system (i.e. outermost loops).
The projection is performed by first eliminating variables in the equations. Variables whose coefficients are 1 or -1 are considered first. (in such case it's integer elimination). Remaining inequalities are projected by Fourier-Motzkin elimination.
cl is the common nesting level. sc is the system to project. sc is modified but psc always points to a consistent Psysteme on return (i.e. it's up to the caller to free it). *psc on return is sc_empty() if *psc on entry turns out to be non-feasible. a long jump buffer must have been initialized to handle overflows The value returned is true if the system is feasible, false otherwise.
find the set of variables to be eliminated
find one
cl | l |
psc | sc |
Definition at line 415 of file testdep_util.c.
References DiVarLevel(), fprintf(), ifdebug, is_test_Di, pips_assert, pips_debug, sc_consistent_p(), sc_empty_p(), sc_projection_optim_along_vecteur_ofl(), Svecteur::succ, vect_add_elem(), vect_debug(), vect_rm(), VECTEUR_NUL, VECTEUR_NUL_P, and vecteur_var.
Referenced by TestDependence().
Psysteme sc_projection_optim_along_vecteur_ofl(Psysteme sc, Pvecteur pv)
This fonction returns the projected system resulting of the SUCCESSIVE projections of the system sc along the variables contained in vecteur pv. Variables are only more or less projected according to their order in pv.
The projection is done first by eliminating variables constrained by equations. The variables whose coefficients are 1 (or -1?) are considered first (in such case it is a valide integer elimination), then variables appearing in equations with non unit coefficient, and finally all left over variables in pv using Fourier-Motzkin elimination. At each step, the order in pv is used.
If the system sc is not faisable, SC_EMPTY is returned.
FI: this function could be moved to linear... but for the debugging stuff. Also, it could be broken into three parts. And the number of return statements should be reduced to one.
The elimination of variables using equations
First,carry out the integer elimination possible
coeff == 1, do this integer elimination for variable v with the others contrainte(equations and inequations
remove v from the list of variables to be projected pve
it's in head
carry out the non-exact elimination if necessary and possible using other equations
find a variable which appears in the equations, eliminate it
liminate v in the list of variables pve
it's in head
carry out the elimination using Fourier-Motzkin for the other variables
detection of non feasability of Psysteme sc
sc->inegalites = contrainte_sort(sc->inegalites, sc->base, BASE_NULLE,
true, false);
debug(8, "", "Sorted system :\n");
sc_syst_debug(sc);
}
Are we done? This used to be always true, but sc_normalize() may promote inequalities as equations. Since the projection steps may reveal some implicit equations, we are not sure here that all projections have been performed by the three steps (equations, equations, inequalities).
See for instance the test dependence in SAC/sgemm for such an example.
Update the base and the dimension of the constraint system sc
Clean up auxiliary data structures
sc | c |
pv | v |
Definition at line 648 of file testdep_util.c.
References Ssysteme::base, base_dup(), base_intersection(), BASE_NULLE, BASE_NULLE_P, base_rm, build_sc_nredund_2pass_ofl_ctrl(), combiner_ofl_with_test(), contrainte_var_min_coeff(), egalite_debug(), Ssysteme::egalites, entity_local_name(), eq, fprintf(), free(), FWD_OFL_CTRL, ifdebug, Ssysteme::inegalites, is_test_Di, is_test_exact, is_test_inexact_eq, nb_elems_list(), Ssysteme::nb_eq, Ssysteme::nb_ineq, NbrFMSystNonAug, NbrProjFMTotal, NbrTestProjEq, NbrTestProjEqDi, NbrTestProjFM, NbrTestProjFMDi, pips_assert, pips_debug, prv(), sc_base_remove_variable(), sc_consistent_p(), sc_empty(), sc_empty_p(), sc_normalize(), sc_rm(), sc_syst_debug(), sc_to_minimal_basis(), Svecteur::succ, value_notone_p, Svecteur::var, vect_dump(), vect_dup(), vect_rm(), and VECTEUR_NUL_P.
Referenced by sc_faisabilite_optim(), sc_minmax_of_variable_optim(), and sc_proj_optim_on_di_ofl().
void set_context_map | ( | statement_mapping | ) |
hash_table statements_to_successors | ( | list | statements, |
graph | dg | ||
) |
creates a hash_table containing statements from statements as keys and their respective succesors according to dg as values
statements | input statements |
dg | dependecy graph |
statements | tatements |
dg | g |
Definition at line 1018 of file util.c.
References dg, FOREACH, gen_find_eq(), graph_vertices, HASH_DEFAULT_SIZE, hash_pointer, hash_put(), hash_table_make(), statement_undefined_p, successors(), VERTEX, vertex_successors, and vertex_to_statement().
Referenced by fs_filter(), and if_conversion_compact_stats().
This is a callback for qsort function, it compares two successor.
succ1 | ucc1 |
succ2 | ucc2 |
Definition at line 116 of file util.c.
References successor_vertex, and vertex_sort_callback().
Referenced by prettyprint_dependence_graph(), and xml_Chain_Graph().
list TestCoupleOfReferences | ( | list | , |
Psysteme | , | ||
statement | , | ||
effect | , | ||
reference | , | ||
list | , | ||
Psysteme | , | ||
statement | , | ||
effect | , | ||
reference | , | ||
list | , | ||
Ptsg * | , | ||
list * | , | ||
Ptsg * | |||
) |
Union is not typed...
l1 | 1 |
l2 | 2 |
Definition at line 376 of file impact_check.c.
References CAR, CHUNK, ENDP, gen_cons(), gen_in_list_p(), gen_nconc(), list_undefined, NIL, and POP.
Referenced by check_new_arc_for_structured_statement().
void vect_chg_var_sign(Pvecteur *ppv, Variable var) changement de signe de la coordonnee var du vecteur *ppv
ppv | pv |
var | ar |
Definition at line 1080 of file testdep_util.c.
References Svecteur::succ, Svecteur::val, value_oppose, and Svecteur::var.
Referenced by sc_invers().
Definition at line 51 of file util.c.
References dg_vertex_label_statement, and vertex_vertex_label.
Referenced by compare_vertex(), get_vertex_of_statement(), and init_statement_equivalence_table().
This is a callback for qsort function, it compares two vertex.
v1 | 1 |
v2 | 2 |
Definition at line 105 of file util.c.
References s1, statement_number, and vertex_to_statement().
Referenced by prettyprint_dependence_graph(), successor_sort_callback(), and xml_Chain_Graph().
cproto-generated files
util.c
cproto-generated files
This information is kept in a static hash_table named OrderingToStatement. See ri-util/ordering.c for more information.
Definition at line 45 of file util.c.
Referenced by prettyprint_dependence_graph(), prettyprint_dependence_graph_view(), prettyprint_dot_dependence_graph(), statements_to_successors(), and vertex_sort_callback().
void writeresult | ( | char * | mod_name | ) |
to avoid warnings from compiler
mod_name | od_name |
Definition at line 2268 of file ricedg.c.
References concatenate(), constdep, db_get_current_workspace_directory(), deptype, DG_FAST, DG_FULL, DG_SEMANTICS, dg_type, FMComp, fprintf(), free(), NbrAllEquals, NbrArrayDepInit, NbrDepCnst, NbrDepInexactEFM, NbrDepInexactEq, NbrDepInexactFM, NbrFMSystNonAug, NbrIndepFind, NbrIndexDep, NbrProjFMTotal, NbrScalDep, NbrTestCnst, NbrTestDiCnst, NbrTestDiVar, NbrTestExact, NbrTestGcd, NbrTestProjEq, NbrTestProjEqDi, NbrTestProjFM, NbrTestProjFMDi, NbrTestSimple, pips_internal_error, safe_fclose(), safe_fopen(), and strdup().
Referenced by rice_dependence_graph().
|
extern |
Definition at line 141 of file ricedg.h.
Referenced by compute_dg_on_statement_from_chains_in_place(), rice_dependence_graph(), TestCoupleOfReferences(), and writeresult().
|
extern |
di variables are pseudo variables created by PIPS and not accessible to the user that represent the distance between two dependent statement iterations. the sign of this distance is sufficient for Kennedy's way of parallelizing programs, but the exact value migth be of interest for other algorithms such as systolic algorithms.
Written by Remi, Yi-Qing; reorganized by Yi-Qing (18/09/91) To deal with overflow errors occuring during the projection of a Psysteme along a variable The tables of di variables, li variables and ds variables.
Variable DiVars[i-1] or LiVars[i-1] is associated to the loop at nesting level i. A di variable represents the difference in iteration number between the two references considered.
The variable DsiVars[i] is associated to the ith element in the list of scalar variables modified in the loops
Definition at line 53 of file testdep_util.c.
Referenced by DiVarLevel(), and GetDiVar().
|
extern |
Definition at line 55 of file testdep_util.c.
Referenced by GetDsiVar().
|
extern |
Definition at line 160 of file ricedg.h.
Referenced by rice_update_dependence_graph(), TestCoupleOfReferences(), and TestDependence().
|
extern |
Definition at line 154 of file ricedg.h.
Referenced by rice_dependence_graph(), and writeresult().
|
extern |
Definition at line 158 of file ricedg.h.
Referenced by TestCoupleOfReferences(), and TestDependence().
|
extern |
or counting the number of F-M complexity less than 16.
The complexity of one projection by F-M is multiply of the nbr. of inequations positive and the nbr. of inequations negatives who containe the variable eliminated.The last elem of the array (ie FMComp[17]) is used to count cases with complexity over 16
Definition at line 155 of file ricedg.h.
Referenced by TestCoupleOfReferences(), and TestDependence().
|
extern |
Definition at line 156 of file ricedg.h.
Referenced by TestCoupleOfReferences(), and TestDependence().
|
extern |
Definition at line 157 of file ricedg.h.
Referenced by TestCoupleOfReferences(), and TestDependence().
|
extern |
Definition at line 54 of file testdep_util.c.
Referenced by GetLiVar().
|
extern |
Definition at line 133 of file ricedg.h.
Referenced by rice_dependence_graph(), TestDependence(), TestDiCnst(), and writeresult().
|
extern |
he variables for the statistics of test of dependence and parallelization
he variables for the statistics of test of dependence and parallelization
Remi Triolet, Yi-qing Yang
Modifications:
Notes:
Definition at line 131 of file ricedg.h.
Referenced by rice_dependence_graph(), TestCoupleOfReferences(), and writeresult().
|
extern |
Definition at line 134 of file ricedg.h.
Referenced by rice_dependence_graph(), TestCoupleOfReferences(), and writeresult().
|
extern |
|
extern |
Definition at line 138 of file ricedg.h.
Referenced by rice_dependence_graph(), TestCoupleOfReferences(), and writeresult().
|
extern |
Definition at line 136 of file ricedg.h.
Referenced by rice_dependence_graph(), TestCoupleOfReferences(), and writeresult().
|
extern |
Definition at line 137 of file ricedg.h.
Referenced by rice_dependence_graph(), TestCoupleOfReferences(), and writeresult().
|
extern |
Definition at line 153 of file ricedg.h.
Referenced by rice_dependence_graph(), and writeresult().
|
extern |
Definition at line 132 of file ricedg.h.
Referenced by rice_dependence_graph(), TestDependence(), and writeresult().
|
extern |
Definition at line 140 of file ricedg.h.
Referenced by rice_dependence_graph(), TestCoupleOfReferences(), and writeresult().
|
extern |
Definition at line 152 of file ricedg.h.
Referenced by rice_dependence_graph(), and writeresult().
|
extern |
Definition at line 139 of file ricedg.h.
Referenced by rice_dependence_graph(), TestCoupleOfReferences(), and writeresult().
|
extern |
Definition at line 143 of file ricedg.h.
Referenced by gcd_and_constant_dependence_test(), rice_dependence_graph(), and writeresult().
|
extern |
Definition at line 146 of file ricedg.h.
Referenced by rice_dependence_graph(), TestDependence(), and writeresult().
|
extern |
Definition at line 151 of file ricedg.h.
Referenced by rice_dependence_graph(), TestDependence(), and writeresult().
|
extern |
Definition at line 68 of file ricedg.c.
Referenced by rice_dependence_graph(), TestCoupleOfReferences(), and writeresult().
|
extern |
Definition at line 144 of file ricedg.h.
Referenced by gcd_and_constant_dependence_test(), rice_dependence_graph(), and writeresult().
|
extern |
Definition at line 149 of file ricedg.h.
Referenced by rice_dependence_graph(), and writeresult().
|
extern |
Definition at line 147 of file ricedg.h.
Referenced by rice_dependence_graph(), and writeresult().
|
extern |
Definition at line 150 of file ricedg.h.
Referenced by rice_dependence_graph(), and writeresult().
|
extern |
Definition at line 148 of file ricedg.h.
Referenced by rice_dependence_graph(), and writeresult().
|
extern |
Definition at line 145 of file ricedg.h.
Referenced by rice_dependence_graph(), TestDependence(), and writeresult().