cgraph.h (struct cgraph_edge): Add prev_caller and prev_callee fields.

2005-03-02  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.

From-SVN: r95777

1 files changed, 80 insertions, 23 deletions

diff --git a/gcc/cgraph.c b/gcc/cgraph.c
index 7d1cca2..11953b4 100644
--- a/gcc/cgraph.c
+++ b/gcc/cgraph.c
@@ -96,6 +96,10 @@ The varpool data structure:
 #include "output.h"
 #include "intl.h"
 
+static void cgraph_node_remove_callers (struct cgraph_node *node);
+static inline void cgraph_edge_remove_caller (struct cgraph_edge *e);
+static inline void cgraph_edge_remove_callee (struct cgraph_edge *e);
+
 /* Hash table used to convert declarations into nodes.  */
 static GTY((param_is (struct cgraph_node))) htab_t cgraph_hash;
 
@@ -289,30 +293,55 @@ cgraph_create_edge (struct cgraph_node *caller, struct cgraph_node *callee,
   edge->caller = caller;
   edge->callee = callee;
   edge->call_expr = call_expr;
+  edge->prev_caller = NULL;
   edge->next_caller = callee->callers;
+  if (callee->callers)
+    callee->callers->prev_caller = edge;
+  edge->prev_callee = NULL;
   edge->next_callee = caller->callees;
+  if (caller->callees)
+    caller->callees->prev_callee = edge;
   caller->callees = edge;
   callee->callers = edge;
   return edge;
 }
 
-/* Remove the edge E the cgraph.  */
+/* Remove the edge E from the list of the callers of the callee.  */
+
+static inline void
+cgraph_edge_remove_callee (struct cgraph_edge *e)
+{
+  if (e->prev_caller)
+    e->prev_caller->next_caller = e->next_caller;
+  if (e->next_caller)
+    e->next_caller->prev_caller = e->prev_caller;
+  if (!e->prev_caller)
+    e->callee->callers = e->next_caller;
+}
+
+/* Remove the edge E from the list of the callees of the caller.  */
+
+static inline void
+cgraph_edge_remove_caller (struct cgraph_edge *e)
+{
+  if (e->prev_callee)
+    e->prev_callee->next_callee = e->next_callee;
+  if (e->next_callee)
+    e->next_callee->prev_callee = e->prev_callee;
+  if (!e->prev_callee)
+    e->caller->callees = e->next_callee;
+}
+
+/* Remove the edge E in the cgraph.  */
 
 void
 cgraph_remove_edge (struct cgraph_edge *e)
 {
-  struct cgraph_edge **edge, **edge2;
+  /* Remove from callers list of the callee.  */
+  cgraph_edge_remove_callee (e);
 
-  for (edge = &e->callee->callers; *edge && *edge != e;
-       edge = &((*edge)->next_caller))
-    continue;
-  gcc_assert (*edge);
-  *edge = (*edge)->next_caller;
-  for (edge2 = &e->caller->callees; *edge2 && *edge2 != e;
-       edge2 = &(*edge2)->next_callee)
-    continue;
-  gcc_assert (*edge2);
-  *edge2 = (*edge2)->next_callee;
+  /* Remove from callees list of the callers.  */
+  cgraph_edge_remove_caller (e);
 }
 
 /* Redirect callee of E to N.  The function does not update underlying
@@ -321,16 +350,46 @@ cgraph_remove_edge (struct cgraph_edge *e)
 void
 cgraph_redirect_edge_callee (struct cgraph_edge *e, struct cgraph_node *n)
 {
-  struct cgraph_edge **edge;
+  /* Remove from callers list of the current callee.  */
+  cgraph_edge_remove_callee (e);
 
-  for (edge = &e->callee->callers; *edge && *edge != e;
-       edge = &((*edge)->next_caller))
-    continue;
-  gcc_assert (*edge);
-  *edge = (*edge)->next_caller;
-  e->callee = n;
+  /* Insert to callers list of the new callee.  */
+  e->prev_caller = NULL;
+  if (n->callers)
+    n->callers->prev_caller = e;
   e->next_caller = n->callers;
   n->callers = e;
+  e->callee = n;
+}
+
+/* Remove all callees from the node.  */
+
+void
+cgraph_node_remove_callees (struct cgraph_node *node)
+{
+  struct cgraph_edge *e;
+
+  /* It is sufficient to remove the edges from the lists of callers of
+     the callees.  The callee list of the node can be zapped with one
+     assignment.  */
+  for (e = node->callees; e; e = e->next_callee)
+    cgraph_edge_remove_callee (e);
+  node->callees = NULL;
+}
+
+/* Remove all callers from the node.  */
+
+static void
+cgraph_node_remove_callers (struct cgraph_node *node)
+{
+  struct cgraph_edge *e;
+
+  /* It is sufficient to remove the edges from the lists of callees of
+     the callers.  The caller list of the node can be zapped with one
+     assignment.  */
+  for (e = node->callers; e; e = e->next_caller)
+    cgraph_edge_remove_caller (e);
+  node->callers = NULL;
 }
 
 /* Remove the node from cgraph.  */
@@ -341,10 +400,8 @@ 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);
+  cgraph_node_remove_callers (node);
+  cgraph_node_remove_callees (node);
   while (node->nested)
     cgraph_remove_node (node->nested);
   if (node->origin)