[patch] Cleanup lambda and loop linear

["Sebastian Pop" <sebpop at gmail dot com>]

Hi,

the attached patch changes the current way we look at the program in
the loop interchange pass by removing the direct access to the trees.

The new way to access the information is via the access matrix
representation, so we can combine several loop linear passes: once we
apply a loop transform, we can then transform the access matrix
representation by applying to it the transform matrix, then it is
possible to apply and determine heuristic informations for the next
loop transform by accessing the transformed access matrix.  This was
not possible before, as one would have had to apply the loop transform
to the gimple representation.

The patch was regstrapped on amd64-linux.  Okay for mainline?

Thanks,
Jan Sjodin, and Sebastian Pop

-- 
AMD - GNU Tools

email: sebpop@gmail.com, jan.sjodin@amd.com
branch:trunk
revision:HEAD
configure:
make:
check:

2008-05-15  Jan Sjodin  <jan.sjodin@amd.com>
	    Sebastian Pop  <sebastian.pop@amd.com>

	* tree-loop-linear.c (gather_interchange_stats): Look in the access matrix,
	and never look at the tree representation of the memory accesses.
	(linear_transform_loops): Computes parameters and access matrices.
	* tree-data-ref.c (compute_data_dependences_for_loop): Returns false when fails.
	(access_matrix_get_index_for_parameter): New.
	* tree-data-ref.h (struct access_matrix): New.
	(AM_LOOP_NEST_NUM, AM_NB_INDUCTION_VARS, AM_PARAMETERS, AM_MATRIX,
	AM_NB_PARAMETERS, AM_CONST_COLUMN_INDEX, AM_NB_COLUMNS,
	AM_GET_SUBSCRIPT_ACCESS_VECTOR, AM_GET_ACCESS_MATRIX_ELEMENT,
	am_vector_index_for_loop): New.
	(struct data_reference): Add field access_matrix.
	(DR_ACCESS_MATRIX): New.
	(compute_data_dependences_for_loop): Update declaration.
	(lambda_collect_parameters, lambda_compute_access_matrices): Declared.
	* lambda.h (lambda_vector_vec_p): Declared.
	* lambda-code.c: Depend on pointer-set.h.
	(lambda_collect_parameters_from_af, lambda_collect_parameters,
	av_for_af_base, av_for_af, build_access_matrix,
	lambda_compute_access_matrices): New.
	* Makefile.in (lambda-code.o): Depend on pointer-set.h.

