do not create unnecessary dimensions in scop scattering

           * graphite-sese-to-poly.c (build_pbb_scattering_polyhedrons): Remove.
           (build_pbb_minimal_scattering_polyhedrons): New.
           (build_scop_scattering): Remove.
           (build_scop_minimal_scattering): New.
           (build_scop_scattering): Call build_pbb_minimal_scattering_polyhedrons.
           (build_poly_scop): Call build_scop_minimal_scattering.

git-svn-id: svn+ssh://gcc.gnu.org/svn/gcc/trunk@229909 138bc75d-0d04-0410-961f-82ee72b054a4

2 files changed, 145 insertions, 54 deletions

diff --git a/gcc/ChangeLog b/gcc/ChangeLog
index 552c51b2ceb..bac7eb87199 100644
--- a/gcc/ChangeLog
+++ b/gcc/ChangeLog
@@ -1,3 +1,12 @@
+2015-11-06  Abderrazek Zaafrani  <a.zaafrani@samsung.com>
+
+	* graphite-sese-to-poly.c (build_pbb_scattering_polyhedrons): Remove.
+	(build_pbb_minimal_scattering_polyhedrons): New.
+	(build_scop_scattering): Remove.
+	(build_scop_minimal_scattering): New.
+	(build_scop_scattering): Call build_pbb_minimal_scattering_polyhedrons.
+	(build_poly_scop): Call build_scop_minimal_scattering.
+
 2015-11-06  Jeff Law <jeff@redhat.com>
 
 	* cfg-flags.def (IGNORE): New edge flag.
diff --git a/gcc/graphite-sese-to-poly.c b/gcc/graphite-sese-to-poly.c
index fa33c50a533..394a281a97e 100644
--- a/gcc/graphite-sese-to-poly.c
+++ b/gcc/graphite-sese-to-poly.c
@@ -231,51 +231,78 @@ isl_id_for_pbb (scop_p s, poly_bb_p pbb)
    | 0   0   1   0   0   0   0   0  -5  = 0  */
 
 static void
