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] cse.c: Speed up delete_trivially_dead_insns.


Hi,

Attached is a patch to speed up delete_trivially_dead_insns by not
iterating.

On mainline, we do a lot of work on constant propagation, DCE, and DOM
among other things, so delete_trivially_dead_insns does not have as
many opportunities to remove insns.  Here are some numbers obtained
while compiling cc1-i files.

version  2 iter 3 iter  insns
-----------------------------
3.4.2     14639     67 246955
mainline  10906      0  82722

"2 iter" is the number of times d_t_d_i had two iterations.  "3 iter"
is similarly defined.  "insns" is the number of insns deleted by
d_t_d_i.  Note that d_t_d_i never iterates 3 times or more on mainline
and that it never iterates 4 iterations or more on 3.4.2 during the
test above.

The patch simply drops the idea of iterating until we reach a fixed
point.

Here is a timing in seconds for ./cc1 -quiet -O2 -o /dev/null.

            original patched   diff%
------------------------------------
c-common.i    18.591  18.535 -0.301%
combine.i     17.668  17.651 -0.096%
fold-const.i  38.647  38.565 -0.212%
reload.i      13.658  13.599 -0.431%
reload1.i     14.425  14.412 -0.090%
cc1-i files  215.031 214.857 -0.080%

cc1-i files were compiled only once.

As a remark, note that we have to have something like the following
insn stream in order to have three or more iterations.

A = B + 3;
  :
  :
insns that don't use A
  :
  :
B = C * 2;

In the first iteration, the assignment to A is removed because there
is no use of A.  In the second iteration, the assignment to B is
removed because there is no use of B.  Note that "three or more
iterations" require this situation to be present at RTL level.  Tree
optimizations along with the property that most code flows downward
except back edges makes it rather difficult to come up with this.

Tested on i686-pc-linux-gnu.  OK to apply?

Kazu Hirata

2005-01-31  Kazu Hirata  <kazu@cs.umass.edu>

	* cse.c (delete_trivially_dead_insn): Don't iterate.

Index: cse.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/cse.c,v
retrieving revision 1.336
diff -c -d -p -r1.336 cse.c
*** cse.c	29 Jan 2005 12:08:04 -0000	1.336
--- cse.c	31 Jan 2005 03:25:17 -0000
*************** delete_trivially_dead_insns (rtx insns, 
*** 7268,7274 ****
    int *counts;
    rtx insn, prev;
    int in_libcall = 0, dead_libcall = 0;
!   int ndead = 0, nlastdead, niterations = 0;
  
    timevar_push (TV_DELETE_TRIVIALLY_DEAD);
    /* First count the number of times each register is used.  */
--- 7268,7274 ----
    int *counts;
    rtx insn, prev;
    int in_libcall = 0, dead_libcall = 0;
!   int ndead = 0;
  
    timevar_push (TV_DELETE_TRIVIALLY_DEAD);
    /* First count the number of times each register is used.  */
*************** delete_trivially_dead_insns (rtx insns, 
*** 7276,7340 ****
    for (insn = next_real_insn (insns); insn; insn = next_real_insn (insn))
      count_reg_usage (insn, counts, 1);
  
!   do
!     {
!       nlastdead = ndead;
!       niterations++;
!       /* Go from the last insn to the first and delete insns that only set unused
! 	 registers or copy a register to itself.  As we delete an insn, remove
! 	 usage counts for registers it uses.
  
! 	 The first jump optimization pass may leave a real insn as the last
! 	 insn in the function.   We must not skip that insn or we may end
! 	 up deleting code that is not really dead.  */
!       insn = get_last_insn ();
!       if (! INSN_P (insn))
! 	insn = prev_real_insn (insn);
  
!       for (; insn; insn = prev)
! 	{
! 	  int live_insn = 0;
  
! 	  prev = prev_real_insn (insn);
  
! 	  /* Don't delete any insns that are part of a libcall block unless
! 	     we can delete the whole libcall block.
  
! 	     Flow or loop might get confused if we did that.  Remember
! 	     that we are scanning backwards.  */
! 	  if (find_reg_note (insn, REG_RETVAL, NULL_RTX))
! 	    {
! 	      in_libcall = 1;
! 	      live_insn = 1;
! 	      dead_libcall = dead_libcall_p (insn, counts);
! 	    }
! 	  else if (in_libcall)
! 	    live_insn = ! dead_libcall;
! 	  else
! 	    live_insn = insn_live_p (insn, counts);
  
! 	  /* If this is a dead insn, delete it and show registers in it aren't
! 	     being used.  */
  
! 	  if (! live_insn)
! 	    {
! 	      count_reg_usage (insn, counts, -1);
! 	      delete_insn_and_edges (insn);
! 	      ndead++;
! 	    }
  
! 	  if (find_reg_note (insn, REG_LIBCALL, NULL_RTX))
! 	    {
! 	      in_libcall = 0;
! 	      dead_libcall = 0;
! 	    }
  	}
      }
-   while (ndead != nlastdead);
  
    if (dump_file && ndead)
!     fprintf (dump_file, "Deleted %i trivially dead insns; %i iterations\n",
! 	     ndead, niterations);
    /* Clean up.  */
    free (counts);
    timevar_pop (TV_DELETE_TRIVIALLY_DEAD);
--- 7276,7334 ----
    for (insn = next_real_insn (insns); insn; insn = next_real_insn (insn))
      count_reg_usage (insn, counts, 1);
  
!   /* Go from the last insn to the first and delete insns that only set unused
!      registers or copy a register to itself.  As we delete an insn, remove
!      usage counts for registers it uses.
  
!      The first jump optimization pass may leave a real insn as the last
!      insn in the function.   We must not skip that insn or we may end
!      up deleting code that is not really dead.  */
!   insn = get_last_insn ();
!   if (! INSN_P (insn))
!     insn = prev_real_insn (insn);
  
!   for (; insn; insn = prev)
!     {
!       int live_insn = 0;
  
!       prev = prev_real_insn (insn);
  
!       /* Don't delete any insns that are part of a libcall block unless
! 	 we can delete the whole libcall block.
  
! 	 Flow or loop might get confused if we did that.  Remember
! 	 that we are scanning backwards.  */
!       if (find_reg_note (insn, REG_RETVAL, NULL_RTX))
! 	{
! 	  in_libcall = 1;
! 	  live_insn = 1;
! 	  dead_libcall = dead_libcall_p (insn, counts);
! 	}
!       else if (in_libcall)
! 	live_insn = ! dead_libcall;
!       else
! 	live_insn = insn_live_p (insn, counts);
  
!       /* If this is a dead insn, delete it and show registers in it aren't
! 	 being used.  */
  
!       if (! live_insn)
! 	{
! 	  count_reg_usage (insn, counts, -1);
! 	  delete_insn_and_edges (insn);
! 	  ndead++;
! 	}
  
!       if (find_reg_note (insn, REG_LIBCALL, NULL_RTX))
! 	{
! 	  in_libcall = 0;
! 	  dead_libcall = 0;
  	}
      }
  
    if (dump_file && ndead)
!     fprintf (dump_file, "Deleted %i trivially dead insns\n",
! 	     ndead);
    /* Clean up.  */
    free (counts);
    timevar_pop (TV_DELETE_TRIVIALLY_DEAD);


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