This is the mail archive of the gcc@gcc.gnu.org mailing list for the GCC project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

Re: bug introduced by inlining patch


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>






Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]