Re: [PATCH] Remove O(N^2) complexity from cgraph_remove_node (fwd)

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

On Tue, 2005-03-01 at 16:44 +0100, Richard Guenther wrote:
> Hi!
> 
> This patch addresses a scalability issue with the cgraph_edge
> structure by changing the singly-linked chains to doubly-linked
> ones.  This shaves off 7% of compile time from the tramp3d-v3
> testcase with the new inlining estimate at -O2 and 4% off a
> -O2 compile with leafify enabled and the old inlining estimates.
> With old inlining estimates and no leafify it saves 1%.
> 
> Bootstrapped on i686-pc-linux-gnu for 4.0,
> bootstrapped and tested on x86_64-unknown-linux-gnu for mainline.
> 
> Ok for mainline?  Ok for branch?
> 
> Richard.
> 
> 
> 2005-Mar-01  Richard Guenther  <rguenth@gcc.gnu.org>
> 
> 	* cgraph.h (struct cgraph_edge): Add prev_caller and
> 	prev_callee fields.
> 	(cgraph_node_remove_callees): Export.
> 	* cgraph.c (cgraph_create_edge): Initialize prev_caller
> 	and prev_callee.
> 	(cgraph_edge_remove_callee): New function.
> 	(cgraph_edge_remove_caller): Likewise.
> 	(cgraph_remove_edge): Use.
> 	(cgraph_redirect_edge_callee): Likewise.
> 	(cgraph_node_remove_callees): New function.
> 	(cgraph_node_remove_callers): Likewise.
> 	(cgraph_remove_node): Use.
> 	* tree-optimize.c (tree_rest_of_compilation): Use
> 	cgraph_node_remove_callees instead of manual loop.
> 	* cgraphunit.c (cgraph_finalize_function): Likewise.
> 	(cgraph_expand_function): Likewise.
> 	(cgraph_remove_unreachable_nodes): Likewise.
Note I would expect this to help with some of the other compile-time
PRs in the database.  I know I saw these bits of the cgraph code show
up as significant time consumers, but I can't remember which of the
many tests it affected (I know it wasn't tramp3d as I've never done
much with that particular test).  You might try it against PR8361.

jeff