2004-08-26 Daniel Berlin <dberlin@dberlin.org>

	* Makefile.in (lambda-code.o): New.
	(lambda-trans.o): Ditto.
	(TREE_DATA_REF_H): Ditto.
	(LAMBDA_H): Ditto.
	(lambda-mat.o): Use LAMBDA_H.
	(tree-data-ref.o): Ditto.
	* lambda-code.c: New file.  Lambda code generation algorithm.
	* lambda-trans.c: Ditto. Lambda transformation matrix support.
	* lambda.h: Add lambda loop structures.
	Add lambda loopnest structures.
	Add lambda body vector structure.
	Add lambda linear expression structures.
	Add prototypes for functions in new files.
	* lambda-mat.c: Include tree.h

2004-08-26  Daniel Berlin <dberlin@dberlin.org>
	    Sebastian Pop  <pop@cri.ensmp.fr>

	* tree-data-ref.h: Include lambda.h
	(free_dependence_relation): Declared here.
	(free_dependence_relations): Ditto.
	(free_data_refs): Ditto.
	* tree-data-ref.c (free_dependence_relation): New function.
	(free_dependence_relations): Ditto.
	(free_data_refs): Ditot.
	(analyze_all_data_dependences): Free datarefs and dependence_relations.
	(build_classic_dist_vector): Store in the dependence_relations the
	information. Each arc in the dependence_relations graph is labelled
	with the distance and direction vectors.
	(build_classic_dir_vector): Ditto.
	(compute_rw_wr_ww_dependences): Renamed again compute_all_dependences.
	Now computes again the whole dependence graph including read-read
	relations.
	(compute_data_dependences_for_loop): Now dependence_relations contains
	all the data, and thus it doesn't need to initialize the classic_dir
	and classic_dist vectors.
	(analyze_all_data_dependences): Adjusted for using the new interface of
	compute_data_dependences_for_loop.  Remove the statistics dump.


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

1 files changed, 103 insertions, 83 deletions

diff --git a/gcc/tree-data-ref.c b/gcc/tree-data-ref.c
index c45762d8540..401bac62626 100644
--- a/gcc/tree-data-ref.c
+++ b/gcc/tree-data-ref.c
@@ -96,8 +96,6 @@ Software Foundation, 59 Temple Place - Suite 330, Boston, MA
 #include "tree-pass.h"
 #include "lambda.h"
 
