[PATCH] Speedup gimple_split_block

[PATCH] Speedup gimple_split_block

[Richard Biener]

This removes the old vestige loop to find a gsi for a stmt (from times
where gsi_for_stmt was O(n)).

PR44563 shows gimple_split_block quite high in the profile (this
patch doesn't fix that) as the tail loop setting BB on all stmts
moved to the new block shows quadratic behavior when inlining
N calls in a basic-block.

Bootstrap and regtest scheduled on x86_64-unknown-linux-gnu.

Richard.

2015-03-10  Richard Biener  <rguenther@suse.de>

	* tree-cfg.c (gimple_split_block): Remove loop finding stmt
	to split on.

Index: gcc/tree-cfg.c
===================================================================
*** gcc/tree-cfg.c	(revision 221277)
--- gcc/tree-cfg.c	(working copy)
*************** gimple_split_block (basic_block bb, void
*** 5697,5722 ****
    FOR_EACH_EDGE (e, ei, new_bb->succs)
      e->src = new_bb;
  
!   if (stmt && gimple_code ((gimple) stmt) == GIMPLE_LABEL)
!     stmt = NULL;
! 
    /* Move everything from GSI to the new basic block.  */
-   for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
-     {
-       act = gsi_stmt (gsi);
-       if (gimple_code (act) == GIMPLE_LABEL)
- 	continue;
- 
-       if (!stmt)
- 	break;
- 
-       if (stmt == act)
- 	{
- 	  gsi_next (&gsi);
- 	  break;
- 	}
-     }
- 
    if (gsi_end_p (gsi))
      return new_bb;
  
--- 5723,5735 ----
    FOR_EACH_EDGE (e, ei, new_bb->succs)
      e->src = new_bb;
  
!   /* Get a stmt iterator pointing to the first stmt to move.  */
!   if (!stmt || gimple_code ((gimple) stmt) == GIMPLE_LABEL)
!     gsi = gsi_after_labels (bb);
!   else
!     gsi = gsi_for_stmt ((gimple) stmt);
!  
    /* Move everything from GSI to the new basic block.  */
    if (gsi_end_p (gsi))
      return new_bb;
  

Re: [PATCH] Speedup gimple_split_block

[Richard Biener]

On Tue, 10 Mar 2015, Richard Biener wrote:

> 
> This removes the old vestige loop to find a gsi for a stmt (from times
> where gsi_for_stmt was O(n)).
> 
> PR44563 shows gimple_split_block quite high in the profile (this
> patch doesn't fix that) as the tail loop setting BB on all stmts
> moved to the new block shows quadratic behavior when inlining
> N calls in a basic-block.
> 
> Bootstrap and regtest scheduled on x86_64-unknown-linux-gnu.

Ok, reveals two errors in my fix and two oddities in omp-low.c - removing
a stmt and then splitting its basic-block after it.

Hopefully the following will finish bootstrap & regtest ok.

Richard.

2015-03-10  Richard Biener  <rguenther@suse.de>

	* tree-cfg.c (gimple_split_block): Remove loop finding stmt
	to split on.
	* omp-low.c (expand_omp_taskreg): Split block before removing
	the stmt.
	(expand_omp_target): Likewise.

Index: gcc/tree-cfg.c
===================================================================
*** gcc/tree-cfg.c	(revision 221324)
--- gcc/tree-cfg.c	(working copy)
*************** gimple_split_block (basic_block bb, void
*** 5683,5689 ****
  {
    gimple_stmt_iterator gsi;
    gimple_stmt_iterator gsi_tgt;
-   gimple act;
    gimple_seq list;
    basic_block new_bb;
    edge e;
--- 5683,5688 ----
*************** gimple_split_block (basic_block bb, void
*** 5697,5722 ****
    FOR_EACH_EDGE (e, ei, new_bb->succs)
      e->src = new_bb;
  
!   if (stmt && gimple_code ((gimple) stmt) == GIMPLE_LABEL)
!     stmt = NULL;
! 
!   /* Move everything from GSI to the new basic block.  */
!   for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
      {
!       act = gsi_stmt (gsi);
!       if (gimple_code (act) == GIMPLE_LABEL)
! 	continue;
! 
!       if (!stmt)
! 	break;
! 
!       if (stmt == act)
! 	{
! 	  gsi_next (&gsi);
! 	  break;
! 	}
      }
! 
    if (gsi_end_p (gsi))
      return new_bb;
  
--- 5696,5711 ----
    FOR_EACH_EDGE (e, ei, new_bb->succs)
      e->src = new_bb;
  
!   /* Get a stmt iterator pointing to the first stmt to move.  */
!   if (!stmt || gimple_code ((gimple) stmt) == GIMPLE_LABEL)
!     gsi = gsi_after_labels (bb);
!   else
      {
!       gsi = gsi_for_stmt ((gimple) stmt);
!       gsi_next (&gsi);
      }
!  
!   /* Move everything from GSI to the new basic block.  */
    if (gsi_end_p (gsi))
      return new_bb;
  
Index: gcc/omp-low.c
===================================================================
*** gcc/omp-low.c	(revision 221324)
--- gcc/omp-low.c	(working copy)
*************** expand_omp_taskreg (struct omp_region *r
*** 5514,5521 ****
        stmt = gsi_stmt (gsi);
        gcc_assert (stmt && (gimple_code (stmt) == GIMPLE_OMP_PARALLEL
  			   || gimple_code (stmt) == GIMPLE_OMP_TASK));
-       gsi_remove (&gsi, true);
        e = split_block (entry_bb, stmt);
        entry_bb = e->dest;
        single_succ_edge (entry_bb)->flags = EDGE_FALLTHRU;
  
--- 5514,5521 ----
        stmt = gsi_stmt (gsi);
        gcc_assert (stmt && (gimple_code (stmt) == GIMPLE_OMP_PARALLEL
  			   || gimple_code (stmt) == GIMPLE_OMP_TASK));
        e = split_block (entry_bb, stmt);
+       gsi_remove (&gsi, true);
        entry_bb = e->dest;
        single_succ_edge (entry_bb)->flags = EDGE_FALLTHRU;
  
*************** expand_omp_target (struct omp_region *re
*** 8889,8896 ****
        stmt = gsi_stmt (gsi);
        gcc_assert (stmt
  		  && gimple_code (stmt) == gimple_code (entry_stmt));
-       gsi_remove (&gsi, true);
        e = split_block (entry_bb, stmt);
        entry_bb = e->dest;
        single_succ_edge (entry_bb)->flags = EDGE_FALLTHRU;
  
--- 8889,8896 ----
        stmt = gsi_stmt (gsi);
        gcc_assert (stmt
  		  && gimple_code (stmt) == gimple_code (entry_stmt));
        e = split_block (entry_bb, stmt);
+       gsi_remove (&gsi, true);
        entry_bb = e->dest;
        single_succ_edge (entry_bb)->flags = EDGE_FALLTHRU;
  

Re: [PATCH] Speedup gimple_split_block

[Richard Biener]

On Tue, 10 Mar 2015, Richard Biener wrote:

> On Tue, 10 Mar 2015, Richard Biener wrote:
> 
> > 
> > This removes the old vestige loop to find a gsi for a stmt (from times
> > where gsi_for_stmt was O(n)).
> > 
> > PR44563 shows gimple_split_block quite high in the profile (this
> > patch doesn't fix that) as the tail loop setting BB on all stmts
> > moved to the new block shows quadratic behavior when inlining
> > N calls in a basic-block.
> > 
> > Bootstrap and regtest scheduled on x86_64-unknown-linux-gnu.
> 
> Ok, reveals two errors in my fix and two oddities in omp-low.c - removing
> a stmt and then splitting its basic-block after it.
> 
> Hopefully the following will finish bootstrap & regtest ok.

Not.  But the following did.

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

Richard.

2015-03-12  Richard Biener  <rguenther@suse.de>

	* tree-cfg.c (gimple_split_block): Remove loop finding stmt
	to split on.
	* omp-low.c (expand_omp_taskreg): Split block before removing
	the stmt.
	(expand_omp_target): Likewise.
	* ubsan.c (ubsan_expand_null_ifn): Adjust stmt if we replaced it.
	* tree-parloops.c (create_call_for_reduction_1): Pass a proper
	stmt to split_block.

Index: gcc/tree-cfg.c
===================================================================
*** gcc/tree-cfg.c	(revision 221324)
--- gcc/tree-cfg.c	(working copy)
*************** gimple_split_block (basic_block bb, void
*** 5683,5689 ****
  {
    gimple_stmt_iterator gsi;
    gimple_stmt_iterator gsi_tgt;
-   gimple act;
    gimple_seq list;
    basic_block new_bb;
    edge e;
--- 5683,5688 ----
*************** gimple_split_block (basic_block bb, void
*** 5697,5722 ****
    FOR_EACH_EDGE (e, ei, new_bb->succs)
      e->src = new_bb;
  
!   if (stmt && gimple_code ((gimple) stmt) == GIMPLE_LABEL)
!     stmt = NULL;
! 
!   /* Move everything from GSI to the new basic block.  */
!   for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
      {
!       act = gsi_stmt (gsi);
!       if (gimple_code (act) == GIMPLE_LABEL)
! 	continue;
! 
!       if (!stmt)
! 	break;
! 
!       if (stmt == act)
! 	{
! 	  gsi_next (&gsi);
! 	  break;
! 	}
      }
! 
    if (gsi_end_p (gsi))
      return new_bb;
  
--- 5696,5711 ----
    FOR_EACH_EDGE (e, ei, new_bb->succs)
      e->src = new_bb;
  
!   /* Get a stmt iterator pointing to the first stmt to move.  */
!   if (!stmt || gimple_code ((gimple) stmt) == GIMPLE_LABEL)
!     gsi = gsi_after_labels (bb);
!   else
      {
!       gsi = gsi_for_stmt ((gimple) stmt);
!       gsi_next (&gsi);
      }
!  
!   /* Move everything from GSI to the new basic block.  */
    if (gsi_end_p (gsi))
      return new_bb;
  
Index: gcc/omp-low.c
===================================================================
*** gcc/omp-low.c	(revision 221324)
--- gcc/omp-low.c	(working copy)
*************** expand_omp_taskreg (struct omp_region *r
*** 5514,5521 ****
        stmt = gsi_stmt (gsi);
        gcc_assert (stmt && (gimple_code (stmt) == GIMPLE_OMP_PARALLEL
  			   || gimple_code (stmt) == GIMPLE_OMP_TASK));
-       gsi_remove (&gsi, true);
        e = split_block (entry_bb, stmt);
        entry_bb = e->dest;
        single_succ_edge (entry_bb)->flags = EDGE_FALLTHRU;
  
--- 5514,5521 ----
        stmt = gsi_stmt (gsi);
        gcc_assert (stmt && (gimple_code (stmt) == GIMPLE_OMP_PARALLEL
  			   || gimple_code (stmt) == GIMPLE_OMP_TASK));
        e = split_block (entry_bb, stmt);
+       gsi_remove (&gsi, true);
        entry_bb = e->dest;
        single_succ_edge (entry_bb)->flags = EDGE_FALLTHRU;
  
*************** expand_omp_target (struct omp_region *re
*** 8889,8896 ****
        stmt = gsi_stmt (gsi);
        gcc_assert (stmt
  		  && gimple_code (stmt) == gimple_code (entry_stmt));
-       gsi_remove (&gsi, true);
        e = split_block (entry_bb, stmt);
        entry_bb = e->dest;
        single_succ_edge (entry_bb)->flags = EDGE_FALLTHRU;
  
--- 8889,8896 ----
        stmt = gsi_stmt (gsi);
        gcc_assert (stmt
  		  && gimple_code (stmt) == gimple_code (entry_stmt));
        e = split_block (entry_bb, stmt);
+       gsi_remove (&gsi, true);
        entry_bb = e->dest;
        single_succ_edge (entry_bb)->flags = EDGE_FALLTHRU;
  
Index: gcc/ubsan.c
===================================================================
*** gcc/ubsan.c	(revision 221324)
--- gcc/ubsan.c	(working copy)
*************** ubsan_expand_null_ifn (gimple_stmt_itera
*** 864,869 ****
--- 864,870 ----
  
        /* Replace the UBSAN_NULL with a GIMPLE_COND stmt.  */
        gsi_replace (&gsi, g, false);
+       stmt = g;
      }
  
    if (check_align)
Index: gcc/tree-parloops.c
===================================================================
*** gcc/tree-parloops.c	(revision 221324)
--- gcc/tree-parloops.c	(working copy)
*************** create_call_for_reduction_1 (reduction_i
*** 1111,1117 ****
    /* Create phi node.  */
    bb = clsn_data->load_bb;
  
!   e = split_block (bb, t);
    new_bb = e->dest;
  
    tmp_load = create_tmp_var (TREE_TYPE (TREE_TYPE (addr)));
--- 1111,1118 ----
    /* Create phi node.  */
    bb = clsn_data->load_bb;
  
!   gsi = gsi_last_bb (bb);
!   e = split_block (bb, gsi_stmt (gsi));
    new_bb = e->dest;
  
    tmp_load = create_tmp_var (TREE_TYPE (TREE_TYPE (addr)));