2004-10-16 Daniel Berlin <dberlin@dberlin.org>

	Fix PR tree-optimization/17672
	Fix PR tree-optimization/18168

	* lambda-code.c (lambda_lattice_compute_base): Fix reversed
	assert test.
	(gcc_tree_to_linear_expression): Add extra to existing constant.
	(depth_of_nest): Factor out function used in various places.
	(gcc_loop_to_lambda_loop): Clean up code a little bit. No
	functional changes.
	(find_induction_var_from_exit_cond): Stop guessing, and just
	get the right answer :).
	(gcc_loopnest_to_lambda_loopnest): Remove useless pre-allocation.
	Print out message about result of attempt to create perfect nest.
	(lbv_to_gcc_expression): Add type argument, use it to do math
	and induction variable creation.
	(lle_to_gcc_expression): Ditto.
	(lambda_loopnest_to_gcc_loopnest): Create new iv with same type as
	oldiv. Pass type argument to lle_to_gcc_expression and
	lbv_to_gcc_expression.
	Reset number of iterations after transformation.
	(perfect_nestify): Remove useless pre-allocation, and cleanup
	a small amount.

	* tree-data-ref.c (build_classic_dist_vector): Return false for
	dependences completely outside of the loop nest we asked about.
	(build_classic_dir_vector): Ditto.
	(compute_data_dependences_for_loop): Only add dependence relations
	inside the loop we asked about.

	* tree-loop-linear.c (linear_transform_loops): Use DDR_SIZE_VECT.
	Compute immediate uses.

	* tree-optimize.c: Move linear_transform_loops to before ivcanon.


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

1 files changed, 52 insertions, 26 deletions

diff --git a/gcc/tree-data-ref.c b/gcc/tree-data-ref.c
index c34ae7fb5de..9a0126c3317 100644
--- a/gcc/tree-data-ref.c
+++ b/gcc/tree-data-ref.c
@@ -1772,9 +1772,12 @@ 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 
-   loop nest.  */
+   loop nest.  
+   Return FALSE if the dependence relation is outside of the loop nest
+   starting with FIRST_LOOP. 
+   Return TRUE otherwise.  */
 
