[PATCH] Clean up early inliner

[Jan Hubicka]

> 
> Does it?  Not for me (neither with nor without the patch).
> It of course sorrry()s out.

Yes, it sorrys out. I was just concerned about memory time before it does
so (as sorrying happens only after all decisios are fixed and function is
being output so if we recursively inline too deep, we would consume too
much of RAM)
> 
> Anyway, I'll shortcut this as well to save some compile-time.
> 
> Note that for the testcase above it doesn't make sense to
> inline bomb() into t at all, still we do it.  To improve
> the situation here we'd indeed need to compute cgraph SCCs
> and simply use the heuristic to not increase SCC size by
> inlining (thus, not inline A into B if they are in different
> non-singleton SCCs).

Well, this is questionable for recursive inlining in general.
Our general strategy to handle these is to make recursive functions inlined as
small functions and handled by same way.

In my experience we have three cases we are shooting for:

  1) functions that are written in recursive way, but the recursion really
     is of fixed depth of 1 or 2 and inlining eliminate them. We have plenty
     of such examples in GCC.
  2) normal recursive functions making many invocations of self with small
     depth (such as recursive walking of RTL). 

     In this case inlining into caller tends to reduce amount of calls
     noticeably and helps.  Recursive inlining can hurt as the call overhead
     of function gets higher (i.e. we have more registers to save in prologue)
     and consequently the leaves of recursion that are in majority can be
     more expensive. Sometimes it helps when the optimizations hits or we
     suceed reducing number of leaves a lot.

     Since in many cases recursion depth is just 1 or 2, we are relatively often
     on the losing side.

  3) functions that do basically iteration via recursion and tends to do very
     deep recursion chain.  In this case recursive inlining helps because it
     reduces return stack mispredict to some constant fraction.

For 1/2 inlining recursive functions into their callers make sense, for 3 it
does not. But this is bit difficult to decide statically.  I made no
experiments with tunning this too much. Not even making profile driven inliner
too much smarter on this except by convincing recursive inliner to give up
on functions with small average recursion depth.

Honza
> 
> Richard.