re PR tree-optimization/18792 (ICE with -O1 -ftree-loop-linear on small test case)

2005-01-06  Daniel Berlin <dberlin@dberlin.org>

	Fix PR tree-optimization/18792

	* tree-data-ref.c (build_classic_dist_vector): Change first_loop
	to first_loop_depth, and use loop depth instead of loop number.
	(build_classic_dir_vector): Ditto.
	(compute_data_dependences_for_loop): Use depth, not loop number.
	* tree-loop-linear.c (try_interchange_loops): Use loop depth, not loop
	number. Pass in loops, instead of loop numbers.
	(gather_interchange_stats): Ditto.
	(linear_transform_loops): Ditto.

From-SVN: r93008

4 files changed, 116 insertions, 81 deletions

diff --git a/gcc/ChangeLog b/gcc/ChangeLog
index 05e7547..bdadf4a 100644
--- a/gcc/ChangeLog
+++ b/gcc/ChangeLog
@@ -1,3 +1,16 @@
+2005-01-06  Daniel Berlin <dberlin@dberlin.org>
+	
+	Fix PR tree-optimization/18792
+
+	* tree-data-ref.c (build_classic_dist_vector): Change first_loop
+	to first_loop_depth, and use loop depth instead of loop number.
+	(build_classic_dir_vector): Ditto.
+	(compute_data_dependences_for_loop): Use depth, not loop number.
+	* tree-loop-linear.c (try_interchange_loops): Use loop depth, not loop 
+	number. Pass in loops, instead of loop numbers.
+	(gather_interchange_stats): Ditto.
+	(linear_transform_loops): Ditto.
+
 2005-01-06  Richard Sandiford  <rsandifo@redhat.com>
 
 	PR rtl-opt/13299
diff --git a/gcc/testsuite/gcc.dg/pr18792.c b/gcc/testsuite/gcc.dg/pr18792.c
new file mode 100644
index 0000000..4e93fe1
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/pr18792.c
@@ -0,0 +1,16 @@
+/* PR tree-optimization/18792 */
+/* { dg-do compile } */
+/* { dg-options "-O1 -ftree-loop-linear" } */
+void put_atoms_in_triclinic_unitcell(float x[][3])
+{
+	int i=0,d;
+
+	while (x[i][3] < 0)
+		for (d=0; d<=3; d++)
+			x[i][d] = 0;
+
+	while (x[i][3] >= 0)
+		for (d=0; d<=3; d++)
+			x[i][d] = 0;
+
+}
diff --git a/gcc/tree-data-ref.c b/gcc/tree-data-ref.c
index 5239821..112522e 100644
--- a/gcc/tree-data-ref.c
+++ b/gcc/tree-data-ref.c
@@ -1781,15 +1781,15 @@ subscript_dependence_tester (struct data_dependence_relation *ddr)
 
    DDR is the data dependence relation to build a vector from.
    NB_LOOPS is the total number of loops we are considering.
-   FIRST_LOOP is the loop->num of the first loop in the analyzed 
+   FIRST_LOOP_DEPTH is the loop->depth of the first loop in the analyzed
    loop nest.  
    Return FALSE if the dependence relation is outside of the loop nest