Index: gcc/tree-loop-linear.c
===================================================================
--- gcc/tree-loop-linear.c	(revision 135661)
+++ gcc/tree-loop-linear.c	(working copy)
@@ -146,19 +146,17 @@ gather_interchange_stats (VEC (ddr_p, he
       for (it = 0; it < DR_NUM_DIMENSIONS (dr); 
 	   it++, ref = TREE_OPERAND (ref, 0))
 	{
-	  tree chrec = DR_ACCESS_FN (dr, it);
-	  tree tstride = evolution_part_in_loop_num (chrec, loop->num);
+	  int num = am_vector_index_for_loop (DR_ACCESS_MATRIX (dr), loop->num);
+	  int istride = AM_GET_ACCESS_MATRIX_ELEMENT (DR_ACCESS_MATRIX (dr), it, num);
 	  tree array_size = TYPE_SIZE (TREE_TYPE (ref));
 	  double_int dstride;
 
-	  if (tstride == NULL_TREE
-	      || array_size == NULL_TREE 
-	      || TREE_CODE (tstride) != INTEGER_CST
+	  if (array_size == NULL_TREE 
 	      || TREE_CODE (array_size) != INTEGER_CST)
 	    continue;
 
 	  dstride = double_int_mul (tree_to_double_int (array_size), 
-				    tree_to_double_int (tstride));
+				    shwi_to_double_int (istride));
 	  (*access_strides) = double_int_add (*access_strides, dstride);
 	}
     }
@@ -320,6 +318,7 @@ linear_transform_loops (void)
   loop_iterator li;
   VEC(tree,heap) *oldivs = NULL;
   VEC(tree,heap) *invariants = NULL;
+  VEC(tree,heap) *lambda_parameters = NULL;
   VEC(tree,heap) *remove_ivs = VEC_alloc (tree, heap, 3);
   struct loop *loop_nest;
   tree oldiv_stmt;
@@ -330,6 +329,7 @@ linear_transform_loops (void)
       unsigned int depth = 0;
       VEC (ddr_p, heap) *dependence_relations;
       VEC (data_reference_p, heap) *datarefs;
+      
       lambda_loopnest before, after;
       lambda_trans_matrix trans;
       struct obstack lambda_obstack;
@@ -341,11 +341,17 @@ linear_transform_loops (void)
 
       VEC_truncate (tree, oldivs, 0);
       VEC_truncate (tree, invariants, 0);
+      VEC_truncate (tree, lambda_parameters, 0);
 
       datarefs = VEC_alloc (data_reference_p, heap, 10);
       dependence_relations = VEC_alloc (ddr_p, heap, 10 * 10);
-      compute_data_dependences_for_loop (loop_nest, true, &datarefs,
-					 &dependence_relations);
+      if (!compute_data_dependences_for_loop (loop_nest, true, &datarefs,
+					      &dependence_relations))
+	continue;
+      
+      lambda_collect_parameters (datarefs, &lambda_parameters);
+      if (!lambda_compute_access_matrices (datarefs, lambda_parameters, loop_nest->num))
+	continue;
 
       if (dump_file && (dump_flags & TDF_DETAILS))
 	dump_ddrs (dump_file, dependence_relations);
Index: gcc/tree-data-ref.c
===================================================================
--- gcc/tree-data-ref.c	(revision 135663)
+++ gcc/tree-data-ref.c	(working copy)
@@ -4180,18 +4180,20 @@ find_loop_nest (struct loop *loop, VEC (
   return true;
 }
 
-/* Given a loop nest LOOP, the following vectors are returned:
+/* Returns true when the data dependences have been computed, false otherwise.
+   Given a loop nest LOOP, the following vectors are returned:
    DATAREFS is initialized to all the array elements contained in this loop, 
    DEPENDENCE_RELATIONS contains the relations between the data references.  
    Compute read-read and self relations if 
    COMPUTE_SELF_AND_READ_READ_DEPENDENCES is TRUE.  */
 
-void
+bool
 compute_data_dependences_for_loop (struct loop *loop, 
 				   bool compute_self_and_read_read_dependences,
 				   VEC (data_reference_p, heap) **datarefs,
 				   VEC (ddr_p, heap) **dependence_relations)
 {
+  bool res = true;
   VEC (loop_p, heap) *vloops = VEC_alloc (loop_p, heap, 3);
 
   memset (&dependence_stats, 0, sizeof (dependence_stats));
@@ -4209,6 +4211,7 @@ compute_data_dependences_for_loop (struc
 	 chrec_dont_know.  */
       ddr = initialize_data_dependence_relation (NULL, NULL, vloops);
       VEC_safe_push (ddr_p, heap, *dependence_relations, ddr);
+      res = false;
     }
   else
     compute_all_dependences (*datarefs, dependence_relations, vloops,
@@ -4260,7 +4263,9 @@ compute_data_dependences_for_loop (struc
 	       dependence_stats.num_miv_independent);
       fprintf (dump_file, "Number of miv tests unimplemented: %d\n",
 	       dependence_stats.num_miv_unimplemented);
-    }    
+    }
+
+  return res;
 }
 
 /* Entry point (for testing only).  Analyze all the data references
@@ -5032,3 +5037,18 @@ remove_similar_memory_refs (VEC (tree, h
   htab_delete (seen);
 }
 
+/* Returns the index of PARAMETER in the parameters vector of the ACCESS_MATRIX.  */
+
+int 
+access_matrix_get_index_for_parameter (tree parameter, struct access_matrix *access_matrix)
+{
+  int i;
+  VEC (tree,heap) *lambda_parameters = AM_PARAMETERS (access_matrix);
+  tree lambda_parameter;
+
+  for (i = 0; VEC_iterate (tree, lambda_parameters, i, lambda_parameter); i++)
+    if (lambda_parameter == parameter)
+      return i + AM_NB_INDUCTION_VARS (access_matrix);
+
+  return -1;
+}
Index: gcc/tree-data-ref.h
===================================================================
--- gcc/tree-data-ref.h	(revision 135661)
+++ gcc/tree-data-ref.h	(working copy)
@@ -96,6 +96,67 @@ struct dr_alias
   bitmap vops;
 };
 
