2013-09-11 Richard Biener <rguenther@suse.de>

	* tree-data-ref.c (dump_rdg_vertex, debug_rdg_vertex,
	dump_rdg_component, debug_rdg_component, dump_rdg, debug_rdg,
	dot_rdg_1, dot_rdg, rdg_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_empty_rdg,
	build_rdg, free_rdg, rdg_defs_used_in_other_loops_p): Move ...
	* tree-loop-distribution.c: ... here.
	* tree-data-ref.h (struct rdg_vertex, RDGV_STMT, RDGV_DATAREFS,
	RDGV_HAS_MEM_WRITE, RDGV_HAS_MEM_READS, RDG_STMT, RDG_DATAREFS,
	RDG_MEM_WRITE_STMT, RDG_MEM_READS_STMT, enum rdg_dep_type,
	struct rdg_edge, RDGE_TYPE, RDGE_LEVEL, RDGE_RELATION): Move ...
	* tree-loop-distribution.c: ... here.
	* tree-loop-distribution.c: Include gimple-pretty-print.h.
	(struct partition_s): Add loops member.
	(partition_alloc, partition_free, rdg_flag_uses, rdg_flag_vertex,
	rdg_flag_vertex_and_dependent, rdg_flag_loop_exits,
	build_rdg_partition_for_component, rdg_build_partitions): Adjust.


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

1 files changed, 0 insertions, 468 deletions

diff --git a/gcc/tree-data-ref.c b/gcc/tree-data-ref.c
index ca2cd8b3ad0..4d99eb3940f 100644
--- a/gcc/tree-data-ref.c
+++ b/gcc/tree-data-ref.c
@@ -4798,471 +4798,3 @@ free_data_refs (vec<data_reference_p> datarefs)
     free_data_ref (dr);
   datarefs.release ();
 }
