Re: cgraph_remove_node slow(?)

[Richard Guenther <rguenth at tat dot physik dot uni-tuebingen dot de>]

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.

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/