Please try out new inlining heuristics

[Jan Hubicka]

> On Fri, 27 Jun 2003, Jan Hubicka wrote:
> > > On Thu, 26 Jun 2003, Jan Hubicka wrote:
> > > > The inline limits are set via
> > > > --param max-inline-insns-auto=X --param max-inline-insns-single=X
> > > > The abstraction penalty (in percents):
> > > > --param inline-abstraction-penalty=25
> > > > Additionally there is --param large-function-insns (defaulting to 30000)
> > > > and --param large-function-growth (defaulting to 200%) used to avoid
> > > > huge function bodies.
> > > >
> > > > If you have some CPU time to spare, I would be interested in performance
> > > > of various settings of inline-abstraction-penalty (20/40/60/80) and
> > > > max-inline-insns-auto+max-inline-insns-single (150/300/600/900).
> > >
> > > In my case, I assume 600/900 are sufficient to test (for the other will
> > > be loose for sure) and perhaps all of 20/40/60/80?
> > First try 600/40.  If that fails/pass we can try increase/decrease the
> > parameters. (600/20 or 600/60 probably can come next)
> 
> Okay, the following is for current mainline versus Jan's patch with
>   --param max-inline-insns-auto=600
>   --param max-inline-insns-single=600
>   --param inline-abstraction-penalty=40 and 50, respectively.
> 
> Build times and sizes are along what we would have expected:
> 
>             Build time	size	stripped size
>   mainline  5:16	2347068	1076480
>   +600/40   4:47        2671331 1096288
>   +600/50   4:53        2698503 1125824
> 
> However, my benchmarks seem _completely_ backwards.  Either I made some
> very silly operator error when building (but then, build times and sizes
> seem okay), or the two options interact very unexpectedly?

Ineed, this is very strange.  I was trying to analyze this statically
(ie computing number of call instructions) and the results are very
similar.  This appears to be bad luck/good luck as moving the values
slightly seems to produce very different results.
This seems suggest that my heuristics is simply too local and can get
into degenerated scenario.  (assuming that I didn't managed to do some
silly mistake somewhere)

I am just working on completely new global heuristics - compute how many
times given function is called, compute code size growth by deciding
each function to be inlined, inline all calls to function causing
smallest growth, update tabels and recompute.  This is similar to
algorithms used for approximating knapsack problems.

When you disable limit on function body size and do just limit on
overall program growth, you do have knapsack problem.  This is what many
papers suggest also so lets try it out.

I will also try to revisit way how I deal with abstraction penalty -
when I inline big function into small function, I reduce size of big
function in given ration, so after repeating this many times I can get
into very small body.

I hope to have something in an hour or so.  Hope it will have more
stable behaviour than current two heuristics we have :)

Unforutnately there are absolutely no papers studying inlining in C++
context, that is very strange.  Most of C related papers use heuristics
as I implemeneted, most of scheme/lisp inlnining papers use
knapsack-like scheme.

Thank you for the benchmarks!  I will try to return to you with
something that produces less calls.  It seems to me that the frequency
of call instructions appears to match quite closely what your results
are so we can avoid spending too much of time on your machines.

Thank you for your patience!  This is more fun than I expected it to be.
Honza
> 
>                     |   mainline  |   +600/40   |   +600/50    |
>       STRATCOMP1-ALL|  6.25 (0.02)|  9.74 (0.21)| 10.29 (0.56) |
>    STRATCOMP-770.2-Q|  0.69 (0.00)|  1.64 (0.00)|  1.67 (0.03) |
>                2QBF1| 18.75 (0.00)| 44.88 (0.07)| 44.93 (0.08) |
>           PRIMEIMPL2|  9.76 (0.00)| 59.85 (0.00)| 64.07 (0.02) |
>             ANCESTOR|107.19 (0.78)|226.90 (0.26)|226.07 (0.05) |
>        3COL-SIMPLEX1|  6.01 (0.00)| 13.76 (0.00)| 13.67 (0.00) |
>          3COL-LADDER|116.00 (0.02)|242.15 (0.18)|237.30 (0.34) |
>        3COL-N-LADDER|  2.49 (0.01)|  4.56 (0.00)|  4.62 (0.04) |
>         3COL-RANDOM1| 10.87 (0.06)| 53.56 (0.12)| 57.23 (0.10) |
>           HP-RANDOM1|  7.31 (0.02)| 26.12 (0.07)| 26.07 (0.04) |
>        HAMCYCLE-FREE|  1.54 (0.00)|  7.16 (0.00)|  7.23 (0.00) |
>              DECOMP2| 13.17 (0.05)| 51.08 (0.01)| 50.58 (0.00) |
>         BW-P4-Esra-a| 74.02 (0.31)|204.28 (0.08)|210.87 (0.09) |
>         BW-P5-nopush|  6.90 (0.02)| 18.16 (0.02)| 18.76 (0.02) |
>        BW-P5-pushbin|  5.57 (0.02)| 17.42 (0.02)| 17.87 (0.02) |
>      BW-P5-nopushbin|  1.78 (0.00)|  5.60 (0.00)|  5.71 (0.01) |
>               3SAT-1| 30.44 (0.02)|182.10 (0.02)|194.13 (0.05) |
>    3SAT-1-CONSTRAINT| 18.51 (0.01)|107.94 (0.04)|112.51 (0.37) |
>         HANOI-Towers|  3.31 (0.01)|  9.27 (0.01)|  9.28 (0.01) |
>               RAMSEY|  6.93 (0.00)| 21.11 (0.00)| 20.91 (0.00) |
>              CRISTAL|  7.00 (0.04)| 16.03 (0.01)| 16.26 (0.02) |
>              HANOI-K| 36.69 (0.07)|169.70 (0.32)|176.80 (0.42) |
>            21-QUEENS|  8.35 (0.03)| 55.87 (0.10)| 57.45 (0.05) |
>    MSTDir[V=13,A=40]| 18.18 (0.03)| 63.51 (0.97)| 63.80 (0.03) |
>    MSTDir[V=15,A=40]| 18.17 (0.02)| 62.46 (0.03)| 63.23 (0.02) |
>  MSTUndir[V=13,A=40]|  9.48 (0.01)| 37.49 (0.01)| 37.90 (0.01) |
>  MSTUndir[V=15,A=40]|154.41 (0.10)|581.99 (0.09)|586.53 (0.04) |
>          TIMETABLING|  9.01 (0.00)| 23.27 (0.00)| 23.43 (0.01) |
> 
> Gerald