Sigh. Inlining heuristics.

[Daniel Berlin <dan at cgsoftware dot com>]

One thing people seem to be missing is that we recursively inline, and
the heuristics are relative to the base of the inlining tree.
So if you have

a->b->c->d->e

and a was large, we'd still inline all of them.

However, then we compile b (which itself was small), we currently
*also* 
inline b->c->d->e when we compile b, 
which makes no sense, since the consumers of b inside the translation
unit already inlined it if it made sense (IE they were larger).

If c is a very large function, you'll end up increasing the code size,
and compile time, but generally not performance.

Simple example.

right now, given these functions and sizes

a
100 stmts
b
2 stmts
c
50 stmts
d
1000 stmts
e 
100 stmts

and the following call trees:

a->b->c->d->[a sometimes, e sometimes]
(it's not an infinite loop)
Right now, with the current heuristics
We go to process a
a will become 100+2+50+1000+100+2+50+1000+100.....  statements long
(it's actually going to become MAX_INLINE_INSNS)
We output code for a.
completely done with a, but saved the tree for inlining into other
functions.
Now we go to process b
b will become 2+50+1000+100+....MAX_INLINE_INSNS statements long
finish processing of b
process c
c will become 50+1000+100...MAX_INLINE_INSNS statements long
finish processing c
process d
d will become 1000+100...MAX_INLINE_INSNS statements long
finish processing d

MAX_INLINE_INSNS is 10k.
So we now have a 2 statement function that got inlined until it was
10k.
And it made no sense. It increased code size, but didn't improve
performance (probably made it much worse). And we spent a long time
compiling it, too. 

Why?
inlining b into a makes sense (arguably, c into b into a makes sense,
but d into c into b into a doesn't. This is the fudge factor i added)

inlining b into a into d  makes sense.

Once you'd done these two, however,
things like
inlining e into d into c into b makes no sense. b is a small function,
it's callers already inlined it (and what it calls). We're just
wasting time here, and increasing the code size.

My heuristic says d into c into b is not smart.

Realize that the argument that something else might call b too doesn't
change anything. If it's inside the translation unit, we'll consider
inlining it when we compile something that calls whatever else calls
b.

We don't have interprocedural analysis, so i haven't pessimized long
call chains anymore that we did before.   I've just stopped inlining
along paths that we can't see making sense.  

The patholigical case for this heuristic is having a call tree where
each function down the call tree is exactly fudge factor * original
root tree size - 1.
We'll do what we do now in this case, for that inlining call tree.

I haven't even actually pessimized any code (our performance on things
like stepanov stayed the same or got better, while compilation time
went down)


Some things to think about if you think i'm wrong. Say you had.

test2.c
int a()
{
        int i;
        for (i = 0; i <50000; i++)
                b(i)
}

test.c
int b(int a)
{
        c(a);
}
int c(int)
{
        10k lines.
}

we would inline c into b right now.

But since a is outside the translation unit, we wouldn't see it
anyway to inline b into. So we've only saved call overhead of b
calling c, at a cost of increase of 10000x in b's
code. Since 10000x code growth is usually more than the number
of instructions involved in making the call, and is more likely to
push other stuff out of the instruction cache, it wasn't a good idea.
My heuristic would say this. 

Now, say you move a into test.c.

Currently, we'll

inline c into b into a for a.

c into b for b.


Since the main caller of b is a, and we already inlined b *and* c into
a, it doesn't make sense to do it again just for b. 10000x code
growth, large compile time increase, no performance increase.

My heuristic will still do
inline c into b into a for a.

which was the important one.

It won't do c into b for b.


Not that i think it's perfect. I know it's not.  but people seem to be trying to raise
an issue that is already pretty much accounted for.

It's pretty hard to come up with cases where we won't do inlining we
should with the heuristic, and equally hard to come with cases where
we should do inlining we don't.

You'd have to deliberately architect your code in such a way that
knows this.  But even if you did that, you'd do worse with what we
currently do anyway.


In addition, we inline anything marked inline (we do now, too), so
that's always a fall back.

--Dan

-- 
"I used to own an ant farm but had to give it up.  I couldn't
find tractors small enough to fit it.
"-Steven Wright