Re: cgraph_remove_node slow(?)

[Jeffrey A Law <law at redhat dot com>]

On Mon, 2004-11-22 at 11:41 +0100, Richard Guenther wrote:
> Hi!
> 
> I'm seeing from a flat profile of cc1plus compiling the tramp3d-v3
> testcase with leafification enabled (aka lots of inlining):
> 
> Each sample counts as 0.01 seconds.
>   %   cumulative   self              self     total
>  time   seconds   seconds    calls   s/call   s/call  name
>   3.63      5.07     5.07   163579     0.00     0.00  cgraph_remove_node
>   2.74      8.90     3.83 44552296     0.00     0.00  ggc_alloc_stat
>   2.49     12.37     3.47   381067     0.00     0.00  cgraph_remove_edge
>   1.68     14.72     2.35    13314     0.00     0.00  compute_immediate_uses
>   1.52     16.84     2.12 56272844     0.00     0.00  bitmap_set_bit
>   1.50     18.93     2.09 54900205     0.00     0.00  ggc_set_mark
> 
> where cgraph_remove_node is called like:
> 
>                 0.01    0.01     266/163579      cgraph_optimize [4]
>                 0.22    0.14    7117/163579      cgraph_finalize_compilation_unit [316]
>                 4.84    3.02  156196/163579      expand_calls_inline [18]
> [24]     5.9    5.07    3.16  163579         cgraph_remove_node [24]
>                 3.10    0.00  340261/381067      cgraph_remove_edge [52]
>                 0.03    0.03  163579/111937201     htab_find_slot <cycle 2> [276]
>                 0.00    0.00   14716/169400      htab_clear_slot [3363]
>                 0.00    0.00   14970/161941      dump_enabled_p [3550]
> 
> Is there some low-hanging fruit to optimize the cgraph_remove_node
> calls from expand_call_inline (I didn't see anything obvious)?
Well, I haven't seen cgraph_remove_node near the top of any profiles in
my wanderings.  However, I have seen cgraph_edge bubble up with
checking-enabled compilers.

I suspect it's probably doing a walk down the list of caller/callees to
find and remove the node -- those are just linear searches with the
current implementation.

jeff