PIPS
|
Go to the source code of this file.
Macros | |
#define | Psysteme_undefined SC_UNDEFINED |
to map statements to execution contexts More... | |
#define | DG_FAST 1 |
Different types of dependence tests: More... | |
#define | DG_FULL 2 |
#define | DG_SEMANTICS 3 |
Functions | |
static bool | rice_dependence_graph (char *) |
INTERFACE FUNCTIONS More... | |
bool | rice_fast_dependence_graph (char *mod_name) |
bool | rice_full_dependence_graph (char *mod_name) |
bool | rice_semantics_dependence_graph (char *mod_name) |
bool | rice_regions_dependence_graph (char *mod_name) |
static void | rdg_unstructured (unstructured) |
STATIC FUNCTION DECLARATIONS More... | |
static void | rdg_statement (statement) |
static void | rdg_loop (statement) |
static void | rice_update_dependence_graph (statement stat, set region) |
Update of dependence graph. More... | |
static list | TestCoupleOfEffects (statement s1, effect e1, statement s2, effect e2, list llv, Ptsg *gs, list *levelsop, Ptsg *gsop) |
DEPENDENCE TEST More... | |
static list | TestDependence (list n1, Psysteme sc1, statement s1, effect ef1, reference r1, list n2, Psysteme sc2, statement s2, effect ef2, reference r2, list llv, Ptsg *gs, list *levelsop, Ptsg *gsop) |
static list TestDependence(list n1, n2, Psysteme sc1, sc2, statement s1, s2, effect ef1, ef2, reference r1, r2, list llv, list *levelsop, Ptsg *gs,*gsop) input : list n1, n2 : enclosing loops for statements s1 and s2; Psysteme sc1, sc2: current context for each statement; statement s1, s2 : currently analyzed statements; effect ef1, ef2 : effects of each statement upon the current variable; (maybe array regions) reference r1, r2 : current variables references; list llv : loop variant list (variables that vary in loop nests n1 and n2?); list *levelsop : dependence levels from s2 to s1 Ptsg *gs,*gsop : dependence cones from s1 to s2 and from s2 to s1 output : dependence levels from s1 to s2 modifies : levelsop, gsop, gs and returns levels More... | |
static bool | build_and_test_dependence_context (reference r1, reference r2, Psysteme sc1, Psysteme sc2, Psysteme *psc_dep, list llv, list s2_enc_loops) |
static bool build_and_test_dependence_context(reference r1, r2, Psystem sc1, sc2, *psc_dep, list llv, s2_enc_loops) input : reference r1, r2 : current array references; Psystem sc1, sc2 : context systems for r1 and r2; they might be modified and even be freed (!) by normalization procedures Psystem *psc_dep : pointer toward the dependence context systeme; list llv : current loop nest variant list; list s2_enc_loops : statement s2 enclosing loops; More... | |
static bool | gcd_and_constant_dependence_test (reference r1, reference r2, list llv, list s2_enc_loops, Psysteme *psc_dep) |
static bool gcd_and_constant_dependence_test(references r1, r2, list llv, s2_enc_loops, Psysteme *psc_dep) input : references r1, r2 : current references; list llv : loop nest variant list; list s2_enc_loops : enclosing loops for statement s2; Psysteme *psc_dep : pointer toward the depedence system; output : true if there is no dependence (GCD and constant test successful); false if independence could not be proved. More... | |
static void | dependence_system_add_lci_and_di (Psysteme *psc_dep, list s1_enc_loops, Pvecteur *p_DiIncNonCons) |
static void dependence_system_add_lci_and_di(Psysteme *psc_dep, list s1_enc_loops, Pvecteur *p_DiIncNonCons) input : Psysteme *psc_dep : pointer toward the dependence system; list s1_enc_loops : statement s1 enclosing loops; Pvecteur *p_DiIncNonCons : pointer toward DiIncNonCons. More... | |
static list | TestDiVariables (Psysteme, int, statement, effect, statement, effect) |
static Ptsg | dependence_cone_positive (Psysteme dep_sc) |
Ptsg dependence_cone_positive(Psysteme dept_syst) More... | |
static list | loop_variant_list (statement) |
static bool | TestDiCnst (Psysteme, int, statement, effect, statement, effect) |
list | TestCoupleOfReferences (list n1, Psysteme sc1 __attribute__((unused)), statement s1, effect ef1, reference r1, list n2, Psysteme sc2 __attribute__((unused)), statement s2, effect ef2, reference r2, list llv, Ptsg *gs __attribute__((unused)), list *levelsop __attribute__((unused)), Ptsg *gsop __attribute__((unused))) |
static list | TestDiVariables (Psysteme ps, int cl, statement s1, effect ef1 __attribute__((unused)), statement s2, effect ef2 __attribute__((unused))) |
static bool | TestDiCnst (Psysteme ps, int cl, statement s1, effect ef1 __attribute__((unused)), statement s2, effect ef2 __attribute__((unused))) |
this function detects intra-statement, non loop carried dependence ( Di=(0,0,...0) and s1 = s2). More... | |
void | writeresult (char *mod_name) |
graph | compute_dg_on_statement_from_chains_in_place (statement s, graph chains) |
graph | compute_dg_on_statement_from_chains (statement s, graph chains) |
Variables | |
int | NbrArrayDepInit = 0 |
Dependence Graph computation for Allen & Kennedy algorithm. More... | |
int | NbrIndepFind = 0 |
int | NbrAllEquals = 0 |
int | NbrDepCnst = 0 |
int | NbrTestExact = 0 |
int | NbrDepInexactEq = 0 |
int | NbrDepInexactFM = 0 |
int | NbrDepInexactEFM = 0 |
int | NbrScalDep = 0 |
int | NbrIndexDep = 0 |
int | deptype [5][3] |
int | constdep [5][3] |
int | NbrTestCnst = 0 |
int | NbrTestGcd = 0 |
int | NbrTestSimple = 0 |
int | NbrTestDiCnst = 0 |
by sc_normalize() More... | |
int | NbrTestProjEqDi = 0 |
int | NbrTestProjFMDi = 0 |
int | NbrTestProjEq = 0 |
int | NbrTestProjFM = 0 |
int | NbrTestDiVar = 0 |
int | NbrProjFMTotal = 0 |
int | NbrFMSystNonAug = 0 |
int | FMComp [18] |
bool | is_test_exact = true |
or counting the number of F-M complexity less than 16. More... | |
bool | is_test_inexact_eq = false |
bool | is_test_inexact_fm = false |
bool | is_dep_cnst = false |
bool | is_test_Di |
bool | Finds2s1 |
static graph | dg |
to map statements to enclosing loops More... | |
static bool | PRINT_RSDG = false |
static int | dg_type = DG_FAST |
int | Nbrdo |
loop.c More... | |
#define DG_FAST 1 |
#define Psysteme_undefined SC_UNDEFINED |
|
static |
static bool build_and_test_dependence_context(reference r1, r2, Psystem sc1, sc2, *psc_dep, list llv, s2_enc_loops) input : reference r1, r2 : current array references; Psystem sc1, sc2 : context systems for r1 and r2; they might be modified and even be freed (!) by normalization procedures Psystem *psc_dep : pointer toward the dependence context systeme; list llv : current loop nest variant list; list s2_enc_loops : statement s2 enclosing loops;
output : bool : false if one of the initial systems is unfeasible after normalization; true otherwise; *psc_dep : dependence system is the function value is true; SC_EMPTY otherwise; no need to sc_rm() in the latter case.
side effects : psc_dep : points toward the dependence context system built from sc1 and sc2, r1 and r2, and llv. Dependence distance variables (di) are introduced in sc2, along with the dsi variables to take care of variables in llv modified in the loop nest; irrelevant (?) existencial constraints are removed. in order to make further manipulations easier. sc1 : side_effect of sc_normalize() sc2 : side_effect of sc_normalize()
Comment :
Modifications:
Construction of initial systems sc_dep and sc_tmp from sc1 and sc2 if not undefined
sc_dep = sc1, but: we keep only useful constraints in the predicate (To avoid overflow errors, and to make projections easier)
sc_tmp = sc2, but: we keep only useful constraints in the predicate (To avoid overflow errors, and to make projections easier)
FI: I'm not sure this is correct. I'm afraid sc2 might be unfeasible and become feasible due to a careless elimination... It all depends on:
sc_restricted_to_variables_transitive_closure()
There might be a better function for that purpose
introduce dependence distance variable if loop increment value is known or ...
FI: a more powerful evaluation function for inc should be called when preconditions are available. For instance, mdg could be handled without having to partial_evaluate it
It's not clear whether sc1 or sc2 should be used to estimate a variable increment like N.
It's not clear whether it's correct or not. You would like N (or other variables in the increment expression) to be constant within the loop nest.
It would be better to know the precondition associated to the corresponding loop statement, but the information is lost in this low-level function.
FI: this is not true, you have sc1 and sc2 at hand to call sc_minmax_of_variable()
take care of variables modified in the loop
sc_tmp is emptied and freed by sc_fusion()
Definition at line 1580 of file ricedg.c.
References Ssysteme::base, base_add_variable(), BASE_NULLE, BASE_UNDEFINED, CAR, CDR, debug(), ENTITY, EXPRESSION, FOREACH, GetLiVar(), ifdebug, loop_increment_value(), loop_index, NIL, NORMALIZE_EXPRESSION, normalized_linear, normalized_linear_p, pips_assert, pips_debug, reference_indices, sc_add_di(), sc_add_dsi(), sc_chg_var(), sc_creer_base(), sc_empty_p(), sc_fusion(), sc_new(), sc_restricted_to_variables_transitive_closure(), sc_syst_debug(), STATEMENT, statement_loop(), Svecteur::succ, TCST, variables, vect_rm(), VECTEUR_NUL_P, and vecteur_var.
Referenced by TestDependence().
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().
Ptsg dependence_cone_positive(Psysteme dept_syst)
add the contraints bj = 0 (1<=j<i)
add the contraints - bi <= -1 (1<=j<i)
dans le cas d'une erreur d'overflow, on fait comme si le test avait renvoye' true. bc.
to mimic previous behavior of sc_normalize
We get a normalized sub lexico-positive dependence system
dep_sc | ep_sc |
Definition at line 2096 of file ricedg.c.
References b1, type_sg::base, base_dup(), CATCH, contrainte_make(), fprintf(), FWD_OFL_CTRL, ifdebug, overflow_error, pips_debug, print_dependence_cone(), sc_dup(), sc_empty(), sc_empty_p(), sc_enveloppe_chernikova(), sc_integer_feasibility_ofl_ctrl(), sc_normalize(), sc_rm(), sc_rn_p(), sc_syst_debug(), sc_to_sg_chernikova(), sg_new(), sg_rm(), SG_UNDEFINED_P, TCST, TRY, UNCATCH, vect_add_elem(), vect_new(), and vect_size().
Referenced by TestDependence().
|
static |
static void dependence_system_add_lci_and_di(Psysteme *psc_dep, list s1_enc_loops, Pvecteur *p_DiIncNonCons) input : Psysteme *psc_dep : pointer toward the dependence system; list s1_enc_loops : statement s1 enclosing loops; Pvecteur *p_DiIncNonCons : pointer toward DiIncNonCons.
output : none
modifies :
*psc_dep, the dependence systeme (addition of constraints with lci and di variables, if useful; lci is a loop counter, di an iteration difference variable);
DiIncNonCons: di variables are added to DiIncNonCons (means Di variables for loops with non constant increment, i.e. unknown increment), if any such loop exists.
comment : DiIncNonCons must be undefined on entry.
Addition of lck, the loop counters, and di, the iteration difference, variables (if useful).
If the loop increment is not trivial, express the current index value as the sum of the lower bound and the product of the loop counter by the loop increment.
Else, this new equation would be redundant
make nl + inc*lc# - ind = 0
If the loop increment is unknown, which is expressed by inc==0, well, I do not understand what li variables are, not how they work
make d::i - l::i + ind = 0 , add d::i in list of DiIncNonCons
Update basis
Definition at line 1883 of file ricedg.c.
References BASE_NULLE_P, BASE_UNDEFINED, CAR, CDR, contrainte_make(), GetDiVar(), GetLiVar(), loop_increment_value(), loop_index, loop_range, MakeLoopCounter(), NIL, NORMALIZE_EXPRESSION, normalized_linear, normalized_linear_p, pips_assert, range_lower, sc_creer_base(), STATEMENT, statement_loop(), vect_add_elem(), vect_dup(), vect_rm(), and VECTEUR_UNDEFINED_P.
Referenced by TestDependence().
|
static |
static bool gcd_and_constant_dependence_test(references r1, r2, list llv, s2_enc_loops, Psysteme *psc_dep) input : references r1, r2 : current references; list llv : loop nest variant list; list s2_enc_loops : enclosing loops for statement s2; Psysteme *psc_dep : pointer toward the depedence system; output : true if there is no dependence (GCD and constant test successful); false if independence could not be proved.
modifies : *psc_dep; at least adds dependence equations on phi variables comment :
Further construction of the dependence system; Constant and GCD tests at the same time.
test of GCD
C assumed
Update base of *psc_dep
Definition at line 1761 of file ricedg.c.
References base_union(), CAR, CDR, COEFF_CST, contrainte_constante_p(), contrainte_make(), egalite_normalize(), ENTITY, entity_user_name(), EXPRESSION, fortran_module_p(), get_current_module_entity(), GetDiVar(), GetDsiVar(), GetLiVar(), int_to_value, loop_increment_value(), loop_index, NbrTestCnst, NbrTestGcd, NIL, NORMALIZE_EXPRESSION, normalized_linear, normalized_linear_p, pips_assert, pips_debug, pips_internal_error, pips_user_warning, reference_indices, reference_variable, sc_consistent_p(), sc_to_minimal_basis(), STATEMENT, statement_loop(), value_notzero_p, value_product, vect_add_elem(), vect_chg_var(), vect_coeff(), vect_dup(), vect_in_basis_p(), vect_rm(), vect_size(), vect_substract(), and VECTEUR_UNDEFINED_P.
Referenced by TestDependence().
stat | tat |
Definition at line 2201 of file ricedg.c.
References action_write_p, CONS, EFFECT, effect_action, effect_entity(), ENTITY, entity_all_locations_p(), entity_integer_scalar_p(), entity_undefined, FOREACH, gen_find_eq(), gen_nconc(), load_cumulated_rw_effects_list(), loop_body, loop_locals, NIL, pips_assert, statement_declarations, statement_loop(), and statement_loop_p().
Referenced by rice_update_dependence_graph().
|
static |
stat | tat |
Definition at line 452 of file ricedg.c.
References distributable_loop(), fprintf(), get_bool_property(), ifdebug, loop_body, print_statement_set(), rdg_statement(), region, region_of_loop(), rice_update_dependence_graph(), set_free(), set_undefined, statement_loop(), and statement_number.
Referenced by rdg_statement().
|
static |
stat | tat |
Definition at line 409 of file ricedg.c.
References FOREACH, forloop_body, forloop_undefined, instruction_block, instruction_forloop, instruction_tag, instruction_test, instruction_unstructured, instruction_whileloop, is_instruction_block, is_instruction_call, is_instruction_expression, is_instruction_forloop, is_instruction_goto, is_instruction_loop, is_instruction_test, is_instruction_unstructured, is_instruction_whileloop, pips_internal_error, rdg_loop(), rdg_unstructured(), STATEMENT, statement_instruction, statement_undefined, test_false, test_true, whileloop_body, and whileloop_undefined.
Referenced by compute_dg_on_statement_from_chains_in_place(), rdg_loop(), rdg_unstructured(), and rice_dependence_graph().
|
static |
STATIC FUNCTION DECLARATIONS
Definition at line 399 of file ricedg.c.
References CONTROL_MAP, control_statement, gen_free_list(), NIL, rdg_statement(), and unstructured_control.
Referenced by rdg_statement().
|
static |
INTERFACE FUNCTIONS
The supplementary call to init_ordering_to_statement should be avoided if ordering.c were more clever.
we need to access the statements from their ordering for the dependance-graph:
Do this as late as possible as it is also used by pipsdbm...
walk thru mod_stat to find well structured loops. update dependence graph for these loops.
write the result to the file correspondant in the order of : module,NbrArrayDeptInit,NbrIndeptFind,NbrArrayDepInit,NbrScalDep, NbrIndexDep,deptype[5][3]
FI: this is not a proper way to do it
mod_name | od_name |
Definition at line 230 of file ricedg.c.
References chains(), clean_enclosing_loops(), concatenate(), constdep, copy_graph(), current_shared_obj_table_size(), db_get_current_workspace_directory(), db_get_memory_resource(), DB_PUT_MEMORY_RESOURCE, debug_off, debug_on, deptype, dg, DG_SEMANTICS, dg_type, FMComp, fprintf(), gen_allocated_memory(), get_bool_property(), get_current_module_statement(), graph_consistent_p(), hash_warn_on_redefinition(), ifdebug, local_name_to_top_level_entity(), loops_mapping_of_statement(), mod_stat, module, NbrAllEquals, NbrArrayDepInit, NbrDepCnst, NbrDepInexactEFM, NbrDepInexactEq, NbrDepInexactFM, Nbrdo, NbrFMSystNonAug, NbrIndepFind, NbrIndexDep, NbrProjFMTotal, NbrScalDep, NbrTestCnst, NbrTestDiCnst, NbrTestDiVar, NbrTestExact, NbrTestGcd, NbrTestProjEq, NbrTestProjEqDi, NbrTestProjFM, NbrTestProjFMDi, NbrTestSimple, pips_debug, prettyprint_dependence_graph(), PRINT_RSDG, quick_privatize_graph(), rdg_statement(), reset_cumulated_rw_effects(), reset_current_module_entity(), reset_current_module_statement(), reset_ordering_to_statement(), reset_precondition_map(), ResetLoopCounter(), RICEDG_PROVIDE_STATISTICS, safe_fclose(), safe_fopen(), set_cumulated_rw_effects(), set_current_module_entity(), set_current_module_statement(), set_enclosing_loops_map(), set_ordering_to_statement(), set_precondition_map(), strdup(), and writeresult().
Referenced by rice_fast_dependence_graph(), rice_full_dependence_graph(), rice_regions_dependence_graph(), and rice_semantics_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().
Update of dependence graph.
The update of conflict information is performed for all statements in a loop. This set of statements seems to be defined by "region", while the loop is defined by "stat".
Let v denote a vertex, a an arc, s a statement attached to a vertex and c a conflict, i.e. a pair of effects (e1,e2). Each arc is labelled by a list of statements. Each vertex points to a list of arcs. Each arc points to a list of conflicts. See dg.f.tex and graph.f.tex in Documentation/Newgen for more details.
The procedure is quite complex because:
The procedure is made of many too many nested loops and tests:
for all vertex v1 in graph dg if statement s1 associated to v1 in region for all arcs a1 outgoing from v1 let v2 be the sink of a1 and s2 the statement associated to v2 if s2 in region for all conflicts c12 carried by a1 if c12 has not yet been refined if c12 may have a symmetric conflict for all arcs a2 outgoing from the sink v2 of a1 if sink(a2) equals v1 for all conflicts c21 if c21 equal c12 halleluia! compute refined dependence information for c12 and possibly c21 possibly update c21 and possibly remove a2 update c12 and possibly remove a1
Good luck for the restructuring! I'm not sure the current procedure might not end up removing as a2 the very same arc a1 it uses to iterate...
This conflict cone has been updated.
ompute this conflit and the opposite one
ooking for the opposite dependence from (s2,e2) to (s1,e1)
Make sure that you do not try to find the very same conflict: eliminate symmetric conflicts like dd's, and, if the KEEP-READ-READ-DEPENDENCE option is on, the unusual uu's.
&& (reference_indices(effect_any_reference(e1))) != NIL)
if (!Finds2s1) pips_internal_error("Expected opposite dependence are not found");
freed in of leaked.
updating DG for the dependence (s1,e1)-->(s2,e2)
updating DG for the dependence (s2,e2)-->(s1,e1)
en_free(cs2s1);
They are in the same conflicts list
This successor has only one conflict that has been killed.
gen_free_list(dg_arc_label_conflicts(dal));
fdebug(4){ prettyprint_dependence_graph(stderr, mod_stat, dg); }
Definition at line 560 of file ricedg.c.
References action_read_p, action_write_p, CAR, CDR, cone_undefined, CONFLICT, conflict_cone, conflict_sink, conflict_source, conflict_undefined, CONS, contexts_mapping_of_nest(), debug(), dg, dg_arc_label_conflicts, dg_arc_label_undefined, DG_FULL, dg_type, dg_vertex_label_sccflags, effect_action, effect_undefined, ENTITY, entity_local_name(), Finds2s1, fprintf(), free_conflict(), free_successor(), gen_copy_seq(), gen_free_list(), gen_nconc(), gen_remove(), get_current_module_statement(), graph_vertices, ifdebug, list_undefined, loop_variant_list(), make_cone(), make_sccflags(), MAP, newgen_arc_label, NIL, pips_assert, pips_debug, prettyprint_dependence_graph(), print_statement_set(), print_words(), region, reset_context_map(), s1, scc_undefined, set_belong_p(), set_context_map(), SG_UNDEFINED, SG_UNDEFINED_P, statement_loop_p(), statement_number, SUCCESSOR, successor_arc_label, successor_arc_label_, successor_undefined, successor_vertex, TestCoupleOfEffects(), VERTEX, vertex_successors, vertex_to_statement(), vertex_undefined, vertex_vertex_label, and words_effect().
Referenced by rdg_loop().
|
static |
DEPENDENCE TEST
use region information if some is available
This is not correct because loop bounds should be frozen on loop entry; we assume variables used in loop bounds are not too often modified by the loop body
s1 | 1 |
e1 | 1 |
s2 | 2 |
e2 | 2 |
llv | lv |
gs | s |
levelsop | evelsop |
gsop | sop |
Definition at line 821 of file ricedg.c.
References DG_FAST, DG_FULL, DG_SEMANTICS, dg_type, effect_any_reference, effect_system, load_statement_context(), load_statement_enclosing_loops(), load_statement_precondition(), pips_internal_error, predicate_system, s1, TestCoupleOfReferences(), and transformer_relation.
Referenced by rice_update_dependence_graph().
list TestCoupleOfReferences | ( | list | n1, |
Psysteme sc1 | __attribute__(unused), | ||
statement | s1, | ||
effect | ef1, | ||
reference | r1, | ||
list | n2, | ||
Psysteme sc2 | __attribute__(unused), | ||
statement | s2, | ||
effect | ef2, | ||
reference | r2, | ||
list | llv, | ||
Ptsg *gs | __attribute__(unused), | ||
list *levelsop | __attribute__(unused), | ||
Ptsg *gsop | __attribute__(unused) | ||
) |
if (e1 == e2 && !entity_scalar_p(e1) && !entity_scalar_p(e2))
FI: Why have two tests under the condition e1==e2?
FI: this test must be modified to take pointer dereferencing such as p[i] into account, although p as an entity generates atomic references.
If chains.c were updated, we could also check that: gen_length(b1)==gen_length(b2).
A(*) reference appears in the dependence graph
llv is freed here
test the dependence type, constant dependence?
test the dependence type, constant dependence? exact dependence?
the case of scalar variables and equivalenced arrays
calar variable dependence
ase of scalar variable dependence
Definition at line 905 of file ricedg.c.
References b1, b2, CONS, constdep, dep_type(), deptype, effect_action, entity_all_locations_p(), entity_atomic_reference_p(), entity_type, entity_user_name(), FindMaximumCommonLevel(), Finds2s1, fprintf(), gen_free_list(), gen_length(), gen_nconc(), get_bool_property(), ifdebug, instruction_loop_p, INT, is_dep_cnst, is_test_exact, is_test_inexact_eq, is_test_inexact_fm, NbrArrayDepInit, NbrDepCnst, NbrDepInexactEFM, NbrDepInexactEq, NbrDepInexactFM, NbrIndexDep, NbrScalDep, NbrTestExact, NIL, pips_user_warning, pointer_type_p(), print_words(), reference_indices, reference_variable, s1, statement_instruction, statement_number, statement_possible_less_p(), TestDependence(), ultimate_type(), and words_effect().
Referenced by TestCoupleOfEffects().
|
static |
static list TestDependence(list n1, n2, Psysteme sc1, sc2, statement s1, s2, effect ef1, ef2, reference r1, r2, list llv, list *levelsop, Ptsg *gs,*gsop) input : list n1, n2 : enclosing loops for statements s1 and s2; Psysteme sc1, sc2: current context for each statement; statement s1, s2 : currently analyzed statements; effect ef1, ef2 : effects of each statement upon the current variable; (maybe array regions) reference r1, r2 : current variables references; list llv : loop variant list (variables that vary in loop nests n1 and n2?); list *levelsop : dependence levels from s2 to s1 Ptsg *gs,*gsop : dependence cones from s1 to s2 and from s2 to s1 output : dependence levels from s1 to s2 modifies : levelsop, gsop, gs and returns levels
Comments :
This procedure has been amplified twice. The initial procedure only computed the dependence levels, "levels", for conflict s1->s2. The dependence cone computation was added by Yi-Qing Yang. She later added the computation of the dependence levels and the dependence cone for symetrical conflict, s2 -> s1, because both conflicts share the same dependence system and because a set of tests can be shared.
For her PhD, Yi-Qing Yang also added intermediate tests and instrumentation.
This much too long procedure is made of three parts: 0. The initialization of the dependence system
Modification :
Automatic variables read in a CATCH block need to be declared volatile as specified by the documentation
Elimination of loop indices from loop variants llv
We use n2 because we take care of variables modified in an iteration only for the second system.
llv is dead, must be freed...
Build the dependence context system from the two initial context systems sc1 and sc2. BC
the context system is not feasible : no dependence. BC
No dep_syst() to deallocate either, FI
Further construction of the dependence system; Constant and GCD tests at the same time.
independence proved
FI: the next statement was commented out...
Consistency Test
find independences (non loop carried dependence, intra-statement).
Such dependences are counted here as independence, but other parallelizer preserve them because they are useful for (assembly) instructon level scheduling
Some kind of arithmetic error, e.g. an integer overflow has occured. Assume dependence to be conservative.
FI: wouldn't it be simpler to enumerate the useful di variables?!?
eliminate non di variables from the basis
Here, the long jump overflow buffer is handled at a lower level!
keep DiIncNonCons variables if their value is unknown or different from zero. Otherwise eliminate them from the dep_syst
FI: I'm lost for this step. My guess DiIncNonCons==VECTEUR_NUL in 99.99 % of all cases...
Compute the levels for dependence arc s1 to s2 and of the opposite dependence arc s2 to s1. Also compute the dependence cones if some level exists (FI: shouldn't it be a loop-carried level?).
For both cases, two systems are allocated, one is used to find the dependence levels, the other one to compute the dependence cone.
For s1->s2, dep_syst is used to compute the levels and dep_syst1 the cone.
For s2->s1, dep_syst_op (op==oppposite) is used to find the dependence levels, and dep_syst2 the dependence cone.
Build the dependence system for the opposite arc s2->s1 before dep_syst is modified
Start processing for arc s1->s2
Make a proper copy of dep_syst before it is destroyed to compute dependence levels. The basis must be in a specific order to check lexico-positivity.
Compute dependence levels for s1->s2
dep_syst is unfeasible or almost empty, and now useless
if (levels == NIL) NbrTestDiVar++; Qui l'a enleve', pourquoi ?
If the cone is not feasible, there are no loop-carried dependences. (FI: the cone is strictly positive then...)
This might not havebeen found by the previous test when computing levels.
But the dependence cone construction does not consider non-loop carried dependences; so we can only remove those levels that are smaller than the number of common levels
print results for arc s1->s2
Start the processing for arc s2->s1
if (*levelsop == NIL) NbrTestDiVar++; Pourquoi?
if the cone is not feasible, there are no loop-carried dependences; this was not found by the previous test when computing levels; but the dependence cone construction does not consider non-loop carried dependences; so we can only remove those levels that are smaller than the number of common levels
the case of "all equals" independence at the same statement
Definition at line 1151 of file ricedg.c.
References assert, Ssysteme::base, base_add_variable(), base_dup(), base_rm, BASE_UNDEFINED, build_and_test_dependence_context(), CATCH, CONS, debug(), dependence_cone_positive(), dependence_system_add_lci_and_di(), Ssysteme::dimension, DiVarLevel(), FindMaximumCommonLevel(), Finds2s1, FOREACH, fprintf(), gcd_and_constant_dependence_test(), gen_free_list(), gen_remove(), ifdebug, INT, is_dep_cnst, is_test_exact, is_test_inexact_eq, is_test_inexact_fm, loop_index, MakeDibaseinorder(), MAP, Ssysteme::nb_eq, NbrAllEquals, NbrIndepFind, NbrTestDiCnst, NbrTestDiVar, NbrTestSimple, NIL, ok, overflow_error, pips_assert, pips_debug, pl, print_arguments(), print_dependence_cone(), s1, sc_consistent_p(), sc_dup(), sc_elim_var(), sc_empty_p(), sc_faisabilite_optim(), sc_invers(), sc_normalize(), sc_proj_optim_on_di_ofl(), sc_rm(), sc_rn(), sc_syst_debug(), sc_value_of_variable(), sc_weak_consistent_p(), sg_empty, sg_rm(), SG_UNDEFINED, SG_UNDEFINED_P, STATEMENT, statement_loop(), Svecteur::succ, TestDiCnst(), TestDiVariables(), TRY, UNCATCH, value_notzero_p, Svecteur::var, vect_debug(), VECTEUR_NUL_P, and vecteur_var.
Referenced by TestCoupleOfReferences().
|
static |
this function detects intra-statement, non loop carried dependence ( Di=(0,0,...0) and s1 = s2).
case of di zero
Definition at line 2231 of file ricedg.c.
References GetDiVar(), NbrAllEquals, s1, sc_dup(), sc_rm(), sc_value_of_variable(), and value_notzero_p.
|
static |
FI: Keep a consistent interface in memory allocation
Psysteme pss = (l==cl) ? ps : sc_dup(ps);
This function does not test feasibility and does not deallocate ps
If there is no dependence at a common loop level: since the system is feasible, it can be a dependence at the innermost level (inside the common loop nest).
WARNING:
If the source and target statements are identical, we do not add the innermost level because the parallelization phase (rice) does not appreciate. In order to be correct, we should add this level 1) because the statement may be a call to an external routine, in which case we cannot be sure that all the writes are performed before the reads and 2) even in the case of a single assignement, the generated code must preserve the order of the write and read memory operations. BC.
Definition at line 1997 of file ricedg.c.
References CONS, entity_local_name(), fprint_string_Value(), fprintf(), gen_nconc(), GetDiVar(), ifdebug, INT, max, min, NIL, pips_debug, s1, sc_dup(), sc_force_variable_to_zero(), sc_minmax_of_variable_optim(), statement_possible_less_p(), value_neg_p, value_pos_p, and value_zero_p.
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().
int constdep[5][3] |
Definition at line 74 of file ricedg.c.
Referenced by compute_dg_on_statement_from_chains_in_place(), rice_dependence_graph(), TestCoupleOfReferences(), and writeresult().
int deptype[5][3] |
Definition at line 74 of file ricedg.c.
Referenced by compute_dg_on_statement_from_chains_in_place(), rice_dependence_graph(), TestCoupleOfReferences(), and writeresult().
|
static |
to map statements to enclosing loops
DEFINE_CURRENT_MAPPING(loops, list) now defined in ri-util, BA, September 1993 the dependence graph being updated
Definition at line 110 of file ricedg.c.
Referenced by compute_dg_on_statement_from_chains(), compute_dg_on_statement_from_chains_in_place(), rice_dependence_graph(), and rice_update_dependence_graph().
Definition at line 128 of file ricedg.c.
Referenced by compute_dg_on_statement_from_chains_in_place(), rice_dependence_graph(), rice_fast_dependence_graph(), rice_full_dependence_graph(), rice_regions_dependence_graph(), rice_semantics_dependence_graph(), rice_update_dependence_graph(), TestCoupleOfEffects(), and writeresult().
bool Finds2s1 |
Definition at line 97 of file ricedg.c.
Referenced by rice_update_dependence_graph(), TestCoupleOfReferences(), and TestDependence().
int FMComp[18] |
Definition at line 86 of file ricedg.c.
Referenced by combiner_ofl_with_test(), rice_dependence_graph(), and writeresult().
Definition at line 95 of file ricedg.c.
Referenced by TestCoupleOfReferences(), and TestDependence().
bool is_test_Di |
Definition at line 96 of file ricedg.c.
Referenced by sc_faisabilite_optim(), sc_proj_optim_on_di_ofl(), and sc_projection_optim_along_vecteur_ofl().
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 92 of file ricedg.c.
Referenced by combiner_ofl_with_test(), sc_projection_optim_along_vecteur_ofl(), TestCoupleOfReferences(), and TestDependence().
Definition at line 93 of file ricedg.c.
Referenced by sc_projection_optim_along_vecteur_ofl(), TestCoupleOfReferences(), and TestDependence().
Definition at line 94 of file ricedg.c.
Referenced by combiner_ofl_with_test(), TestCoupleOfReferences(), and TestDependence().
int NbrAllEquals = 0 |
Definition at line 66 of file ricedg.c.
Referenced by rice_dependence_graph(), TestDependence(), TestDiCnst(), and writeresult().
int NbrArrayDepInit = 0 |
Dependence Graph computation for Allen & Kennedy algorithm.
he variables for the statistics of test of dependence and parallelization
Remi Triolet, Yi-qing Yang
Modifications:
Notes:
Definition at line 64 of file ricedg.c.
Referenced by rice_dependence_graph(), TestCoupleOfReferences(), and writeresult().
int NbrDepCnst = 0 |
Definition at line 67 of file ricedg.c.
Referenced by rice_dependence_graph(), TestCoupleOfReferences(), and writeresult().
int NbrDepInexactEFM = 0 |
Definition at line 71 of file ricedg.c.
Referenced by rice_dependence_graph(), TestCoupleOfReferences(), and writeresult().
int NbrDepInexactEq = 0 |
Definition at line 69 of file ricedg.c.
Referenced by rice_dependence_graph(), TestCoupleOfReferences(), and writeresult().
int NbrDepInexactFM = 0 |
Definition at line 70 of file ricedg.c.
Referenced by rice_dependence_graph(), TestCoupleOfReferences(), and writeresult().
int NbrFMSystNonAug = 0 |
Definition at line 85 of file ricedg.c.
Referenced by rice_dependence_graph(), sc_projection_optim_along_vecteur_ofl(), and writeresult().
int NbrIndepFind = 0 |
Definition at line 65 of file ricedg.c.
Referenced by rice_dependence_graph(), TestDependence(), and writeresult().
int NbrIndexDep = 0 |
Definition at line 73 of file ricedg.c.
Referenced by rice_dependence_graph(), TestCoupleOfReferences(), and writeresult().
int NbrProjFMTotal = 0 |
Definition at line 84 of file ricedg.c.
Referenced by rice_dependence_graph(), sc_projection_optim_along_vecteur_ofl(), and writeresult().
int NbrScalDep = 0 |
Definition at line 72 of file ricedg.c.
Referenced by rice_dependence_graph(), TestCoupleOfReferences(), and writeresult().
int NbrTestCnst = 0 |
Definition at line 75 of file ricedg.c.
Referenced by gcd_and_constant_dependence_test(), rice_dependence_graph(), and writeresult().
int NbrTestDiCnst = 0 |
Definition at line 78 of file ricedg.c.
Referenced by rice_dependence_graph(), TestDependence(), and writeresult().
int NbrTestDiVar = 0 |
Definition at line 83 of file ricedg.c.
Referenced by rice_dependence_graph(), TestDependence(), and writeresult().
int NbrTestExact = 0 |
Definition at line 68 of file ricedg.c.
Referenced by rice_dependence_graph(), TestCoupleOfReferences(), and writeresult().
int NbrTestGcd = 0 |
Definition at line 76 of file ricedg.c.
Referenced by gcd_and_constant_dependence_test(), rice_dependence_graph(), and writeresult().
int NbrTestProjEq = 0 |
Definition at line 81 of file ricedg.c.
Referenced by rice_dependence_graph(), sc_projection_optim_along_vecteur_ofl(), and writeresult().
int NbrTestProjEqDi = 0 |
Definition at line 79 of file ricedg.c.
Referenced by rice_dependence_graph(), sc_projection_optim_along_vecteur_ofl(), and writeresult().
int NbrTestProjFM = 0 |
Definition at line 82 of file ricedg.c.
Referenced by rice_dependence_graph(), sc_projection_optim_along_vecteur_ofl(), and writeresult().
int NbrTestProjFMDi = 0 |
Definition at line 80 of file ricedg.c.
Referenced by rice_dependence_graph(), sc_projection_optim_along_vecteur_ofl(), and writeresult().
int NbrTestSimple = 0 |
Definition at line 77 of file ricedg.c.
Referenced by rice_dependence_graph(), TestDependence(), and writeresult().
Definition at line 112 of file ricedg.c.
Referenced by rice_dependence_graph().