tree-data-ref.c (find_vertex_for_stmt, [...]): New.

	* tree-data-ref.c (find_vertex_for_stmt, create_rdg_edge_for_ddr,
	create_rdg_edges_for_scalar, create_rdg_edges, create_rdg_vertices,
	stmts_from_loop, known_dependences_p, build_rdg): New.
	* tree-data-ref.h: Depends on graphds.h.
	(rdg_vertex, RDGV_STMT, rdg_dep_type, rdg_edge, RDGE_TYPE): New.
	(build_rdg): Declared.
	* Makefile.in (TREE_DATA_REF_H): Depends on graphds.h.

From-SVN: r126859

4 files changed, 236 insertions, 1 deletions

diff --git a/gcc/ChangeLog b/gcc/ChangeLog
index c5376f3..9d8ea76 100644
--- a/gcc/ChangeLog
+++ b/gcc/ChangeLog
@@ -1,3 +1,13 @@
+2007-07-23  Sebastian Pop  <sebpop@gmail.com>
+
+	* tree-data-ref.c (find_vertex_for_stmt, create_rdg_edge_for_ddr,
+	create_rdg_edges_for_scalar, create_rdg_edges, create_rdg_vertices,
+	stmts_from_loop, known_dependences_p, build_rdg): New.
+	* tree-data-ref.h: Depends on graphds.h.
+	(rdg_vertex, RDGV_STMT, rdg_dep_type, rdg_edge, RDGE_TYPE): New.
+	(build_rdg): Declared.
+	* Makefile.in (TREE_DATA_REF_H): Depends on graphds.h.
+
 2007-07-23  Daniel Berlin  <dberlin@dberlin.org>
 
 	* tree-ssa-propagate.c (valid_gimple_expression_p): Match up with
diff --git a/gcc/Makefile.in b/gcc/Makefile.in
index 7aa1efb..dc1f390 100644
--- a/gcc/Makefile.in
+++ b/gcc/Makefile.in
@@ -812,7 +812,7 @@ DIAGNOSTIC_H = diagnostic.h diagnostic.def $(PRETTY_PRINT_H) options.h
 C_PRETTY_PRINT_H = c-pretty-print.h $(PRETTY_PRINT_H) $(C_COMMON_H) $(TREE_H)
 SCEV_H = tree-scalar-evolution.h $(GGC_H) tree-chrec.h $(PARAMS_H)
 LAMBDA_H = lambda.h $(TREE_H) vec.h $(GGC_H)
-TREE_DATA_REF_H = tree-data-ref.h $(LAMBDA_H) omega.h
+TREE_DATA_REF_H = tree-data-ref.h $(LAMBDA_H) omega.h graphds.h
 VARRAY_H = varray.h $(MACHMODE_H) $(SYSTEM_H) coretypes.h $(TM_H)
 TREE_INLINE_H = tree-inline.h $(VARRAY_H) pointer-set.h
 REAL_H = real.h $(MACHMODE_H)
diff --git a/gcc/tree-data-ref.c b/gcc/tree-data-ref.c
index db1d83b..d217a24 100644
--- a/gcc/tree-data-ref.c
+++ b/gcc/tree-data-ref.c
@@ -4312,3 +4312,187 @@ free_data_refs (VEC (data_reference_p, heap) *datarefs)
   VEC_free (data_reference_p, heap, datarefs);
 }
 
