Please try out new inlining heuristics

[Jan Hubicka]

>  Jan,
> 
> You may want to try to figure out a way to get better estimates of function
> size from the front ends before tuning your heuristics.
> 
> G++ produces really poor function size estimates.  It overestimates function
> size, which is particularly bad for small functions.  It uses add_stmt too
> often, so even simple one-line functions from templates sometimes have as
> many as 20 statements in it according to DECL_NUM_STMTS.  I suppose that
> Gerald's code is mostly C++, so it doesn't surprise me that you get funny
> results here :-)  The C front end could also do better.  An "if (cond)"
> statment where cond is a very large expression still only counts as a single
> statement (in C and C++), but obviously that large expression will expand to
> way more than just the 10 insns you get from DECL_NUM_STMTS *
> INSNS_PER_STMT...
> 
> So you try tuning your new inliner heuristics with very broken function body
> size heuristics.  When somebody later fixes the latter, you can start all
> over again.

Yes, kind of.
My belief is that the code size estimate is quite entirely broken, but
fixing it properly needs lower level language (like we do have on AST
branch), so I don't want to get too far into busyness of trying to develop some
wrong sollution to this.  I realize I am doing this with inlinining
heuristics itself, but I am primarily interested in the interfaces to be
set up and whant to get the heuristics itself very trivial, if possible,
and extend it once AST is on place.

But perhaps simple code in add_stmt to skip statements that are actually
nops (like scope regions) would do a wonders.  From where the mistake
comes?  (ie is it actually the case that final function body has 20
statements, or are the statements constructed but lost later by
instantiation or so?  Perhaps simple walk of function counting real
statements in function body would do better job.

Would be possible for you to construct simple testcase where I can see
the problem?

Honza
> 
> Gr.
> Steven
> 
> 
> 
> 
> 
> -----Original Message-----
> From: Jan Hubicka
> To: Gerald Pfeifer
> Cc: Jan Hubicka; gcc@gcc.gnu.org
> Sent: 6/28/03 11:42 AM
> Subject: Re: Please try out new inlining heuristics
> 
> > 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