[RFC/patch] Callgraph based inlining heuristics

[Steven Bosscher]

Richard Guenther wrote:

>On Mon, 23 Jun 2003, Steven Bosscher wrote:
>  
>
>>Richard Guenther wrote:
>>    
>>
>>>Yes, we really want such an attribute. There are cases where you benefit
>>>      
>>>
>>I know that _you_ really want it because you want to have your
>>application work well right now, and I understand that.  What I am
>>afraid of with this attribute is that we implement yet another very ugly
>>(IMHO) "feature" and be stuck with it forever...  And "leafify" only
>>papers over the real problem, it is better to find a way to fix that
>>instead.  Of course this fix will not be as easy to implement as
>>"leafify".  The Dark Side is easier, more seductive...
>>    
>>
>Of course ;) I just fear we'll be not there even in the 3.5 cycle, then.
>
That is so far ahead still, so who knows...

>Hm - we have profiling feedback for loop iterations, no? This way we could
>
Well, yes and no.  Profile information is available in the RTL CFG, 
which is not constructed until _after_ tree-optimizations, including 
tree inlining.

>adjust the inlining heuristics to account for loops that run many times
>and have many calls inside them.
>
Eventually that would be the plan.  See Honza's latest mail.

>But of course inlining after optimizing will be possible in tree-ssa, I
>hope. So we could do a loop
>
>do {
>  inline;
>  tree-optimize;
>} while (inlined_something)
>
This could be _very_ expensive because you need to go in and out of SSA 
form all the time for each function (unless there is a way to inline a 
function while maintaining SSA form; can that be done??), maintain the 
CFG for each function as well as the call graph, and the individual 
passes could be very expensive as well.  Not something for the avarage 
-O2 user :-)

>and possibly tree-optimize the to-be inlined function (with its current
>parameters) before applying any heuristics. Of course this will be
>
In fact, the weird thing about unit-at-a-time is that it changes the 
current behavior of tree-ssa in a peculiar way.  With -finline-functions 
when not in unit-at-a-time mode, each function is first tree-optimized 
and then deferred and later inlined.  With unit-at-a-time, the functions 
are first deferred, then inlined, and tree-optimizing them is the final 
step.  So _without_ unit-at-a-time, we inline optimized function bodies, 
but _with_ unit-at-a-time we do not!

Ideally we would tree-optimize first (allowing better estimates of the 
function size) and then defer for unit-at-a-time, but there were some 
issues with C++, GIMPLE and unit-at-a-time which I didn't quite 
understand but which seemed to be the reason why C++ unit-at-a-time took 
so long to implement.  Again, Honza?  ;-)

>expensive. But at -O4 I'll pay this price if the result is good.
>

Yup.

Gr.
Steven