OSDN Git Service

2009-08-28 Konrad Trifunovic <konrad.trifunovic@gmail.com>
authorspop <spop@138bc75d-0d04-0410-961f-82ee72b054a4>
Fri, 28 Aug 2009 20:33:10 +0000 (20:33 +0000)
committerspop <spop@138bc75d-0d04-0410-961f-82ee72b054a4>
Fri, 28 Aug 2009 20:33:10 +0000 (20:33 +0000)
    Sebastian Pop  <sebastian.pop@amd.com>

* 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
gcc/ChangeLog.graphite
gcc/graphite-blocking.c
gcc/graphite-poly.c
gcc/graphite-poly.h

index ca28282..d9dfa5c 100644 (file)
@@ -1,4 +1,22 @@
 2009-08-28  Konrad Trifunovic  <konrad.trifunovic@gmail.com>
+           Sebastian Pop  <sebastian.pop@amd.com>
+
+       * 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  <konrad.trifunovic@gmail.com>
 
        * 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.
index 979c25f..a83c0ed 100644 (file)
@@ -1,4 +1,22 @@
 2009-08-25  Konrad Trifunovic  <konrad.trifunovic@gmail.com>
+           Sebastian Pop  <sebastian.pop@amd.com>
+
+       * 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  <konrad.trifunovic@gmail.com>
 
        * 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.
index 45f3bc6..80a991c 100644 (file)
@@ -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;
 }
index 6184aae..4576a28 100644 (file)
@@ -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
 
index a42e242..081e186 100644 (file)
@@ -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.  */