+
+
+/* Returns the index of STMT in RDG.  */
+
+static int
+find_vertex_for_stmt (struct graph *rdg, tree stmt)
+{
+  int i;
+
+  for (i = 0; i < rdg->n_vertices; i++)
+    if (RDGV_STMT (&(rdg->vertices[i])) == stmt)
+      return i;
+
+  gcc_unreachable ();
+  return 0;
+}
+
+/* Creates an edge in RDG for each distance vector from DDR.  */
+
+static void
+create_rdg_edge_for_ddr (struct graph *rdg, ddr_p ddr)
+{
+  int va, vb;
+  data_reference_p dra;
+  data_reference_p drb;
+  struct graph_edge *e;
+
+  if (DDR_REVERSED_P (ddr))
+    {
+      dra = DDR_B (ddr);
+      drb = DDR_A (ddr);
+    }
+  else
+    {
+      dra = DDR_A (ddr);
+      drb = DDR_B (ddr);
+    }
+
+  va = find_vertex_for_stmt (rdg, DR_STMT (dra));
+  vb = find_vertex_for_stmt (rdg, DR_STMT (drb));
+
+  e = add_edge (rdg, va, vb);
+  e->data = XNEW (struct rdg_edge);
+
+  /* Determines the type of the data dependence.  */
+  if (DR_IS_READ (dra) && DR_IS_READ (drb))
+    RDGE_TYPE (e) = input_dd;
+  else if (!DR_IS_READ (dra) && !DR_IS_READ (drb))
+    RDGE_TYPE (e) = output_dd;
+  else if (!DR_IS_READ (dra) && DR_IS_READ (drb))
+    RDGE_TYPE (e) = flow_dd;
+  else if (DR_IS_READ (dra) && !DR_IS_READ (drb))
+    RDGE_TYPE (e) = anti_dd;
+}
+
+/* Creates dependence edges in RDG for all the uses of DEF.  IDEF is
+   the index of DEF in RDG.  */
+
+static void
+create_rdg_edges_for_scalar (struct graph *rdg, tree def, int idef)
+{
+  use_operand_p imm_use_p;
+  imm_use_iterator iterator;
+           
+  FOR_EACH_IMM_USE_FAST (imm_use_p, iterator, def)
+    {
+      int use = find_vertex_for_stmt (rdg, USE_STMT (imm_use_p));
+      struct graph_edge *e = add_edge (rdg, idef, use);
+
+      e->data = XNEW (struct rdg_edge);
+      RDGE_TYPE (e) = flow_dd;
+    }
+}
+
+/* Creates the edges of the reduced dependence graph RDG.  */
+
+static void
+create_rdg_edges (struct graph *rdg, VEC (ddr_p, heap) *ddrs)
+{
+  int i;
+  struct data_dependence_relation *ddr;
+  def_operand_p def_p;
+  ssa_op_iter iter;
+
+  for (i = 0; VEC_iterate (ddr_p, ddrs, i, ddr); i++)
+    if (DDR_ARE_DEPENDENT (ddr) == NULL_TREE)
+      create_rdg_edge_for_ddr (rdg, ddr);
+
+  for (i = 0; i < rdg->n_vertices; i++)
+    FOR_EACH_PHI_OR_STMT_DEF (def_p, RDGV_STMT (&(rdg->vertices[i])),
+			      iter, SSA_OP_ALL_DEFS)
+      create_rdg_edges_for_scalar (rdg, DEF_FROM_PTR (def_p), i);
+}
+
+/* Build the vertices of the reduced dependence graph RDG.  */
+
+static void
+create_rdg_vertices (struct graph *rdg, VEC (tree, heap) *stmts)
+{
+  int i;
+  tree s;
+
+  for (i = 0; VEC_iterate (tree, stmts, i, s); i++)
+    {
+      struct vertex *v = &(rdg->vertices[i]);
+
+      v->data = XNEW (struct rdg_vertex);
+      RDGV_STMT (v) = s;
+    }
+}
+
+/* Initialize STMTS with all the statements and PHI nodes of LOOP.  */
+
+static void
+stmts_from_loop (struct loop *loop, VEC (tree, heap) **stmts)
+{
+  unsigned int i;
+  basic_block *bbs = get_loop_body_in_dom_order (loop);
+
+  for (i = 0; i < loop->num_nodes; i++)
+    {
+      tree phi;
+      basic_block bb = bbs[i];
+      block_stmt_iterator bsi;
+
+      for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
+	VEC_safe_push (tree, heap, *stmts, phi);
+
+      for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
+	VEC_safe_push (tree, heap, *stmts, bsi_stmt (bsi));
+    }
+
+  free (bbs);
+}
+
+/* Returns true when all the dependences are computable.  */
+
+static bool
+known_dependences_p (VEC (ddr_p, heap) *dependence_relations)
+{
+  ddr_p ddr;
+  unsigned int i;
+
+  for (i = 0; VEC_iterate (ddr_p, dependence_relations, i, ddr); i++)
+    if (DDR_ARE_DEPENDENT (ddr) == chrec_dont_know)
+      return false;
+ 
+  return true;
+}
+
+/* Build a Reduced Dependence Graph with one vertex per statement of the
+   loop nest and one edge per data dependence or scalar dependence.  */
+
+struct graph *
+build_rdg (struct loop *loop)
+{
+  int nb_data_refs = 10;
+  struct graph *rdg = NULL;
+  VEC (ddr_p, heap) *dependence_relations;
+  VEC (data_reference_p, heap) *datarefs;
+  VEC (tree, heap) *stmts = VEC_alloc (tree, heap, 10);
+  
+  dependence_relations = VEC_alloc (ddr_p, heap, nb_data_refs * nb_data_refs) ;
+  datarefs = VEC_alloc (data_reference_p, heap, nb_data_refs);
+  compute_data_dependences_for_loop (loop, 
+                                     false,
+                                     &datarefs,
+                                     &dependence_relations);
+  
+  if (!known_dependences_p (dependence_relations))
+    goto end_rdg;
+
+  stmts_from_loop (loop, &stmts);
+  rdg = new_graph (VEC_length (tree, stmts));
+  create_rdg_vertices (rdg, stmts);
+  create_rdg_edges (rdg, dependence_relations);
+
+ end_rdg:
+  free_dependence_relations (dependence_relations);
+  free_data_refs (datarefs);
+  VEC_free (tree, heap, stmts);
+
+  return rdg;
+}
diff --git a/gcc/tree-data-ref.h b/gcc/tree-data-ref.h
index 0c04c4b..b5a6640 100644
--- a/gcc/tree-data-ref.h
+++ b/gcc/tree-data-ref.h
@@ -22,6 +22,7 @@ Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
 #ifndef GCC_TREE_DATA_REF_H
 #define GCC_TREE_DATA_REF_H
 