-
-
-
-/* Dump vertex I in RDG to FILE.  */
-
-static void
-dump_rdg_vertex (FILE *file, struct graph *rdg, int i)
-{
-  struct vertex *v = &(rdg->vertices[i]);
-  struct graph_edge *e;
-
-  fprintf (file, "(vertex %d: (%s%s) (in:", i,
-	   RDG_MEM_WRITE_STMT (rdg, i) ? "w" : "",
-	   RDG_MEM_READS_STMT (rdg, i) ? "r" : "");
-
-  if (v->pred)
-    for (e = v->pred; e; e = e->pred_next)
-      fprintf (file, " %d", e->src);
-
-  fprintf (file, ") (out:");
-
-  if (v->succ)
-    for (e = v->succ; e; e = e->succ_next)
-      fprintf (file, " %d", e->dest);
-
-  fprintf (file, ")\n");
-  print_gimple_stmt (file, RDGV_STMT (v), 0, TDF_VOPS|TDF_MEMSYMS);
-  fprintf (file, ")\n");
-}
-
-/* Call dump_rdg_vertex on stderr.  */
-
-DEBUG_FUNCTION void
-debug_rdg_vertex (struct graph *rdg, int i)
-{
-  dump_rdg_vertex (stderr, rdg, i);
-}
-
-/* Dump component C of RDG to FILE.  If DUMPED is non-null, set the
-   dumped vertices to that bitmap.  */
-
-static void
-dump_rdg_component (FILE *file, struct graph *rdg, int c, bitmap dumped)
-{
-  int i;
-
-  fprintf (file, "(%d\n", c);
-
-  for (i = 0; i < rdg->n_vertices; i++)
-    if (rdg->vertices[i].component == c)
-      {
-	if (dumped)
-	  bitmap_set_bit (dumped, i);
-
-	dump_rdg_vertex (file, rdg, i);
-      }
-
-  fprintf (file, ")\n");
-}
-
-/* Call dump_rdg_vertex on stderr.  */
-
-DEBUG_FUNCTION void
-debug_rdg_component (struct graph *rdg, int c)
-{
-  dump_rdg_component (stderr, rdg, c, NULL);
-}
-
-/* Dump the reduced dependence graph RDG to FILE.  */
-
-void
-dump_rdg (FILE *file, struct graph *rdg)
-{
-  int i;
-  bitmap dumped = BITMAP_ALLOC (NULL);
-
-  fprintf (file, "(rdg\n");
-
-  for (i = 0; i < rdg->n_vertices; i++)
-    if (!bitmap_bit_p (dumped, i))
-      dump_rdg_component (file, rdg, rdg->vertices[i].component, dumped);
-
-  fprintf (file, ")\n");
-  BITMAP_FREE (dumped);
-}
-
-/* Call dump_rdg on stderr.  */
-
-DEBUG_FUNCTION void
-debug_rdg (struct graph *rdg)
-{
-  dump_rdg (stderr, rdg);
-}
-
-static void
-dot_rdg_1 (FILE *file, struct graph *rdg)
-{
-  int i;
-
-  fprintf (file, "digraph RDG {\n");
-
-  for (i = 0; i < rdg->n_vertices; i++)
-    {
-      struct vertex *v = &(rdg->vertices[i]);
-      struct graph_edge *e;
-
-      /* Highlight reads from memory.  */
-      if (RDG_MEM_READS_STMT (rdg, i))
-       fprintf (file, "%d [style=filled, fillcolor=green]\n", i);
-
-      /* Highlight stores to memory.  */
-      if (RDG_MEM_WRITE_STMT (rdg, i))
-       fprintf (file, "%d [style=filled, fillcolor=red]\n", i);
-
-      if (v->succ)
-       for (e = v->succ; e; e = e->succ_next)
-         switch (RDGE_TYPE (e))
-           {
-           case input_dd:
-             fprintf (file, "%d -> %d [label=input] \n", i, e->dest);
-             break;
-
-           case output_dd:
-             fprintf (file, "%d -> %d [label=output] \n", i, e->dest);
-             break;
-
-           case flow_dd:
-             /* These are the most common dependences: don't print these. */
-             fprintf (file, "%d -> %d \n", i, e->dest);
-             break;
-
-           case anti_dd:
-             fprintf (file, "%d -> %d [label=anti] \n", i, e->dest);
-             break;
-
-           default:
-             gcc_unreachable ();
-           }
-    }
-
-  fprintf (file, "}\n\n");
-}
-
-/* Display the Reduced Dependence Graph using dotty.  */
-extern void dot_rdg (struct graph *);
-
-DEBUG_FUNCTION void
-dot_rdg (struct graph *rdg)
-{
-  /* When debugging, enable the following code.  This cannot be used
-     in production compilers because it calls "system".  */
-#if 0
-  FILE *file = fopen ("/tmp/rdg.dot", "w");
-  gcc_assert (file != NULL);
-
-  dot_rdg_1 (file, rdg);
-  fclose (file);
-
-  system ("dotty /tmp/rdg.dot &");
-#else
-  dot_rdg_1 (stderr, rdg);
-#endif
-}
-
-/* Returns the index of STMT in RDG.  */
-
-int
-rdg_vertex_for_stmt (struct graph *rdg ATTRIBUTE_UNUSED, gimple stmt)
-{
-  int index = gimple_uid (stmt);
-  gcc_checking_assert (index == -1 || RDG_STMT (rdg, index) == stmt);
-  return index;
-}
-
-/* Creates an edge in RDG for each distance vector from DDR.  The
-   order that we keep track of in the RDG is the order in which
-   statements have to be executed.  */
-
-static void
-create_rdg_edge_for_ddr (struct graph *rdg, ddr_p ddr)
-{
-  struct graph_edge *e;
-  int va, vb;
-  data_reference_p dra = DDR_A (ddr);
-  data_reference_p drb = DDR_B (ddr);
-  unsigned level = ddr_dependence_level (ddr);
-
-  /* For non scalar dependences, when the dependence is REVERSED,
-     statement B has to be executed before statement A.  */
-  if (level > 0
-      && !DDR_REVERSED_P (ddr))
-    {
-      data_reference_p tmp = dra;
-      dra = drb;
-      drb = tmp;
-    }
-
-  va = rdg_vertex_for_stmt (rdg, DR_STMT (dra));
-  vb = rdg_vertex_for_stmt (rdg, DR_STMT (drb));
-
-  if (va < 0 || vb < 0)
-    return;
-
-  e = add_edge (rdg, va, vb);
-  e->data = XNEW (struct rdg_edge);
-
-  RDGE_LEVEL (e) = level;
-  RDGE_RELATION (e) = ddr;
-
-  /* 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_WRITE (dra) && DR_IS_WRITE (drb))
-    RDGE_TYPE (e) = output_dd;
-  else if (DR_IS_WRITE (dra) && DR_IS_READ (drb))
-    RDGE_TYPE (e) = flow_dd;
-  else if (DR_IS_READ (dra) && DR_IS_WRITE (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)
-    {
-      struct graph_edge *e;
-      int use = rdg_vertex_for_stmt (rdg, USE_STMT (imm_use_p));
-
-      if (use < 0)
-	continue;
-
-      e = add_edge (rdg, idef, use);
-      e->data = XNEW (struct rdg_edge);
-      RDGE_TYPE (e) = flow_dd;
-      RDGE_RELATION (e) = NULL;
-    }
-}
-
-/* Creates the edges of the reduced dependence graph RDG.  */
-
-static void
-create_rdg_edges (struct graph *rdg, vec<ddr_p> ddrs)
-{
-  int i;
-  struct data_dependence_relation *ddr;
-  def_operand_p def_p;
-  ssa_op_iter iter;
-
-  FOR_EACH_VEC_ELT (ddrs, i, ddr)
-    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, RDG_STMT (rdg, i),
-			      iter, SSA_OP_DEF)
-      create_rdg_edges_for_scalar (rdg, DEF_FROM_PTR (def_p), i);
-}
-
-/* Build the vertices of the reduced dependence graph RDG.  Return false
-   if that failed.  */
-
-static bool
-create_rdg_vertices (struct graph *rdg, vec<gimple> stmts, loop_p loop,
-		     vec<data_reference_p> *datarefs)
-{
-  int i;
-  gimple stmt;
-
-  FOR_EACH_VEC_ELT (stmts, i, stmt)
-    {
-      struct vertex *v = &(rdg->vertices[i]);
-
-      /* Record statement to vertex mapping.  */
-      gimple_set_uid (stmt, i);
-
-      v->data = XNEW (struct rdg_vertex);
-      RDGV_STMT (v) = stmt;
-      RDGV_DATAREFS (v).create (0);
-      RDGV_HAS_MEM_WRITE (v) = false;
-      RDGV_HAS_MEM_READS (v) = false;
-      if (gimple_code (stmt) == GIMPLE_PHI)
-	continue;
-
-      unsigned drp = datarefs->length ();
-      if (!find_data_references_in_stmt (loop, stmt, datarefs))
-	return false;
-      for (unsigned j = drp; j < datarefs->length (); ++j)
-	{
-	  data_reference_p dr = (*datarefs)[j];
-	  if (DR_IS_READ (dr))
-	    RDGV_HAS_MEM_READS (v) = true;
-	  else
-	    RDGV_HAS_MEM_WRITE (v) = true;
-	  RDGV_DATAREFS (v).safe_push (dr);
-	}
-    }
-  return true;
-}
-
-/* Initialize STMTS with all the statements of LOOP.  When
-   INCLUDE_PHIS is true, include also the PHI nodes.  The order in
-   which we discover statements is important as
-   generate_loops_for_partition is using the same traversal for
-   identifying statements. */
-
-static void
-stmts_from_loop (struct loop *loop, vec<gimple> *stmts)
-{
-  unsigned int i;
-  basic_block *bbs = get_loop_body_in_dom_order (loop);
-
-  for (i = 0; i < loop->num_nodes; i++)
-    {
-      basic_block bb = bbs[i];
-      gimple_stmt_iterator bsi;
-      gimple stmt;
-
-      for (bsi = gsi_start_phis (bb); !gsi_end_p (bsi); gsi_next (&bsi))
-	stmts->safe_push (gsi_stmt (bsi));
-
-      for (bsi = gsi_start_bb (bb); !gsi_end_p (bsi); gsi_next (&bsi))
-	{
-	  stmt = gsi_stmt (bsi);
-	  if (gimple_code (stmt) != GIMPLE_LABEL && !is_gimple_debug (stmt))
-	    stmts->safe_push (stmt);
-	}
-    }
-
-  free (bbs);
-}
-
-/* Returns true when all the dependences are computable.  */
-
-static bool
-known_dependences_p (vec<ddr_p> dependence_relations)
-{
-  ddr_p ddr;
-  unsigned int i;
-
-  FOR_EACH_VEC_ELT (dependence_relations, i, ddr)
-    if (DDR_ARE_DEPENDENT (ddr) == chrec_dont_know)
-      return false;
-
-  return true;
-}
-
-/* Build the Reduced Dependence Graph (RDG) with one vertex per
-   statement of the loop nest, and one edge per data dependence or
-   scalar dependence.  */
-
-struct graph *
-build_empty_rdg (int n_stmts)
-{
-  struct graph *rdg = new_graph (n_stmts);
-  return rdg;
-}
-
-/* Build the Reduced Dependence Graph (RDG) 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)
-{
-  struct graph *rdg;
-  vec<loop_p> loop_nest;
-  vec<gimple> stmts;
-  vec<data_reference_p> datarefs;
-  vec<ddr_p> dependence_relations;
-
-  loop_nest.create (3);
-  if (!find_loop_nest (loop, &loop_nest))
-    {
-      loop_nest.release ();
-      return NULL;
-    }
-
-  stmts.create (10);
-  stmts_from_loop (loop, &stmts);
-  rdg = build_empty_rdg (stmts.length ());
-  datarefs.create (10);
-  if (!create_rdg_vertices (rdg, stmts, loop, &datarefs))
-    {
-      stmts.release ();
-      free_rdg (rdg);
-      return NULL;
-    }
-  stmts.release ();
-  dependence_relations.create (100);
-  if (!compute_all_dependences (datarefs, &dependence_relations, loop_nest,
-				false)
-      || !known_dependences_p (dependence_relations))
-    {
-      loop_nest.release ();
-      datarefs.release ();
-      dependence_relations.release ();
-      free_rdg (rdg);
-      return NULL;
-    }
-  loop_nest.release ();
-  create_rdg_edges (rdg, dependence_relations);
-  dependence_relations.release ();
-
-  return rdg;
-}
-
-/* Free the reduced dependence graph RDG.  */
-
-void
-free_rdg (struct graph *rdg)
-{
-  int i;
-
-  for (i = 0; i < rdg->n_vertices; i++)
-    {
-      struct vertex *v = &(rdg->vertices[i]);
-      struct graph_edge *e;
-
-      for (e = v->succ; e; e = e->succ_next)
-	{
-	  free_dependence_relation (RDGE_RELATION (e));
-	  free (e->data);
-	}
-
-      if (v->data)
-	{
-	  gimple_set_uid (RDGV_STMT (v), -1);
-	  free_data_refs (RDGV_DATAREFS (v));
-	  free (v->data);
-	}
-    }
-
-  free_graph (rdg);
-}
-
-/* Determines whether the statement from vertex V of the RDG has a
-   definition used outside the loop that contains this statement.  */
-
-bool
-rdg_defs_used_in_other_loops_p (struct graph *rdg, int v)
-{
-  gimple stmt = RDG_STMT (rdg, v);
-  struct loop *loop = loop_containing_stmt (stmt);
-  use_operand_p imm_use_p;
-  imm_use_iterator iterator;
-  ssa_op_iter it;
-  def_operand_p def_p;
-
-  if (!loop)
-    return true;
-
-  FOR_EACH_PHI_OR_STMT_DEF (def_p, stmt, it, SSA_OP_DEF)
-    {
-      FOR_EACH_IMM_USE_FAST (imm_use_p, iterator, DEF_FROM_PTR (def_p))
-	{
-	  if (loop_containing_stmt (USE_STMT (imm_use_p)) != loop)
-	    return true;
-	}
-    }
-
-  return false;
-}