This is the mail archive of the gcc-patches@gcc.gnu.org mailing list for the GCC project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

[PATCH] More loop-distribution TLC


This is the last cleanup before I start adding new features.

Bootstrapped and tested on x86_64-unknown-linux-gnu, applied to trunk.

Richard.

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

	* tree-data-ref.h (known_dependences_p): Move here ...
	* tree-loop-distribution.c (known_dependences_p): ... from here.
	(dump_rdg_component, debug_rdg_component): Remove.
	(dump_rdg): Adjust.
	(generate_loops_for_partition): Use gimple_uid instead of
	relying on matching stmt visit order.
	(rdg_build_partitions): Take starting stmt vector.
	(ldist_gen): Merge into ...
	(distribute_loop): ... this function.  Do not compute starting
	vertices vector.

Index: gcc/tree-data-ref.h
===================================================================
*** gcc/tree-data-ref.h	(revision 202558)
--- gcc/tree-data-ref.h	(working copy)
*************** ddrs_have_anti_deps (vec<ddr_p> dependen
*** 482,487 ****
--- 482,502 ----
    return false;
  }
  
+ /* Returns true when all the dependences are computable.  */
+ 
+ inline 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;
+ }
+ 
  /* Returns the dependence level for a vector DIST of size LENGTH.
     LEVEL = 0 means a lexicographic dependence, i.e. a dependence due
     to the sequence of statements, not carried by any loop.  */
Index: gcc/tree-cfg.c
===================================================================
*** gcc/tree-cfg.c	(revision 202558)
--- gcc/tree-cfg.c	(working copy)
*************** gimple_duplicate_bb (basic_block bb)
*** 5563,5568 ****
--- 5583,5589 ----
        copy = create_phi_node (NULL_TREE, new_bb);
        create_new_def_for (gimple_phi_result (phi), copy,
  			  gimple_phi_result_ptr (copy));
+       gimple_set_uid (copy, gimple_uid (phi));
      }
  
    gsi_tgt = gsi_start_bb (new_bb);
Index: gcc/tree-loop-distribution.c
===================================================================
*** gcc/tree-loop-distribution.c	(revision 202558)
--- gcc/tree-loop-distribution.c	(working copy)
*************** debug_rdg_vertex (struct graph *rdg, int
*** 150,201 ****
    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.  */
  
  static 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.  */
--- 150,164 ----
    dump_rdg_vertex (stderr, rdg, i);
  }
  
  /* Dump the reduced dependence graph RDG to FILE.  */
  
  static void
  dump_rdg (FILE *file, struct graph *rdg)
  {
    fprintf (file, "(rdg\n");
!   for (int i = 0; i < rdg->n_vertices; i++)
!     dump_rdg_vertex (file, rdg, i);
    fprintf (file, ")\n");
  }
  
  /* Call dump_rdg on stderr.  */
*************** create_rdg_vertices (struct graph *rdg,
*** 425,435 ****
    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)
--- 388,397 ----
    return true;
  }
  
! /* Initialize STMTS with all the statements of LOOP.  The order in
     which we discover statements is important as
     generate_loops_for_partition is using the same traversal for
!    identifying statements in loop copies.  */
  
  static void
  stmts_from_loop (struct loop *loop, vec<gimple> *stmts)
