2009-10-14 Konrad Trifunovic <konrad.trifunovic@gmail.com>

	    Sebastian Pop  <sebastian.pop@amd.com>

	* graphite-interchange.c (build_linearized_memory_access): Pass an
	offset as parameter.
	(memory_stride_in_loop): Include transform scattering in the
	access functions to be able to querry the strides in the
	transformed loops.
	(pbb_interchange_loop_depths): Interchange the psct_dynamic_dim,
	not the psct_iterator_dim.

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

1 files changed, 172 insertions, 63 deletions

diff --git a/gcc/graphite-interchange.c b/gcc/graphite-interchange.c
index 43655f66f73..cb703f27bdf 100644
--- a/gcc/graphite-interchange.c
+++ b/gcc/graphite-interchange.c
@@ -60,10 +60,18 @@ along with GCC; see the file COPYING3.  If not see
 
    For an array A[10][20] with two subscript locations s0 and s1, the
    linear memory access is 20 * s0 + s1: a stride of 1 in subscript s0
-   corresponds to a memory stride of 20.  */
+   corresponds to a memory stride of 20.
+
+   OFFSET is a number of dimensions to prepend before the
+   subscript dimensions: s_0, s_1, ..., s_n.
+
+   Thus, the final linear expression has the following format:
+   0 .. 0_{offset} | 0 .. 0_{nit} | 0 .. 0_{gd} | 0 | c_0 c_1 ... c_n
+   where the expression itself is:
+   c_0 * s_0 + c_1 * s_1 + ... c_n * s_n.  */
 
 static ppl_Linear_Expression_t
