[graphite] Fixed data dependence analysis code for

["Konrad Trifunovic" <konrad dot trifunovic at gmail dot com>]

Hi,

Recent changes introduced by Tobias changed the way how the loop
domains are represented.
We can no longer assume that each loop nest iteration domain is
represented by a matrices
with the same dimensionality.

This patch fixes array access function construction and data dependence analysis
code that was broken by introduced changes.

I've also fixed a bug in array access function construction.

2008-02-20  Konrad Trifunovic  <konrad.trifunovic@inria.fr>

        * graphite.c (outermost_loop_in_scop_without_dummy,
        loop_domain_dim, ref_nb_loops, loop_iteration_vector_dim) : New.

        (build_access_matrix_with_af, build_access_matrix, 
        initialize_dependence_polyhedron) : fixed for new matrix layout.
        We can no longer assume that all iteration domains are of the same
        dimensionality

        (build_scop_data_accesses) : replace a call to outermost_loop_in_scop_without                      
        with a call to outermost_loop_in_scop_without_dummy. This solves a
        problem with construction of access function using scalar evolutions                                                                         
                             
Index: graphite.c
===================================================================
--- graphite.c	(revision 132633)
+++ graphite.c	(working copy)
@@ -361,6 +361,21 @@ outermost_loop_in_scop (scop_p scop, bas
   return nest;
 }
 
+/* Returns the outermost loop in SCOP that contains BB without
+   considering loop 0 as a loop  (still if BB belongs directly to loop 0
+   it will return loop 0) */
+
+static struct loop *
+outermost_loop_in_scop_without_dummy (scop_p scop, basic_block bb)
+{
+  struct loop *nest;
+
+  nest = bb->loop_father;
+  while (loop_outer (nest) && loop_outer (nest)->num != 0 && loop_in_scop_p (loop_outer (nest), scop))
+    nest = loop_outer (nest);
+
+  return nest;
+}
+
 /* Return true when EXPR is an affine function in LOOP for the current
    open scop.  EXPR is contained in BB.  */
 
@@ -1343,18 +1358,47 @@ build_scop_iteration_domain (scop_p scop
   return true;
 }
 
