From ee0d08ad4c28590d39010b7421e8d7a8ca51c158 Mon Sep 17 00:00:00 2001 From: spop Date: Fri, 28 Aug 2009 20:33:10 +0000 Subject: [PATCH] 2009-08-28 Konrad Trifunovic Sebastian Pop * graphite-blocking.c (pbb_strip_mine_loop_depth): Renamed pbb_strip_mine_time_depth. Changed the implementation so that transformation is expressed as a transformation on time (scatttering) dimensions. Also, ensures that the 2d+1 scheduling format is preserved. (pbb_strip_mine_profitable_p): Profitability is based on the iteration number of a given time (scattering) dimension, and not on a original loop depth dimension. (pbb_strip_mine): Call pbb_number_of_iterations_at_time. (pbb_do_strip_mine): Call psct_dynamic_dim. * graphite-poly.c (pbb_number_of_iterations_at_time): New. * graphite-poly.h (pbb_number_of_iterations_at_time): Declared. (pbb_nb_dynamic_scattering_transform): New. (psct_dynamic_dim): New. git-svn-id: svn+ssh://gcc.gnu.org/svn/gcc/trunk@151186 138bc75d-0d04-0410-961f-82ee72b054a4 --- gcc/ChangeLog | 18 +++++++++++++++++ gcc/ChangeLog.graphite | 18 +++++++++++++++++ gcc/graphite-blocking.c | 54 ++++++++++++++++++++++++++++++++++++------------- gcc/graphite-poly.c | 41 +++++++++++++++++++++++++++++++++++++ gcc/graphite-poly.h | 25 +++++++++++++++++++++++ 5 files changed, 142 insertions(+), 14 deletions(-) diff --git a/gcc/ChangeLog b/gcc/ChangeLog index ca28282..d9dfa5c 100644 --- a/gcc/ChangeLog +++ b/gcc/ChangeLog @@ -1,4 +1,22 @@ 2009-08-28 Konrad Trifunovic + Sebastian Pop + + * graphite-blocking.c (pbb_strip_mine_loop_depth): Renamed + pbb_strip_mine_time_depth. Changed the implementation so that + transformation is expressed as a transformation on + time (scatttering) dimensions. Also, ensures that the 2d+1 + scheduling format is preserved. + (pbb_strip_mine_profitable_p): Profitability is based on the + iteration number of a given time (scattering) dimension, + and not on a original loop depth dimension. + (pbb_strip_mine): Call pbb_number_of_iterations_at_time. + (pbb_do_strip_mine): Call psct_dynamic_dim. + * graphite-poly.c (pbb_number_of_iterations_at_time): New. + * graphite-poly.h (pbb_number_of_iterations_at_time): Declared. + (pbb_nb_dynamic_scattering_transform): New. + (psct_dynamic_dim): New. + +2009-08-28 Konrad Trifunovic * graphite-ppl.c (ppl_max_for_le): Renamed ppl_max_for_le_pointset. * graphite-ppl.h (ppl_max_for_le): Renamed ppl_max_for_le_pointset. diff --git a/gcc/ChangeLog.graphite b/gcc/ChangeLog.graphite index 979c25f..a83c0ed 100644 --- a/gcc/ChangeLog.graphite +++ b/gcc/ChangeLog.graphite @@ -1,4 +1,22 @@ 2009-08-25 Konrad Trifunovic + Sebastian Pop + + * graphite-blocking.c (pbb_strip_mine_loop_depth): Renamed + pbb_strip_mine_time_depth. Changed the implementation so that + transformation is expressed as a transformation on + time (scatttering) dimensions. Also, ensures that the 2d+1 + scheduling format is preserved. + (pbb_strip_mine_profitable_p): Profitability is based on the + iteration number of a given time (scattering) dimension, + and not on a original loop depth dimension. + (pbb_strip_mine): Call pbb_number_of_iterations_at_time. + (pbb_do_strip_mine): Call psct_dynamic_dim. + * graphite-poly.c (pbb_number_of_iterations_at_time): New. + * graphite-poly.h (pbb_number_of_iterations_at_time): Declared. + (pbb_nb_dynamic_scattering_transform): New. + (psct_dynamic_dim): New. + +2009-08-25 Konrad Trifunovic * graphite-ppl.c (ppl_max_for_le): Renamed ppl_max_for_le_pointset. * graphite-ppl.h (ppl_max_for_le): Renamed ppl_max_for_le_pointset. diff --git a/gcc/graphite-blocking.c b/gcc/graphite-blocking.c index 45f3bc6..80a991c 100644 --- a/gcc/graphite-blocking.c +++ b/gcc/graphite-blocking.c @@ -54,8 +54,10 @@ along with GCC; see the file COPYING3. If not see #include "graphite-poly.h" -/* Strip mines with a factor STRIDE the loop around PBB at depth - LOOP_DEPTH. The following example comes from the wiki page: +/* Strip mines with a factor STRIDE the scattering (time) dimension + around PBB at depth TIME_DEPTH. + + The following example comes from the wiki page: http://gcc.gnu.org/wiki/Graphite/Strip_mine The strip mine of a loop with a tile of 64 can be obtained with a @@ -106,16 +108,19 @@ along with GCC; see the file COPYING3. If not see */ static bool -pbb_strip_mine_loop_depth (poly_bb_p pbb, int loop_depth, int stride) +pbb_strip_mine_time_depth (poly_bb_p pbb, int time_depth, int stride) { - ppl_dimension_type iter, dim; + ppl_dimension_type iter, dim, strip; ppl_Polyhedron_t res = PBB_TRANSFORMED_SCATTERING (pbb); - ppl_dimension_type strip = psct_scattering_dim_for_loop_depth (pbb, - loop_depth); + /* STRIP is the dimension that iterates with stride STRIDE. */ + /* ITER is the dimension that enumerates single iterations inside + one strip that has at most STRIDE iterations. */ + strip = time_depth; + iter = strip + 2; psct_add_scattering_dimension (pbb, strip); + psct_add_scattering_dimension (pbb, strip + 1); - iter = psct_iterator_dim (pbb, loop_depth); ppl_Polyhedron_space_dimension (res, &dim); /* Lower bound of the striped loop. */ @@ -149,15 +154,31 @@ pbb_strip_mine_loop_depth (poly_bb_p pbb, int loop_depth, int stride) ppl_delete_Constraint (new_cstr); } + /* Static scheduling for ITER level. + This is mandatory to keep the 2d + 1 canonical scheduling format. */ + { + ppl_Constraint_t new_cstr; + ppl_Linear_Expression_t expr; + + ppl_new_Linear_Expression_with_dimension (&expr, dim); + ppl_set_coef (expr, strip + 1, 1); + ppl_set_inhomogeneous (expr, 0); + + ppl_new_Constraint (&new_cstr, expr, PPL_CONSTRAINT_TYPE_EQUAL); + ppl_delete_Linear_Expression (expr); + ppl_Polyhedron_add_constraint (res, new_cstr); + ppl_delete_Constraint (new_cstr); + } + return true; } /* Returns true when strip mining with STRIDE of the loop around PBB - at depth LOOP_DEPTH is profitable. */ + at scattering time TIME_DEPTH is profitable. */ static bool pbb_strip_mine_profitable_p (poly_bb_p pbb, - graphite_dim_t loop_depth, + graphite_dim_t time_depth, int stride) { Value niter, strip_stride; @@ -166,7 +187,7 @@ pbb_strip_mine_profitable_p (poly_bb_p pbb, value_init (strip_stride); value_init (niter); value_set_si (strip_stride, stride); - pbb_number_of_iterations (pbb, loop_depth, niter); + pbb_number_of_iterations_at_time (pbb, time_depth, niter); res = value_gt (niter, strip_stride); value_clear (strip_stride); value_clear (niter); @@ -180,13 +201,18 @@ pbb_strip_mine_profitable_p (poly_bb_p pbb, static bool pbb_do_strip_mine (poly_bb_p pbb) { - graphite_dim_t loop_depth; + graphite_dim_t s_dim; int stride = 64; bool transform_done = false; - for (loop_depth = 0; loop_depth < pbb_dim_iter_domain (pbb); loop_depth++) - if (pbb_strip_mine_profitable_p (pbb, loop_depth, stride)) - transform_done |= pbb_strip_mine_loop_depth (pbb, loop_depth, stride); + for (s_dim = 0; s_dim < pbb_nb_dynamic_scattering_transform (pbb); s_dim++) + if (pbb_strip_mine_profitable_p (pbb, psct_dynamic_dim (pbb, s_dim), + stride)) + { + ppl_dimension_type d = psct_dynamic_dim (pbb, s_dim); + transform_done |= pbb_strip_mine_time_depth (pbb, d, stride); + s_dim++; + } return transform_done; } diff --git a/gcc/graphite-poly.c b/gcc/graphite-poly.c index 6184aae..4576a28 100644 --- a/gcc/graphite-poly.c +++ b/gcc/graphite-poly.c @@ -724,5 +724,46 @@ pbb_number_of_iterations (poly_bb_p pbb, ppl_delete_Linear_Expression (le); } +/* Returns the number of iterations NITER of the loop around PBB at + time(scattering) dimension TIME_DEPTH. */ + +void +pbb_number_of_iterations_at_time (poly_bb_p pbb, + graphite_dim_t time_depth, + Value niter) +{ + ppl_Pointset_Powerset_C_Polyhedron_t ext_domain, sctr; + ppl_Linear_Expression_t le; + ppl_dimension_type dim; + + value_set_si (niter, -1); + + /* Takes together domain and scattering polyhedrons, and composes + them into the bigger polyhedron that has the following format: + t0..t_{n-1} | l0..l_{nlcl-1} | i0..i_{niter-1} | g0..g_{nparm-1}. + t0..t_{n-1} are time dimensions (scattering dimensions) + l0..l_{nclc-1} are local variables in scatterin function + i0..i_{niter-1} are original iteration variables + g0..g_{nparam-1} are global parameters. */ + + ppl_new_Pointset_Powerset_C_Polyhedron_from_Pointset_Powerset_C_Polyhedron + (&ext_domain, PBB_DOMAIN (pbb)); + ppl_insert_dimensions_pointset (ext_domain, 0, + pbb_nb_scattering_transform (pbb) + + pbb_nb_local_vars (pbb)); + ppl_new_Pointset_Powerset_C_Polyhedron_from_C_Polyhedron (&sctr, + PBB_TRANSFORMED_SCATTERING (pbb)); + ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (sctr, ext_domain); + + ppl_Pointset_Powerset_C_Polyhedron_space_dimension (sctr, &dim); + ppl_new_Linear_Expression_with_dimension (&le, dim); + ppl_set_coef (le, time_depth, 1); + ppl_max_for_le_pointset (sctr, le, niter); + + ppl_delete_Linear_Expression (le); + ppl_delete_Pointset_Powerset_C_Polyhedron (sctr); + ppl_delete_Pointset_Powerset_C_Polyhedron (ext_domain); +} + #endif diff --git a/gcc/graphite-poly.h b/gcc/graphite-poly.h index a42e242..081e186 100644 --- a/gcc/graphite-poly.h +++ b/gcc/graphite-poly.h @@ -307,6 +307,7 @@ extern void debug_iteration_domains (scop_p); extern bool scop_do_interchange (scop_p); extern bool scop_do_strip_mine (scop_p); extern void pbb_number_of_iterations (poly_bb_p, graphite_dim_t, Value); +extern void pbb_number_of_iterations_at_time (poly_bb_p, graphite_dim_t, Value); /* The index of the PBB. */ @@ -372,6 +373,17 @@ pbb_nb_scattering_transform (const struct poly_bb *pbb) return PBB_NB_SCATTERING_TRANSFORM (pbb); } +/* The number of dynamic scattering dimensions in PBB. */ + +static inline graphite_dim_t +pbb_nb_dynamic_scattering_transform (const struct poly_bb *pbb) +{ + /* This function requires the 2d + 1 scattering format to be + invariant during all transformations. */ + gcc_assert (PBB_NB_SCATTERING_TRANSFORM (pbb) % 2); + return PBB_NB_SCATTERING_TRANSFORM (pbb) / 2; +} + /* Returns the number of local variables used in the transformed scattering polyhedron of PBB. */ @@ -480,6 +492,19 @@ psct_parameter_dim (poly_bb_p pbb, graphite_dim_t param) + pbb_dim_iter_domain (pbb); } +/* The scattering dimension of PBB corresponding to the dynamic level + LEVEL. */ + +static inline ppl_dimension_type +psct_dynamic_dim (poly_bb_p pbb, graphite_dim_t level) +{ + graphite_dim_t result; + result = 1 + 2 * level; + + gcc_assert (result < pbb_nb_scattering_transform (pbb)); + return result; +} + /* Adds to the transformed scattering polyhedron of PBB a new local variable and returns its index. */ -- 2.7.4