-build_linearized_memory_access (poly_dr_p pdr)
+build_linearized_memory_access (ppl_dimension_type offset, poly_dr_p pdr)
 {
   ppl_Linear_Expression_t res;
   ppl_Linear_Expression_t le;
@@ -71,7 +79,7 @@ build_linearized_memory_access (poly_dr_p pdr)
   ppl_dimension_type first = pdr_subscript_dim (pdr, 0);
   ppl_dimension_type last = pdr_subscript_dim (pdr, PDR_NB_SUBSCRIPTS (pdr));
   Value size, sub_size;
-  graphite_dim_t dim = pdr_dim (pdr);
+  graphite_dim_t dim = offset + pdr_dim (pdr);
 
   ppl_new_Linear_Expression_with_dimension (&res, dim);
 
@@ -82,9 +90,9 @@ build_linearized_memory_access (poly_dr_p pdr)
 
   for (i = last - 1; i >= first; i--)
     {
-      ppl_set_coef_gmp (res, i, size);
+      ppl_set_coef_gmp (res, i + offset, size);
 
-      ppl_new_Linear_Expression_with_dimension (&le, dim);
+      ppl_new_Linear_Expression_with_dimension (&le, dim - offset);
       ppl_set_coef (le, i, 1);
       ppl_max_for_le_pointset (PDR_ACCESSES (pdr), le, sub_size);
       value_multiply (size, size, sub_size);
@@ -97,72 +105,169 @@ build_linearized_memory_access (poly_dr_p pdr)
 }
 
 /* Set STRIDE to the stride of PDR in memory by advancing by one in
-   loop DEPTH.  */
+   time dimension DEPTH.  */
 
 static void
 memory_stride_in_loop (Value stride, graphite_dim_t depth, poly_dr_p pdr)
 {
   ppl_Linear_Expression_t le, lma;
   ppl_Constraint_t new_cstr;
-  ppl_Pointset_Powerset_C_Polyhedron_t p1, p2;
-  graphite_dim_t nb_subscripts = PDR_NB_SUBSCRIPTS (pdr);
   ppl_dimension_type i, *map;
-  ppl_dimension_type dim = pdr_dim (pdr);
-  ppl_dimension_type dim_i = pdr_iterator_dim (pdr, depth);
-  ppl_dimension_type dim_k = dim;
-  ppl_dimension_type dim_L1 = dim + nb_subscripts + 1;
-  ppl_dimension_type dim_L2 = dim + nb_subscripts + 2;
-  ppl_dimension_type new_dim = dim + nb_subscripts + 3;
-
-  /* Add new dimensions to the polyhedron corresponding to
-     k, s0', s1',..., L1, and L2.  These new variables are at
-     dimensions dim, dim + 1,... of the polyhedron P1 respectively.  */
-  ppl_new_Pointset_Powerset_C_Polyhedron_from_Pointset_Powerset_C_Polyhedron
-    (&p1, PDR_ACCESSES (pdr));
-  ppl_Pointset_Powerset_C_Polyhedron_add_space_dimensions_and_embed
-    (p1, nb_subscripts + 3);
-
-  lma = build_linearized_memory_access (pdr);
-  ppl_set_coef (lma, dim_L1, -1);
-  ppl_new_Constraint (&new_cstr, lma, PPL_CONSTRAINT_TYPE_EQUAL);
-  ppl_Pointset_Powerset_C_Polyhedron_add_constraint (p1, new_cstr);
-
-  /* Build P2.  */
-  ppl_new_Pointset_Powerset_C_Polyhedron_from_Pointset_Powerset_C_Polyhedron
-    (&p2, p1);
-  map = ppl_new_id_map (new_dim);
-  ppl_interchange (map, dim_L1, dim_L2);
-  ppl_interchange (map, dim_i, dim_k);
-  for (i = 0; i < PDR_NB_SUBSCRIPTS (pdr); i++)
-    ppl_interchange (map, pdr_subscript_dim (pdr, i), dim + i + 1);
-  ppl_Pointset_Powerset_C_Polyhedron_map_space_dimensions (p2, map, new_dim);
-  free (map);
-
-  /* Add constraint k = i + 1.  */
-  ppl_new_Linear_Expression_with_dimension (&le, new_dim);
-  ppl_set_coef (le, dim_i, 1);
-  ppl_set_coef (le, dim_k, -1);
-  ppl_set_inhomogeneous (le, 1);
-  ppl_new_Constraint (&new_cstr, le, PPL_CONSTRAINT_TYPE_EQUAL);
-  ppl_Pointset_Powerset_C_Polyhedron_add_constraint (p2, new_cstr);
-  ppl_delete_Linear_Expression (le);
-  ppl_delete_Constraint (new_cstr);
+  ppl_Pointset_Powerset_C_Polyhedron_t p1, p2, sctr;
+  graphite_dim_t nb_subscripts = PDR_NB_SUBSCRIPTS (pdr) + 1;
+  poly_bb_p pbb = PDR_PBB (pdr);
+  ppl_dimension_type offset = pbb_nb_scattering_transform (pbb)
+                              + pbb_nb_local_vars (pbb)
+                              + pbb_dim_iter_domain (pbb);
+  ppl_dimension_type offsetg = offset + pbb_nb_params (pbb);
+  ppl_dimension_type dim_sctr = pbb_nb_scattering_transform (pbb)
+                                + pbb_nb_local_vars (pbb);
+  ppl_dimension_type dim_L1 = offset + offsetg + 2 * nb_subscripts;
+  ppl_dimension_type dim_L2 = offset + offsetg + 2 * nb_subscripts + 1;
+  ppl_dimension_type new_dim = offset + offsetg + 2 * nb_subscripts + 2;
+
+  /* The resulting polyhedron should have the following format:
+     T|I|T'|I'|G|S|S'|l1|l2
+     where:
+     | T = t_1..t_{dim_sctr}
+     | I = i_1..i_{dim_iter_domain}
+     | T'= t'_1..t'_{dim_sctr}
+     | I'= i'_1..i'_{dim_iter_domain}
+     | G = g_1..g_{nb_params}
+     | S = s_1..s_{nb_subscripts}
+     | S'= s'_1..s'_{nb_subscripts}
+     | l1 and l2 are scalars.
+
+     Some invariants:
+     offset = dim_sctr + dim_iter_domain + nb_local_vars
+     offsetg = dim_sctr + dim_iter_domain + nb_local_vars + nb_params.  */
+
+  /* Construct the T|I|0|0|G|0|0|0|0 part.  */
+  {
+    ppl_new_Pointset_Powerset_C_Polyhedron_from_C_Polyhedron
+      (&sctr, PBB_TRANSFORMED_SCATTERING (pbb));
+    ppl_Pointset_Powerset_C_Polyhedron_add_space_dimensions_and_embed
+      (sctr, 2 * nb_subscripts + 2);
+    ppl_insert_dimensions_pointset (sctr, offset, offset);
+  }
+
+  /* Construct the 0|I|0|0|G|S|0|0|0 part.  */
+  {
+    ppl_new_Pointset_Powerset_C_Polyhedron_from_Pointset_Powerset_C_Polyhedron
+      (&p1, PDR_ACCESSES (pdr));
+    ppl_Pointset_Powerset_C_Polyhedron_add_space_dimensions_and_embed
+      (p1, nb_subscripts + 2);
+    ppl_insert_dimensions_pointset (p1, 0, dim_sctr);
+    ppl_insert_dimensions_pointset (p1, offset, offset);
+  }
+
+  /* Construct the 0|0|0|0|0|S|0|l1|0 part.  */
+  {
+    lma = build_linearized_memory_access (offset + dim_sctr, pdr);
+    ppl_set_coef (lma, dim_L1, -1);
+    ppl_new_Constraint (&new_cstr, lma, PPL_CONSTRAINT_TYPE_EQUAL);
+    ppl_Pointset_Powerset_C_Polyhedron_add_constraint (p1, new_cstr);
+  }
+
+  /* Now intersect all the parts to get:
+     T|I|0|0|G|0|0|0 |0
+     0|I|0|0|G|S|0|0 |0
+     0|0|0|0|0|S|0|l1|0
+     ------------------
+     T|I|0|0|G|S|0|l1|0.  */
+
+  ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (p1, sctr);
+  ppl_delete_Pointset_Powerset_C_Polyhedron (sctr);
+
+  /* Build P2, which would have the following form:
+     0|0|T'|I'|G|0|S'|0|l2
+
+     P2 is built, by remapping the P1 polyhedron:
+     T|I|0|0|G|S|0|l1|0
+
+     using the following mapping:
+     T->T'
+     I->I'
+     S->S'
+     l1->l2.  */
+  {
+    ppl_new_Pointset_Powerset_C_Polyhedron_from_Pointset_Powerset_C_Polyhedron
+      (&p2, p1);
+
+    map = ppl_new_id_map (new_dim);
+
+    /* T->T' and I->I'.  */
+    for (i = 0; i < offset; i++)
+      ppl_interchange (map, i, i + offset);
+
+    /* l1->l2.  */
+    ppl_interchange (map, dim_L1, dim_L2);
+
+    /* S->S'.  */
+    for (i = 0; i < nb_subscripts; i++)
+      ppl_interchange (map, offset + offsetg + i,
+		       offset + offsetg + nb_subscripts + i);
+
+    ppl_Pointset_Powerset_C_Polyhedron_map_space_dimensions (p2, map, new_dim);
+    free (map);
+  }
+
+  /* Add equalities:
+     | t1 = t1'
+     | ...
+     | t_{depth-1} = t'_{depth-1}
+     | t_{depth+1} = t'_{depth+1}
+     | ...
+     | t_{dim_sctr} = t'_{dim_sctr}
+
+     This means that all the time dimensions are equal except for
+     depth, where we will add t_{depth} = t'_{depth} + 1 in the next
+     step.  */
+  for (i = 0; i < dim_sctr; i++)
+    if (i != depth)
+      {
+        ppl_new_Linear_Expression_with_dimension (&le, new_dim);
+        ppl_set_coef (le, i, 1);
+        ppl_set_coef (le, i + offset, -1);
+        ppl_new_Constraint (&new_cstr, le, PPL_CONSTRAINT_TYPE_EQUAL);
+        ppl_Pointset_Powerset_C_Polyhedron_add_constraint (p2, new_cstr);
+        ppl_delete_Linear_Expression (le);
+        ppl_delete_Constraint (new_cstr);
+      }
+
+  /* Add equality : t_{depth} = t'_{depth} + 1.
+     This is the core part of this alogrithm, since this
+     constraint asks for the memory access stride (difference)
+     between two consecutive points in time dimensions.  */
+  {
+    ppl_new_Linear_Expression_with_dimension (&le, new_dim);
+    ppl_set_coef (le, depth, 1);
+    ppl_set_coef (le, depth + offset, -1);
+    ppl_set_inhomogeneous (le, 1);
+    ppl_new_Constraint (&new_cstr, le, PPL_CONSTRAINT_TYPE_EQUAL);
+    ppl_Pointset_Powerset_C_Polyhedron_add_constraint (p2, new_cstr);
+    ppl_delete_Linear_Expression (le);
+    ppl_delete_Constraint (new_cstr);
+  }
 
   /* P1 = P1 inter P2.  */
-  ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (p1, p2);
-  ppl_delete_Pointset_Powerset_C_Polyhedron (p2);
+  {
+    ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (p1, p2);
+    ppl_delete_Pointset_Powerset_C_Polyhedron (p2);
+  }
 
   /* Maximise the expression L2 - L1.  */
-  ppl_new_Linear_Expression_with_dimension (&le, new_dim);
-  ppl_set_coef (le, dim_L2, 1);
-  ppl_set_coef (le, dim_L1, -1);
-  ppl_max_for_le_pointset (p1, le, stride);
-  ppl_delete_Linear_Expression (le);
+  {
+    ppl_new_Linear_Expression_with_dimension (&le, new_dim);
+    ppl_set_coef (le, dim_L2, 1);
+    ppl_set_coef (le, dim_L1, -1);
+    ppl_max_for_le_pointset (p1, le, stride);
+    ppl_delete_Linear_Expression (le);
+  }
 }
 
-
-/* Returns true when it is profitable to interchange loop at DEPTH1
-   and loop at DEPTH2 with DEPTH1 < DEPTH2 for PBB.
+/* Returns true when it is profitable to interchange time dimensions DEPTH1
+   and DEPTH2 with DEPTH1 < DEPTH2 for PBB.
 
    Example:
 
@@ -197,6 +302,9 @@ memory_stride_in_loop (Value stride, graphite_dim_t depth, poly_dr_p pdr)
    | i   j   N   a  s0  s1   1
    | 0   0   0   0 100   1   0
 
+   TODO: the shown format is not valid as it does not show the fact
+   that the iteration domain "i j" is transformed using the scattering.
+
    Next, to measure the impact of iterating once in loop "i", we build
    a maximization problem: first, we add to DR accesses the dimensions
    k, s2, s3, L1 = 100 * s0 + s1, L2, and D1: polyhedron P1.
@@ -212,7 +320,7 @@ memory_stride_in_loop (Value stride, graphite_dim_t depth, poly_dr_p pdr)
    | 0   0   0   0 100   1   0   0   0  -1   0   0   0    = 0  L1 = 100 * s0 + s1
 
    Then, we generate the polyhedron P2 by interchanging the dimensions
-   (s0, s2), (s1, s3), (L1, L2), (i0, i)
+   (s0, s2), (s1, s3), (L1, L2), (k, i)
 
    | i   j   N   a  s0  s1   k  s2  s3  L1  L2  D1   1
    | 0   0   0   1   0   0   0   0   0   0   0   0  -5    = 0  alias = 5
@@ -230,7 +338,7 @@ memory_stride_in_loop (Value stride, graphite_dim_t depth, poly_dr_p pdr)
 
    and finally we maximize the expression "D1 = max (P1 inter P2, L2 - L1)".
 
-   For determining the impact of one iteration on loop "j", we
+   Similarly, to determine the impact of one iteration on loop "j", we
    interchange (k, j), we add "k = j + 1", and we compute D2 the
    maximal value of the difference.
 
@@ -284,13 +392,14 @@ pbb_interchange_profitable_p (graphite_dim_t depth1, graphite_dim_t depth2,
    scattering.  */
 
 static void
-pbb_interchange_loop_depths (graphite_dim_t depth1, graphite_dim_t depth2, poly_bb_p pbb)
+pbb_interchange_loop_depths (graphite_dim_t depth1, graphite_dim_t depth2,
+			     poly_bb_p pbb)
 {
   ppl_dimension_type i, dim;
   ppl_dimension_type *map;
   ppl_Polyhedron_t poly = PBB_TRANSFORMED_SCATTERING (pbb);
-  ppl_dimension_type dim1 = psct_iterator_dim (pbb, depth1);
-  ppl_dimension_type dim2 = psct_iterator_dim (pbb, depth2);
+  ppl_dimension_type dim1 = psct_dynamic_dim (pbb, depth1);
+  ppl_dimension_type dim2 = psct_dynamic_dim (pbb, depth2);
 
   ppl_Polyhedron_space_dimension (poly, &dim);
   map = (ppl_dimension_type *) XNEWVEC (ppl_dimension_type, dim);