*************** stmts_from_loop (struct loop *loop, vec<
*** 458,478 ****
    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.  */
--- 420,425 ----
*************** static void
*** 693,699 ****
  generate_loops_for_partition (struct loop *loop, partition_t partition,
  			      bool copy_p)
  {
!   unsigned i, x;
    gimple_stmt_iterator bsi;
    basic_block *bbs;
  
--- 640,646 ----
  generate_loops_for_partition (struct loop *loop, partition_t partition,
  			      bool copy_p)
  {
!   unsigned i;
    gimple_stmt_iterator bsi;
    basic_block *bbs;
  
*************** generate_loops_for_partition (struct loo
*** 705,757 ****
        create_bb_after_loop (loop);
      }
  
!   /* Remove stmts not in the PARTITION bitmap.  The order in which we
!      visit the phi nodes and the statements is exactly as in
!      stmts_from_loop.  */
    bbs = get_loop_body_in_dom_order (loop);
  
    if (MAY_HAVE_DEBUG_STMTS)
!     for (x = 0, i = 0; i < loop->num_nodes; i++)
        {
  	basic_block bb = bbs[i];
  
  	for (bsi = gsi_start_phis (bb); !gsi_end_p (bsi); gsi_next (&bsi))
! 	  if (!virtual_operand_p (gimple_phi_result (gsi_stmt (bsi)))
! 	      && !bitmap_bit_p (partition->stmts, x++))
! 	    reset_debug_uses (gsi_stmt (bsi));
  
  	for (bsi = gsi_start_bb (bb); !gsi_end_p (bsi); gsi_next (&bsi))
  	  {
  	    gimple stmt = gsi_stmt (bsi);
  	    if (gimple_code (stmt) != GIMPLE_LABEL
  		&& !is_gimple_debug (stmt)
! 		&& !bitmap_bit_p (partition->stmts, x++))
  	      reset_debug_uses (stmt);
  	  }
        }
  
!   for (x = 0, i = 0; i < loop->num_nodes; i++)
      {
        basic_block bb = bbs[i];
  
        for (bsi = gsi_start_phis (bb); !gsi_end_p (bsi);)
! 	if (!virtual_operand_p (gimple_phi_result (gsi_stmt (bsi)))
! 	    && !bitmap_bit_p (partition->stmts, x++))
! 	  {
! 	    gimple phi = gsi_stmt (bsi);
! 	    if (virtual_operand_p (gimple_phi_result (phi)))
! 	      mark_virtual_phi_result_for_renaming (phi);
  	    remove_phi_node (&bsi, true);
! 	  }
! 	else
! 	  gsi_next (&bsi);
  
        for (bsi = gsi_start_bb (bb); !gsi_end_p (bsi);)
  	{
  	  gimple stmt = gsi_stmt (bsi);
  	  if (gimple_code (stmt) != GIMPLE_LABEL
  	      && !is_gimple_debug (stmt)
! 	      && !bitmap_bit_p (partition->stmts, x++))
  	    {
  	      unlink_stmt_vdef (stmt);
  	      gsi_remove (&bsi, true);
--- 652,703 ----
        create_bb_after_loop (loop);
      }
  
!   /* Remove stmts not in the PARTITION bitmap.  */
    bbs = get_loop_body_in_dom_order (loop);
  
    if (MAY_HAVE_DEBUG_STMTS)
!     for (i = 0; i < loop->num_nodes; i++)
        {
  	basic_block bb = bbs[i];
  
  	for (bsi = gsi_start_phis (bb); !gsi_end_p (bsi); gsi_next (&bsi))
! 	  {
! 	    gimple phi = gsi_stmt (bsi);
! 	    if (!virtual_operand_p (gimple_phi_result (phi))
! 		&& !bitmap_bit_p (partition->stmts, gimple_uid (phi)))
! 	      reset_debug_uses (phi);
! 	  }
  
  	for (bsi = gsi_start_bb (bb); !gsi_end_p (bsi); gsi_next (&bsi))
  	  {
  	    gimple stmt = gsi_stmt (bsi);
  	    if (gimple_code (stmt) != GIMPLE_LABEL
  		&& !is_gimple_debug (stmt)
! 		&& !bitmap_bit_p (partition->stmts, gimple_uid (stmt)))
  	      reset_debug_uses (stmt);
  	  }
        }
  
!   for (i = 0; i < loop->num_nodes; i++)
      {
        basic_block bb = bbs[i];
  
        for (bsi = gsi_start_phis (bb); !gsi_end_p (bsi);)
! 	{
! 	  gimple phi = gsi_stmt (bsi);
! 	  if (!virtual_operand_p (gimple_phi_result (phi))
! 	      && !bitmap_bit_p (partition->stmts, gimple_uid (phi)))
  	    remove_phi_node (&bsi, true);
! 	  else
! 	    gsi_next (&bsi);
! 	}
  
        for (bsi = gsi_start_bb (bb); !gsi_end_p (bsi);)
  	{
  	  gimple stmt = gsi_stmt (bsi);
  	  if (gimple_code (stmt) != GIMPLE_LABEL
  	      && !is_gimple_debug (stmt)
! 	      && !bitmap_bit_p (partition->stmts, gimple_uid (stmt)))
  	    {
  	      unlink_stmt_vdef (stmt);
  	      gsi_remove (&bsi, true);
*************** similar_memory_accesses (struct graph *r
*** 1372,1387 ****
  
  static void
  rdg_build_partitions (struct graph *rdg,
! 		      vec<int> starting_vertices,
  		      vec<partition_t> *partitions)
  {
    bitmap processed = BITMAP_ALLOC (NULL);
!   int i, v;
    partition_t partition = partition_alloc (NULL, NULL);
  
!   FOR_EACH_VEC_ELT (starting_vertices, i, v)
      {
        partition_t np;
  
        if (bitmap_bit_p (processed, v))
  	continue;
--- 1318,1339 ----
  
  static void
  rdg_build_partitions (struct graph *rdg,
! 		      vec<gimple> starting_stmts,
  		      vec<partition_t> *partitions)
  {
    bitmap processed = BITMAP_ALLOC (NULL);
!   int i;
!   gimple stmt;
    partition_t partition = partition_alloc (NULL, NULL);
  
!   FOR_EACH_VEC_ELT (starting_stmts, i, stmt)
      {
        partition_t np;
+       int v = rdg_vertex_for_stmt (rdg, stmt);
+ 
+       if (dump_file && (dump_flags & TDF_DETAILS))
+ 	fprintf (dump_file,
+ 		 "ldist asked to generate code for vertex %d\n", v);
  
        if (bitmap_bit_p (processed, v))
  	continue;
*************** partition_contains_all_rw (struct graph
*** 1504,1523 ****
    return false;
  }
  
! /* Generate code from STARTING_VERTICES in RDG.  Returns the number of
!    distributed loops.  */
  
  static int
! ldist_gen (struct loop *loop, struct graph *rdg,
! 	   vec<int> starting_vertices)
  {
!   int i, nbp;
    vec<partition_t> partitions;
-   partitions.create (3);
    partition_t partition;
    bool any_builtin;
  
!   rdg_build_partitions (rdg, starting_vertices, &partitions);
  
    any_builtin = false;
    FOR_EACH_VEC_ELT (partitions, i, partition)
--- 1456,1501 ----
    return false;
  }
  
! 
! /* Distributes the code from LOOP in such a way that producer
!    statements are placed before consumer statements.  Tries to separate
!    only the statements from STMTS into separate loops.
!    Returns the number of distributed loops.  */
  
  static int
! distribute_loop (struct loop *loop, vec<gimple> stmts)
  {
!   struct graph *rdg;
!   vec<loop_p> loop_nest;
    vec<partition_t> partitions;
    partition_t partition;
    bool any_builtin;
+   int i, nbp;
+ 
+   loop_nest.create (3);
+   if (!find_loop_nest (loop, &loop_nest))
+     {
+       loop_nest.release ();
+       return 0;
+     }
+ 
+   rdg = build_rdg (loop_nest);
+   if (!rdg)
+     {
+       if (dump_file && (dump_flags & TDF_DETAILS))
+ 	fprintf (dump_file,
+ 		 "Loop %d not distributed: failed to build the RDG.\n",
+ 		 loop->num);
+ 
+       loop_nest.release ();
+       return 0;
+     }
+ 
+   if (dump_file && (dump_flags & TDF_DETAILS))
+     dump_rdg (dump_file, rdg);
  
!   partitions.create (3);
!   rdg_build_partitions (rdg, stmts, &partitions);
  
    any_builtin = false;
    FOR_EACH_VEC_ELT (partitions, i, partition)
*************** ldist_gen (struct loop *loop, struct gra
*** 1637,1706 ****
  
    FOR_EACH_VEC_ELT (partitions, i, partition)
      partition_free (partition);
- 
    partitions.release ();
-   return nbp;
- }
- 
- /* Distributes the code from LOOP in such a way that producer
-    statements are placed before consumer statements.  When STMTS is
-    NULL, performs the maximal distribution, if STMTS is not NULL,
-    tries to separate only these statements from the LOOP's body.
-    Returns the number of distributed loops.  */
- 
- static int
- distribute_loop (struct loop *loop, vec<gimple> stmts)
- {
-   int res = 0;
-   struct graph *rdg;
-   gimple s;
-   unsigned i;
-   vec<int> vertices;
-   vec<loop_p> loop_nest;
  
-   loop_nest.create (3);
-   if (!find_loop_nest (loop, &loop_nest))
-     {
-       loop_nest.release ();
-       return 0;
-     }
- 
-   rdg = build_rdg (loop_nest);
-   if (!rdg)
-     {
-       if (dump_file && (dump_flags & TDF_DETAILS))
- 	fprintf (dump_file,
- 		 "Loop %d not distributed: failed to build the RDG.\n",
- 		 loop->num);
- 
-       loop_nest.release ();
-       return res;
-     }
- 
-   vertices.create (3);
- 
-   if (dump_file && (dump_flags & TDF_DETAILS))
-     dump_rdg (dump_file, rdg);
- 
-   FOR_EACH_VEC_ELT (stmts, i, s)
-     {
-       int v = rdg_vertex_for_stmt (rdg, s);
- 
-       if (v >= 0)
- 	{
- 	  vertices.safe_push (v);
- 
- 	  if (dump_file && (dump_flags & TDF_DETAILS))
- 	    fprintf (dump_file,
- 		     "ldist asked to generate code for vertex %d\n", v);
- 	}
-     }
- 
-   res = ldist_gen (loop, rdg, vertices);
-   vertices.release ();
    free_rdg (rdg);
    loop_nest.release ();
!   return res;
  }
  
  /* Distribute all loops in the current function.  */
--- 1615,1625 ----
  
    FOR_EACH_VEC_ELT (partitions, i, partition)
      partition_free (partition);
    partitions.release ();
  
    free_rdg (rdg);
    loop_nest.release ();
!   return nbp;
  }
  
  /* Distribute all loops in the current function.  */


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]