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] Speed up cleanup_tree_cfg() - Part 2


Hi,

Attached is a patch to further speed up cleanup_tree_cfg().

Consider the while loop in cleanup_tree_cfg().

  while (something_changed)
    {
      something_changed = delete_unreachable_blocks ();
      something_changed |= thread_jumps ();
      retval |= something_changed;
    }

Note that if delete_unreachable_blocks() changes something, but
thread_jumps() does not, we are effectively calling
delete_unreachable_blocks() twice in a row.  Since
delete_unreachable_blocks() removes all unreachable blocks, the second
call to delete_unreachable_blocks() does not change anything.

The patch avoids this redundant computation by

1) rotating the loop,

2) pulling one call to delete_unreachable_blocks() before the loop
   (because thread_jumps() assumes that all blocks are reachable), and

3) making the in-loop call to delete_unreachable_blocks() conditional
   - only when thread_jumps() does something.

Here is the timing for 10 runs of "cc1 -O2 -o /dev/null fold-const.i".

      original          patched                patched*
real:  183.523   183.281 (0.131% down)   182.731 (0.431% down)
user:  180.742   180.629 (0.052% down)   180.362 (0.200% down)

ctc:   869       869                     869
ccf:  1152      1152                    1152
dub:  1246      1397    (12.118% up)    1114    (10.593% down)
tj:   1246      1114    (10.593% down)  1114    (10.593% down)

ctc: the number of calls to cleanup_tree_cfg
ccf: the number of calls to cleanup_control_flow from ctc
dub: the number of calls to delete_unreachable_blocks from ctc
tj:  the number of calls to thread_jumps from ctc

"patched*" is the patched GCC without the following

  gcc_assert (!delete_unreachable_blocks ());

I am again wondering if we actually need the new gcc_assert().  I'll
leave it up to you to decide whether we should keep it.  I sort of do
not want to because the number of calls to delete_unreachable_blocks()
goes up with this patch if we enable checking, and it's trivial to
show that the new gcc_assert will not trigger.  In any case, the
running time does not go up.

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

p.s.
There is still room left in speeding up cleanup_tree_cfg(), but I'll
address that in subsequent patches.

Kazu Hirata

2004-10-01  Kazu Hirata  <kazu@cs.umass.edu>

	* tree-cfg.c (cleanup_tree_cfg): Speed up by calling
	delete_unrechable_blocks() only when necessary.

Index: tree-cfg.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-cfg.c,v
retrieving revision 2.61
diff -c -r2.61 tree-cfg.c
*** tree-cfg.c	1 Oct 2004 14:51:25 -0000	2.61
--- tree-cfg.c	1 Oct 2004 15:20:23 -0000
***************
*** 718,736 ****
    timevar_push (TV_TREE_CLEANUP_CFG);
  
    retval = cleanup_control_flow ();
  
!   /* These two transformations can cascade, so we iterate on them until
!      nothing changes.  */
    while (something_changed)
      {
!       something_changed = delete_unreachable_blocks ();
!       something_changed |= thread_jumps ();
        retval |= something_changed;
      }
  
  #ifdef ENABLE_CHECKING
    if (retval)
!     gcc_assert (!cleanup_control_flow ());
  #endif
  
    /* Merging the blocks creates no new opportunities for the other
--- 718,746 ----
    timevar_push (TV_TREE_CLEANUP_CFG);
  
    retval = cleanup_control_flow ();
+   retval |= delete_unreachable_blocks ();
  
!   /* thread_jumps() sometimes leaves further transformation
!      opportunities for itself, so iterate on it until nothing
!      changes.  */
    while (something_changed)
      {
!       something_changed = thread_jumps ();
! 
!       /* delete_unreachable_blocks() does its job only when
! 	 thread_jumps() produces more unreachable blocks.  */
!       if (something_changed)
! 	delete_unreachable_blocks ();
! 
        retval |= something_changed;
      }
  
  #ifdef ENABLE_CHECKING
    if (retval)
!     {
!       gcc_assert (!cleanup_control_flow ());
!       gcc_assert (!delete_unreachable_blocks ());
!     }
  #endif
  
    /* Merging the blocks creates no new opportunities for the other


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