smarter and faster try_forward_edges

[Jan Hubicka <jh at suse dot cz>]

Hi,
I've conveienced myself that I will need the structures on AUX
fields anyway to implement jump threading effectivly, so this
patch adds the two flags I needed in first part - forwarder_block
and loop_block.

Forwarder_block is merely used to avoid re-calling forwarder_block_p
to each block many times, while loop_block is used to simplify
infinite loops as mentioned in my last email.

Regtested/bootstrapped i586
Honza

Fri Jun 29 14:55:09 CEST 2001  Jan Hubicka  <jh@suse.cz>

	* flow.c (expunge_block): Set AUX to NULL.
	(struct block_info): New.
	(BLOCK_INFO): New macro.
	(set_basic_block_flags): New static function.
	(try_simplify_condjump): Use BLOCK_INFO.
	(try_forward_edges): Use BLOCK_INFO; detect infinite
	loop and drop marker; fix updating of frequency;
	always examine all edges.
	(try_optimize_cfg): Dump flow info before optimizing;
	allocate BLOCK_INFO; call set_basic_block_flags;
	keep BLOCK_INFO up to date; clear aux fields afterwards.

Index: flow.c
===================================================================
RCS file: /cvs/gcc/egcs/gcc/flow.c,v
retrieving revision 1.410
diff -c -3 -p -r1.410 flow.c
*** flow.c	2001/06/29 03:30:17	1.410
--- flow.c	2001/06/29 12:44:48
*************** static bool can_fallthru		PARAMS ((basic
*** 387,392 ****
--- 389,395 ----
  static bool try_redirect_by_replacing_jump PARAMS ((edge, basic_block));
  static bool try_simplify_condjump	PARAMS ((basic_block));
  static bool try_forward_edges		PARAMS ((basic_block));
+ static void set_basic_block_flags	PARAMS ((void));
  static void tidy_fallthru_edges		PARAMS ((void));
  static int verify_wide_reg_1		PARAMS ((rtx *, void *));
  static void verify_wide_reg		PARAMS ((int, rtx, rtx));
*************** expunge_block (b)
*** 2450,2455 ****
--- 2474,2480 ----
        BASIC_BLOCK (i) = x;
        x->index = i;
      }
+   b->aux = NULL;
  
    basic_block_info->num_elements--;
    n_basic_blocks--;
*************** merge_blocks (e, b, c)
*** 2841,2846 ****
--- 2866,2881 ----
      }
  }
  
+ /* Information hold about basic block in the CFG optimizing pass.  */
+ struct block_info
+ {
+   /* Set in case block just forwards CFG to other direction.  */
+   unsigned forwarder_block : 1;
+   /* Set in case block is inside loop constructed by forward blocks.  */
+   unsigned loop_block : 1;
+ };
+ #define BLOCK_INFO(bb) ((struct block_info *)(bb)->aux)
+ 
  /* Simplify conditional jump around an jump.  
     Return nonzero in case optimization matched.  */
  
*************** try_simplify_condjump (src)
*** 2860,2866 ****
    /* Following block must be simple forwarder block with single
       entry and must not be last in the stream.  */
    next_block = fallthru->dest;
!   if (!forwarder_block_p (next_block)
        || next_block->pred->pred_next
        || next_block->index == n_basic_blocks - 1)
      return false;
--- 2895,2902 ----
    /* Following block must be simple forwarder block with single
       entry and must not be last in the stream.  */
    next_block = fallthru->dest;
!   if (next_block == EXIT_BLOCK_PTR
!       || !BLOCK_INFO (next_block)->forwarder_block
        || next_block->pred->pred_next
        || next_block->index == n_basic_blocks - 1)
      return false;
*************** try_forward_edges (b)
*** 2902,2952 ****
       basic_block b;
  {
    bool changed = 0;
!   edge e;
!   for (e = b->succ; e; e = e->succ_next)
      {
        basic_block target = e->dest, first = e->dest;
        int counter = 0;
  
        /* Look for the real destination of jump.
           Avoid inifinite loop in the infinite empty loop by counting
           up to n_basic_blocks.  */
!       while (forwarder_block_p (target)
  	     && target->succ->dest != EXIT_BLOCK_PTR
  	     && counter < n_basic_blocks)
  	{
  	  /* Bypass trivial infinite loops.  */
! 	  if (target == target->succ->dest)
  	    counter = n_basic_blocks;
- 	  target = target->succ->dest, counter++;
  	}
  
!       if (target != first && counter < n_basic_blocks
! 	  && redirect_edge_and_branch (e, target))
! 	{
! 	  while (first != target)
  	    {
! 	      first->count -= e->count;
! 	      first->succ->count -= e->count;
! 	      first->frequency -= ((e->probability * b->frequency
! 				    + REG_BR_PROB_BASE / 2)
! 				   / REG_BR_PROB_BASE);
! 	      first = first->succ->dest;
  	    }
! 	  /* We've possibly removed the edge.  */
! 	  changed = 1;
! 	  e = b->succ;
! 	}
!       else if (rtl_dump_file && counter == n_basic_blocks)
! 	fprintf (rtl_dump_file, "Infinite loop in BB %i.\n", target->index);
!       else if (rtl_dump_file && first != target)
! 	fprintf (rtl_dump_file,
! 		 "Forwarding edge %i->%i to %i failed.\n", b->index,
! 		 e->dest->index, target->index);
      }
    return changed;
  }
  
  /* Do simple CFG optimizations - basic block merging, simplifying of jump
     instructions etc.
  
--- 2937,3020 ----
       basic_block b;
  {
    bool changed = 0;
!   edge e, next;
!   for (e = b->succ; e; e = next)
      {
        basic_block target = e->dest, first = e->dest;
        int counter = 0;
  
+       next = e->succ_next;
+ 
+       if (target == EXIT_BLOCK_PTR)
+ 	continue;
+ 
        /* Look for the real destination of jump.
           Avoid inifinite loop in the infinite empty loop by counting
           up to n_basic_blocks.  */