+/* Each vector of the access matrix represents a linear access
+   function for a subscript.  First elements correspond to the
+   leftmost indices, ie. for a[i][j] the first vector corresponds to
+   the subscript in "i".  The elements of a vector are relative to
+   the loop nests in which the data reference is considered,
+   i.e. the vector is relative to the SCoP that provides the context
+   in which this data reference occurs.
+
+   For example, in
+
+   | loop_1
+   |    loop_2
+   |      a[i+3][2*j+n-1]
+
+   if "i" varies in loop_1 and "j" varies in loop_2, the access 
+   matrix with respect to the loop nest {loop_1, loop_2} is:
+
+   | loop_1  loop_2  param_n  cst
+   |   1       0        0      3
+   |   0       2        1     -1
+
+   whereas the access matrix with respect to loop_2 considers "i" as
+   a parameter:
+
+   | loop_2  param_i  param_n  cst
+   |   0       1         0      3
+   |   2       0         1     -1
+*/
+struct access_matrix
+{
+  int loop_nest_num;
+  int nb_induction_vars;
+  VEC (tree, heap) *parameters;
+  VEC (lambda_vector, heap) *matrix;
+};
+
+#define AM_LOOP_NEST_NUM(M) (M)->loop_nest_num
+#define AM_NB_INDUCTION_VARS(M) (M)->nb_induction_vars
+#define AM_PARAMETERS(M) (M)->parameters
+#define AM_MATRIX(M) (M)->matrix
+#define AM_NB_PARAMETERS(M) (VEC_length (tree, AM_PARAMETERS(M)))
+#define AM_CONST_COLUMN_INDEX(M) (AM_NB_INDUCTION_VARS (M) + AM_NB_PARAMETERS (M))
+#define AM_NB_COLUMNS(M) (AM_NB_INDUCTION_VARS (M) + AM_NB_PARAMETERS (M) + 1)
+#define AM_GET_SUBSCRIPT_ACCESS_VECTOR(M, I) VEC_index (lambda_vector, AM_MATRIX (M), I)
+#define AM_GET_ACCESS_MATRIX_ELEMENT(M, I, J) AM_GET_SUBSCRIPT_ACCESS_VECTOR (M, I)[J]
+
+/* Return the column in the access matrix of LOOP_NUM.  */
+
+static inline int
+am_vector_index_for_loop (struct access_matrix *access_matrix, int loop_num)
+{
+  gcc_assert (loop_num >= AM_LOOP_NEST_NUM (access_matrix));
+  return loop_num - AM_LOOP_NEST_NUM (access_matrix);
+}
+
+/* Finds the index of PARAMETER in LAMBDA_PARAMETERS, if the given parameter
+   does not exist -1 will be returned.  */
+
+int 
+access_matrix_get_index_for_parameter (tree parameter, struct access_matrix *access_matrix);
+
 struct data_reference
 {
   /* A pointer to the statement that contains this DR.  */
@@ -118,11 +179,10 @@ struct data_reference
 
   /* Alias information for the data reference.  */
   struct dr_alias alias;
-};
 
