Inlining heuristics for C++

[Daniel Berlin <dan at cgsoftware dot com>]

Right now, they are horrific.

As I recently posted, a simple 5 line C++ program using map and string
in normal ways gets inlined from 300 insns to 15k.

This is because we have a few major deficiencies in our inlining
heuristics.

Mainly, we never consider *not* inlining something unless we can't for some
reason (IE it's a varargs function), or we've hit the limit of a
supposed 10000 insns (which really translated into 15k in reality).

Consider the following:

1 main function.

using namespace std;
int main(void)
{
        map<string, string> simple;
        simple["test"]="test";
}

We'll ignore what happens if we init with arguments that could be
inlined. 

We proceed to recursively inline 128 functions into this simple main function
operator call. (Bet you didn't think there were 128 functions you could
inline here)

Why?
Because we never make *any* choices.
Until main is 15k insns long, we won't stop inlining.

We literally inline *everything* we still have the tree's for.

We'll even inline if say, the destruction function for foo or a string
is 50 times bigger than the function it's being inlined into.

I've got a very simple heuristic that says "don't inline things <some
configurable number currently defaulting to 10> times bigger than we
were when we started inlining, into us" I.E. don't inline a 100
statement function into a 10 statement one.

This is effectively expressing the rule: "Small functions should be
inlined into larger ones.  Larger functions should not be inlined into
small ones".

Where what is considered "larger" is fudged by a factor.

If you have a one line member, that calls a huge function, whatever
*calls* that member will inline the member, and then whatever that member calls
will probably beinlined, but the the externally visible member call itself (ie the non-inlined one) will not
inline the huge function into itself.

Which seems to make sense to me.

However, this doesn't control code growth, it could inline a lot of
small functions until it hits the limit.

So the other heuristic i've added controls code growth by saying we don't
want to increase the number of statements in the function by more than
a factor of x over what we started with (when we started inlining).

An expression of the rule: "Don't make the function more than x times bigger than
it originally was".

By comparison, Right now we only have one rule "Don't make the function larger than
MAX_INLINE_INSNS".

So we end up, even with simple looking code, with functions that are
generally MAX_INLINE_INSNS long.

And take *forever* to compile.

Are these generally acceptable heuristics to add?
They seem pretty common sense to me, maybe i'm missing something
however, I wanted to check before I submitted a patch.
They certainly reduce compile time, and only seem to stop inlining
huge functions into smaller ones. Which are the cases where the
performance probably didn't increase, since we are recursively
inlining (and thus, if there were relatively larger functions calling
the smaller one, both the smaller one, and what it called, would be
inlined back into that function, obviating the real need to inline the
larger into the smaller on it's own). 

--Dan
-- 
"I can levitate birds.  No one cares.
"-Steven Wright