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 <rguent...@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
