25 #include "pips_config.h"
106 pips_assert(
"interactive_partitioning_matrix", n>=1);
112 string saved_ptr,
buffer,elem = NULL;
116 for(row=1;row<=n;row++){
117 elem = strtok_r(
line,
" ",&ctxt1);
121 if(!elem) elem =
col==row ?
"1" :
"0";
123 elem = strtok_r(NULL,
" ",&ctxt1);
125 line = strtok_r(NULL,
",",&ctxt0);
142 bool return_status =
false;
148 pips_assert(
"interactive_partitioning_matrix", n>=1);
149 debug(8,
"interactive_partitioning_matrix",
"Reading P\n");
151 for(row=1; row<=n; row++) {
153 "(give all its integer coordinates on one line of %d per row): ",
155 if (resp[0] ==
'\0') {
156 user_log(
"Tiling loop transformation has been cancelled.\n");
157 return_status =
false;
160 cn = strtok(resp,
" \t");
162 return_status =
true;
166 "Tiling loop transformation has been cancelled.\n");
167 return_status =
false;
173 "Hyperplane loop transformation has been cancelled.\n");
174 return_status =
false;
177 cn = strtok(NULL,
" \t");
183 "Tiling loop transformation has been cancelled.\n");
184 return_status =
false;
200 return return_status;
224 debug(8,
"tile_membership_constraints",
"Begin with Matrix HT:\n");
230 for(row = 1; row <= dim; row++) {
236 for(
col = 1, civ = initial_basis, ctv = tile_basis;
262 pips_debug(8,
"End with constraint system mc:\n");
290 debug(8,
"tile_membership_constraints",
"Begin with Matrix HT:\n");
307 if(!
empty_string_p(tile_direction) && strcmp(tile_direction,
"TP") == 0) {
313 (void)
fprintf(stdout,
"The hyperplane direction h_tile is :");
322 (void)
fprintf(stderr,
"The tile scanning base G_tile is :");
334 for(row = 1; row <= dim; row++) {
349 for(col2 = 1, ctv = tile_basis; col2 <= dim; col2++,ctv =
vecteur_succ(ctv)) {
369 pips_debug(8,
"End with constraint system mc:\n");
382 for(row=0; row<dim; row++) {
385 h_tile[row]+=
ACCESS(P, dim, row+1,
col+1);
395 (void)
fprintf(stdout,
"The first scanning direction h_tile in %s mode is :",(option==1)?
"LP":
"LS");
424 if (!
empty_string_p(local_tile_direction) && strcmp(local_tile_direction,
"LI") != 0) {
426 if(strcmp(local_tile_direction,
"LP") == 0) {
435 if(strcmp(local_tile_direction,
"LS") == 0) {
438 for (pdim=1; !legal && pdim<=n; pdim++) {
442 fprintf(stderr,
"Check the legality of the chosen LOCAL basis");
443 (void)
fprintf(stderr,
"Temporary local tile scanning base G_tile obtained with %d-th Pvecteur :",pdim);
449 if (pdim>n && !legal)
457 (void)
fprintf(stderr,
"The local tile scanning base G_tile - i = G_tile.i_prime is :");
470 for(row = 1, civ = initial_basis; row <= dim; row++, civ =
vecteur_succ(civ)) {
485 pips_debug(8,
"End with constraint system mc:\n");
490 sc_projection_along_variables_ofl_ctrl(&mc2,initial_basis ,
OFL_CTRL);
492 pips_debug(8,
"End with constraint system mc after change of basis:\n");
506 for (cs = lls; cs !=
NIL; cs =
CDR(cs)){
533 Psysteme sc_B_second = SC_UNDEFINED;
534 Pbase initial_basis = NULL;
535 Pbase tile_basis = NULL;
536 Pbase reverse_tile_basis = NULL;
538 Pbase new_basis = NULL;
553 pips_debug(8,
"Begin with iteration domain:\n");
563 for (
int k=1; k <=(
int)strlen(smatrix); k++)
564 if (smatrix[k]==
',') ndim++;
600 pips_debug(8,
"Inverse partitioning matrix HT:");
611 (void)
fprintf(stderr,
"Tile membership constraints:\n");
617 (void)
fprintf(stderr,
"sc_B_prime after call to sc_append (is the basis ok?):\n");
624 sc_B_second =
sc_dup(sc_B_prime);
628 sc_projection_along_variables_ofl_ctrl(&sc_B_prime, initial_basis,
OFL_CTRL);
630 (void)
fprintf(stderr,
"Tile domain:\n");
637 (void)
fprintf(stderr,
"Tile domain in echelon format:\n");
645 (void)
fprintf(stderr,
"new_basis\n");
652 (void)
fprintf(stderr,
"sc_B_second:\n");
657 (void)
fprintf(stderr,
"Iteration domain for one tile:\n");
674 (void)
fprintf(stderr,
"The tile scanning base G is before ID:");
679 (void)
fprintf(stderr,
"The tile scanning base G is:");
692 (void)
fprintf(stderr,
"The local coordinate change vector is:");
693 for (
int i=1; i<=n; i++)
699 new_basis, sc_tile,
false);
704 for (pb = reverse_tile_basis; pb!=NULL; pb=pb->
succ) {
727 bool return_status =
false;
731 return return_status;
755 for (row=1; row<=dim; row++) {
766 fprintf(stdout,
"NON LEGAL TILING: H(%d,*)*SG =%d <0\n", row,accu);
769 *legal=(*legal) &&
false;
774 fprintf(stdout,
"LEGAL TILING: H(%d,*)*SG =%d >=0\n", row,accu);
854 fprintf(stdout,
" Different SIZES for base %d and matrice %d, Partial tiling case ?\n",bl,dim);
861 for (row=1; row<=bl; row++) {
878 pips_user_warning(
" Different SIZES for dependence cone basis %d and partitioning matrice %d\n",bl,dim);
913 sc_projection_along_variable_ofl_ctrl
918 if (SC_EMPTY_P(sc2)) {
928 if (SC_EMPTY_P(sc3)) {
949 Psysteme sc_B_prime_2 = SC_UNDEFINED;
950 Pbase initial_basis = NULL;
951 Pbase tile_basis = NULL;
952 Pbase local_tile_basis = NULL;
953 Pbase reverse_tile_basis = NULL;
954 Pbase new_basis = NULL;
965 #define maxscinfosize 100
974 pips_debug(8,
"Begin with iteration domain:\n");
980 for (
int k=1; k <=(
int)strlen(smatrix); k++)
981 if (smatrix[k]==
',') ndim++;
1017 pips_debug(8,
"Inverse partitioning matrix HT = P^-1:");
1032 (void)
fprintf(stderr,
"Tile membership constraints:\n");
1038 (void)
fprintf(stderr,
"sc_B_prime after call to sc_append :\n");
1047 (void)
fprintf(stderr,
"sc_B_prime2 after change of local basis:\n");
1054 (void)
fprintf(stderr,
"new_basis\n");
1058 sc_tmp=
sc_dup(sc_B_prime_2);
1062 sc_proj2 =
sc_dup(sc_B_prime_2);
1074 sc_tmp=
sc_dup(list_of_systems[1]);
1075 for (i = 2; sc_tmp != NULL && i <=
vect_size(new_basis);i++) {
1081 fprintf(stdout,
" Constraints on the %d-th var. :\n",i);
1089 sc_tile =
sc_dup(list_of_systems[1]);
1093 (void)
fprintf(stderr,
"Tile domain in echelon format:\n");
1097 sc_local_tile =
sc_dup(list_of_systems[i]);
1100 sc_local_tile =
sc_intersection(sc_local_tile,sc_local_tile,list_of_systems[i]);
1102 (void)
fprintf(stderr,
"Iteration domain for one tile:\n");
1109 (void)
fprintf(stderr,
"The local coordonate change vector is:");
1110 for (
int i=1; i<=n; i++)
1115 local_tile_basis, sc_local_tile,
false);
1119 for (pb = reverse_tile_basis; pb!=NULL; pb=pb->
succ) {
1134 else pips_user_warning(
"PIPS legality test for Tiling transformation NOT VERIFIED, Verify data dependencies or simplify array access functions\n");
1145 bool return_status =
false;
1147 return return_status;
static void statement_in_loopnest(statement s)
static statement test_statement_of_reference
Psysteme local_tile_constraints(Pbase initial_basis, Pbase local_tile_basis, Psysteme sc, matrice P, Pvecteur *pvch, statement st)
statement parallel_tiling(list lls, _UNUSED_ bool(*u)(statement))
Pvecteur loop_nest_to_offset(list lls)
bool parallel_loop_tiling(const char *module_name)
bool loop_tiling(const char *module_name)
Psysteme sc_projection_concat_proj_on_variables(Psysteme sc, Pbase index_base)
static entity make_local_tile_index_entity(entity old_index)
dg_vertex_label vertex_label
static Psysteme tile_membership_constraints(Pbase initial_basis, Pbase tile_basis, matrice HT, Pvecteur tiling_offset)
Generate the tile membership constraints between a tile coordinates and an iteration coordinate.
bool static_partitioning_matrix(matrice P, int n, const char *serialized_matrix)
tiling.c
statement tiling_transformation(list lls, _UNUSED_ bool(*u)(statement))
Generate tiled code for a loop nest, PPoPP'91, p.
bool check_tiling_legality(statement loopnest_st, matrice H, int dim)
static void legal_point_p(Pvecteur v, Ptsg gs, matrice H, int dim, bool *legal)
dg_arc_label arc_label
package tiling
Psysteme tile_hyperplane_constraints(Pbase initial_basis, Pbase tile_basis, matrice HT, Pvecteur tiling_offset)
Generate the tile membership constraints between a tile coordinates and an iteration coordinate.
static entity make_tile_index_entity(entity old_index)
Create a new entity for tile index.
static bool statement_in_loopnest_p
static void check_positive_dependence(Ptsg gs, matrice H, int dim, bool *legal)
bool interactive_partitioning_matrix(matrice P, int n)
Query the user for a partitioning matrix P.
static void compute_local_change_of_basis(Value *h_tile, matrice P, matrice G, int option, int dim, int selected_Pdim)
void user_log(const char *format,...)
execution make_execution(enum execution_utype tag, void *val)
loop make_loop(entity a1, range a2, statement a3, entity a4, execution a5, list a6)
expression copy_expression(expression p)
EXPRESSION.
instruction make_instruction(enum instruction_utype tag, void *val)
range make_range(expression a1, expression a2, expression a3)
#define value_uminus(val)
unary operators on values
void const char const char const int
Pbase base_add_variable(Pbase b, Variable var)
Pbase base_add_variable(Pbase b, Variable v): add variable v as a new dimension to basis b at the end...
bool vect_in_basis_p(Pvecteur v, Pbase b)
Pvecteur vect_in_basis_p(Pvecteur v, Pbase b): check that all coordinates in v are in b,...
Pbase base_reversal(Pbase b_in)
Pbase base_reversal(Pbase b_in): produces a basis b_out, having the same basis vectors as b_in,...
static graph dg
dg is the dependency graph ; FIXME : should not be static global ?
void derive_new_basis(Pbase base_oldindex, Pbase *base_newindex, entity(*new_entity)(entity))
package conversion
void scanning_base_to_vect(matrice G, int n, Pbase base, pvg)
void scanning_base_to_vect(matrice G,int n,Pbase base,Pvecteur pvg[n]) compute G*base and put the res...
statement code_generation(list lls, Pvecteur pvg[], Pbase base_oldindex, Pbase base_newindex, Psysteme sc_newbase, bool preserve_entry_label_p)
package hyperplane
void constraint_distribution(Psysteme sc, Psysteme *bound_systems, Pbase index_base, int sc_info[][4])
Distribution of the constraints of the system sc into several systems.
#define CONTRAINTE_UNDEFINED
Pcontrainte contrainte_make(Pvecteur pv)
Pcontrainte contrainte_make(Pvecteur pv): allocation et initialisation d'une contrainte avec un vecte...
Psysteme loop_iteration_domaine_to_sc(list, Pbase *)
loop_iteration_domaine_to_sc.c
struct _newgen_struct_status_ * status
#define cone_generating_system(x)
#define CONFLICT(x)
CONFLICT.
#define dg_arc_label_conflicts(x)
bool empty_string_p(const char *s)
const char * module_name(const char *s)
Return the module part of an entity name.
char * get_string_property(const char *)
bool get_bool_property(const string)
FC 2015-07-20: yuk, moved out to prevent an include cycle dependency include "properties....
#define gen_recurse(start, domain_number, flt, rwt)
#define successor_vertex(x)
#define successor_arc_label(x)
struct _newgen_struct_graph_ * graph
#define vertex_successors(x)
#define SUCCESSOR(x)
SUCCESSOR.
#define graph_vertices(x)
statement instruction_to_statement(instruction)
Build a statement from a give instruction.
const char * get_current_module_name(void)
Get the name of the current module.
statement get_current_module_statement(void)
Get the current module statement.
bool gen_true(__attribute__((unused)) gen_chunk *unused)
Return true and ignore the argument.
#define NIL
The empty list (nil in Lisp)
size_t gen_length(const list l)
#define CAR(pcons)
Get the value of the first element of a list.
#define FOREACH(_fe_CASTER, _fe_item, _fe_list)
Apply/map an instruction block on all the elements of a list.
#define CDR(pcons)
Get the list less its first element.
#define list_undefined
Undefined list definition :-)
string db_get_memory_resource(const char *rname, const char *oname, bool pure)
Return the pointer to the resource, whatever it is.
void scanning_base_hyperplane(Value[], int, matrice)
scanning_base.c
statement vertex_to_statement(vertex v)
Vertex_to_statement looks for the statement that is pointed to by vertex v.
static statement mod_stat
We want to keep track of the current statement inside the recurse.
float_t space[SIZE][SIZE]
void vect_fprint(FILE *f, Pvecteur v, get_variable_name_t variable_name)
void vect_fprint(FILE * f, Pvecteur v, char * (*variable_name)()): impression d'un vecteur creux v su...
int vect_size(Pvecteur v)
package vecteur - reductions
#define DENOMINATOR(matrix)
int DENOMINATEUR(matrix): acces au denominateur global d'une matrice matrix La combinaison *(&()) est...
#define ACCESS(matrix, column, i, j)
Macros d'acces aux elements d'une matrice.
#define matrice_new(n, m)
Allocation et desallocation d'une matrice.
Value * matrice
package matrice
void matrice_general_inversion(matrice a, matrice inv_a, int n)
void matrice_general_inversion(matrice a; matrice inv_a; int n) calcul de l'inversion du matrice gene...
void matrice_identite(matrice, int, int)
void matrice_identite(matrice ID, int n, int level) Construction d'une sous-matrice identite dans ID(...
void matrice_fprint(FILE *, matrice, int, int)
matrice_io.c
#define pips_debug
these macros use the GNU extensions that allow variadic macros, including with an empty list.
#define pips_user_warning
#define pips_assert(what, predicate)
common macros, two flavors depending on NDEBUG
void debug(const int the_expected_debug_level, const char *calling_function_name, const char *a_message_format,...)
ARARGS0.
string user_request(const char *,...)
Psysteme elim_redund_sc_with_sc(Psysteme sc1, Psysteme sc2, Pbase index_base, int dim)
Build the system of inequations of sc1 no-redundant with system sc2.
#define string_undefined_p(s)
hash_table set_ordering_to_statement(statement s)
To be used instead of initialize_ordering_to_statement() to make sure that the hash table ots is in s...
void reset_ordering_to_statement(void)
Reset the mapping from ordering to statement.
void make_bound_expression(Variable index, Pbase base, Psysteme sc, expression *lower, expression *upper)
void make_bound_expression(variable index, Pbase base, Psysteme sc, expression *lower,...
const char * entity_user_name(entity e)
Since entity_local_name may contain PIPS special characters such as prefixes (label,...
const char * entity_local_name(entity e)
entity_local_name modified so that it does not core when used in vect_fprint, since someone thought t...
entity entity_empty_label(void)
bool expression_integer_value(expression e, intptr_t *pval)
expression int_to_expression(_int i)
transform an int into an expression and generate the corresponding entity if necessary; it is not cle...
entity make_new_index_entity(entity, string)
#define instruction_loop(x)
#define statement_domain
newgen_sizeofexpression_domain_defined
#define statement_instruction(x)
@ is_execution_sequential
#define statement_number(x)
#define statement_undefined
#define STATEMENT(x)
STATEMENT.
Psysteme sc_empty(Pbase b)
Psysteme sc_empty(Pbase b): build a Psysteme with one unfeasible constraint to define the empty subsp...
void sc_creer_base(Psysteme ps)
void sc_creer_base(Psysteme ps): initialisation des parametres dimension et base d'un systeme lineair...
void sc_rm(Psysteme ps)
void sc_rm(Psysteme ps): liberation de l'espace memoire occupe par le systeme de contraintes ps;
void sc_add_egalite(Psysteme p, Pcontrainte e)
void sc_add_egalite(Psysteme p, Pcontrainte e): macro ajoutant une egalite e a un systeme p; la base ...
Psysteme sc_new(void)
Psysteme sc_new(): alloue un systeme vide, initialise tous les champs avec des valeurs nulles,...
Psysteme sc_init_with_sc(Psysteme sc)
This function returns a new empty system which has been initialized with the same dimension and base ...
void sc_add_inegalite(Psysteme p, Pcontrainte i)
void sc_add_inegalite(Psysteme p, Pcontrainte i): macro ajoutant une inegalite i a un systeme p; la b...
Psysteme sc_dup(Psysteme ps)
Psysteme sc_dup(Psysteme ps): should becomes a link.
Psysteme sc_copy(Psysteme ps)
Psysteme sc_copy(Psysteme ps): duplication d'un systeme (allocation et copie complete des champs sans...
void build_sc_nredund_1pass(Psysteme volatile *ps)
Computation of a new system sc from the system ps, where each constraint of the system ps is added to...
Psysteme build_integer_sc_nredund(volatile Psysteme ps, Pbase index_base, int tab_info[][4], int loop_level, int dim_h __attribute__((unused)), int n __attribute__((unused)))
Computation of a new system sc from the system ps, where each constraint of the system ps is added to...
void sc_integer_projection_information(Psysteme sc, Pbase index_base, int sc_info[][4], int dim_h, int n)
This function gives information about the variables and the constraints of the system.
Psysteme sc_append(Psysteme s1, Psysteme s2)
Psysteme sc_append(Psysteme s1, Psysteme s2): calcul de l'intersection des polyedres definis par s1 e...
Psysteme sc_intersection(Psysteme s1, Psysteme s2, Psysteme s3)
Psysteme sc_intersection(Psysteme s1, Psysteme s2, Psysteme s3): calcul d'un systeme de contraintes s...
void sc_fprint(FILE *fp, Psysteme ps, get_variable_name_t nom_var)
void sc_fprint(FILE * f, Psysteme ps, char * (*nom_var)()): cette fonction imprime dans le fichier po...
int fprintf()
test sc_min : ce test s'appelle par : programme fichier1.data fichier2.data ...
Psysteme new_loop_bound(Psysteme scn, Pbase base_index)
Psysteme new_loop_bound(Psysteme scn, Pbase base_index) computation of the new iteration space (given...
Psysteme sc_normalize(Psysteme ps)
Psysteme sc_normalize(Psysteme ps): normalisation d'un systeme d'equation et d'inequations lineaires ...
#define G(j, a, b)
maybe most of them should be functions?
Psysteme sc_elim_var(Psysteme sc, Variable v)
package sur les systemes de contraintes sc
void vect_chg_sgn(Pvecteur v)
void vect_chg_sgn(Pvecteur v): multiplie v par -1
static int line
FLEX_SCANNER.
#define sg_sommets(sg)
vieilles definitions des fonctions d'impression void sg_fprint(); #define print_sg(sg) sg_fprint(stdo...
#define sg_rayons(sg)
acces au premier rayon de la liste des rayons d'un systeme generateur defini par un pointeur: sg_rayo...
struct type_sg * Ptsg
Representation d'un systeme generateur par trois ensembles de sommets de rayons et de droites.
#define sg_nbre_sommets(sg)
nombre de sommets: int sg_nbre_sommets(Ptsg)
#define SG_UNDEFINED_P(sg)
#define sg_nbre_droites(sg)
nombre de droites: int sg_nbre_droites(Ptsg)
#define sg_nbre_rayons(sg)
nombre de rayons: int sg_nbre_rayons(Ptsg)
#define sg_droites(sg)
acces a la premiere droite de la liste des droites d'un systeme generateur defini par un pointeur: sg...
void sg_fprint_as_dense(FILE *f, Ptsg sg, Pbase b)
void sg_fprint_as_dense(FILE * f, Ptsg sg): impression d'un systeme generateur
le type des coefficients dans les vecteurs: Value est defini dans le package arithmetique
The structure used to build lists in NewGen.
structure de donnees Sommet
Representation d'un systeme generateur par trois ensembles de sommets de rayons et de droites.
#define VARIABLE_DEFINED_P(v)
#define TCST
VARIABLE REPRESENTANT LE TERME CONSTANT.
#define VECTEUR_NUL
DEFINITION DU VECTEUR NUL.
char *(* get_variable_name_t)(Variable)
void * Variable
arithmetique is a requirement for vecteur, but I do not want to inforce it in all pips files....
#define base_dimension(b)
#define OFL_CTRL
I do thing that overflows are managed in a very poor manner.
struct Svecteur Svecteur
le type des coefficients dans les vecteurs: Value est defini dans le package arithmetique
Pbase vect_copy(Pvecteur b)
direct duplication.
Pvecteur vect_dup(Pvecteur v_in)
Pvecteur vect_dup(Pvecteur v_in): duplication du vecteur v_in; allocation de et copie dans v_out;.
Pvecteur vect_new(Variable var, Value coeff)
Pvecteur vect_new(Variable var,Value coeff): allocation d'un vecteur colineaire au vecteur de base va...
Pbase base_copy(Pbase b)
Direct duplication.
void vect_rm(Pvecteur v)
void vect_rm(Pvecteur v): desallocation des couples de v;
Pvecteur vect_add(Pvecteur v1, Pvecteur v2)
package vecteur - operations binaires
void vect_add_elem(Pvecteur *pvect, Variable var, Value val)
void vect_add_elem(Pvecteur * pvect, Variable var, Value val): addition d'un vecteur colineaire au ve...
Value vect_coeff(Variable var, Pvecteur vect)
Variable vect_coeff(Variable var, Pvecteur vect): coefficient de coordonnee var du vecteur vect —> So...
void vect_chg_coeff(Pvecteur *ppv, Variable var, Value val)
void vect_chg_coeff(Pvecteur *ppv, Variable var, Value val): mise de la coordonnee var du vecteur *pp...