+/* Returns the dimensionality of a loop iteration domain for 
+   a given loop (identified by LOOP_NUM) with a respect to a given SCoP (SCOP) */
+
+static int
+loop_domain_dim (unsigned int loop_num, scop_p scop)
+{
+  struct loop_to_cloog_loop_str tmp, *slot; 
+  
+  tmp.loop_num = loop_num;
+  slot = (struct loop_to_cloog_loop_str *) htab_find (SCOP_LOOP2CLOOG_LOOP(scop) , &tmp); 
+  return slot->cloog_loop->domain->polyhedron->Dimension + 2;
+}
+
+/* Returns the dimensionality of a enclosing loop iteration domain with respect to
+   enclosing ScoP for a given  data reference (REF) */
+
+static int
+ref_nb_loops (data_reference_p ref)
+{
+  return loop_domain_dim (loop_containing_stmt (DR_STMT (ref))->num, DR_SCOP (ref));
+}
+
+/* Returns the dimensionality of a loop iteration vector in a  loop iteration domain for 
+   a given loop (identified by LOOP_NUM) with a respect to a given SCoP (SCOP) */
+
+static int
+loop_iteration_vector_dim (unsigned int loop_num, scop_p scop)
+{
+  return loop_domain_dim (loop_num, scop) - 2 - nb_params_in_scop (scop);
+}
+
 /* Initializes an equation CY of the access matrix using the
    information for a subscript from ACCESS_FUN, relatively to the loop
-   indexes from LOOP_NEST and parameter indexes from PARAMS.  Returns
-   true when the operation succeeded.  */
+   indexes from LOOP_NEST and parameter indexes from PARAMS. NDIM is the
+   dimensionality of the array access (number of subscripts). Returns true
+   when the operation succeeded. */
 
 static bool
 build_access_matrix_with_af (tree access_fun, lambda_vector cy,
-			     scop_p scop)
+			     scop_p scop, unsigned ndim)
 {
-  VEC (loop_p, heap) *loop_nest = SCOP_LOOP_NEST (scop);
-  VEC (tree, heap) *params = SCOP_PARAMS (scop);
-
   switch (TREE_CODE (access_fun))
     {
     case POLYNOMIAL_CHREC:
@@ -1363,47 +1407,40 @@ build_access_matrix_with_af (tree access
 	tree right = CHREC_RIGHT (access_fun);
 	int var = CHREC_VARIABLE (access_fun);
 	unsigned var_idx;
-	struct loop *loopi;
+	/*struct loop *loopi;*/
 
 	if (TREE_CODE (right) != INTEGER_CST)
 	  return false;
 
 	/* Find the index of the current variable VAR_IDX in the
 	   LOOP_NEST array.  */
-	for (var_idx = 0; VEC_iterate (loop_p, loop_nest, var_idx, loopi);
-	     var_idx++)
-	  if (loopi->num == var)
-	    break;
-
-	gcc_assert (loopi && loopi->num == var);
-
+        
+        var_idx = loop_iteration_vector_dim (var, scop);
 	cy[var_idx] = int_cst_value (right);
 
 	switch (TREE_CODE (left))
 	  {
 	  case POLYNOMIAL_CHREC:
-	    return build_access_matrix_with_af (left, cy, scop);
+	    return build_access_matrix_with_af (left, cy, scop, ndim);
 
 	  case INTEGER_CST:
 	    {
 	      /* Constant part.  */
-	      unsigned nb_loops = VEC_length (loop_p, loop_nest);
-	      unsigned nb_params = VEC_length (tree, params);
-
-	      cy[nb_loops + nb_params] = int_cst_value (left);
+	      cy[ndim - 1] = int_cst_value (left);
 	      return true;
 	    }
 
 	  default:
-	    return false;
+            {
+              /* TODO: also consider that access_fn can have parameters */
+              return false;
+            }
 	  }
       }
     case INTEGER_CST:
       {
 	/* Constant part.  */
-	unsigned nb_loops = VEC_length (loop_p, loop_nest);
-	unsigned nb_params = VEC_length (tree, params);
-	cy[nb_loops + nb_params] = int_cst_value (access_fun);
+	cy[ndim - 1] = int_cst_value (access_fun);
 	return true;
       }
 
@@ -1426,11 +1463,11 @@ build_access_matrix (data_reference_p re
 
   for (i = 0; i < ndim; i++)
     {
-      lambda_vector v = lambda_vector_new (gbb_dim_domain (gb));
+      lambda_vector v = lambda_vector_new (ref_nb_loops (ref));
       scop_p scop = GBB_SCOP (gb);
       tree af = DR_ACCESS_FN (ref, i);
 
-      if (!build_access_matrix_with_af (af, v, scop))
+      if (!build_access_matrix_with_af (af, v, scop, ref_nb_loops (ref)))
 	return false;
 
       VEC_safe_push (lambda_vector, heap, DR_ACCESS_MATRIX (ref), v);
@@ -1452,7 +1489,7 @@ build_scop_data_accesses (scop_p scop)
       unsigned j;
       block_stmt_iterator bsi;
       data_reference_p dr;
-      struct loop *nest = outermost_loop_in_scop (scop, GBB_BB (gb));
+      struct loop *nest = outermost_loop_in_scop_without_dummy (scop, GBB_BB (gb));
 
       /* On each statement of the basic block, gather all the occurences
 	 to read/write memory.  */
@@ -1523,7 +1560,7 @@ initialize_dependence_polyhedron (scop_p
                                   struct data_reference *a, 
                                   struct data_reference *b)
 {
-  unsigned nb_cols, nb_rows, nb_loops, nb_params;
+  unsigned nb_cols, nb_rows, nb_loops, nb_params, nb_iter1, nb_iter2;
   struct loop_to_cloog_loop_str tmp, *slot1, *slot2; 
   unsigned row, col;
   CloogMatrix *domain1, *domain2;
@@ -1545,10 +1582,14 @@ initialize_dependence_polyhedron (scop_p
 
   /* Adding 2 columns: one for the eq/neq column, one for constant
      term.  */
-  nb_cols = scop_nb_loops (scop) * 2 + scop_nb_params (scop) + 2;
-  nb_rows = domain1->NbRows + domain2->NbRows + DR_NUM_DIMENSIONS (a);
-  nb_loops = scop_nb_loops (scop);
+  
   nb_params = scop_nb_params (scop);
+  nb_iter1 = domain1->NbColumns - 2 - nb_params;
+  nb_iter2 = domain2->NbColumns - 2 - nb_params;
+  nb_loops = scop_nb_loops (scop) - 1; /*without dummy loop */
+
+  nb_cols = nb_iter1 + nb_iter2 + scop_nb_params (scop) + 2;
+  nb_rows = domain1->NbRows + domain2->NbRows + DR_NUM_DIMENSIONS (a);
   dep_constraints = cloog_matrix_alloc (nb_rows, nb_cols);
 
   /* Initialize dependence polyhedron.  TODO: do we need it?  */
@@ -1559,7 +1600,7 @@ initialize_dependence_polyhedron (scop_p
   /* Copy the iterator part of Ds (domain of S statement), with eq/neq
      column.  */
   for (row = 0; row < domain1->NbRows; row++)
-    for (col = 0; col <= nb_loops; col++)
+    for (col = 0; col <= nb_iter1; col++)
       value_assign (dep_constraints->p[row][col], domain1->p[row][col]);
 
   /* Copy the parametric and constant part of Ds.  */
@@ -1568,51 +1609,52 @@ initialize_dependence_polyhedron (scop_p
       value_assign (dep_constraints->p[row][nb_cols-1],
 		    domain1->p[row][domain1->NbColumns - 1]);
       for (col = 1; col <= nb_params; col++)
-	value_assign (dep_constraints->p[row][col + 2 * scop_nb_loops (scop)],
-		      domain1->p[row][col + scop_nb_loops (scop)]);
+	value_assign (dep_constraints->p[row][col + nb_iter1 + nb_iter2],
+		      domain1->p[row][col + nb_iter1]);
     }
 
   /* Copy the iterator part of Dt (domain of T statement), without eq/neq column.  */
   for (row = 0; row < domain2->NbRows; row++)
-    for (col = 1; col <= nb_loops; col++)
-      value_assign (dep_constraints->p[row + domain1->NbRows][col + scop_nb_loops (scop)],
+    for (col = 1; col <= nb_iter2; col++)
+      value_assign (dep_constraints->p[row + domain1->NbRows][col + nb_iter2],
 		    domain2->p[row][col]);
   
   /* Copy the eq/neq column of Dt to dependence polyhedron.  */
   for (row = 0; row < domain2->NbRows; row++)
-    value_assign (dep_constraints->p[row + domain1->NbRows][0], domain1->p[row][0]);
+    value_assign (dep_constraints->p[row + domain1->NbRows][0], domain2->p[row][0]);
 
+  /* Copy the parametric and constant part of Dt.  */
   for (row = 0; row < domain2->NbRows; row++)
     {
       value_assign (dep_constraints->p[row + domain1->NbRows][nb_cols-1],
 		    domain1->p[row][domain2->NbColumns - 1]);
       for (col = 1; col <= nb_params; col++)
-        value_assign (dep_constraints->p[row + domain1->NbRows][col + 2 * scop_nb_loops (scop)],
-                      domain2->p[row][col + scop_nb_loops (scop)]);
+        value_assign (dep_constraints->p[row + domain1->NbRows][col + nb_iter1 + nb_iter2],
+                      domain2->p[row][col + nb_iter2]);
     }
 
   /* Copy Ds access matrix.  */
   for (row = 0; VEC_iterate (lambda_vector, DR_ACCESS_MATRIX (a), row, access_row_vector); row++)
     {
-      for (col = 0; col < nb_loops; col++)
-	value_set_si (dep_constraints->p[row + domain1->NbRows + domain2->NbRows][col + 1],
+      for (col = 1; col <= nb_iter1; col++)
+	value_set_si (dep_constraints->p[row + domain1->NbRows + domain2->NbRows][col],
 		      access_row_vector[col]);              
 
       value_set_si (dep_constraints->p[row + domain1->NbRows + domain2->NbRows][nb_cols-1], 
-                    access_row_vector[scop_dim_domain (scop) - 1]);
+                    access_row_vector[ref_nb_loops (a) - 1]);
       /* TODO: do not forget about parametric part.  */
     }
 
   /* Copy -Dt access matrix.  */
   for (row = 0; VEC_iterate (lambda_vector, DR_ACCESS_MATRIX (b), row, access_row_vector); row++)
     {
-      for (col = 0; col < nb_loops; col++)
-	value_set_si (dep_constraints->p[row + domain1->NbRows + domain2->NbRows][scop_nb_loops (scop) + col + 1], 
+      for (col = 1; col <= nb_iter2; col++)
+	value_set_si (dep_constraints->p[row + domain1->NbRows + domain2->NbRows][nb_iter1 + col], 
 		      -access_row_vector[col]);              
 
       value_sub_int (dep_constraints->p[row + domain1->NbRows + domain2->NbRows][nb_cols-1],
                      dep_constraints->p[row + domain1->NbRows + domain2->NbRows][nb_cols-1],
-                     access_row_vector[scop_dim_domain (scop) - 1]);
+                     access_row_vector[ref_nb_loops (b) - 1]);
     }
          
   return dep_constraints;