[patch] Speed up cleanup_tree_cfg() - Part 3

[Kazu Hirata <kazu at cs dot umass dot edu>]

Hi,

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

It turns out that with a minor tweak to thread_jumps(), we can
establish a property that it never leaves unreachable blocks provided
that it starts out with no unreachable blocks.  It's actually easy to
do so.  Without the patch, thread_jumps() removes unreachable blocks
only when the dominator info is valid.  All we have to do is to have
it always remove unreachable blocks as they appear as a result of jump
threading.

The new property in turn allows us to dramatically simplify the while
loop in cleanup_tree_cfg() because thread_jumps() no longer leaves
unreachable blocks.

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

      original          patched
real:  183.359   183.034 (0.177% down)
user:  180.814   180.809 (0.002% down)

ctc:   869       869
ccf:  1152      1152
dub:  1397      1152    (17.537% down)
tj:   1114      1114

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

Note that we have "gcc_assert (!delete_unreachable_blocks())"
immediately after the while loop, so when I tested my patch, the
gcc_assert acted as an evidence (but not a proof) that thread_jumps()
never leaves unreachable blocks.

I tested the attached patch on top of

http://gcc.gnu.org/ml/gcc-patches/2004-10/msg00169.html

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

p.s.
Admittedly, this speed up is very small, but my next patch will remove
the while loop and will bring a bigger speed up, so stay tuned.

Kazu Hirata

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

	* tree-cfg.c (cleanup_tree_cfg): Don't call
	delete_unreachable_blosk() after thread_jumps().
	(thread_jumps): Always remove basic blocks as they become
	unreachable.

diff -u tree-cfg.c tree-cfg.c
*** tree-cfg.c	2 Oct 2004 13:06:20 -0000
--- tree-cfg.c	2 Oct 2004 02:03:34 -0000
***************
*** 723,734 ****
       opportunities for itself, so iterate on it until nothing
       changes.  */
    while (thread_jumps ())
!     {
!       /* delete_unreachable_blocks() does its job only when
! 	 thread_jumps() produces more unreachable blocks.  */
!       delete_unreachable_blocks ();
!       retval = true;
!     }
  
  #ifdef ENABLE_CHECKING
    if (retval)
--- 723,729 ----
       opportunities for itself, so iterate on it until nothing
       changes.  */
    while (thread_jumps ())
!     retval = true;
  
  #ifdef ENABLE_CHECKING
    if (retval)
***************
*** 3969,3990 ****
  		}
  	    }
  
! 	  /* Update the dominators.  */
! 	  if (dom_computed[CDI_DOMINATORS] >= DOM_CONS_OK)
  	    {
! 	      /* Remove the unreachable blocks (observe that if all blocks
! 		 were reachable before, only those in the path we threaded
! 		 over and did not have any predecessor outside of the path
! 		 become unreachable).  */
! 	      for (; old_dest != dest; old_dest = tmp)
! 		{
! 		  tmp = EDGE_SUCC (old_dest, 0)->dest;
  
! 		  if (EDGE_COUNT (old_dest->preds) > 0)
! 		    break;
  
! 		  delete_basic_block (old_dest);
! 		}
  	      /* If the dominator of the destination was in the path, set its
  		 dominator to the start of the redirected edge.  */
  	      if (get_immediate_dominator (CDI_DOMINATORS, old_dest) == NULL)
--- 3964,3986 ----
  		}
  	    }
  
! 	  /* Remove the unreachable blocks (observe that if all blocks
! 	     were reachable before, only those in the path we threaded
! 	     over and did not have any predecessor outside of the path
! 	     become unreachable).  */
! 	  for (; old_dest != dest; old_dest = tmp)
  	    {
! 	      tmp = EDGE_SUCC (old_dest, 0)->dest;
  
! 	      if (EDGE_COUNT (old_dest->preds) > 0)
! 		break;
  
! 	      delete_basic_block (old_dest);
! 	    }
! 
! 	  /* Update the dominators.  */
! 	  if (dom_computed[CDI_DOMINATORS] >= DOM_CONS_OK)
! 	    {
  	      /* If the dominator of the destination was in the path, set its
  		 dominator to the start of the redirected edge.  */
  	      if (get_immediate_dominator (CDI_DOMINATORS, old_dest) == NULL)