Re: [call graph, patch] Reuse call graph nodes

[Martin Jambor <mjambor at suse dot cz>]

Hi,

On Sat, Sep 13, 2008 at 01:47:50PM +0200, Jan Hubicka wrote:
> I think it might be interesting trying same change for
> nodes; after all early inliner produces tons of clones that makes tables
> sparse too.  Then it would be interesting to see how sparse the tables
> are, as tables of pointers would be probably somewhat more robust (and
> slow) than what we have now.

Here we go then, this patch reuses node structures in the same way we
do it for edges.  It has been bootstrapped and tested on
x86_64-suse-linux, revision 140555.

I  have had  a brief  look at  what the  vector memory  statistics are
without  and  with  the  patch  when compiling  tramp3d  with  -O2  on
i686-linux.   Without the  patch,  check_create_node_params is  listed
three times,  taking up roughly  1MB, 2MB and 2MB  respectively, after
the patch  is applied  the function is  listed only twice  with almost
474kB both times.  So I guess it is an improvement worth applying now.
OK?

Thanks

Martin



2008-09-23  Martin Jambor  <mjambor@suse.cz>

	* cgraph.c (free_nodes): New variable.
	(NEXT_FREE_NODE): New macro.
	(cgraph_create_node): Reuse nodes from the free list.  Do not
	update uid if doing so.
	(cgraph_remove_node): Add the node to the free list.


Index: iinln/gcc/cgraph.c
===================================================================
--- iinln.orig/gcc/cgraph.c
+++ iinln/gcc/cgraph.c
@@ -177,11 +177,15 @@ struct cgraph_2node_hook_list *first_cgr
 /* List of hooks triggered when an function is inserted.  */
 struct cgraph_node_hook_list *first_cgraph_function_insertion_hook;
 
+/* Head of a linked list of unused (freed) call graph nodes.
+   Do not GTY((delete)) this list so UIDs gets reliably recycled.  */
+static GTY(()) struct cgraph_node *free_nodes;
 /* Head of a linked list of unused (freed) call graph edges.
    Do not GTY((delete)) this list so UIDs gets reliably recycled.  */
 static GTY(()) struct cgraph_edge *free_edges;
 
-/* Macro to access the next item in the list of free cgraph edges. */
+/* Macro to access the next item in the list of free cgraph nodes and edges. */
+#define NEXT_FREE_NODE(NODE) (NODE)->next
 #define NEXT_FREE_EDGE(EDGE) (EDGE)->prev_caller
 
 /* Register HOOK to be called with DATA on each removed edge.  */
@@ -417,9 +421,18 @@ cgraph_create_node (void)
 {
   struct cgraph_node *node;
 
-  node = GGC_CNEW (struct cgraph_node);
+  if (free_nodes)
+    {
+      node = free_nodes;
+      free_nodes = NEXT_FREE_NODE (node);
+    }
+  else
+    {
+      node = GGC_CNEW (struct cgraph_node);
+      node->uid = cgraph_max_uid++;
+    }
+
   node->next = cgraph_nodes;
-  node->uid = cgraph_max_uid++;
   node->pid = -1;
   node->order = cgraph_order++;
   if (cgraph_nodes)
@@ -933,6 +946,7 @@ cgraph_remove_node (struct cgraph_node *
   void **slot;
   bool kill_body = false;
   struct cgraph_node *n;
+  int uid = node->uid;
 
   cgraph_call_node_removal_hooks (node);
   cgraph_node_remove_callers (node);
@@ -1020,7 +1034,13 @@ cgraph_remove_node (struct cgraph_node *
       node->call_site_hash = NULL;
     }
   cgraph_n_nodes--;
-  /* Do not free the structure itself so the walk over chain can continue.  */
+
+  /* Clear out the node to NULL all pointers and add the node to the free
+     list.  */
+  memset (node, 0, sizeof(*node));
+  node->uid = uid;
+  NEXT_FREE_NODE (node) = free_nodes;
+  free_nodes = node;
 }
 
 /* Notify finalize_compilation_unit that given node is reachable.  */