-static void
+static bool
 build_classic_dist_vector (struct data_dependence_relation *ddr, 
 			   int nb_loops, unsigned int first_loop)
 {
@@ -1787,7 +1790,7 @@ build_classic_dist_vector (struct data_dependence_relation *ddr,
   lambda_vector_clear (init_v, nb_loops);
   
   if (DDR_ARE_DEPENDENT (ddr) != NULL_TREE)
-    return;
+    return true;
   
   for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++)
     {
@@ -1797,7 +1800,7 @@ build_classic_dist_vector (struct data_dependence_relation *ddr,
       if (chrec_contains_undetermined (SUB_DISTANCE (subscript)))
 	{
 	  non_affine_dependence_relation (ddr);
-	  return;
+	  return true;
 	}
 
       access_fn_a = DR_ACCESS_FN (DDR_A (ddr), i);
@@ -1811,6 +1814,15 @@ build_classic_dist_vector (struct data_dependence_relation *ddr,
 	  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 loops for both variables are at a lower depth than 
+	     the first_loop's depth, then they 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)
+	    return false;
 
 	  if (loop_nb_a != loop_nb_b
 	      && !flow_loop_nested_p (loop_a, loop_b)
@@ -1828,7 +1840,7 @@ build_classic_dist_vector (struct data_dependence_relation *ddr,
 		 the dependence relation cannot be captured by the
 		 distance abstraction.  */
 	      non_affine_dependence_relation (ddr);
-	      return;
+	      return true;
 	    }
 
 	  /* The dependence is carried by the outermost loop.  Example:
@@ -1850,7 +1862,7 @@ build_classic_dist_vector (struct data_dependence_relation *ddr,
 	  if (chrec_contains_undetermined (SUB_DISTANCE (subscript)))
 	    {
 	      non_affine_dependence_relation (ddr);
-	      return;
+	      return true;
 	    }
 	  
 	  dist = int_cst_value (SUB_DISTANCE (subscript));
@@ -1865,7 +1877,7 @@ build_classic_dist_vector (struct data_dependence_relation *ddr,
 	      && dist_v[loop_nb] != dist)
 	    {
 	      finalize_ddr_dependent (ddr, chrec_known);
-	      return;
+	      return true;
 	    }
 
 	  dist_v[loop_nb] = dist;
@@ -1928,6 +1940,7 @@ build_classic_dist_vector (struct data_dependence_relation *ddr,
   
   DDR_DIST_VECT (ddr) = dist_v;
   DDR_SIZE_VECT (ddr) = nb_loops;
+  return true;
 }
 
 /* Compute the classic per loop direction vector.  
@@ -1935,9 +1948,12 @@ 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 
-   loop nest.  */
+   loop nest.
+   Return FALSE if the dependence relation is outside of the loop nest
+   starting with FIRST_LOOP. 
+   Return TRUE otherwise.  */
 
-static void
+static bool
 build_classic_dir_vector (struct data_dependence_relation *ddr, 
 			  int nb_loops, unsigned int first_loop)
 {
@@ -1950,7 +1966,7 @@ build_classic_dir_vector (struct data_dependence_relation *ddr,
   lambda_vector_clear (init_v, nb_loops);
   
   if (DDR_ARE_DEPENDENT (ddr) != NULL_TREE)
-    return;
+    return true;
   
   for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++)
     {
@@ -1960,7 +1976,7 @@ build_classic_dir_vector (struct data_dependence_relation *ddr,
       if (chrec_contains_undetermined (SUB_DISTANCE (subscript)))
 	{
 	  non_affine_dependence_relation (ddr);
-	  return;
+	  return true;
 	}
 
       access_fn_a = DR_ACCESS_FN (DDR_A (ddr), i);
@@ -1974,6 +1990,14 @@ build_classic_dir_vector (struct data_dependence_relation *ddr,
 	  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 loops for both variables are at a lower depth than 
+	     the first_loop's depth, then they can't possibly matter */
+	     
+	  if (loop_a->depth < loop_first->depth
+	      && loop_b->depth < loop_first->depth)
+	    return false;
 
 	  if (loop_nb_a != loop_nb_b
 	      && !flow_loop_nested_p (loop_a, loop_b)
@@ -1991,7 +2015,7 @@ build_classic_dir_vector (struct data_dependence_relation *ddr,
 		 the dependence relation cannot be captured by the
 		 distance abstraction.  */
 	      non_affine_dependence_relation (ddr);
-	      return;
+	      return true;
 	    }
 
 	  /* The dependence is carried by the outermost loop.  Example:
@@ -2014,7 +2038,7 @@ build_classic_dir_vector (struct data_dependence_relation *ddr,
 	  if (chrec_contains_undetermined (SUB_DISTANCE (subscript)))
 	    {
 	      non_affine_dependence_relation (ddr);
-	      return;
+	      return true;
 	    }
 
 	  dist = int_cst_value (SUB_DISTANCE (subscript));
@@ -2038,7 +2062,7 @@ build_classic_dir_vector (struct data_dependence_relation *ddr,
 	      && (enum data_dependence_direction) dir_v[loop_nb] != dir_star)
 	    {
 	      finalize_ddr_dependent (ddr, chrec_known);
-	      return;
+	      return true;
 	    }
 	  
 	  dir_v[loop_nb] = dir;
@@ -2099,6 +2123,7 @@ build_classic_dir_vector (struct data_dependence_relation *ddr,
   
   DDR_DIR_VECT (ddr) = dir_v;
   DDR_SIZE_VECT (ddr) = nb_loops;
+  return true;
 }
 
 /* Returns true when all the access functions of A are affine or
@@ -2195,10 +2220,8 @@ compute_all_dependences (varray_type datarefs,
    DATAREFS.  Returns chrec_dont_know when failing to analyze a
    difficult case, returns NULL_TREE otherwise.
    
-   FIXME: This is a "dumb" walker over all the trees in the loop body.
-   Find another technique that avoids this costly walk.  This is
-   acceptable for the moment, since this function is used only for
-   debugging purposes.  */
+   TODO: This function should be made smarter so that it can handle address
+   arithmetic as if they were array accesses, etc.  */
 
 tree 
 find_data_references_in_loop (struct loop *loop, varray_type *datarefs)
@@ -2226,7 +2249,7 @@ find_data_references_in_loop (struct loop *loop, varray_type *datarefs)
 	      && !V_MUST_DEF_OPS (ann)
 	      && !V_MAY_DEF_OPS (ann))
 	    continue;
-
+	  
 	  /* In the GIMPLE representation, a modify expression
   	     contains a single load or store to memory.  */
 	  if (TREE_CODE (TREE_OPERAND (stmt, 0)) == ARRAY_REF)
@@ -2238,7 +2261,6 @@ find_data_references_in_loop (struct loop *loop, varray_type *datarefs)
 	    VARRAY_PUSH_GENERIC_PTR 
 		    (*datarefs, analyze_array (stmt, TREE_OPERAND (stmt, 1), 
 					       true));
-
   	  else
 	    {
 	      if (dont_know_node_not_inserted)
@@ -2251,7 +2273,6 @@ find_data_references_in_loop (struct loop *loop, varray_type *datarefs)
 		  DR_BASE_NAME (res) = NULL;
 		  DR_IS_READ (res) = false;
 		  VARRAY_PUSH_GENERIC_PTR (*datarefs, res);
-
 		  dont_know_node_not_inserted = false;
 		}
 	    }
@@ -2286,6 +2307,7 @@ compute_data_dependences_for_loop (unsigned nb_loops,
 				   varray_type *dependence_relations)
 {
   unsigned int i;
+  varray_type allrelations;
 
   /* If one of the data references is not computable, give up without
      spending time to compute other dependences.  */
@@ -2302,14 +2324,18 @@ compute_data_dependences_for_loop (unsigned nb_loops,
       return;
     }
 
-  compute_all_dependences (*datarefs, dependence_relations);
+  VARRAY_GENERIC_PTR_INIT (allrelations, 1, "Data dependence relations");
+  compute_all_dependences (*datarefs, &allrelations);
 
-  for (i = 0; i < VARRAY_ACTIVE_SIZE (*dependence_relations); i++)
+  for (i = 0; i < VARRAY_ACTIVE_SIZE (allrelations); i++)
     {
       struct data_dependence_relation *ddr;
-      ddr = VARRAY_GENERIC_PTR (*dependence_relations, i);
-      build_classic_dist_vector (ddr, nb_loops, loop->num);
-      build_classic_dir_vector (ddr, nb_loops, loop->num);    
+      ddr = VARRAY_GENERIC_PTR (allrelations, i);
+      if (build_classic_dist_vector (ddr, nb_loops, loop->num))
+	{
+	  VARRAY_PUSH_GENERIC_PTR (*dependence_relations, ddr);
+	  build_classic_dir_vector (ddr, nb_loops, loop->num);
+	}
     }
 }