[patch] tree-cfg.c: Speed up tree_forwarder_block_p.

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

Hi,

Attached is a patch to speed up tree_forwarder_block_p.

tree_forwarder_block_p performs a series of tests to see if a given
basic block qualifies as a forwarder block.  Some tests trigger more
often than others.

It turns out that tree_forwarder_block_p checks for corner cases
before common cases.  Specifically, it checks

1. whether BB is a predecessor of EXIT_BLOCK_PTR,
2. whether BB's outgoing edge is abnormal
3. whether BB is ENTRY_BLOCK_PTR, and
4. whether BB is a successor of ENTRY_BLOCK_PTR

before checking whether BB has any PHI nodes.  Obviously, real-world
programs contain more basic blocks with PHI nodes than those that fit
in the corner cases above.

The patch reorders checks so that the PHI node check is performed
before the four checks above.

Note that as a good side effect, check No.1 is often subsumed by the
PHI node check because we now have exactly one return statement per
function, and the basic block containing the return statement often
has a PHI node if the function return a value.  One stone kills two
birds!

The patch turns check No.3 into gcc_assert wrapped by ENABLE_CHECKING
because we no longer call tree_forwarder_block_p with ENTRY_BLOCK_PTR.
thread_jumps, the only user of tree_forwarder_block_p, uses
FOR_EACH_BB, which skips ENTRY_BLOCK_PTR.

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

Kazu Hirata

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

	* tree-cfg.c (tree_forwarder_block_p): Reorder checks so that
	common cases will be caught earlier than others.

Index: tree-cfg.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-cfg.c,v
retrieving revision 2.71
diff -c -r2.71 tree-cfg.c
*** tree-cfg.c	7 Oct 2004 23:31:04 -0000	2.71
--- tree-cfg.c	8 Oct 2004 02:58:58 -0000
***************
*** 3694,3700 ****
  
  /* Return true if basic block BB does nothing except pass control
     flow to another block and that we can safely insert a label at
!    the start of the successor block.  */
  
  static bool
  tree_forwarder_block_p (basic_block bb)
--- 3694,3703 ----
  
  /* Return true if basic block BB does nothing except pass control
     flow to another block and that we can safely insert a label at
!    the start of the successor block.
! 
!    As a precondition, we require that BB be not equal to
!    ENTRY_BLOCK_PTR.  */
  
  static bool
  tree_forwarder_block_p (basic_block bb)
***************
*** 3708,3724 ****
    if (! bb_ann (bb)->forwardable)
      return false;
  
!   /* BB must have a single outgoing normal edge.  Otherwise it can not be
!      a forwarder block.  */
    if (EDGE_COUNT (bb->succs) != 1
        || EDGE_SUCC (bb, 0)->dest == EXIT_BLOCK_PTR
!       || (EDGE_SUCC (bb, 0)->flags & EDGE_ABNORMAL)
!       || bb == ENTRY_BLOCK_PTR)
      {
        bb_ann (bb)->forwardable = 0;
        return false; 
      }
  
    /* Successors of the entry block are not forwarders.  */
    FOR_EACH_EDGE (e, ei, ENTRY_BLOCK_PTR->succs)
      if (e->dest == bb)
--- 3711,3735 ----
    if (! bb_ann (bb)->forwardable)
      return false;
  
!   /* BB must have a single outgoing edge.  */
    if (EDGE_COUNT (bb->succs) != 1
+       /* BB can not have any PHI nodes.  This could potentially be
+ 	 relaxed early in compilation if we re-rewrote the variables
+ 	 appearing in any PHI nodes in forwarder blocks.  */
+       || phi_nodes (bb)
+       /* BB may not be a predecessor of EXIT_BLOCK_PTR.  */
        || EDGE_SUCC (bb, 0)->dest == EXIT_BLOCK_PTR
!       /* BB may not have an abnormal outgoing edge.  */
!       || (EDGE_SUCC (bb, 0)->flags & EDGE_ABNORMAL))
      {
        bb_ann (bb)->forwardable = 0;
        return false; 
      }
  
+ #if ENABLE_CHECKING
+   gcc_assert (bb != ENTRY_BLOCK_PTR);
+ #endif
+ 
    /* Successors of the entry block are not forwarders.  */
    FOR_EACH_EDGE (e, ei, ENTRY_BLOCK_PTR->succs)
      if (e->dest == bb)
***************
*** 3727,3741 ****
  	return false;
        }
  
-   /* BB can not have any PHI nodes.  This could potentially be relaxed
-      early in compilation if we re-rewrote the variables appearing in
-      any PHI nodes in forwarder blocks.  */
-   if (phi_nodes (bb))
-     {
-       bb_ann (bb)->forwardable = 0;
-       return false; 
-     }
- 
    /* Now walk through the statements.  We can ignore labels, anything else
       means this is not a forwarder block.  */
    for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
--- 3738,3743 ----