Re: Sigh. Inlining heuristics.

[Linus Torvalds <torvalds at transmeta dot com>]

Why do you care about the relative size of the inliner vs the inlinee AT
ALL?

If you have function (a) that calls function (b), it doesn't really
_matter_ whether (a) is smaller than (b) or not.

The only thing that matters is the transformation you do: turn a
"call/ret" into a inlined copy of (b).  The size of function (a) never
enters the picture. 

Therefore you should compare the size of (b) with the size of the call
itself, not with the size of (a).  And notice that the "size of the
call" is more than just the call instruction, it is
 - the call instruction
 - the return
 - the saving/restoring of registers around the call
 - the argument setup
 - the argument loading in the function

If you're looking for a heuristic for the "size" for the call, assume
something like (5+2*nr-of-arguments) instructions.  You can tweak it
later. 

So why not make the heuristic be:
 - if the target function tree is less than N times the size of the
   call tree, then inline it.

where "N" would be some small integer (and we all know that all random
small integers have the initial value "3", don't we?). 

And don't allow this to percolate.  Remember: the disadvantage of
inlining is code bloat and bad icache, so it is _NOT_ valid to just
recursively use the same heuristic, because that would cause exponential
code growth (BAD!) with only linear performance improvement.  That's a
bad trade-off. You allow _linear_ code growth only, up to the factor N.

So once you've used up a factor of 2 for a call-site that got inlined,
you can't just recursively use another factor of N - you now only have a
factor of "N-2" left. 

So assuming a call cost of roughtly 10 instructions on average, you
should hesitate to inline anything that grows to more than 30
instructions in size. 

Unless the user _tells_ you to inline, of course.  The programmer may
know that the function is only called once, and is worth inlining.  So
if the user specifically asks for inlining, you might bump the "max
instructions" up a bit - say from 30 to 100 instructions.

An inlining limit of 15,000 instructions is just completely ridiculous. 

			Linus