!       while (BLOCK_INFO (target)->forwarder_block
! 	     && !BLOCK_INFO (target)->loop_block
  	     && target->succ->dest != EXIT_BLOCK_PTR
  	     && counter < n_basic_blocks)
  	{
+ 	  target = target->succ->dest, counter++;
  	  /* Bypass trivial infinite loops.  */
! 	  if (target->succ && target == target->succ->dest)
  	    counter = n_basic_blocks;
  	}
  
!       /* Once the infinite loop is detected, tag it wita loop_block flag.
!          All edges then will be redirected to this block causing it to be
!          single jump to itself.  */
!       if (counter == n_basic_blocks)
! 	{
! 	  if (rtl_dump_file)
! 	    fprintf (rtl_dump_file, "Infinite loop in BB %i.\n", target->index);
! 	  BLOCK_INFO (target)->loop_block = 1;
! 	}
! 
!       if (target != first)
! 	{
! 	  gcov_type count;
! 	  int frequency;
! 
! 	  /* We may remove the edge.  */
! 	  count = e->count;
! 	  frequency = ((b->frequency * e->probability + REG_BR_PROB_BASE / 2)
! 		       / REG_BR_PROB_BASE);
! 	  if (redirect_edge_and_branch (e, target))
  	    {
! 	      while (first != target)
! 		{
! 		  first->count -= count;
! 		  first->succ->count -= count;
! 		  first->frequency -= frequency;
! 		  first = first->succ->dest;
! 		}
! 	      /* We've possibly removed the edge.  */
! 	      changed = 1;
! 	      next = b->succ;
  	    }
! 	  else if (rtl_dump_file)
! 	    fprintf (rtl_dump_file,
! 		     "Forwarding edge %i->%i to %i failed.\n", b->index,
! 		     e->dest->index, target->index);
! 	}
      }
+   if (changed)
+     BLOCK_INFO (b)->forwarder_block = forwarder_block_p (b);
    return changed;
  }
  
+ /* Compute flags we maitain about each basic block.  */
+ static void
+ set_basic_block_flags ()
+ {
+   int i;
+   for (i = 0; i < n_basic_blocks; i++)
+     BLOCK_INFO (BASIC_BLOCK (i))->forwarder_block =
+       forwarder_block_p (BASIC_BLOCK (i));
+ }
+ 
  /* Do simple CFG optimizations - basic block merging, simplifying of jump
     instructions etc.
  
*************** try_optimize_cfg ()
*** 2958,2964 ****
--- 3026,3041 ----
    int i;
    bool changed_overall = 0;
    bool changed;
+   struct block_info *infos;
  
+   if (rtl_dump_file)
+     dump_flow_info (rtl_dump_file);
+ 
+   infos = xcalloc (sizeof (struct block_info), n_basic_blocks);
+   for (i = 0; i < n_basic_blocks; i ++)
+     BLOCK_INFO (BASIC_BLOCK (i)) = infos + i;
+   set_basic_block_flags ();
+ 
    /* 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 ()
*** 3007,3013 ****
  		 /* If the jump insn has side effects, we can't kill the edge.  */
  		 && (GET_CODE (b->end) != JUMP_INSN
  		     || onlyjump_p (b->end)) && merge_blocks (s, b, c))
! 	    changed_here = 1;
  
  	  if (try_simplify_condjump (b))
  	    changed_here = 1;
--- 3085,3094 ----
  		 /* If the jump insn has side effects, we can't kill the edge.  */
  		 && (GET_CODE (b->end) != JUMP_INSN
  		     || onlyjump_p (b->end)) && merge_blocks (s, b, c))
! 	    {
! 	      BLOCK_INFO (b)->forwarder_block = forwarder_block_p (b);
! 	      changed_here = 1;
! 	    }
  
  	  if (try_simplify_condjump (b))
  	    changed_here = 1;
*************** try_optimize_cfg ()
*** 3025,3031 ****
  	      && GET_CODE (b->end) == JUMP_INSN
  	      && b->succ->dest != EXIT_BLOCK_PTR
  	      && redirect_edge_and_branch (b->succ, b->succ->dest))
! 	    changed_here = 1;
  
  	  if (try_forward_edges (b))
  	    changed_here = 1;
--- 3106,3115 ----
  	      && GET_CODE (b->end) == JUMP_INSN
  	      && b->succ->dest != EXIT_BLOCK_PTR
  	      && redirect_edge_and_branch (b->succ, b->succ->dest))
! 	    {
! 	      BLOCK_INFO (b)->forwarder_block = forwarder_block_p (b);
! 	      changed_here = 1;
! 	    }
  
  	  if (try_forward_edges (b))
  	    changed_here = 1;
*************** try_optimize_cfg ()
*** 3045,3050 ****
--- 3136,3144 ----
    if (changed)
      verify_flow_info ();
  #endif
+   free (infos);
+   for (i = 0; i < n_basic_blocks; i ++)
+     BLOCK_INFO (BASIC_BLOCK (i)) = NULL;
    return changed_overall;
  }