[PATCH] Last PR44563 fix (from me)

[PATCH] Last PR44563 fix (from me)

[Richard Biener]

The following fixes quadraticness observed in PR44563 related to
basic block splitting and merging (which both are O(n) in the size
of the "tail" due to adjusting stmts BB pointer).  The splitting is induced by
the inliner which processes calls in a basic-block in a non-optimal
order (front-to-back).  The patch changes this to work back-to-front
(minimizing the size of the "tail").  This then runs into a similar
issue with CFG cleanups block merging which works optimal only if
one merges a chain of blocks by iterating on merging the first block
of the chain with the second.  The patch achieves that by not performing
block merging with the successor if the predecessor would merge with
the block.

The whole series improved the PR44563 testcase from (-O1, release 
checking):

 ipa inlining heuristics : 155.14 (12%) usr   0.37 ( 2%) sys 155.31 (12%) 
wall  396289 kB (11%) ggc
 integration             : 958.73 (75%) usr   2.18 (13%) sys 960.89 (74%) 
wall   86527 kB ( 2%) ggc
 tree CFG cleanup        : 116.57 ( 9%) usr   0.30 ( 2%) sys 116.77 ( 9%) 
wall       0 kB ( 0%) ggc
 TOTAL                 :1285.25            17.15          1302.17            
3514948 kB

to

 phase opt and generate  : 193.97 (99%) usr  13.82 (93%) sys 207.75 (99%) 
wall 3311016 kB (94%) ggc
 ipa inlining heuristics : 140.48 (72%) usr   0.44 ( 3%) sys 141.13 (67%) 
wall  396289 kB (11%) ggc
 dominance computation   :   2.99 ( 2%) usr   1.00 ( 7%) sys   3.89 ( 2%) 
wall       0 kB ( 0%) ggc
 integrated RA           :   4.05 ( 2%) usr   0.85 ( 6%) sys   5.26 ( 3%) 
wall 1577496 kB (45%) ggc
 rest of compilation     :   6.53 ( 3%) usr   1.67 (11%) sys   7.91 ( 4%) 
wall  155664 kB ( 4%) ggc
 unaccounted todo        :   3.82 ( 2%) usr   1.07 ( 7%) sys   4.98 ( 2%) 
wall       0 kB ( 0%) ggc
 TOTAL                 : 195.46            14.79           210.23            
3514948 kB

everything <= 1% dropped.

Bootstrapped and tested on x86_64-unknown-linux-gnu, applied to trunk.

Richard.

2015-03-12  Richard Biener  <rguenther@suse.de>

	PR middle-end/44563
	* tree-inline.c (gimple_expand_calls_inline): Walk BB backwards
	to avoid quadratic behavior with inline expansion splitting blocks.
	* tree-cfgcleanup.c (cleanup_tree_cfg_bb): Do not merge block
	with the successor if the predecessor will be merged with it.
	* tree-cfg.c (gimple_can_merge_blocks_p): We can't merge the
	entry block with its successor.

Index: gcc/tree-inline.c
===================================================================
--- gcc/tree-inline.c	(revision 221317)
+++ gcc/tree-inline.c	(working copy)
@@ -4777,18 +4781,19 @@ static bool
 gimple_expand_calls_inline (basic_block bb, copy_body_data *id)
 {
   gimple_stmt_iterator gsi;
+  bool inlined = false;
 
-  for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
+  for (gsi = gsi_last_bb (bb); !gsi_end_p (gsi);)
     {
       gimple stmt = gsi_stmt (gsi);
+      gsi_prev (&gsi);
 
       if (is_gimple_call (stmt)
-	  && !gimple_call_internal_p (stmt)
-	  && expand_call_inline (bb, stmt, id))
-	return true;
+	  && !gimple_call_internal_p (stmt))
+	inlined |= expand_call_inline (bb, stmt, id);
     }
 
-  return false;
+  return inlined;
 }
 
 
Index: gcc/tree-cfgcleanup.c
===================================================================
*** gcc/tree-cfgcleanup.c	(revision 221392)
--- gcc/tree-cfgcleanup.c	(working copy)
*************** cleanup_tree_cfg_bb (basic_block bb)
*** 672,679 ****
    if (single_succ_p (bb)
        && can_merge_blocks_p (bb, single_succ (bb)))
      {
!       merge_blocks (bb, single_succ (bb));
!       return true;
      }
  
    return retval;
--- 650,667 ----
    if (single_succ_p (bb)
        && can_merge_blocks_p (bb, single_succ (bb)))
      {
!       /* If there is a merge opportunity with the predecessor
!          do nothing now but wait until we process the predecessor.
! 	 This happens when we visit BBs in a non-optimal order and
! 	 avoids quadratic behavior with adjusting stmts BB pointer.  */
!       if (single_pred_p (bb)
! 	  && can_merge_blocks_p (single_pred (bb), bb))
! 	;
!       else
! 	{
! 	  merge_blocks (bb, single_succ (bb));
! 	  return true;
! 	}
      }
  
    return retval;

Index: gcc/tree-cfg.c
===================================================================
*** gcc/tree-cfg.c	(revision 221392)
--- gcc/tree-cfg.c	(working copy)
*************** gimple_can_merge_blocks_p (basic_block a
*** 1703,1709 ****
    if (!single_pred_p (b))
      return false;
  
!   if (b == EXIT_BLOCK_PTR_FOR_FN (cfun))
      return false;
  
    /* If A ends by a statement causing exceptions or something similar, we
--- 1703,1710 ----
    if (!single_pred_p (b))
      return false;
  
!   if (a == ENTRY_BLOCK_PTR_FOR_FN (cfun)
!       || b == EXIT_BLOCK_PTR_FOR_FN (cfun))
      return false;
  
    /* If A ends by a statement causing exceptions or something similar, we