Partial inlining

Hi,
this patch implements function splitting that allows partial inlining.
Functions are split if there is BB whose frequency is smaller than frequency of
entry BB such that the control flow must past through it just once and
afterwards we don't use values computed beforehand.

I tested the patch on spec2k with and without LTO, spec2k6 and C++ benchmarks.
The storry is always pretty much the same, the patch allows to reduce function
size for inlining from 50 to 40 estimated instructions.  This is still a lot.
However previously we hit number of issues on spec2000 that are gone now.  First
offender is botan that gets huge (>40%) regressions.  It might be interesting to
analyze those.  Offnoise changes on spec2k6 are as follows:

SPEC2k6 time (bigger is better):
milc 6%
povray 4.2%
lbm -2%
wrf 1.1%

SPEC2k6 size (smaller is better):
Perlbench -1.3%
Bzip2 0.3%
gcc 0.1%
gobmk 0.4%
hmmer 0.2%
sjeng 0.1%
libquantum -36%
h264ref -0.7%
omnetpp 0.6%
astar +4%
xlanbmk -1%

So largest gain is probably 36% code size saving at libquantum and 6% speedup
on milc.

We get regression in lbm and some small code size growth when splitting makes
inlining possible, but the inlining is useless.

Total compile time on spec2k6 has reduced a bit (as result of libquantum I
guess), but within noise factor.

Bootstrap time seems also comparable even if we do quite a lot of splitting.

On GCC LTO bootstrap we actually do quite a lot of useful splitting, in
cgraph_node, some vector functions (splitting away the error code) and in many
places where we have cheap guard in header of fucntion.

Due to nature of the problem, there are many possible improvements to the pass,
I want to track them incrementally to avoid pass getting too complicated
without too much of testing.  In particular I think it would be useful

1) resolve some stupid limitations we have now (return by value, EH code etc)
2) make it split large functions (i.e. not to help inlining, but to speed up
   compilation)
3) Add support for passing non-SSA values (currently if split part needs something
   non-SSA we just give up)
4) Make split part to recompute cheap values computed in header
5) Allow splitting into multiple parts
6) ...

There is also problem with debug quality.  Currently the split function will
appear as two functions in backtrace.  I hoped to solve it same way as openMP
but as Jakub told me we don't solve it there and we would probably need dwarf
extension to properly declare split function.
Well, in any case we should be able to fix things back when the split part gets
inlined back to header.

I had the patch in my local tree for a while and it is not causing troubles,
does it seem OK for mainline?

Bootstrapped/regtested x86_64-linux.

Honza

	* tree-pass.h (pass_split_functions): Declare.
	* opts.c (decode_options): Enable function splitting at -O2
	* timevar.def (TV_IPA_FNSPLIT): New macro.
	* ipa-split.c: New file.
	* common.opt (-fpartial-inlining): New flag.
	* Makefile.in (ipa-split.o): New object file.
	* passes.c (init_optimization_passes): Add ipa-split.
	* params.def (max-inline-insns-auto): Reduce max-inline-insns-auto to 40.
	(partial-inlining-entry-probability): New parameters.
	* doc/invoke.texi (-fpartial-inlining): New.

	* testsuite/gcc.dg/tree-ssa/ipa-split.c

/* { dg-do compile } */
/* { dg-options "-O3 -fdump-tree-fnsplit" } */
int test2(a)
{
   if (a<100)
     return 1;
   do_something_big ();
   do_something_big ();
   do_something_big ();
   do_something_big ();
   do_something_big ();
   do_something_big ();
   do_something_big ();
   do_something_big ();
   do_something_big ();
   do_something_big ();
   do_something_big ();
   do_something_big ();
   do_something_big ();
   return 0;
}

test()
{
  test2(10);
  test2(20);
}
/* { dg-final { scan-tree-dump-times "Splitting function" 1 "fnsplit"} } */
/* { dg-final { cleanup-tree-dump "fnsplit" } } */
Index: doc/invoke.texi
===================================================================
*** doc/invoke.texi	(revision 159621)
--- doc/invoke.texi	(working copy)
*************** Objective-C and Objective-C++ Dialects}.
*** 361,367 ****
  -fno-sched-interblock -fno-sched-spec -fno-signed-zeros @gol
  -fno-toplevel-reorder -fno-trapping-math -fno-zero-initialized-in-bss @gol
  -fomit-frame-pointer -foptimize-register-move -foptimize-sibling-calls @gol
! -fpeel-loops -fpredictive-commoning -fprefetch-loop-arrays @gol
  -fprofile-correction -fprofile-dir=@var{path} -fprofile-generate @gol
  -fprofile-generate=@var{path} @gol
  -fprofile-use -fprofile-use=@var{path} -fprofile-values @gol
--- 361,367 ----
  -fno-sched-interblock -fno-sched-spec -fno-signed-zeros @gol
  -fno-toplevel-reorder -fno-trapping-math -fno-zero-initialized-in-bss @gol
  -fomit-frame-pointer -foptimize-register-move -foptimize-sibling-calls @gol
! -fpartial-inlining -fpeel-loops -fpredictive-commoning -fprefetch-loop-arrays @gol
  -fprofile-correction -fprofile-dir=@var{path} -fprofile-generate @gol
  -fprofile-generate=@var{path} @gol
  -fprofile-use -fprofile-use=@var{path} -fprofile-values @gol
*************** also turns on the following optimization
*** 5851,5856 ****
--- 5851,5857 ----
  -findirect-inlining @gol
  -fipa-sra @gol
  -foptimize-sibling-calls @gol
+ -fpartial-inlining @gol
  -fpeephole2 @gol
  -fregmove @gol
  -freorder-blocks  -freorder-functions @gol
*************** This optimization is enabled by default.
*** 7001,7006 ****
--- 7002,7015 ----
  With this option, the compiler will create multiple copies of some
  local variables when unrolling a loop which can result in superior code.

+ @item -fpartial-inlining
+ @opindex fpartial-inlining
+ Inline parts of functions.  This option has any effect only
+ when inlining itself is turned on by the @option{-finline-functions}
+ or @option{-finline-small-functions} options.
+ 
+ Enabled at level @option{-O2}.
+ 
  @item -fpredictive-commoning
  @opindex fpredictive-commoning
  Perform predictive commoning optimization, i.e., reusing computations

Partial inlining

Commit Message

Comments

Patch