[call graph, patch] Reuse call graph edges

[Martin Jambor <mjambor at suse dot cz>]

Hi,

as Honza noted in
http://gcc.gnu.org/ml/gcc-patches/2008-09/msg00893.html, the
ipa-prop.c vectors  take up big  amounts of memory because  call graph
edge UIDs  are very  sparse.  The following  patch should fix  that by
reusing the call graph edges altogether with their UIDs.

The    patch   passed   bootstrapped    and   regression    tests   on
x86_64-suse-linux, revision 140294.  However, I have not had a look at
how it helps  because I can't compile the  latest trunk revision (even
an unpatched  one) for some reason.   I will report on  that later (or
Honza will have a look himself :-)

Martin

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

	* cgraph.c (free_edges): New variable.
	(NEXT_FREE_EDGE): New macro.
	(cgraph_remove_edge_1): New function.
	(cgraph_remove_edge): Call cgraph_remove_edge_1.
	(cgraph_node_remove_callees): Likewise.
	(cgraph_node_remove_callers): Likewise.
	(cgraph_create_edge): Reuse edges from the free list.  Do not
	update uid if doing so.


Index: iinln/gcc/cgraph.c
===================================================================
--- iinln.orig/gcc/cgraph.c	2008-09-11 15:38:17.000000000 +0200
+++ iinln/gcc/cgraph.c	2008-09-11 15:40:00.000000000 +0200
@@ -176,6 +176,11 @@ 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 edges.  */
+static GTY(()) struct cgraph_edge *free_edges;
+
+/* Macro to access the next item in the list of free cgraph edges. */
+#define NEXT_FREE_EDGE(EDGE) (EDGE)->prev_caller
 
 /* Register HOOK to be called with DATA on each removed edge.  */
 struct cgraph_edge_hook_list *
@@ -635,7 +640,7 @@ struct cgraph_edge *
 cgraph_create_edge (struct cgraph_node *caller, struct cgraph_node *callee,
 		    gimple call_stmt, gcov_type count, int freq, int nest)
 {
-  struct cgraph_edge *edge = GGC_NEW (struct cgraph_edge);
+  struct cgraph_edge *edge;
 
 #ifdef ENABLE_CHECKING
   /* This is rather pricely check possibly trigerring construction of call stmt
@@ -645,6 +650,17 @@ cgraph_create_edge (struct cgraph_node *
 
   gcc_assert (is_gimple_call (call_stmt));
 
+  if (free_edges)
+    {
+      edge = free_edges;
+      free_edges = NEXT_FREE_EDGE (edge);
+    }
+  else
+    {
+      edge = GGC_NEW (struct cgraph_edge);
+      edge->uid = cgraph_edge_max_uid++;
+    }
+
   if (!callee->analyzed)
     edge->inline_failed = N_("function body not available");
   else if (callee->local.redefined_extern_inline)
@@ -677,7 +693,6 @@ cgraph_create_edge (struct cgraph_node *
   gcc_assert (freq <= CGRAPH_FREQ_MAX);
   edge->loop_nest = nest;
   edge->indirect_call = 0;
-  edge->uid = cgraph_edge_max_uid++;
   if (caller->call_site_hash)
     {
       void **slot;
@@ -722,17 +737,31 @@ cgraph_edge_remove_caller (struct cgraph
 	  		       htab_hash_pointer (e->call_stmt));
 }
 
+/* Put the edge onto the free list.  */
+
+static void
+cgraph_remove_edge_1 (struct cgraph_edge *e)
+{
+  NEXT_FREE_EDGE (e) = free_edges;
+  free_edges = e;
+}
+
 /* Remove the edge E in the cgraph.  */
 
 void
 cgraph_remove_edge (struct cgraph_edge *e)
 {
+  /* Call all edge removal hooks.  */
   cgraph_call_edge_removal_hooks (e);
+
   /* Remove from callers list of the callee.  */
   cgraph_edge_remove_callee (e);
 
   /* Remove from callees list of the callers.  */
   cgraph_edge_remove_caller (e);
+
+  /* Put the edge onto the free list.  */
+  cgraph_remove_edge_1 (e);
 }
 
 /* Redirect callee of E to N.  The function does not update underlying
@@ -814,6 +843,7 @@ cgraph_node_remove_callees (struct cgrap
     {
       cgraph_call_edge_removal_hooks (e);
       cgraph_edge_remove_callee (e);
+      cgraph_remove_edge_1 (e);
     }
   node->callees = NULL;
   if (node->call_site_hash)
@@ -837,6 +867,7 @@ cgraph_node_remove_callers (struct cgrap
     {
       cgraph_call_edge_removal_hooks (e);
       cgraph_edge_remove_caller (e);
+      cgraph_remove_edge_1 (e);
     }
   node->callers = NULL;
 }