Re: bug introduced by inlining patch

[Daniel Berlin <dberlin at dberlin dot org>]

On Wednesday, September 4, 2002, at 02:51  PM, Kurt Garloff wrote:

> Hi Daniel,
>
> On Wed, Sep 04, 2002 at 02:35:44PM -0400, Daniel Berlin wrote:
> > > Next improvement would be to calculate the complete call graph
> > > and then
> > > take decisions on where to cut it based on inlining limits, loop 
> > > depth
> > > and function size. There you would probably start with inlining from
> > > the leaf functions not the trunk.
> > Once again, there is never a good reason to inline starting at the
> > leaves when you have good information like loop depth, estimated call
> > counts, etc.
> Quite strong statement.
>
> > Haven't we gone over this before?
> Yes. Well, apparently neither of us succeeded in convincing the other.
> Basically your argument is ...
>
> > No good compiler does it (look at Intel's compiler, Pro64, just about
> > every compiler producing good code).
> ... which I do not consider very convincing, whereas mine is that 
> you'll
> have more calls to leaves than somewhere else in the call tree.
I'm curious as to two things:
1. Why you think this isn't convincing.  Do you honestly think that 
nobody has spent large amounts of time studying this very issue, doing 
benchmarking, etc, before choosing trunk->leaves over leaves->trunk?  
In other words, that everyone got it wrong, and that these compilers 
would do a lot better if they followed a bottom up approach.
2. Why you think on average, most calls are to leaves.  Most functions 
we want to inline tend to call other functions, not nothing, in my 
experience.  Look at profiles of gcc, fer instance.


> (You can construct cases where this is not the case of course, as there
>  are conditionals, but in average it will be true.)
You have some statistics to back this up?

> > This is because if you know the functions with loops and loop depth,
> > you want to inline functions *into* them, not take random leaf
> > functions and try to figure out where they are called from, and 
> > whether
> > they are called in loops, etc.
> But if you gather the complete information of your call tree, your
> inlining decisions will be independent from where you start with it,
> so this discussion is a noop. Rather an implementation detail.
Yes, i'm quite aware, however, starting at the trunk will let you do it 
in a single walk.
Starting at the leaves wouldn't (unless you've got a callee graph 
computed as well, which would require at least as much work as 
computing the call graph, and isn't as useful, since most things don't 
want to walk bottom-up)
> In presence of very incomplete information, I'd still bet that starting
> from the leaves is better.
Very incomplete, sure.
But it's easy to make sure we have enough info.

> PS: I would love to have enough time to work on this.
I'm happy to give you code that gives you the call graph construction, 
including information on which functions have loops, if it would speed 
it up.

> Regards,
> --
> Kurt Garloff  <garloff@suse.de>                          Eindhoven, NL
> GPG key: See mail header, key servers         Linux kernel development
> SuSE Linux AG, Nuernberg, DE                            SCSI, Security
> <mime-attachment>