[PATCH] ipa-inline.c: fix caching of estimated_growth

[Josh Conner <jconner at apple dot com>]

In the IPA inliner, a node's (function's) "estimated_growth"  
represents the estimated impact of inlining that function at all of  
its call sites.  This value is used to select in what order functions  
are inlined.

The value estimated_growth is calculated in cgraph_estimated_growth,  
where the value is cached -- it is only recalculated when invalidated  
(by setting it to INT_MIN).  When a function is selected for  
inlining, all functions that are affected by that decision are  
supposed to have their "estimated_growth" reset to INT_MIN so they  
are recalculated the next time they are requested.

By adding a gcc_assert into this code to verify that the recalculated  
value is equivalent to any existing value, I discovered that we are  
missing some instances where the value needs to be recalculated.

Instance #1: when a function with more than one caller is inlined,  
its estimated_growth is not updated.  This is because the following  
code in cgraph_decide_inlining_of_small_functions:

    cgraph_mark_inline_edge (edge);
    update_callee_keys (heap, edge->callee, updated_nodes);

Function cgraph_mark_inline_edge duplicates the callee node, and the  
edge points to the inlined node.  So the remaining non-inlined  
instances never get updated (even though their overall impact is  
affected).  This can be fixed by keeping track of the original callee:

    callee = edge->callee;
    cgraph_mark_inline_edge (edge);
    update_callee_keys (heap, callee, updated_nodes);

Instance #2: for a function that calls another function multiply --  
when one of the instances is inlined, the caller needs to have its  
estimated_growth updated (as it just got larger).  This can be  
addressed by marking it for recalculation in the function  
update_caller_keys (see patch).

Tested on i686-pc-linux-gnu with no regressions.
Verified on sample source base (as described above with runtime  
verification of the cached value) with no incorrect values seen.
Benchmarked on SPEC2000 with marginal performance improvements (see  
bmk_results.txt)

OK for mainline?

- Josh

2005-07-27  Josh Conner  <jconner@apple.com>

        * ipa-inline.c (update_caller_keys): Fix estimated_growth  
caching.
        (cgraph_decide_inlining_of_small_functions): Likewise.

Attachment: inl-propagate.patch
Description: Binary data

Attachment: bmk_results.txt
Description: Text document