-typedef struct data_reference *data_reference_p;
-DEF_VEC_P(data_reference_p);
-DEF_VEC_ALLOC_P (data_reference_p, heap);
+  /* Matrix representation for the data access functions.  */
+  struct access_matrix *access_matrix;
+};
 
 #define DR_STMT(DR)                (DR)->stmt
 #define DR_REF(DR)                 (DR)->ref
@@ -139,6 +199,11 @@ DEF_VEC_ALLOC_P (data_reference_p, heap)
 #define DR_PTR_INFO(DR)            (DR)->alias.ptr_info
 #define DR_VOPS(DR)		   (DR)->alias.vops
 #define DR_ALIGNED_TO(DR)          (DR)->innermost.aligned_to
+#define DR_ACCESS_MATRIX(DR)       (DR)->access_matrix
+
+typedef struct data_reference *data_reference_p;
+DEF_VEC_P(data_reference_p);
+DEF_VEC_ALLOC_P (data_reference_p, heap);
 
 enum data_dependence_direction {
   dir_positive, 
@@ -309,7 +374,7 @@ DEF_VEC_ALLOC_O (data_ref_loc, heap);
 
 bool get_references_in_stmt (tree, VEC (data_ref_loc, heap) **);
 void dr_analyze_innermost (struct data_reference *);
-extern void compute_data_dependences_for_loop (struct loop *, bool,
+extern bool compute_data_dependences_for_loop (struct loop *, bool,
 					       VEC (data_reference_p, heap) **,
 					       VEC (ddr_p, heap) **);
 extern void print_direction_vector (FILE *, lambda_vector, int);
@@ -494,6 +559,8 @@ rdg_has_similar_memory_accesses (struct 
 
 /* In lambda-code.c  */
 bool lambda_transform_legal_p (lambda_trans_matrix, int, VEC (ddr_p, heap) *);
+void lambda_collect_parameters (VEC (data_reference_p, heap) *, VEC (tree, heap) **);
+bool lambda_compute_access_matrices (VEC (data_reference_p, heap) *, VEC (tree, heap) *, int);
 
 /* In tree-data-refs.c  */
 void split_constant_offset (tree , tree *, tree *);
Index: gcc/lambda.h
===================================================================
--- gcc/lambda.h	(revision 135661)
+++ gcc/lambda.h	(working copy)
@@ -28,10 +28,13 @@ along with GCC; see the file COPYING3.  
    and scalar multiplication.  In this vector space, an element is a list of
    integers.  */
 typedef int *lambda_vector;
-
 DEF_VEC_P(lambda_vector);
 DEF_VEC_ALLOC_P(lambda_vector,heap);
 
+typedef VEC(lambda_vector, heap) *lambda_vector_vec_p;
+DEF_VEC_P (lambda_vector_vec_p);
+DEF_VEC_ALLOC_P (lambda_vector_vec_p, heap);
+
 /* An integer matrix.  A matrix consists of m vectors of length n (IE
    all vectors are the same length).  */
 typedef lambda_vector *lambda_matrix;
@@ -487,4 +490,3 @@ dependence_level (lambda_vector dist_vec
 }
 
 #endif /* LAMBDA_H  */
-
Index: gcc/lambda-code.c
===================================================================
--- gcc/lambda-code.c	(revision 135661)
+++ gcc/lambda-code.c	(working copy)
@@ -42,6 +42,7 @@
 #include "vec.h"
 #include "lambda.h"
 #include "vecprim.h"
+#include "pointer-set.h"
 
 /* This loop nest code generation is based on non-singular matrix
    math.
@@ -2641,3 +2642,198 @@ lambda_transform_legal_p (lambda_trans_m
     }
   return true;
 }
+
+
+/* Collects parameters from affine function ACCESS_FUNCTION, and push
+   them in PARAMETERS.  */
+
+static void
+lambda_collect_parameters_from_af (tree access_function,
+				   struct pointer_set_t *param_set,
+				   VEC (tree, heap) **parameters)
+{
+  if (access_function == NULL)
+    return;
+
+  if (TREE_CODE (access_function) == SSA_NAME
+      && pointer_set_contains (param_set, access_function) == 0)
+    {
+      pointer_set_insert (param_set, access_function);
+      VEC_safe_push (tree, heap, *parameters, access_function);
+    }
+  else
+    {
+      int i, num_operands = tree_operand_length (access_function);
+
+      for (i = 0; i < num_operands; i++)
+	lambda_collect_parameters_from_af (TREE_OPERAND (access_function, i),
+					   param_set, parameters);
+    }
+}
+
+/* Collects parameters from DATAREFS, and push them in PARAMETERS.  */
+
+void
+lambda_collect_parameters (VEC (data_reference_p, heap) *datarefs,
+			   VEC (tree, heap) **parameters)
+{
+  unsigned i, j;
+  struct pointer_set_t *parameter_set = pointer_set_create ();
+  data_reference_p data_reference;
+
+  for (i = 0; VEC_iterate (data_reference_p, datarefs, i, data_reference); i++)
+    for (j = 0; j < DR_NUM_DIMENSIONS (data_reference); j++)
+      lambda_collect_parameters_from_af (DR_ACCESS_FN (data_reference, j),
+					 parameter_set, parameters);
+}
+
+/* Translates BASE_EXPR to vector CY.  AM is needed for inferring
+   indexing positions in the data access vector.  CST is the analyzed
+   integer constant.  */
+
+static bool
+av_for_af_base (tree base_expr, lambda_vector cy, struct access_matrix *am,
+		int cst)
+{
+  bool result = true;
+
+  switch (TREE_CODE (base_expr))
+    {
+    case INTEGER_CST:
+      /* Constant part.  */
+      cy[AM_CONST_COLUMN_INDEX (am)] += int_cst_value (base_expr) * cst;
+      return true;
+
+    case SSA_NAME:
+      {
+	int param_index =
+	  access_matrix_get_index_for_parameter (base_expr, am);
+
+	if (param_index >= 0)
+	  {
+	    cy[param_index] = cst + cy[param_index];
+	    return true;
+	  }
+
+	return false;
+      }
+
+    case PLUS_EXPR:
+      return av_for_af_base (TREE_OPERAND (base_expr, 0), cy, am, cst)
+	&& av_for_af_base (TREE_OPERAND (base_expr, 1), cy, am, cst);
+
+    case MINUS_EXPR:
+      return av_for_af_base (TREE_OPERAND (base_expr, 0), cy, am, cst)
+	&& av_for_af_base (TREE_OPERAND (base_expr, 1), cy, am, -1 * cst);
+
+    case MULT_EXPR:
+      if (TREE_CODE (TREE_OPERAND (base_expr, 0)) == INTEGER_CST)
+	result = av_for_af_base (TREE_OPERAND (base_expr, 1), 
+				 cy, am,
+				 int_cst_value (TREE_OPERAND (base_expr, 0)) * cst);
+      else if (TREE_CODE (TREE_OPERAND (base_expr, 1)) == INTEGER_CST)
+	result = av_for_af_base (TREE_OPERAND (base_expr, 0),
+				 cy, am,
+				 int_cst_value (TREE_OPERAND (base_expr, 1)) * cst);
+      else
+	result = false;
+
+      return result;
+
+    case NEGATE_EXPR:
+      return av_for_af_base (TREE_OPERAND (base_expr, 0), cy, am, -1 * cst);
+
+    default:
+      return false;
+    }
+
+  return result;
+}
+
+/* Translates ACCESS_FUN to vector CY.  AM is needed for inferring
+   indexing positions in the data access vector.  */
+
+static bool
+av_for_af (tree access_fun, lambda_vector cy, struct access_matrix *am)
+{
+  switch (TREE_CODE (access_fun))
+    {
+    case POLYNOMIAL_CHREC:
+      {
+	tree left = CHREC_LEFT (access_fun);
+	tree right = CHREC_RIGHT (access_fun);
+	unsigned var;
+
+	if (TREE_CODE (right) != INTEGER_CST)
+	  return false;
+
+	var = am_vector_index_for_loop (am, CHREC_VARIABLE (access_fun));
+	cy[var] = int_cst_value (right);
+
+	if (TREE_CODE (left) == POLYNOMIAL_CHREC)
+	  return av_for_af (left, cy, am);
+	else
+	  return av_for_af_base (left, cy, am, 1);
+      }
+
+    case INTEGER_CST:
+      /* Constant part.  */
+      return av_for_af_base (access_fun, cy, am, 1);
+
+    default:
+      return false;
+    }
+}
+
+/* Initializes the access matrix for DATA_REFERENCE.  */
+
+static bool
+build_access_matrix (data_reference_p data_reference,
+		     VEC (tree, heap) *parameters, int loop_nest_num)
+{
+  struct access_matrix *am = GGC_NEW (struct access_matrix);
+  unsigned i, ndim = DR_NUM_DIMENSIONS (data_reference);
+  struct loop *loop = bb_for_stmt (DR_STMT (data_reference))->loop_father;
+  unsigned nb_induction_vars = loop_depth (loop) - loop_nest_num + 1;
+  unsigned lambda_nb_columns;
+  lambda_vector_vec_p matrix;
+
+  AM_LOOP_NEST_NUM (am) = loop_nest_num;
+  AM_NB_INDUCTION_VARS (am) = nb_induction_vars;
+  AM_PARAMETERS (am) = parameters;
+
+  lambda_nb_columns = AM_NB_COLUMNS (am);
+  matrix = VEC_alloc (lambda_vector, heap, lambda_nb_columns);
+  AM_MATRIX (am) = matrix;
+
+  for (i = 0; i < ndim; i++)
+    {
+      lambda_vector access_vector = lambda_vector_new (lambda_nb_columns);
+      tree access_function = DR_ACCESS_FN (data_reference, i);
+
+      if (!av_for_af (access_function, access_vector, am))
+	return false;
+
+      VEC_safe_push (lambda_vector, heap, matrix, access_vector);
+    }
+
+  DR_ACCESS_MATRIX (data_reference) = am;
+  return true;
+}
+
+/* Returns false when one of the access matrices cannot be built.  */
+
+bool
+lambda_compute_access_matrices (VEC (data_reference_p, heap) *datarefs,
+				VEC (tree, heap) *parameters,
+				int loop_nest_num)
+{
+  data_reference_p dataref;
+  unsigned ix;
+
+  for (ix = 0; VEC_iterate (data_reference_p, datarefs, ix, dataref); ix++)
+    if (!build_access_matrix (dataref, parameters, loop_nest_num))
+      return false;
+
+  return true;
+}
Index: gcc/Makefile.in
===================================================================
--- gcc/Makefile.in	(revision 135661)
+++ gcc/Makefile.in	(working copy)
@@ -2885,7 +2885,7 @@ lambda-code.o: lambda-code.c $(LAMBDA_H)
    $(TM_H) $(OPTABS_H) $(TREE_H) $(RTL_H) $(BASIC_BLOCK_H) \
    $(DIAGNOSTIC_H) $(TREE_FLOW_H) $(TREE_DUMP_H) $(TIMEVAR_H) $(CFGLOOP_H) \
    $(TREE_DATA_REF_H) $(SCEV_H) $(EXPR_H) coretypes.h $(TARGET_H) \
-   tree-chrec.h tree-pass.h vec.h vecprim.h $(OBSTACK_H)
+   tree-chrec.h tree-pass.h vec.h vecprim.h $(OBSTACK_H) pointer-set.h
 params.o : params.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(TM_H) $(PARAMS_H) toplev.h
 pointer-set.o: pointer-set.c pointer-set.h $(CONFIG_H) $(SYSTEM_H)
 hooks.o: hooks.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(TM_H) $(HOOKS_H)