-static unsigned int data_ref_id = 0;
-
 
 /* This is the simplest data dependence test: determines whether the
    data references A and B access the same array/region. If can't determine -
@@ -352,7 +350,7 @@ dump_data_reference (FILE *outf,
 {
   unsigned int i;
   
-  fprintf (outf, "(Data Ref %d: \n  stmt: ", DR_ID (dr));
+  fprintf (outf, "(Data Ref: \n  stmt: ");
   print_generic_stmt (outf, DR_STMT (dr), 0);
   fprintf (outf, "  ref: ");
   print_generic_stmt (outf, DR_REF (dr), 0);
@@ -380,7 +378,7 @@ dump_data_dependence_relation (FILE *outf,
   drb = DDR_B (ddr);
   
   if (dra && drb)
-    fprintf (outf, "(Data Dep (A = %d, B = %d):", DR_ID (dra), DR_ID (drb));
+    fprintf (outf, "(Data Dep:");
   else
     fprintf (outf, "(Data Dep:");
 
@@ -547,9 +545,8 @@ analyze_array (tree stmt, tree ref, bool is_read)
       fprintf (dump_file, ")\n");
     }
   
-  res = ggc_alloc (sizeof (struct data_reference));
+  res = xmalloc (sizeof (struct data_reference));
   
-  DR_ID (res) = data_ref_id++;
   DR_STMT (res) = stmt;
   DR_REF (res) = ref;
   VARRAY_TREE_INIT (DR_ACCESS_FNS (res), 3, "access_fns");
@@ -583,9 +580,8 @@ init_data_ref (tree stmt,
       fprintf (dump_file, ")\n");
     }
   
-  res = ggc_alloc (sizeof (struct data_reference));
+  res = xmalloc (sizeof (struct data_reference));
   
-  DR_ID (res) = data_ref_id++;
   DR_STMT (res) = stmt;
   DR_REF (res) = ref;
   VARRAY_TREE_INIT (DR_ACCESS_FNS (res), 5, "access_fns");
@@ -640,7 +636,7 @@ initialize_data_dependence_relation (struct data_reference *a,
   struct data_dependence_relation *res;
   bool differ_p;
   
-  res = ggc_alloc (sizeof (struct data_dependence_relation));
+  res = xmalloc (sizeof (struct data_dependence_relation));
   DDR_A (res) = a;
   DDR_B (res) = b;
 
@@ -665,13 +661,12 @@ initialize_data_dependence_relation (struct data_reference *a,
 	{
 	  struct subscript *subscript;
 	  
-	  subscript = ggc_alloc (sizeof (struct subscript));
+	  subscript = xmalloc (sizeof (struct subscript));
 	  SUB_CONFLICTS_IN_A (subscript) = chrec_dont_know;
 	  SUB_CONFLICTS_IN_B (subscript) = chrec_dont_know;
 	  SUB_LAST_CONFLICT_IN_A (subscript) = chrec_dont_know;
 	  SUB_LAST_CONFLICT_IN_B (subscript) = chrec_dont_know;
 	  SUB_DISTANCE (subscript) = chrec_dont_know;
-	  SUB_DIRECTION (subscript) = dir_star;
 	  VARRAY_PUSH_GENERIC_PTR (DDR_SUBSCRIPTS (res), subscript);
 	}
     }
@@ -686,6 +681,13 @@ static inline void
 finalize_ddr_dependent (struct data_dependence_relation *ddr, 
 			tree chrec)
 {
+  if (dump_file && (dump_flags & TDF_DETAILS))
+    {
+      fprintf (dump_file, "(dependence classified: ");
+      print_generic_expr (dump_file, chrec, 0);
+      fprintf (dump_file, ")\n");
+    }
+
   DDR_ARE_DEPENDENT (ddr) = chrec;  
   varray_clear (DDR_SUBSCRIPTS (ddr));
 }
@@ -1429,14 +1431,12 @@ subscript_dependence_tester (struct data_dependence_relation *ddr)
 
 /* Compute the classic per loop distance vector.
 
-   RES is the data dependence relation to build a vector from.
-   CLASSIC_DIST is the varray to place the vector in.
+   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.  */
 
 static void