+#include "graphds.h"
 #include "lambda.h"
 #include "omega.h"
 
@@ -329,6 +330,46 @@ bool find_loop_nest (struct loop *, VEC (loop_p, heap) **);
 void compute_all_dependences (VEC (data_reference_p, heap) *,
 			      VEC (ddr_p, heap) **, VEC (loop_p, heap) *, bool);
 
+
+
+/* A RDG vertex representing a statement.  */
+typedef struct rdg_vertex
+{
+  /* The statement represented by this vertex.  */
+  tree stmt;
+} *rdg_vertex_p;
+
+#define RDGV_STMT(V)       ((struct rdg_vertex *) ((V)->data))->stmt
+
+/* Data dependence type.  */
+
+enum rdg_dep_type 
+{
+  /* Read After Write (RAW).  */
+  flow_dd = 'f',
+  
+  /* Write After Read (WAR).  */
+  anti_dd = 'a',
+  
+  /* Write After Write (WAW).  */
+  output_dd = 'o', 
+  
+  /* Read After Read (RAR).  */
+  input_dd = 'i' 
+};
+
+/* Dependence information attached to an edge of the RDG.  */
+
+typedef struct rdg_edge 
+{
+  /* Type of the dependence.  */
+  enum rdg_dep_type type;
+} *rdg_edge_p;
+
+#define RDGE_TYPE(E)        ((struct rdg_edge *) ((E)->data))->type
+
+struct graph *build_rdg (struct loop *);
+
 /* Return the index of the variable VAR in the LOOP_NEST array.  */
 
 static inline int