-build_pbb_scattering_polyhedrons (isl_aff *static_sched,
-				  poly_bb_p pbb)
+build_pbb_minimal_scattering_polyhedrons (isl_aff *static_sched, poly_bb_p pbb,
+					  int *sequence_dims,
+					  int nb_sequence_dim)
 {
-  isl_val *val;
+  int local_dim = isl_set_dim (pbb->domain, isl_dim_set);
+
+  /* Remove a sequence dimension if irrelevant to domain of current pbb.  */
+  int actual_nb_dim = 0;
+  for (int i = 0; i < nb_sequence_dim; i++)
+    if (sequence_dims[i] <= local_dim)
+      actual_nb_dim++;
+
+  /* Build an array that combines sequence dimensions and loops dimensions info.
+     This is used later to compute the static scattering polyhedrons.  */
+  bool *sequence_and_loop_dims = NULL;
+  if (local_dim + actual_nb_dim > 0)
+    {
+      sequence_and_loop_dims = XNEWVEC (bool, local_dim + actual_nb_dim);
 
-  int scattering_dimensions = isl_set_dim (pbb->domain, isl_dim_set) * 2 + 1;
+      int i = 0, j = 0;
+      for (; i < local_dim; i++)
+	{
+	  if (sequence_dims && sequence_dims[j] == i)
+	    {
+	      /* True for sequence dimension.  */
+	      sequence_and_loop_dims[i + j] = true;
+	      j++;
+	    }
+	  /* False for loop dimension.  */
+	  sequence_and_loop_dims[i + j] = false;
+	}
+      /* Fake loops make things shifted by one.  */
+      if (sequence_dims && sequence_dims[j] == i)
+	sequence_and_loop_dims[i + j] = true;
+    }
 
+  int scattering_dimensions = local_dim + actual_nb_dim;
   isl_space *dc = isl_set_get_space (pbb->domain);
-  isl_space *dm = isl_space_add_dims (isl_space_from_domain (dc),
-				      isl_dim_out, scattering_dimensions);
+  isl_space *dm = isl_space_add_dims (isl_space_from_domain (dc), isl_dim_out,
+				      scattering_dimensions);
   pbb->schedule = isl_map_universe (dm);
 
+  int k = 0;
   for (int i = 0; i < scattering_dimensions; i++)
     {
-      /* Textual order inside this loop.  */
-      if ((i % 2) == 0)
+      if (!sequence_and_loop_dims[i])
 	{
-	  isl_constraint *c = isl_equality_alloc
-	      (isl_local_space_from_space (isl_map_get_space (pbb->schedule)));
-
-	  val = isl_aff_get_coefficient_val (static_sched, isl_dim_in, i / 2);
-	  gcc_assert (val && isl_val_is_int (val));
-
-	  val = isl_val_neg (val);
-	  c = isl_constraint_set_constant_val (c, val);
-	  c = isl_constraint_set_coefficient_si (c, isl_dim_out, i, 1);
-	  pbb->schedule = isl_map_add_constraint (pbb->schedule, c);
-	}
-
-      /* Iterations of this loop.  */
-      else /* if ((i % 2) == 1) */
-	{
-	  int loop = (i - 1) / 2;
-	  pbb->schedule = isl_map_equate (pbb->schedule, isl_dim_in, loop,
+	  /* Iterations of this loop - loop dimension.  */
+	  pbb->schedule = isl_map_equate (pbb->schedule, isl_dim_in, k,
 					  isl_dim_out, i);
+	  k++;
+	  continue;
 	}
+
+      /* Textual order inside this loop - sequence dimension.  */
+      isl_space *s = isl_map_get_space (pbb->schedule);
+      isl_local_space *ls = isl_local_space_from_space (s);
+      isl_constraint *c = isl_equality_alloc (ls);
+      isl_val *val = isl_aff_get_coefficient_val (static_sched, isl_dim_in, k);
+      gcc_assert (val && isl_val_is_int (val));
+      val = isl_val_neg (val);
+      c = isl_constraint_set_constant_val (c, val);
+      c = isl_constraint_set_coefficient_si (c, isl_dim_out, i, 1);
+      pbb->schedule = isl_map_add_constraint (pbb->schedule, c);
     }
 
+  XDELETEVEC (sequence_and_loop_dims);
   pbb->transformed = isl_map_copy (pbb->schedule);
 }
 
-/* Build for BB the static schedule.
-
-   The static schedule is a Dewey numbering of the abstract syntax
-   tree: http://en.wikipedia.org/wiki/Dewey_Decimal_Classification
+/* Build the static schedule for BB.  This function minimizes the number of
+   dimensions used for pbb sequences.
 
    The following example informally defines the static schedule:
 
@@ -283,40 +310,94 @@ build_pbb_scattering_polyhedrons (isl_aff *static_sched,
    for (i: ...)
      {
        for (j: ...)
-         {
-           B
-           C
-         }
-
+	{
+	  B
+	  C
+	}
+     }
+   for (i: ...)
+     {
        for (k: ...)
-         {
-           D
-           E
-         }
+	{
+	  D
+	  E
+	}
      }
    F
 
    Static schedules for A to F:
 
-     DEPTH
-     0 1 2
-   A 0
-   B 1 0 0
-   C 1 0 1
-   D 1 1 0
-   E 1 1 1
-   F 2
+   A (0)
+   B (1 i0 i1 0)
+   C (1 i0 i1 1)
+   D (2 i0 i1 2)
+   E (2 i0 i1 3)
+   F (3)
 */
 
 static void
-build_scop_scattering (scop_p scop)
+build_scop_minimal_scattering (scop_p scop)
 {
   gimple_poly_bb_p previous_gbb = NULL;
-  isl_space *dc = isl_set_get_space (scop->param_context);
-  isl_aff *static_sched;
+  int *temp_for_sequence_dims = NULL;
+  int i;
+  poly_bb_p pbb;
+
+  /* Go through the pbbs to determine the minimum number of dimensions needed to
+     build the static schedule.  */
+  int nb_dims = 0;
+  FOR_EACH_VEC_ELT (scop->pbbs, i, pbb)
+    {
+      int dim = isl_set_dim (pbb->domain, isl_dim_set);
+      if (dim > nb_dims)
+	nb_dims = dim;
+    }
+
+  /* One extra dimension for the outer fake loop.  */
+  nb_dims++;
+  temp_for_sequence_dims = XCNEWVEC (int, nb_dims);
 
+  /* Record the number of common loops for each dimension.  */
+  FOR_EACH_VEC_ELT (scop->pbbs, i, pbb)
+    {
+      gimple_poly_bb_p gbb = PBB_BLACK_BOX (pbb);
+      int prefix = 0;
+
+      if (previous_gbb)
+	{
+	  prefix = nb_common_loops (scop->scop_info->region, previous_gbb, gbb);
+	  temp_for_sequence_dims[prefix] += 1;
+	}
+      previous_gbb = gbb;
+    }
+
+  /* Analyze the info in temp_for_sequence_dim and determine the minimal number
+     of sequence dimensions.  A dimension that did not appear as common
+     dimension should not be considered as a sequence dimension.  */
+  int nb_sequence_params = 0;
+  for (i = 0; i < nb_dims; i++)
+    if (temp_for_sequence_dims[i] > 0)
+      nb_sequence_params++;
+
+  int *sequence_dims = NULL;
+  if (nb_sequence_params > 0)
+    {
+      int j = 0;
+      sequence_dims = XNEWVEC (int, nb_sequence_params);
+      for (i = 0; i < nb_dims; i++)
+	if (temp_for_sequence_dims[i] > 0)
+	  {
+	    sequence_dims[j] = i;
+	    j++;
+	  }
+    }
+
+  XDELETEVEC (temp_for_sequence_dims);
+
+  isl_space *dc = isl_set_get_space (scop->param_context);
   dc = isl_space_add_dims (dc, isl_dim_set, number_of_loops (cfun));
-  static_sched = isl_aff_zero_on_domain (isl_local_space_from_space (dc));
+  isl_local_space *local_space = isl_local_space_from_space (dc);
+  isl_aff *static_sched = isl_aff_zero_on_domain (local_space);
 
   /* We have to start schedules at 0 on the first component and
      because we cannot compare_prefix_loops against a previous loop,
@@ -324,8 +405,7 @@ build_scop_scattering (scop_p scop)
      incremented before copying.  */
   static_sched = isl_aff_add_coefficient_si (static_sched, isl_dim_in, 0, -1);
 
-  int i;
-  poly_bb_p pbb;
+  previous_gbb = NULL;
   FOR_EACH_VEC_ELT (scop->pbbs, i, pbb)
     {
       gimple_poly_bb_p gbb = PBB_BLACK_BOX (pbb);
@@ -338,9 +418,11 @@ build_scop_scattering (scop_p scop)
 
       static_sched = isl_aff_add_coefficient_si (static_sched, isl_dim_in,
 						 prefix, 1);
-      build_pbb_scattering_polyhedrons (static_sched, pbb);
+      build_pbb_minimal_scattering_polyhedrons (static_sched, pbb,
+						sequence_dims, nb_sequence_params);
     }
 
+  XDELETEVEC (sequence_dims);
   isl_aff_free (static_sched);
 }
 
@@ -1716,7 +1798,7 @@ build_poly_scop (scop_p scop)
   rewrite_cross_bb_scalar_deps_out_of_ssa (scop);
 
   build_scop_drs (scop);
-  build_scop_scattering (scop);
+  build_scop_minimal_scattering (scop);
 
   /* This SCoP has been translated to the polyhedral
      representation.  */