-build_classic_dist_vector (struct data_dependence_relation *res, 
-			   varray_type *classic_dist, 
+build_classic_dist_vector (struct data_dependence_relation *ddr, 
 			   int nb_loops, unsigned int first_loop)
 {
   unsigned i;
@@ -1447,12 +1447,12 @@ build_classic_dist_vector (struct data_dependence_relation *res,
   lambda_vector_clear (dist_v, nb_loops);
   lambda_vector_clear (init_v, nb_loops);
   
-  if (DDR_ARE_DEPENDENT (res) != NULL_TREE)
+  if (DDR_ARE_DEPENDENT (ddr) != NULL_TREE)
     return;
   
-  for (i = 0; i < DDR_NUM_SUBSCRIPTS (res); i++)
+  for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++)
     {
-      struct subscript *subscript = DDR_SUBSCRIPT (res, i);
+      struct subscript *subscript = DDR_SUBSCRIPT (ddr, i);
 
       if (chrec_contains_undetermined (SUB_DISTANCE (subscript)))
 	return;
@@ -1479,7 +1479,7 @@ build_classic_dist_vector (struct data_dependence_relation *res,
 	  if (init_v[loop_nb] != 0
 	      && dist_v[loop_nb] != dist)
 	    {
-	      finalize_ddr_dependent (res, chrec_known);
+	      finalize_ddr_dependent (ddr, chrec_known);
 	      return;
 	    }
 
@@ -1497,8 +1497,8 @@ build_classic_dist_vector (struct data_dependence_relation *res,
   */
   {
     struct loop *lca, *loop_a, *loop_b;
-    struct data_reference *a = DDR_A (res);
-    struct data_reference *b = DDR_B (res);
+    struct data_reference *a = DDR_A (ddr);
+    struct data_reference *b = DDR_B (ddr);
     int lca_nb;
     loop_a = loop_containing_stmt (DR_STMT (a));
     loop_b = loop_containing_stmt (DR_STMT (b));
@@ -1535,19 +1535,17 @@ build_classic_dist_vector (struct data_dependence_relation *res,
       }
   }
   
-  VARRAY_PUSH_GENERIC_PTR (*classic_dist, dist_v);
+  DDR_DIST_VECT (ddr) = dist_v;
 }
 
 /* Compute the classic per loop direction vector.  
 
-   RES is the data dependence relation to build a vector from.
-   CLASSIC_DIR is the varray to place the vector in.
+   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.  */
 
 static void
-build_classic_dir_vector (struct data_dependence_relation *res, 
-			  varray_type *classic_dir, 
+build_classic_dir_vector (struct data_dependence_relation *ddr, 
 			  int nb_loops, unsigned int first_loop)
 {
   unsigned i;
@@ -1558,12 +1556,12 @@ build_classic_dir_vector (struct data_dependence_relation *res,
   lambda_vector_clear (dir_v, nb_loops);
   lambda_vector_clear (init_v, nb_loops);
   
-  if (DDR_ARE_DEPENDENT (res) != NULL_TREE)
+  if (DDR_ARE_DEPENDENT (ddr) != NULL_TREE)
     return;
   
-  for (i = 0; i < DDR_NUM_SUBSCRIPTS (res); i++)
+  for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++)
     {
-      struct subscript *subscript = DDR_SUBSCRIPT (res, i);
+      struct subscript *subscript = DDR_SUBSCRIPT (ddr, i);
 
       if (TREE_CODE (SUB_CONFLICTS_IN_A (subscript)) == POLYNOMIAL_CHREC
 	  && TREE_CODE (SUB_CONFLICTS_IN_B (subscript)) == POLYNOMIAL_CHREC)
@@ -1606,7 +1604,7 @@ build_classic_dir_vector (struct data_dependence_relation *res,
 	      && (enum data_dependence_direction) dir_v[loop_nb] != dir
 	      && (enum data_dependence_direction) dir_v[loop_nb] != dir_star)
 	    {
-	      finalize_ddr_dependent (res, chrec_known);
+	      finalize_ddr_dependent (ddr, chrec_known);
 	      return;
 	    }
 	  
@@ -1624,8 +1622,8 @@ build_classic_dir_vector (struct data_dependence_relation *res,
   */
   {
     struct loop *lca, *loop_a, *loop_b;
-    struct data_reference *a = DDR_A (res);
-    struct data_reference *b = DDR_B (res);
+    struct data_reference *a = DDR_A (ddr);
+    struct data_reference *b = DDR_B (ddr);
     int lca_nb;
     loop_a = loop_containing_stmt (DR_STMT (a));
     loop_b = loop_containing_stmt (DR_STMT (b));
@@ -1660,7 +1658,7 @@ build_classic_dir_vector (struct data_dependence_relation *res,
       }
   }
   
-  VARRAY_PUSH_GENERIC_PTR (*classic_dir, dir_v);
+  DDR_DIR_VECT (ddr) = dir_v;
 }
 
 /* Returns true when all the access functions of A are affine or
@@ -1697,8 +1695,7 @@ compute_affine_dependence (struct data_dependence_relation *ddr)
   
   if (dump_file && (dump_flags & TDF_DETAILS))
     {
-      fprintf (dump_file, "(compute_affine_dependence (%d, %d)\n", 
-	       DR_ID (dra), DR_ID (drb));
+      fprintf (dump_file, "(compute_affine_dependence\n");
       fprintf (dump_file, "  (stmt_a = \n");
       print_generic_expr (dump_file, DR_STMT (dra), 0);
       fprintf (dump_file, ")\n  (stmt_b = \n");
@@ -1731,8 +1728,8 @@ compute_affine_dependence (struct data_dependence_relation *ddr)
    in DEPENDENCE_RELATIONS.  */
 
 static void 
-compute_rw_wr_ww_dependences (varray_type datarefs, 
-			      varray_type *dependence_relations)
+compute_all_dependences (varray_type datarefs, 
+			 varray_type *dependence_relations)
 {
   unsigned int i, j, N;
 
@@ -1747,10 +1744,6 @@ compute_rw_wr_ww_dependences (varray_type datarefs,
 	a = VARRAY_GENERIC_PTR (datarefs, i);
 	b = VARRAY_GENERIC_PTR (datarefs, j);
 
-	/* Don't compute the "read-read" relations.  */
-	if (DR_IS_READ (a) && DR_IS_READ (b))
-	  continue;
-
 	ddr = initialize_data_dependence_relation (a, b);
 
 	VARRAY_PUSH_GENERIC_PTR (*dependence_relations, ddr);
@@ -1818,17 +1811,13 @@ find_data_references_in_loop (struct loop *loop, varray_type *datarefs)
 
 /* 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, 
-   *CLASSIC_DIST contains the set of distance vectors,
-   *CLASSIC_DIR contains the set of direction vectors.  */
+   *DEPENDENCE_RELATIONS contains the relations between the data references.  */
 
 void
 compute_data_dependences_for_loop (unsigned nb_loops, 
 				   struct loop *loop,
 				   varray_type *datarefs,
-				   varray_type *dependence_relations,
-				   varray_type *classic_dist, 
-				   varray_type *classic_dir)
+				   varray_type *dependence_relations)
 {
   unsigned int i;
 
@@ -1842,19 +1831,19 @@ 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, classic_dist, nb_loops, loop->num);
-      build_classic_dir_vector (ddr, classic_dir, nb_loops, loop->num);
+      build_classic_dist_vector (ddr, nb_loops, loop->num);
+      build_classic_dir_vector (ddr, nb_loops, loop->num);
       return;
     }
 
-  compute_rw_wr_ww_dependences (*datarefs, dependence_relations);
+  compute_all_dependences (*datarefs, dependence_relations);
 
   for (i = 0; i < VARRAY_ACTIVE_SIZE (*dependence_relations); i++)
     {
       struct data_dependence_relation *ddr;
       ddr = VARRAY_GENERIC_PTR (*dependence_relations, i);
-      build_classic_dist_vector (ddr, classic_dist, nb_loops, loop->num);
-      build_classic_dir_vector (ddr, classic_dir, nb_loops, loop->num);    
+      build_classic_dist_vector (ddr, nb_loops, loop->num);
+      build_classic_dir_vector (ddr, nb_loops, loop->num);    
     }
 }
 
@@ -1886,11 +1875,8 @@ analyze_all_data_dependences (struct loops *loops)
   unsigned int i;
   varray_type datarefs;
   varray_type dependence_relations;
-  varray_type classic_dist, classic_dir;
   int nb_data_refs = 10;
 
-  VARRAY_GENERIC_PTR_INIT (classic_dist, 10, "classic_dist");
-  VARRAY_GENERIC_PTR_INIT (classic_dir, 10, "classic_dir");
   VARRAY_GENERIC_PTR_INIT (datarefs, nb_data_refs, "datarefs");
   VARRAY_GENERIC_PTR_INIT (dependence_relations, 
 			   nb_data_refs * nb_data_refs,
@@ -1898,8 +1884,7 @@ analyze_all_data_dependences (struct loops *loops)
 
   /* Compute DDs on the whole function.  */
   compute_data_dependences_for_loop (loops->num, loops->parray[0], 
-				     &datarefs, &dependence_relations, 
-				     &classic_dist, &classic_dir);
+				     &datarefs, &dependence_relations);
 
   if (dump_file)
     {
@@ -1911,21 +1896,20 @@ analyze_all_data_dependences (struct loops *loops)
      testsuite.  */
   if (dump_file && (dump_flags & TDF_DETAILS))
     {
-      for (i = 0; i < VARRAY_ACTIVE_SIZE (classic_dist); i++)
-	{
-	  fprintf (dump_file, "DISTANCE_V (");
-	  print_lambda_vector (dump_file, 
-			       VARRAY_GENERIC_PTR (classic_dist, i),
-			       loops->num);
-	  fprintf (dump_file, ")\n");
-	}
-      for (i = 0; i < VARRAY_ACTIVE_SIZE (classic_dir); i++)
+      for (i = 0; i < VARRAY_ACTIVE_SIZE (dependence_relations); i++)
 	{
-	  fprintf (dump_file, "DIRECTION_V (");
-	  print_lambda_vector (dump_file, 
-			       VARRAY_GENERIC_PTR (classic_dir, i),
-			       loops->num);
-	  fprintf (dump_file, ")\n");
+	  struct data_dependence_relation *ddr = 
+	    (struct data_dependence_relation *) 
+	    VARRAY_GENERIC_PTR (dependence_relations, i);
+	  if (DDR_ARE_DEPENDENT (ddr) == NULL_TREE)
+	    {
+	      fprintf (dump_file, "DISTANCE_V (");
+	      print_lambda_vector (dump_file, DDR_DIST_VECT (ddr), loops->num);
+	      fprintf (dump_file, ")\n");
+	      fprintf (dump_file, "DIRECTION_V (");
+	      print_lambda_vector (dump_file, DDR_DIR_VECT (ddr), loops->num);
+	      fprintf (dump_file, ")\n");
+	    }
 	}
       fprintf (dump_file, "\n\n");
     }
@@ -1962,21 +1946,57 @@ analyze_all_data_dependences (struct loops *loops)
 	    nb_chrec_relations++;
 	}
       
-      fprintf (dump_file, "\n(\n");
-      fprintf (dump_file, "%d\tnb_top_relations\n", nb_top_relations);
-      fprintf (dump_file, "%d\tnb_bot_relations\n", nb_bot_relations);
-      fprintf (dump_file, "%d\tnb_basename_differ\n", nb_basename_differ);
-      fprintf (dump_file, "%d\tnb_distance_relations\n", (int) VARRAY_ACTIVE_SIZE (classic_dist));
-      fprintf (dump_file, "%d\tnb_chrec_relations\n", nb_chrec_relations);
-      fprintf (dump_file, "\n)\n");
-      
       gather_stats_on_scev_database ();
     }
-  
+
+  free_dependence_relations (dependence_relations);
+  free_data_refs (datarefs);
+}
+
+/* Free the memory used by a data dependence relation DDR.  */
+
+void
+free_dependence_relation (struct data_dependence_relation *ddr)
+{
+  if (ddr == NULL)
+    return;
+
+  if (DDR_ARE_DEPENDENT (ddr) == NULL_TREE && DDR_SUBSCRIPTS (ddr))
+    varray_clear (DDR_SUBSCRIPTS (ddr));
+  free (ddr);
+}
+
+/* Free the memory used by the data dependence relations from
+   DEPENDENCE_RELATIONS.  */
+
+void 
+free_dependence_relations (varray_type dependence_relations)
+{
+  unsigned int i;
+  if (dependence_relations == NULL)
+    return;
+
+  for (i = 0; i < VARRAY_ACTIVE_SIZE (dependence_relations); i++)
+    free_dependence_relation (VARRAY_GENERIC_PTR (dependence_relations, i));
   varray_clear (dependence_relations);
-  varray_clear (datarefs);
-  varray_clear (classic_dist);
-  varray_clear (classic_dir);
 }
 
+/* Free the memory used by the data references from DATAREFS.  */
+
+void
+free_data_refs (varray_type datarefs)
+{
+  unsigned int i;
+  
+  if (datarefs == NULL)
+    return;
 
+  for (i = 0; i < VARRAY_ACTIVE_SIZE (datarefs); i++)
+    {
+      struct data_reference *dr = (struct data_reference *) 
+	VARRAY_GENERIC_PTR (datarefs, i);
+      if (dr && DR_ACCESS_FNS (dr))
+	varray_clear (DR_ACCESS_FNS (dr));
+    }
+  varray_clear (datarefs);
+}