Speed up jump threading

[Jan Hubicka]

Hi,
part of cselib problems I am seeing is that it is used quite extensivly by jump
threading.  The patch reduces number of calls of cselib_init from 17000 to
roughly 9757 on combine.c compilation with no effect on final code by
keeping track of basic blocks that has been modified and avoiding
re-doing the job on basic blocks that didn't.

Bootstrapped/regtested i686-pc-gnu-linux.  OK?

Honza

2004-01-22  Jan Hubicka  <jh@suse.cz>
	* cfgcleanup.c (first_pass): New static variable.
	(try_forward_edges):  Add work limiting check for threading.
	(try_crossjump_bb):  Add work limiting check for crossjumping.
	(try_optimize_cfg):  Maintain first pass variable.
Index: cfgcleanup.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/cfgcleanup.c,v
retrieving revision 1.101
diff -c -3 -p -r1.101 cfgcleanup.c
*** cfgcleanup.c	21 Jan 2004 20:39:52 -0000	1.101
--- cfgcleanup.c	22 Jan 2004 16:31:36 -0000
*************** enum bb_flags
*** 67,72 ****
--- 67,74 ----
  
  #define FORWARDER_BLOCK_P(BB) (BB_FLAGS (BB) & BB_FORWARDER_BLOCK)
  
+ /* Set to true when we are running first pass of try_optimize_cfg loop.  */
+ static bool first_pass;
  static bool try_crossjump_to_edge (int, edge, edge);
  static bool try_crossjump_bb (int, basic_block);
  static bool outgoing_edges_match (int, basic_block, basic_block);
*************** try_forward_edges (int mode, basic_block
*** 423,434 ****
--- 425,438 ----
    bool changed = false;
    edge e, next, *threaded_edges = NULL;
  
+ 
    for (e = b->succ; e; e = next)
      {
        basic_block target, first;
        int counter;
        bool threaded = false;
        int nthreaded_edges = 0;
+       bool may_thread = first_pass | (b->flags & BB_DIRTY);
  
        next = e->succ_next;
  
*************** try_forward_edges (int mode, basic_block
*** 447,452 ****
--- 451,457 ----
  	{
  	  basic_block new_target = NULL;
  	  bool new_target_threaded = false;
+ 	  may_thread |= target->flags & BB_DIRTY;
  
  	  if (FORWARDER_BLOCK_P (target)
  	      && target->succ->dest != EXIT_BLOCK_PTR)
*************** try_forward_edges (int mode, basic_block
*** 459,465 ****
  
  	  /* Allow to thread only over one edge at time to simplify updating
  	     of probabilities.  */
! 	  else if (mode & CLEANUP_THREADING)
  	    {
  	      edge t = thread_jump (mode, e, target);
  	      if (t)
--- 464,470 ----
  
  	  /* Allow to thread only over one edge at time to simplify updating
  	     of probabilities.  */
! 	  else if ((mode & CLEANUP_THREADING) && may_thread)
  	    {
  	      edge t = thread_jump (mode, e, target);
  	      if (t)
*************** try_crossjump_bb (int mode, basic_block 
*** 1573,1578 ****
--- 1578,1590 ----
  	     If there is a match, we'll do it the other way around.  */
  	  if (e == fallthru)
  	    continue;
+ 	  /* If nothing changed since the last attempt, there is nothing
+ 	     we can do.  */
+ 	  if (!first_pass
+ 	      && (!(e->src->flags & BB_DIRTY)
+ 		  && !(fallthru->src->flags & BB_DIRTY)))
+ 	    continue;
+ 
  
  	  if (try_crossjump_to_edge (mode, e, fallthru))
  	    {
*************** try_crossjump_bb (int mode, basic_block 
*** 1615,1620 ****
--- 1627,1639 ----
  	  if (e->src->index > e2->src->index)
  	    continue;
  
+ 	  /* If nothing changed since the last attempt, there is nothing
+ 	     we can do.  */
+ 	  if (!first_pass
+ 	      && (!(e->src->flags & BB_DIRTY)
+ 		  && !(e2->src->flags & BB_DIRTY)))
+ 	    continue;
+ 
  	  if (try_crossjump_to_edge (mode, e, e2))
  	    {
  	      changed = true;
*************** try_optimize_cfg (int mode)
*** 1644,1654 ****
    FOR_EACH_BB (bb)
      update_forwarder_flag (bb);
  
!   if (mode & CLEANUP_UPDATE_LIFE)
      clear_bb_flags ();
  
    if (! (* targetm.cannot_modify_jumps_p) ())
      {
        /* Attempt to merge blocks as made possible by edge removal.  If
  	 a block has only one successor, and the successor has only
  	 one predecessor, they may be combined.  */
--- 1663,1674 ----
    FOR_EACH_BB (bb)
      update_forwarder_flag (bb);
  
!   if (mode & (CLEANUP_UPDATE_LIFE | CLEANUP_CROSSJUMP | CLEANUP_THREADING))
      clear_bb_flags ();
  
    if (! (* targetm.cannot_modify_jumps_p) ())
      {
+       first_pass = true;
        /* Attempt to merge blocks as made possible by edge removal.  If
  	 a block has only one successor, and the successor has only
  	 one predecessor, they may be combined.  */
*************** try_optimize_cfg (int mode)
*** 1824,1829 ****
--- 1844,1850 ----
  #endif
  
  	  changed_overall |= changed;
+ 	  first_pass = false;
  	}
        while (changed);
      }