cgraph_remove_node slow(?)

[Jan Hubicka]

> On Mon, 22 Nov 2004, Jeffrey A Law wrote:
> 
> > On Mon, 2004-11-22 at 11:41 +0100, Richard Guenther wrote:
> > >
> > >                 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.
> 
> Yup, looking at cgraph_remove_node, it looks very much quadratic :/
> For
> 
> void
> cgraph_remove_node (struct cgraph_node *node)
> {
>   void **slot;
>   bool check_dead = 1;
> 
>   while (node->callers)
>     cgraph_remove_edge (node->callers);
>   while (node->callees)
>     cgraph_remove_edge (node->callees);
>   while (node->nested)
>     cgraph_remove_node (node->nested);
> 
> we should be able to at least pass either edge or edge2 that
> is computed in cgraph_remove_edge to cgraph_remove_edge and
> avoid searching for it.  Though I'm somewhat confused about
> callee and caller and e->callee->callers ...  I guess Jan
> could exploit this possibility fastest.  But it wouldn't
> solve the O(n^2) issue.

I have to look into this deeper once I return from Tokyo, but the code
in general does just removing from doubly linked lists and that should
not be quadratic (the loop is reprately removing the first members of
the list).

Later the code is walking list of all clones to figure out if body is
dead, perhaps this is the problem.

Honza
> 
> Maybe there can be done something more.  I'd vote for
> adding cgraph_remove_caller, cgraph_remove_callee and
> cgraph_remove_nested if that helps.
> 
> Richard.
> 
> --
> Richard Guenther <richard dot guenther at uni-tuebingen dot de>
> WWW: http://www.tat.physik.uni-tuebingen.de/~rguenth/