-   starting with FIRST_LOOP. 
+   starting at FIRST_LOOP_DEPTH. 
    Return TRUE otherwise.  */
 
 static bool
 build_classic_dist_vector (struct data_dependence_relation *ddr, 
-			   int nb_loops, unsigned int first_loop)
+			   int nb_loops, int first_loop_depth)
 {
   unsigned i;
   lambda_vector dist_v, init_v;
@@ -1819,19 +1819,18 @@ build_classic_dist_vector (struct data_dependence_relation *ddr,
       if (TREE_CODE (access_fn_a) == POLYNOMIAL_CHREC 
 	  && TREE_CODE (access_fn_b) == POLYNOMIAL_CHREC)
 	{
-	  int dist, loop_nb;
+	  int dist, loop_nb, loop_depth;
 	  int loop_nb_a = CHREC_VARIABLE (access_fn_a);
 	  int loop_nb_b = CHREC_VARIABLE (access_fn_b);
 	  struct loop *loop_a = current_loops->parray[loop_nb_a];
 	  struct loop *loop_b = current_loops->parray[loop_nb_b];
-	  struct loop *loop_first = current_loops->parray[first_loop];
 
 	  /* If the loop for either variable is at a lower depth than 
 	     the first_loop's depth, then we can't possibly have a
 	     dependency at this level of the loop.  */
 	     
-	  if (loop_a->depth < loop_first->depth
-	      || loop_b->depth < loop_first->depth)
+	  if (loop_a->depth < first_loop_depth
+	      || loop_b->depth < first_loop_depth)
 	    return false;
 
 	  if (loop_nb_a != loop_nb_b
@@ -1862,13 +1861,13 @@ build_classic_dist_vector (struct data_dependence_relation *ddr,
 	     | endloop_1
 	     In this case, the dependence is carried by loop_1.  */
 	  loop_nb = loop_nb_a < loop_nb_b ? loop_nb_a : loop_nb_b;
-	  loop_nb -= first_loop;
+	  loop_depth = current_loops->parray[loop_nb]->depth - first_loop_depth;
 
 	  /* If the loop number is still greater than the number of
 	     loops we've been asked to analyze, or negative,
 	     something is borked.  */
-	  gcc_assert (loop_nb >= 0);
-	  gcc_assert (loop_nb < nb_loops);
+	  gcc_assert (loop_depth >= 0);
+	  gcc_assert (loop_depth < nb_loops);
 	  if (chrec_contains_undetermined (SUB_DISTANCE (subscript)))
 	    {
 	      non_affine_dependence_relation (ddr);
@@ -1883,15 +1882,15 @@ build_classic_dist_vector (struct data_dependence_relation *ddr,
 	     |   ... = T[i][i]
 	     | endloop
 	     There is no dependence.  */
-	  if (init_v[loop_nb] != 0
-	      && dist_v[loop_nb] != dist)
+	  if (init_v[loop_depth] != 0
+	      && dist_v[loop_depth] != dist)
 	    {
 	      finalize_ddr_dependent (ddr, chrec_known);
 	      return true;
 	    }
 
-	  dist_v[loop_nb] = dist;
-	  init_v[loop_nb] = 1;
+	  dist_v[loop_depth] = dist;
+	  init_v[loop_depth] = 1;
 	}
     }
   
@@ -1906,43 +1905,43 @@ build_classic_dist_vector (struct data_dependence_relation *ddr,
     struct loop *lca, *loop_a, *loop_b;
     struct data_reference *a = DDR_A (ddr);
     struct data_reference *b = DDR_B (ddr);
-    int lca_nb;
+    int lca_depth;
     loop_a = loop_containing_stmt (DR_STMT (a));
     loop_b = loop_containing_stmt (DR_STMT (b));
     
     /* Get the common ancestor loop.  */
     lca = find_common_loop (loop_a, loop_b); 
     
-    lca_nb = lca->num;
-    lca_nb -= first_loop;
-    gcc_assert (lca_nb >= 0);
-    gcc_assert (lca_nb < nb_loops);
+    lca_depth = lca->depth;
+    lca_depth -= first_loop_depth;
+    gcc_assert (lca_depth >= 0);
+    gcc_assert (lca_depth < nb_loops);
 
     /* For each outer loop where init_v is not set, the accesses are
        in dependence of distance 1 in the loop.  */
     if (lca != loop_a
 	&& lca != loop_b
-	&& init_v[lca_nb] == 0)
-      dist_v[lca_nb] = 1;
+	&& init_v[lca_depth] == 0)
+      dist_v[lca_depth] = 1;
     
     lca = lca->outer;
     
     if (lca)
       {
-	lca_nb = lca->num - first_loop;
+	lca_depth = lca->depth - first_loop_depth;
 	while (lca->depth != 0)
 	  {
 	    /* If we're considering just a sub-nest, then don't record
 	       any information on the outer loops.  */
-	    if (lca_nb < 0)
+	    if (lca_depth < 0)
 	      break;
 
-	    gcc_assert (lca_nb < nb_loops);
+	    gcc_assert (lca_depth < nb_loops);
 
-	    if (init_v[lca_nb] == 0)
-	      dist_v[lca_nb] = 1;
+	    if (init_v[lca_depth] == 0)
+	      dist_v[lca_depth] = 1;
 	    lca = lca->outer;
-	    lca_nb = lca->num - first_loop;
+	    lca_depth = lca->depth - first_loop_depth;
 	  
 	  }
       }
@@ -1957,15 +1956,15 @@ build_classic_dist_vector (struct data_dependence_relation *ddr,
 
    DDR is the data dependence relation to build a vector from.
    NB_LOOPS is the total number of loops we are considering.
-   FIRST_LOOP is the loop->num of the first loop in the analyzed 
+   FIRST_LOOP_DEPTH is the loop->depth of the first loop in the analyzed 
    loop nest.
    Return FALSE if the dependence relation is outside of the loop nest
-   starting with FIRST_LOOP. 
+   at FIRST_LOOP_DEPTH. 
    Return TRUE otherwise.  */
 
 static bool
 build_classic_dir_vector (struct data_dependence_relation *ddr, 
-			  int nb_loops, unsigned int first_loop)
+			  int nb_loops, int first_loop_depth)
 {
   unsigned i;
   lambda_vector dir_v, init_v;
@@ -1994,20 +1993,19 @@ build_classic_dir_vector (struct data_dependence_relation *ddr,
       if (TREE_CODE (access_fn_a) == POLYNOMIAL_CHREC
 	  && TREE_CODE (access_fn_b) == POLYNOMIAL_CHREC)
 	{
-	  int dist, loop_nb;
+	  int dist, loop_nb, loop_depth;
 	  enum data_dependence_direction dir = dir_star;
 	  int loop_nb_a = CHREC_VARIABLE (access_fn_a);
 	  int loop_nb_b = CHREC_VARIABLE (access_fn_b);
 	  struct loop *loop_a = current_loops->parray[loop_nb_a];
 	  struct loop *loop_b = current_loops->parray[loop_nb_b];
-	  struct loop *loop_first = current_loops->parray[first_loop];
  
 	  /* If the loop for either variable is at a lower depth than 
 	     the first_loop's depth, then we can't possibly have a
 	     dependency at this level of the loop.  */
 	     
-	  if (loop_a->depth < loop_first->depth
-	      || loop_b->depth < loop_first->depth)
+	  if (loop_a->depth < first_loop_depth
+	      || loop_b->depth < first_loop_depth)
 	    return false;
 
 	  if (loop_nb_a != loop_nb_b
@@ -2038,13 +2036,13 @@ build_classic_dir_vector (struct data_dependence_relation *ddr,
 	     | endloop_1
 	     In this case, the dependence is carried by loop_1.  */
 	  loop_nb = loop_nb_a < loop_nb_b ? loop_nb_a : loop_nb_b;
-	  loop_nb -= first_loop;
+	  loop_depth = current_loops->parray[loop_nb]->depth - first_loop_depth;
 
 	  /* If the loop number is still greater than the number of
 	     loops we've been asked to analyze, or negative,
 	     something is borked.  */
-	  gcc_assert (loop_nb >= 0);
-	  gcc_assert (loop_nb < nb_loops);
+	  gcc_assert (loop_depth >= 0);
+	  gcc_assert (loop_depth < nb_loops);
 
 	  if (chrec_contains_undetermined (SUB_DISTANCE (subscript)))
 	    {
@@ -2067,17 +2065,17 @@ build_classic_dir_vector (struct data_dependence_relation *ddr,
 	     |   ... = T[i][i]
 	     | endloop
 	     There is no dependence.  */
-	  if (init_v[loop_nb] != 0
+	  if (init_v[loop_depth] != 0
 	      && dir != dir_star
-	      && (enum data_dependence_direction) dir_v[loop_nb] != dir
-	      && (enum data_dependence_direction) dir_v[loop_nb] != dir_star)
+	      && (enum data_dependence_direction) dir_v[loop_depth] != dir
+	      && (enum data_dependence_direction) dir_v[loop_depth] != dir_star)
 	    {
 	      finalize_ddr_dependent (ddr, chrec_known);
 	      return true;
 	    }
 	  
-	  dir_v[loop_nb] = dir;
-	  init_v[loop_nb] = 1;
+	  dir_v[loop_depth] = dir;
+	  init_v[loop_depth] = 1;
 	}
     }
   
@@ -2092,41 +2090,41 @@ build_classic_dir_vector (struct data_dependence_relation *ddr,
     struct loop *lca, *loop_a, *loop_b;
     struct data_reference *a = DDR_A (ddr);
     struct data_reference *b = DDR_B (ddr);
-    int lca_nb;
+    int lca_depth;
     loop_a = loop_containing_stmt (DR_STMT (a));
     loop_b = loop_containing_stmt (DR_STMT (b));
     
     /* Get the common ancestor loop.  */
     lca = find_common_loop (loop_a, loop_b); 
-    lca_nb = lca->num - first_loop;
+    lca_depth = lca->depth - first_loop_depth;
 
-    gcc_assert (lca_nb >= 0);
-    gcc_assert (lca_nb < nb_loops);
+    gcc_assert (lca_depth >= 0);
+    gcc_assert (lca_depth < nb_loops);
 
     /* For each outer loop where init_v is not set, the accesses are
        in dependence of distance 1 in the loop.  */
     if (lca != loop_a
 	&& lca != loop_b
-	&& init_v[lca_nb] == 0)
-      dir_v[lca_nb] = dir_positive;
+	&& init_v[lca_depth] == 0)
+      dir_v[lca_depth] = dir_positive;
     
     lca = lca->outer;
     if (lca)
       {
-	lca_nb = lca->num - first_loop;
+	lca_depth = lca->depth - first_loop_depth;
 	while (lca->depth != 0)
 	  {
 	    /* If we're considering just a sub-nest, then don't record
 	       any information on the outer loops.  */
-	    if (lca_nb < 0)
+	    if (lca_depth < 0)
 	      break;
 
-	    gcc_assert (lca_nb < nb_loops);
+	    gcc_assert (lca_depth < nb_loops);
 
-	    if (init_v[lca_nb] == 0)
-	      dir_v[lca_nb] = dir_positive;
+	    if (init_v[lca_depth] == 0)
+	      dir_v[lca_depth] = dir_positive;
 	    lca = lca->outer;
-	    lca_nb = lca->num - first_loop;
+	    lca_depth = lca->depth - first_loop_depth;
 	   
 	  }
       }
@@ -2330,8 +2328,8 @@ compute_data_dependences_for_loop (unsigned nb_loops,
 	 chrec_dont_know.  */
       ddr = initialize_data_dependence_relation (NULL, NULL);
       VARRAY_PUSH_GENERIC_PTR (*dependence_relations, ddr);
-      build_classic_dist_vector (ddr, nb_loops, loop->num);
-      build_classic_dir_vector (ddr, nb_loops, loop->num);
+      build_classic_dist_vector (ddr, nb_loops, loop->depth);
+      build_classic_dir_vector (ddr, nb_loops, loop->depth);
       return;
     }
 
@@ -2342,10 +2340,10 @@ compute_data_dependences_for_loop (unsigned nb_loops,
     {
       struct data_dependence_relation *ddr;
       ddr = VARRAY_GENERIC_PTR (allrelations, i);
-      if (build_classic_dist_vector (ddr, nb_loops, loop->num))
+      if (build_classic_dist_vector (ddr, nb_loops, loop->depth))
 	{
 	  VARRAY_PUSH_GENERIC_PTR (*dependence_relations, ddr);
-	  build_classic_dir_vector (ddr, nb_loops, loop->num);
+	  build_classic_dir_vector (ddr, nb_loops, loop->depth);
 	}
     }
 }
diff --git a/gcc/tree-loop-linear.c b/gcc/tree-loop-linear.c
index fcb93ea..8309789 100644
--- a/gcc/tree-loop-linear.c
+++ b/gcc/tree-loop-linear.c
@@ -55,19 +55,19 @@ Software Foundation, 59 Temple Place - Suite 330, Boston, MA
    transform matrix for locality purposes.
    TODO: Completion of partial transforms.  */
 
-/* Gather statistics for loop interchange.  LOOP_NUMBER is a relative
-   index in the considered loop nest.  The first loop in the
-   considered loop nest is FIRST_LOOP, and consequently the index of
-   the considered loop is obtained by FIRST_LOOP + LOOP_NUMBER.
+/* Gather statistics for loop interchange.  LOOP is the loop being
+   considered. The first loop in the considered loop nest is
+   FIRST_LOOP, and consequently, the index of the considered loop is
+   obtained by LOOP->DEPTH - FIRST_LOOP->DEPTH
    
    Initializes:
    - DEPENDENCE_STEPS the sum of all the data dependence distances
-   carried by loop LOOP_NUMBER,
+   carried by loop LOOP,
 
    - NB_DEPS_NOT_CARRIED_BY_LOOP the number of dependence relations
-   for which the loop LOOP_NUMBER is not carrying any dependence,
+   for which the loop LOOP is not carrying any dependence,
 
-   - ACCESS_STRIDES the sum of all the strides in LOOP_NUMBER.
+   - ACCESS_STRIDES the sum of all the strides in LOOP.
 
    Example: for the following loop,
 
@@ -93,8 +93,8 @@ Software Foundation, 59 Temple Place - Suite 330, Boston, MA
 static void
 gather_interchange_stats (varray_type dependence_relations, 
 			  varray_type datarefs,
-			  unsigned int loop_number, 
-			  unsigned int first_loop,
+			  struct loop *loop,
+			  struct loop *first_loop,
 			  unsigned int *dependence_steps, 
 			  unsigned int *nb_deps_not_carried_by_loop, 
 			  unsigned int *access_strides)
@@ -123,7 +123,7 @@ gather_interchange_stats (varray_type dependence_relations,
       
 
       
-      dist = DDR_DIST_VECT (ddr)[loop_number];
+      dist = DDR_DIST_VECT (ddr)[loop->depth - first_loop->depth];
       if (dist == 0)
 	(*nb_deps_not_carried_by_loop) += 1;
       else if (dist < 0)
@@ -139,17 +139,16 @@ gather_interchange_stats (varray_type dependence_relations,
       struct data_reference *dr = VARRAY_GENERIC_PTR (datarefs, i);
       tree stmt = DR_STMT (dr);
       struct loop *stmt_loop = loop_containing_stmt (stmt);
-      struct loop *inner_loop = current_loops->parray[first_loop + 1];
-
-      if (!flow_loop_nested_p (inner_loop, stmt_loop)
-	  && inner_loop->num != stmt_loop->num)
+      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++)
 	{
 	  tree chrec = DR_ACCESS_FN (dr, it);
 	  tree tstride = evolution_part_in_loop_num 
-	    (chrec, first_loop + loop_number);
+	    (chrec, loop->num);
 	  
 	  if (tstride == NULL_TREE
 	      || TREE_CODE (tstride) != INTEGER_CST)
@@ -173,9 +172,10 @@ try_interchange_loops (lambda_trans_matrix trans,
 		       unsigned int depth,		       
 		       varray_type dependence_relations,
 		       varray_type datarefs, 
-		       unsigned int first_loop)
+		       struct loop *first_loop)
 {
-  unsigned int loop_i, loop_j;
+  struct loop *loop_i;
+  struct loop *loop_j;
   unsigned int dependence_steps_i, dependence_steps_j;
   unsigned int access_strides_i, access_strides_j;
   unsigned int nb_deps_not_carried_by_i, nb_deps_not_carried_by_j;
@@ -189,8 +189,12 @@ try_interchange_loops (lambda_trans_matrix trans,
     return trans;
   
   /* LOOP_I is always the outer loop.  */
-  for (loop_j = 1; loop_j < depth; loop_j++)
-    for (loop_i = 0; loop_i < loop_j; loop_i++)
+  for (loop_j = first_loop->inner; 
+       loop_j; 
+       loop_j = loop_j->inner)
+    for (loop_i = first_loop; 
+	 loop_i->depth < loop_j->depth; 
+	 loop_i = loop_i->inner)
       {
 	gather_interchange_stats (dependence_relations, datarefs,
 				  loop_i, first_loop,
@@ -218,11 +222,15 @@ try_interchange_loops (lambda_trans_matrix trans,
 	    || nb_deps_not_carried_by_i > nb_deps_not_carried_by_j
 	    || access_strides_i < access_strides_j)
 	  {
-	    lambda_matrix_row_exchange (LTM_MATRIX (trans), loop_i, loop_j);
+	    lambda_matrix_row_exchange (LTM_MATRIX (trans),
+					loop_i->depth - first_loop->depth,
+					loop_j->depth - first_loop->depth);
 	    /* Validate the resulting matrix.  When the transformation
 	       is not valid, reverse to the previous transformation.  */
 	    if (!lambda_transform_legal_p (trans, depth, dependence_relations))
-	      lambda_matrix_row_exchange (LTM_MATRIX (trans), loop_i, loop_j);
+	      lambda_matrix_row_exchange (LTM_MATRIX (trans), 
+					  loop_i->depth - first_loop->depth, 
+					  loop_j->depth - first_loop->depth);
 	  }
       }
 
@@ -318,7 +326,7 @@ linear_transform_loops (struct loops *loops)
       lambda_matrix_id (LTM_MATRIX (trans), depth);
 
       trans = try_interchange_loops (trans, depth, dependence_relations,
-				     datarefs, loop_nest->num);
+				     datarefs, loop_nest);
 
       if (lambda_trans_matrix_id_p (trans))
 	{