PIPS
|
#include <stdlib.h>
#include <stdio.h>
#include <strings.h>
#include "genC.h"
#include "linear.h"
#include "ri.h"
#include "effects.h"
#include "misc.h"
#include "text.h"
#include "pipsdbm.h"
#include "boolean.h"
#include "vecteur.h"
#include "contrainte.h"
#include "sc.h"
#include "matrice.h"
#include "matrix.h"
#include "sparse_sc.h"
#include "ri-util.h"
#include "effects-util.h"
#include "conversion.h"
#include "dg.h"
#include "graph.h"
#include "ricedg.h"
#include "transformations.h"
#include "properties.h"
#include "tiling.h"
#include "movements.h"
#include "hyperplane.h"
Go to the source code of this file.
Macros | |
#define | maxscinfosize 100 |
Typedefs | |
typedef dg_arc_label | arc_label |
package tiling More... | |
typedef dg_vertex_label | vertex_label |
Functions | |
static entity | make_tile_index_entity (entity old_index) |
Create a new entity for tile index. More... | |
static entity | make_local_tile_index_entity (entity old_index) |
bool | static_partitioning_matrix (matrice P, int n, const char *serialized_matrix) |
tiling.c More... | |
bool | interactive_partitioning_matrix (matrice P, int n) |
Query the user for a partitioning matrix P. More... | |
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. More... | |
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. More... | |
static void | compute_local_change_of_basis (Value *h_tile, matrice P, matrice G, int option, int dim, int selected_Pdim) |
Psysteme | local_tile_constraints (Pbase initial_basis, Pbase local_tile_basis, Psysteme sc, matrice P, Pvecteur *pvch, statement st) |
Pvecteur | loop_nest_to_offset (list lls) |
statement | tiling_transformation (list lls, _UNUSED_ bool(*u)(statement)) |
Generate tiled code for a loop nest, PPoPP'91, p. More... | |
bool | loop_tiling (const char *module_name) |
static void | statement_in_loopnest (statement s) |
static void | legal_point_p (Pvecteur v, Ptsg gs, matrice H, int dim, bool *legal) |
static void | check_positive_dependence (Ptsg gs, matrice H, int dim, bool *legal) |
bool | check_tiling_legality (statement loopnest_st, matrice H, int dim) |
Psysteme | sc_projection_concat_proj_on_variables (Psysteme sc, Pbase index_base) |
statement | parallel_tiling (list lls, _UNUSED_ bool(*u)(statement)) |
bool | parallel_loop_tiling (const char *module_name) |
Variables | |
static bool | statement_in_loopnest_p = false |
static statement | test_statement_of_reference |
#define maxscinfosize 100 |
typedef dg_arc_label arc_label |
package tiling
typedef dg_vertex_label vertex_label |
Definition at line 782 of file tiling.c.
References legal_point_p(), sg_droites, sg_nbre_droites, sg_nbre_rayons, sg_nbre_sommets, sg_rayons, sg_sommets, vect_chg_sgn(), vect_copy(), and vect_rm().
Referenced by check_tiling_legality().
loopnest_st | oopnest_st |
dim | im |
Definition at line 812 of file tiling.c.
References ACCESS, type_sg::base, check_positive_dependence(), cone_generating_system, cone_undefined, CONFLICT, conflict_cone, db_get_memory_resource(), DENOMINATOR, dg, dg_arc_label_conflicts, FOREACH, fprintf(), gen_recurse, gen_true(), get_current_module_name(), graph_vertices, ifdebug, matrice_free, matrice_identite(), matrice_new, module_name(), pips_user_warning, SG_UNDEFINED_P, statement_domain, statement_in_loopnest(), statement_in_loopnest_p, SUCCESSOR, successor_arc_label, successor_vertex, test_statement_of_reference, vect_size(), VERTEX, vertex_successors, and vertex_to_statement().
Referenced by local_tile_constraints(), and parallel_tiling().
|
static |
computation of the hyperplane tile direction in the tile basis: = sum(hi)= 1H
The local tile direction is colinear to the (selected_Pdim) partitioning vecteur
computation of the local tile scanning base G according to h_tile
Definition at line 376 of file tiling.c.
References ACCESS, fprintf(), G, ifdebug, printf(), scanning_base_hyperplane(), and VALUE_ZERO.
Referenced by local_tile_constraints().
Query the user for a partitioning matrix P.
Query the user for P's components
Definition at line 137 of file tiling.c.
References ACCESS, debug(), DENOMINATOR, fprintf(), ifdebug, matrice_fprint(), pips_assert, pips_debug, string_undefined, user_log(), user_request(), VALUE_FMT, and VALUE_ONE.
Referenced by parallel_tiling(), and tiling_transformation().
Definition at line 749 of file tiling.c.
References ACCESS, type_sg::base, fprintf(), ifdebug, pips_debug, sg_fprint_as_dense(), Svecteur::succ, VARIABLE_DEFINED_P, vect_coeff(), vect_in_basis_p(), VECTEUR_NUL_P, and vecteur_var.
Referenced by check_positive_dependence().
Psysteme local_tile_constraints | ( | Pbase | initial_basis, |
Pbase | local_tile_basis, | ||
Psysteme | sc, | ||
matrice | P, | ||
Pvecteur * | pvch, | ||
statement | st | ||
) |
computation of the hyperplane tile direction in the tile basis: = sum(hi)= 1H
The local tile direction is legal and colinear to the partitioning vecteur (pdim)
Build the constraints 0 <= det(HT).[HT. (i -i0)]<det(HT).1 with i0=P.G_tile.i_tile <==> 0 <= det(HT).[HT. (i -P.G_tile.i_tile)]<det(HT).1 <==> 0 <= det(HT).[HT.i -G_tile.i_tile]<= det(HT)-1
initial_basis | nitial_basis |
local_tile_basis | ocal_tile_basis |
sc | c |
pvch | vch |
st | t |
Definition at line 407 of file tiling.c.
References ACCESS, Ssysteme::base, base_add_variable(), base_dimension, BASE_UNDEFINED, check_tiling_legality(), compute_local_change_of_basis(), contrainte_make(), CONTRAINTE_UNDEFINED, Ssysteme::dimension, empty_string_p(), entity_local_name(), fprintf(), get_string_property(), ifdebug, malloc(), matrice_fprint(), matrice_general_inversion(), matrice_identite(), matrice_new, OFL_CTRL, pips_assert, pips_debug, sc_add_egalite(), sc_dup(), sc_fprint(), scanning_base_to_vect(), VALUE_ONE, VALUE_ZERO, vect_add_elem(), vect_new(), VECTEUR_NUL_P, vecteur_succ, and vecteur_var.
Referenced by parallel_tiling().
lls | ls |
Definition at line 501 of file tiling.c.
References CAR, CDR, expression_integer_value(), instruction_loop, intptr_t, list_undefined, loop_index, loop_range, NIL, origin, range_lower, STATEMENT, statement_instruction, vect_chg_coeff(), and VECTEUR_NUL.
Referenced by parallel_tiling(), and tiling_transformation().
bool loop_tiling | ( | const char * | module_name | ) |
module_name | odule_name |
Definition at line 725 of file tiling.c.
References interactive_loop_transformation(), module_name(), and tiling_transformation().
Definition at line 98 of file tiling.c.
References make_new_index_entity().
Referenced by parallel_tiling().
Create a new entity for tile index.
Because of the module name, it is easier to postfix by "_t" than to prefix by "t_".
Definition at line 93 of file tiling.c.
References make_new_index_entity().
Referenced by parallel_tiling(), and tiling_transformation().
bool parallel_loop_tiling | ( | const char * | module_name | ) |
module_name | odule_name |
Definition at line 1143 of file tiling.c.
References interactive_loop_transformation(), module_name(), and parallel_tiling().
iteration domain
Tile membership constraints
Partitioning matrix
Transposed matrix of the inverse of P
number of indices, i.e. loop nest depth
Tiling offset: 0 by default
computation of the partitioning matrix P and its inverse HT
make the constraint system for the iteration space and find a good origin for the tiling if the transformation is legal
Compute B': each iteration i in the iteration space is linked to its tile s
mc and SC_B_prime are aliased after this call
computation of the base scanning local tile elements and its constraints
Build the new basis (tile_basis+local_tile_basis)
generation of code for scanning one tile
generation of code to scan one tile and update of loop body using pvch
generation of code for scanning all tiles
Definition at line 942 of file tiling.c.
References base_dimension, base_reversal(), build_integer_sc_nredund(), CAR, CDR, check_tiling_legality(), code_generation(), constraint_distribution(), copy_expression(), debug_off, debug_on, derive_new_basis(), Ssysteme::dimension, elim_redund_sc_with_sc(), empty_string_p(), entity_empty_label(), entity_user_name(), fprintf(), gen_length(), get_bool_property(), get_current_module_statement(), get_string_property(), ifdebug, instruction_to_statement(), int, int_to_expression(), interactive_partitioning_matrix(), is_execution_sequential, is_instruction_loop, local_tile_constraints(), loop_iteration_domaine_to_sc(), loop_nest_to_offset(), loop_undefined, make_bound_expression(), make_execution(), make_instruction(), make_local_tile_index_entity(), make_loop(), make_range(), make_tile_index_entity(), malloc(), matrice_fprint(), matrice_general_inversion(), matrice_new, maxscinfosize, mod_stat, NIL, pips_debug, pips_user_error, pips_user_warning, reset_ordering_to_statement(), sc_append(), sc_dup(), sc_fprint(), sc_init_with_sc(), sc_integer_projection_information(), sc_intersection(), sc_normalize(), sc_projection_concat_proj_on_variables(), sc_rm(), set_ordering_to_statement(), space, STATEMENT, statement_undefined, static_partitioning_matrix(), string_undefined_p, Svecteur::succ, tile_hyperplane_constraints(), UU, Svecteur::var, vect_add(), vect_dup(), vect_fprint(), vect_size(), VECTEUR_NUL, and vecteur_var.
Referenced by parallel_loop_tiling().
sc | c |
index_base | ndex_base |
Definition at line 890 of file tiling.c.
References Ssysteme::base, base_copy(), base_reversal(), build_sc_nredund_1pass(), CATCH, FWD_OFL_CTRL, overflow_error, sc_append(), sc_copy(), sc_dup(), sc_elim_var(), sc_empty(), sc_init_with_sc(), sc_normalize(), Svecteur::succ, TRY, UNCATCH, vect_copy(), vect_size(), VECTEUR_NUL_P, and vecteur_var.
Referenced by parallel_tiling().
|
static |
Definition at line 738 of file tiling.c.
References statement_in_loopnest_p, statement_number, and test_statement_of_reference.
Referenced by check_tiling_legality().
tiling.c
serialized_matrix | erialized_matrix |
Definition at line 104 of file tiling.c.
References ACCESS, buffer, DENOMINATOR, empty_string_p(), free(), line, pips_assert, strdup(), string_undefined, string_undefined_p, and VALUE_ONE.
Referenced by parallel_tiling(), and tiling_transformation().
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.
computation of the hyperplane tile direction in the tile basis: = sum(hi)= 1H
computation of the tile scanning base G.
Build the constraints 0 <= det(HT).[HT. (i -i0)]<det(HT).1 with i0=P.G_tile.i_tile <==> 0 <= det(HT).[HT. (i -P.G_tile.i_tile)]<det(HT).1 <==> 0 <= det(HT).[HT.i -G_tile.i_tile]<= det(HT)-1
Find the origin of the iteration domain. Use 0 as default coordinate
initial_basis | nitial_basis |
tile_basis | ile_basis |
HT | T |
tiling_offset | iling_offset |
Definition at line 274 of file tiling.c.
References ACCESS, base_dimension, BASE_UNDEFINED, contrainte_make(), CONTRAINTE_UNDEFINED, debug(), DENOMINATOR, empty_string_p(), entity_local_name(), fprintf(), get_string_property(), ifdebug, malloc(), matrice_fprint(), matrice_identite(), matrice_new, offset, pips_assert, pips_debug, printf(), sc_add_inegalite(), sc_creer_base(), sc_fprint(), sc_new(), scanning_base_hyperplane(), TCST, VALUE_ONE, value_uminus, VALUE_ZERO, vect_add_elem(), vect_chg_sgn(), vect_coeff(), vect_dup(), VECTEUR_NUL, vecteur_succ, and vecteur_var.
Referenced by parallel_tiling().
|
static |
Generate the tile membership constraints between a tile coordinates and an iteration coordinate.
Definition at line 209 of file tiling.c.
References ACCESS, base_dimension, BASE_UNDEFINED, contrainte_make(), CONTRAINTE_UNDEFINED, debug(), DENOMINATOR, entity_local_name(), ifdebug, matrice_fprint(), offset, pips_assert, pips_debug, sc_add_inegalite(), sc_creer_base(), sc_fprint(), sc_new(), TCST, VALUE_ONE, value_uminus, VALUE_ZERO, vect_add_elem(), vect_chg_sgn(), vect_coeff(), vect_dup(), VECTEUR_NUL, vecteur_succ, and vecteur_var.
Referenced by tiling_transformation().
Generate tiled code for a loop nest, PPoPP'91, p.
46, Figure 15.
The row-echelon algorithm is called from new_loop_bound().
iteration domain
Tile membership constraints
Pbase local_basis = NULL;
Partitioning matrix
Transposed matrix of the inverse of P
Change of basis in the tile space to use vector 1 as hyperplane direction
number of indices, i.e. loop nest depth
Tiling offset: 0 by default
make the constraint system for the iteration space and find a good origin for the tiling
computation of the partitioning matrix P and its inverse HT
Compute B': each iteration i in the iteration space is linked to its tile s
mc and SC_B_prime are aliased after this call
Save a copy to compute B" later
Get constraints on tile coordinates
Build the constraint system to scan the set of tiles
CA: Build the new basis (tile_basis+initial_basis)
base It, Jt, I, J pour notre exemple
Build the constraint system sc_tile to scan one tile (BS IN PPoPP'91 paper)
computation of the hyperplane tile direction: let's use the default 1 vector
computation of the tile scanning base G: right now, let's assume it's Id. This is OK to tile parallel loops... or to scan tiles sequentially on a monoprocessor.
generation of code for scanning one tile
Compute the local coordinate changes: there should be none for the time being because we keep the initial basis to scan iterations within one tile, i.e G must be the identity matrix
generation of code to scan one tile, and update of loop body using pvg
generation of code for scanning all tiles
Definition at line 526 of file tiling.c.
References base_dimension, base_reversal(), CDR, code_generation(), copy_expression(), debug_off, debug_on, derive_new_basis(), empty_string_p(), entity_empty_label(), entity_local_name(), fprintf(), G, gen_length(), get_bool_property(), get_string_property(), ifdebug, instruction_to_statement(), int, int_to_expression(), interactive_partitioning_matrix(), is_execution_sequential, is_instruction_loop, loop_iteration_domaine_to_sc(), loop_nest_to_offset(), loop_undefined, make_bound_expression(), make_execution(), make_instruction(), make_loop(), make_range(), make_tile_index_entity(), malloc(), matrice_fprint(), matrice_general_inversion(), matrice_identite(), matrice_new, new_loop_bound(), NIL, OFL_CTRL, pips_debug, pips_user_error, sc_append(), sc_dup(), sc_fprint(), sc_normalize(), scanning_base_hyperplane(), scanning_base_to_vect(), static_partitioning_matrix(), string_undefined_p, Svecteur::succ, tile_membership_constraints(), UU, VALUE_ONE, Svecteur::var, vect_add(), vect_dup(), vect_fprint(), VECTEUR_NUL, and vecteur_var.
Referenced by loop_tiling().
Definition at line 736 of file tiling.c.
Referenced by check_tiling_legality(), and statement_in_loopnest().
|
static |
Definition at line 737 of file tiling.c.
Referenced by check_tiling_legality(), and statement_in_loopnest().