PIPS
|
Go to the source code of this file.
Macros | |
#define | ILCMAX 100000 |
Management of loop counters. More... | |
Functions | |
entity | MakeDiVar (int l) |
This function creates di variables. More... | |
entity | GetDiVar (int l) |
This functions looks up a di variable of nesting level l in table DiVars. More... | |
entity | MakeLiVar (int l) |
This function creates li variables(thee ith loop index variable). More... | |
entity | GetLiVar (int l) |
entity | MakeDsiVar (int l) |
This function creates dsi variables. More... | |
entity | GetDsiVar (int l) |
int | DiVarLevel (entity e) |
this function returns the nesting level of a given di variable e. More... | |
void | sc_add_di (int l, entity e, Psysteme s, int li) |
void | sc_add_dsi (int l, entity e, Psysteme s) |
int | sc_proj_on_di (int cl, Psysteme s) |
Pbase | MakeDibaseinorder (int n) |
Pbase MakeDibaseinorder(int n) make a base of D#1 ... More... | |
int | FindMaximumCommonLevel (cons *n1, cons *n2) |
void | ResetLoopCounter () |
entity | MakeLoopCounter () |
Create a new loop counter variable. More... | |
int | dep_type (action ac1, action ac2) |
int dep_type(action ac1,action ac2) This function test the type of the dependence. More... | |
int | sc_proj_optim_on_di_ofl (int cl, Psysteme *psc) |
int sc_proj_optim_on_di_ofl(cl, sc) More... | |
bool | sc_faisabilite_optim (Psysteme sc) |
bool sc_faisabilite_optim (Psysteme sc) : More... | |
static bool | combiner_ofl_with_test (Psysteme sc, Variable v) |
bool combiner_ofl_with_test(Psysteme sc, Variable v): More... | |
Psysteme | sc_projection_optim_along_vecteur_ofl (Psysteme sc, Pvecteur pv) |
Psysteme sc_projection_optim_along_vecteur_ofl(Psysteme sc, Pvecteur pv) More... | |
bool | sc_minmax_of_variable_optim (Psysteme volatile ps, Variable var, Value *pmin, Value *pmax) |
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. More... | |
Psysteme | sc_invers (Psysteme ps) |
Psysteme sc_invers(Psysteme ps): calcul un systeme des contraintes qui est l'invers du systeme initial. More... | |
void | vect_chg_var_sign (Pvecteur *ppv, Variable var) |
void vect_chg_var_sign(Pvecteur *ppv, Variable var) changement de signe de la coordonnee var du vecteur *ppv More... | |
Variables | |
entity | DiVars [MAXDEPTH] |
here is a collection of function intended to create and manipulate "di" variables and test of dependence. More... | |
entity | LiVars [MAXDEPTH] |
entity | DsiVars [MAXSV] |
static int | ilc = ILCMAX |
#define ILCMAX 100000 |
Management of loop counters.
Definition at line 325 of file testdep_util.c.
bool combiner_ofl_with_test(Psysteme sc, Variable v):
the copy of combiner() adding the test of suffisants conditions of integer combination.
It returns true if exact
apres les combinaisons eliminer les elements devenus inutiles
mise a jour du systeme
Definition at line 533 of file testdep_util.c.
References contrainte_constante_p(), contrainte_free(), contrainte_verifiee(), contraintes_free(), FMComp, FWD_OFL_CTRL, Ssysteme::inegalites, is_test_exact, is_test_inexact_fm, nb_elems_list(), Ssysteme::nb_ineq, sc_dup(), sc_rm(), Scontrainte::succ, value_neg_p, value_pos_p, vect_coeff(), and Scontrainte::vecteur.
Referenced by sc_projection_optim_along_vecteur_ofl().
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().
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().
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().
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().
void ResetLoopCounter | ( | void | ) |
Definition at line 329 of file testdep_util.c.
References ilc.
Referenced by 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 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().
here is a collection of function intended to create and manipulate "di" variables and test of dependence.
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().
Definition at line 55 of file testdep_util.c.
Referenced by GetDsiVar().
Definition at line 327 of file testdep_util.c.
Referenced by MakeLoopCounter(), and ResetLoopCounter().
Definition at line 54 of file testdep_util.c.
Referenced by GetLiVar().