Memory footprint/compile time explosion caused by the tree inliner

[Steven Bosscher]

Op vr 18-04-2003, om 01:38 schreef Mike Stump:
> On Thursday, April 17, 2003, at 03:15 PM, Eric Botcazou wrote:
> > PR optimization/10160 reports a huge compile time regression (4h30min 
> > vs a few minutes) on the 3.3 branch wrt the 3.2 branch for LyX/QT on Sparc.
> 
> We fix this, then break it, then fix it, then break it.  :-(  We are 
> doing something wrong.

Assuming GCC hackers are capable people, it would indicate that the tree
inliner is not very roboust or well understood  ;-)

> Let me explain, in C++, there are no non-inlined functions.  In C++, 
> there are no function bigger than 5 lines.  Now, choose your inlining 
> strategy.

Read: "Now, choose your inlining strategy for C++".  How would your
suggestions work out for C and other languages?

> Hint, inlining all function under 6 lines doesn't work.  Hint, inlining 
> all functions that are inline doesn't work.
> 
> Possible solutions, don't allow more than 15x growth in caller, don't 
> allow caller to grow past 1,000 stmts.

Well, what do you define as a single statement?

If you look at the tree inliner, you'll see it's trying to predict the
size of the (maybe) inline function in insns.  We now count insns via
INSNS_PER_STMT, but, for example, a SCOPE_STMT is also counted as a
STMT, so for each scope (i.e. SCOPE_STMT + DECL_STMT) you get 20 insns,
which is not a very good guess I think.  Add a COMPOUND_STMT, and you
have 30 fictuous insns in the tree-inliner for the minimal function.

(If you don't believe me: Look at "int foo (int a) { a = 1; }" and see
that it counts as 40 insns: 30 for the function and 10 for the
EXPR_STMT.)

Especially for your small line functions, this hurts.  Just an empty
function body account for 30 insns, and then you have, say, 10 stmts. 
Gives you (10*10 + 30) == 130 == PARAM_MIN_INLINE_INSNS, so just on the
limit of being too big for inlining when a lot of inlining has been done
already.  Add one more statement and the function is no longer an inline
candidate after repeated inlining.

This may explain why Richard Guenther says it helps for POOMA
performance to increase PARAM_MIN_INLINE_INSNS.  Bumping it gave him
more inlined functions and better performance with only a very small
compile time increase.
(see http://gcc.gnu.org/ml/gcc/2003-04/msg00795.html).


> > For example, one constructor grows from 128 stmts to 15437 stmts 
> > (154370
> > insns according to the fixed conversion factor), that is more than 100
> > times. Given that the scheduler is at least O(n^2), the game is over.
> >
> >
> > The problem is the new heuristics of the tree inliner:
> >
> >       int sum_insns = (id ? id->inlined_stmts : 0) * INSNS_PER_STMT
> > 		     + currfn_insns;
> >       /* In the extreme case that we have exceeded the recursive  inlining
> >          limit by a huge factor (128), we just say no. Should not happen
> >          in real life.  */
> 
> This comment it wrong.  The comment should read, this happens all the 
> time in C++.

128 times the recursive inlining limit is a really large number of
insns.  So I don't think this is real the problem.

In the end it depends on where you _start_ inlining from (call graph
based or just at random like we do now).  Maybe we should allow
-finline-functions only  with -funit-at-a-time in the future (*)... or
at least see how things look when unit-at-a-time for C++ is available.


> Thanks for tacking this down, wanna try testing out the code above and 
> find a reasonable constant and submit it?

You make it sound like this analysis is a Great Discovery, but in fact
these issues with inline parameters have been discussed quite a few
times on gcc-bugs and in at least three high priority PRs for 3.3. 
Remember my mail from yesterday about inline parameters, to which only
Richard Guenther gave serious replies??

Greetz
Steven



*) I've also played a bit with the compile time regression PRs and the
tree-ssa branch, and for example 1687 does not occur there because the
tree of the inline candidate is much simpler, so walk_tree does not
consume so much time.