Improve the analysis of loop interchange

["Sebastian Pop" <sebastian dot pop at inria dot fr>]

Hi,

Here is a patch that corrects the analysis of strides for the
loop interchange.  We used to not transform loops like the
one from the testcase ltrans-5.c with multidimensional data:

int A[100][1111];

for( i = 0; i < 1111; i++)
 for( j = 0; j < 100; j++)
   A[j][i] = 5 * A[j][i];

The strides are collected in each dimension, for instance in
this testcase we collected the evolution in loop_i from A[j][i]
is 2 (there are two references with strides of 1), and the
evolution in loop_j from A[j][i] was wrongly computed equal
to 2, as the strides in the array A are of size of a line, not just
of 1.

With this patch we collect the strides for loop_j 2222 for A[j][i],
and we realize that this is bigger than 200 for loop_i, such that we
trigger the interchange transform for having smaller strides that are
better for cache locality.

Bootstrapped and tested on amd64-linux.  Okay for trunk?

Sebastian
	* tree-loop-linear.c (gather_interchange_stats): For multidimensional
	arrays, multiply the access strides by the size of the sub-array.
	* testsuite/gcc.dg/tree-ssa/ltrans-5.c: New.

Index: tree-loop-linear.c
===================================================================
--- tree-loop-linear.c	(revision 122880)
+++ tree-loop-linear.c	(working copy)
@@ -134,24 +134,30 @@ gather_interchange_stats (VEC (ddr_p, he
   for (i = 0; VEC_iterate (data_reference_p, datarefs, i, dr); i++)
     {
       unsigned int it;
+      tree ref = DR_REF (dr);
       tree stmt = DR_STMT (dr);
       struct loop *stmt_loop = loop_containing_stmt (stmt);
       struct loop *inner_loop = first_loop->inner;
-      
+
       if (inner_loop != stmt_loop 
 	  && !flow_loop_nested_p (inner_loop, stmt_loop))
 	continue;
-      for (it = 0; it < DR_NUM_DIMENSIONS (dr); it++)
+
+      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);
-	  
+	  tree tstride = evolution_part_in_loop_num (chrec, loop->num);
+	  tree array_size = TYPE_SIZE (TREE_TYPE (ref));
+
 	  if (tstride == NULL_TREE
-	      || TREE_CODE (tstride) != INTEGER_CST)
+	      || array_size == NULL_TREE 
+	      || TREE_CODE (tstride) != INTEGER_CST
+	      || TREE_CODE (array_size) != INTEGER_CST)
 	    continue;
-	  
-	  (*access_strides) += int_cst_value (tstride);
+
+	  (*access_strides) += 
+	    int_cst_value (array_size) * int_cst_value (tstride);
 	}
     }
 }
Index: testsuite/gcc.dg/tree-ssa/ltrans-5.c
===================================================================
--- testsuite/gcc.dg/tree-ssa/ltrans-5.c	(revision 0)
+++ testsuite/gcc.dg/tree-ssa/ltrans-5.c	(revision 0)
@@ -0,0 +1,17 @@
+/* { dg-do compile } */ 
+/* { dg-options "-O2 -ftree-loop-linear -fdump-tree-ltrans-all" } */
+
+int foo ()
+{
+  int A[100][1111];
+  int i, j;
+
+  for( i = 0; i < 1111; i++)
+    for( j = 0; j < 100; j++)
+      A[j][i] = 5 * A[j][i];
+
+  return A[10][10];
+}
+
+/* { dg-final { scan-tree-dump-times "transformed loop" 1 "ltrans"} } */ 
+/* { dg-final { cleanup-tree-dump "ltrans" } } */