* cgraph.h (cgraph_remove_unreachable_nodes): Rename to ...

	(symtab_remove_unreachable_nodes): ... this one.
	* ipa-cp.c (ipcp_driver): Do not remove unreachable nodes.
	* cgraphunit.c (ipa_passes): Update.
	* cgraphclones.c (cgraph_materialize_all_clones): Update.
	* cgraph.c (cgraph_release_function_body): Only turn initial
	into error mark when initial was previously set.
	* ipa-inline.c (ipa_inline): Update.
	* ipa.c: Include ipa-inline.h
	(enqueue_cgraph_node, enqueue_varpool_node): Remove.
	(enqueue_node): New function.
	(process_references): Update.
	(symtab_remove_unreachable_nodes): Cleanup.
	* passes.c (execute_todo, execute_one_pass): Update.


git-svn-id: https://gcc.gnu.org/svn/gcc/trunk@187375 138bc75d-0d04-0410-961f-82ee72b054a4

1 files changed, 166 insertions, 187 deletions

diff --git a/gcc/ipa.c b/gcc/ipa.c
index 42e90615da7..766b26f0313 100644
--- a/gcc/ipa.c
+++ b/gcc/ipa.c
@@ -33,6 +33,7 @@ along with GCC; see the file COPYING3.  If not see
 #include "tree-iterator.h"
 #include "ipa-utils.h"
 #include "pointer-set.h"
+#include "ipa-inline.h"
 
 /* Look for all functions inlined to NODE and update their inlined_to pointers
    to INLINED_TO.  */
@@ -49,7 +50,7 @@ update_inlined_to_pointer (struct cgraph_node *node, struct cgraph_node *inlined
       }
 }
 
-/* Add cgraph NODE to queue starting at FIRST.
+/* Add symtab NODE to queue starting at FIRST.
 
    The queue is linked via AUX pointers and terminated by pointer to 1.
    We enqueue nodes at two occasions: when we find them reachable or when we find
@@ -58,8 +59,8 @@ update_inlined_to_pointer (struct cgraph_node *node, struct cgraph_node *inlined
    reachable.  */
 
 static void
-enqueue_cgraph_node (struct cgraph_node *node, struct cgraph_node **first,
-		     struct pointer_set_t *reachable)
+enqueue_node (symtab_node node, symtab_node *first,
+	      struct pointer_set_t *reachable)
 {
   /* Node is still in queue; do nothing.  */
   if (node->symbol.aux && node->symbol.aux != (void *) 2)
@@ -72,21 +73,11 @@ enqueue_cgraph_node (struct cgraph_node *node, struct cgraph_node **first,
   *first = node;
 }
 
-/* Add varpool NODE to queue starting at FIRST.  */
-
-static void
-enqueue_varpool_node (struct varpool_node *node, struct varpool_node **first)
-{
-  node->symbol.aux = *first;
-  *first = node;
-}
-
 /* Process references.  */
 
 static void
 process_references (struct ipa_ref_list *list,
-		    struct cgraph_node **first,
-		    struct varpool_node **first_varpool,
+		    symtab_node *first,
 		    bool before_inlining_p,
 		    struct pointer_set_t *reachable)
 {
@@ -97,18 +88,21 @@ process_references (struct ipa_ref_list *list,
       if (symtab_function_p (ref->referred))
 	{
 	  struct cgraph_node *node = ipa_ref_node (ref);
+
 	  if (node->analyzed
 	      && (!DECL_EXTERNAL (node->symbol.decl)
 		  || node->alias
 	          || before_inlining_p))
 	    pointer_set_insert (reachable, node);
-	  enqueue_cgraph_node (node, first, reachable);
+	  enqueue_node ((symtab_node) node, first, reachable);
 	}
       else
 	{
 	  struct varpool_node *node = ipa_ref_varpool_node (ref);
-	  if (!pointer_set_insert (reachable, node))
-	    enqueue_varpool_node (node, first_varpool);
+
+	  if (node->analyzed)
+	    pointer_set_insert (reachable, node);
+	  enqueue_node ((symtab_node) node, first, reachable);
 	}
     }
 }
@@ -162,19 +156,63 @@ has_addr_references_p (struct cgraph_node *node,
 }
 
 /* Perform reachability analysis and reclaim all unreachable nodes.
-   If BEFORE_INLINING_P is true this function is called before inlining
-   decisions has been made.  If BEFORE_INLINING_P is false this function also
-   removes unneeded bodies of extern inline functions.  */
+
+   The algorithm is basically mark&sweep but with some extra refinements:
+
+   - reachable extern inline functions needs special handling; the bodies needs
+     to stay in memory until inlining in hope that they will be inlined.
+     After inlining we release their bodies and turn them into unanalyzed
+     nodes even when they are reachable.
+
+     BEFORE_INLINING_P specify whether we are before or after inlining.
+
+   - virtual functions are kept in callgraph even if they seem unreachable in
+     hope calls to them will be devirtualized. 
+
+     Again we remove them after inlining.  In late optimization some
+     devirtualization may happen, but it is not importnat since we won't inline
+     the call. In theory early opts and IPA should work out all important cases.
+
+   - virtual clones needs bodies of their origins for later materialization;
+     this means that we want to keep the body even if the origin is unreachable
+     otherwise.  To avoid origin from sitting in the callgraph and being
+     walked by IPA passes, we turn them into unanalyzed nodes with body
+     defined.
+
+     We maintain set of function declaration where body needs to stay in
+     body_needed_for_clonning
+
+     Inline clones represent special case: their declaration match the
+     declaration of origin and cgraph_remove_node already knows how to
+     reshape callgraph and preserve body when offline copy of function or
+     inline clone is being removed.
+
+   We maintain queue of both reachable symbols (i.e. defined symbols that needs
+   to stay) and symbols that are in boundary (i.e. external symbols referenced
+   by reachable symbols or origins of clones).  The queue is represented
+   as linked list by AUX pointer terminated by 1.
+
+   A the end we keep all reachable symbols. For symbols in boundary we always
+   turn definition into a declaration, but we may keep function body around
+   based on body_needed_for_clonning
+
+   All symbols that enter the queue have AUX pointer non-zero and are in the
+   boundary.  Pointer set REACHABLE is used to track reachable symbols.
+
+   Every symbol can be visited twice - once as part of boundary and once
+   as real reachable symbol. enqueue_node needs to decide whether the
+   node needs to be re-queued for second processing.  For this purpose
+   we set AUX pointer of processed symbols in the boundary to constant 2.  */
 
 bool
-cgraph_remove_unreachable_nodes (bool before_inlining_p, FILE *file)
+symtab_remove_unreachable_nodes (bool before_inlining_p, FILE *file)
 {
-  struct cgraph_node *first = (struct cgraph_node *) (void *) 1;
-  struct varpool_node *first_varpool = (struct varpool_node *) (void *) 1;
+  symtab_node first = (symtab_node) (void *) 1;
   struct cgraph_node *node, *next;
   struct varpool_node *vnode, *vnext;
   bool changed = false;
   struct pointer_set_t *reachable = pointer_set_create ();
+  struct pointer_set_t *body_needed_for_clonning = pointer_set_create ();
 
 #ifdef ENABLE_CHECKING
   verify_symtab ();
@@ -191,8 +229,8 @@ cgraph_remove_unreachable_nodes (bool before_inlining_p, FILE *file)
      This is mostly when they can be referenced externally.  Inline clones
      are special since their declarations are shared with master clone and thus
      cgraph_can_remove_if_no_direct_calls_and_refs_p should not be called on them.  */
-  FOR_EACH_FUNCTION (node)
-    if (node->analyzed && !node->global.inlined_to
+  FOR_EACH_DEFINED_FUNCTION (node)
+    if (!node->global.inlined_to
 	&& (!cgraph_can_remove_if_no_direct_calls_and_refs_p (node)
 	    /* Keep around virtual functions for possible devirtualization.  */
 	    || (before_inlining_p
@@ -200,198 +238,126 @@ cgraph_remove_unreachable_nodes (bool before_inlining_p, FILE *file)
 		&& (DECL_COMDAT (node->symbol.decl) || DECL_EXTERNAL (node->symbol.decl)))))
       {
         gcc_assert (!node->global.inlined_to);
-	enqueue_cgraph_node (node, &first, reachable);
 	pointer_set_insert (reachable, node);
+	enqueue_node ((symtab_node)node, &first, reachable);
       }
     else
       gcc_assert (!node->symbol.aux);
 
   /* Mark variables that are obviously needed.  */
-  FOR_EACH_VARIABLE (vnode)
+  FOR_EACH_DEFINED_VARIABLE (vnode)
+    if (!varpool_can_remove_if_no_refs (vnode))
+      {
+	pointer_set_insert (reachable, vnode);
+	enqueue_node ((symtab_node)vnode, &first, reachable);
+      }
+
+  /* Perform reachability analysis.  */
+  while (first != (symtab_node) (void *) 1)
     {
-      if ((vnode->analyzed || vnode->symbol.force_output)
-	  && !varpool_can_remove_if_no_refs (vnode))
-	{
-	  pointer_set_insert (reachable, vnode);
-	  enqueue_varpool_node (vnode, &first_varpool);
-	}
-    }
+      bool in_boundary_p = !pointer_set_contains (reachable, first);
+      symtab_node node = first;
 
-  /* Perform reachability analysis.  As a special case do not consider
-     extern inline functions not inlined as live because we won't output
-     them at all. 
+      first = (symtab_node)first->symbol.aux;
 
-     We maintain two worklist, one for cgraph nodes other for varpools and
-     are finished once both are empty.  */
+      /* If we are processing symbol in boundary, mark its AUX pointer for
+	 possible later re-processing in enqueue_node.  */
+      if (in_boundary_p)
+	node->symbol.aux = (void *)2;
+      else
+	{
+	  /* If any symbol in a comdat group is reachable, force
+	     all other in the same comdat group to be also reachable.  */
+	  if (node->symbol.same_comdat_group)
+	    {
+	      symtab_node next;
+	      for (next = node->symbol.same_comdat_group;
+		   next != node;
+		   next = next->symbol.same_comdat_group)
+		if (!pointer_set_insert (reachable, next))
+		  enqueue_node ((symtab_node) next, &first, reachable);
+	    }
+	  /* Mark references as reachable.  */
+	  process_references (&node->symbol.ref_list, &first,
+			      before_inlining_p, reachable);
+	}
 
-  while (first != (struct cgraph_node *) (void *) 1
-  	 || first_varpool != (struct varpool_node *) (void *) 1)
-    {
-      if (first != (struct cgraph_node *) (void *) 1)
+      if (symtab_function_p (node))
 	{
-	  struct cgraph_edge *e;
-	  node = first;
-	  first = (struct cgraph_node *) first->symbol.aux;
-	  if (!pointer_set_contains (reachable, node))
-	    node->symbol.aux = (void *)2;
-	  /* If we found this node reachable, first mark on the callees
-	     reachable too, unless they are direct calls to extern inline functions
-	     we decided to not inline.  */
-	  else 
+	  struct cgraph_node *cnode = cgraph (node);
+
+	  /* Mark the callees reachable unless they are direct calls to extern
+ 	     inline functions we decided to not inline.  */
+	  if (!in_boundary_p)
 	    {
-	      for (e = node->callees; e; e = e->next_callee)
+	      struct cgraph_edge *e;
+	      for (e = cnode->callees; e; e = e->next_callee)
 		{
-		  if (node->analyzed
+		  if (e->callee->analyzed
 		      && (!e->inline_failed
 			  || !DECL_EXTERNAL (e->callee->symbol.decl)
-			  || node->alias
+			  || cnode->alias
 			  || before_inlining_p))
 		    pointer_set_insert (reachable, e->callee);
-		  enqueue_cgraph_node (e->callee, &first, reachable);
-		}
-	      process_references (&node->symbol.ref_list, &first,
-				  &first_varpool, before_inlining_p,
-				  reachable);
-
-	      /* If any function in a comdat group is reachable, force
-		 all other functions in the same comdat group to be
-		 also reachable.  */
-	      if (node->symbol.same_comdat_group
-		  && !node->global.inlined_to)
-		{
-		  for (next = cgraph (node->symbol.same_comdat_group);
-		       next != node;
-		       next = cgraph (next->symbol.same_comdat_group))
-		    if (!pointer_set_insert (reachable, next))
-		      enqueue_cgraph_node (next, &first, reachable);
+		  enqueue_node ((symtab_node) e->callee, &first, reachable);
 		}
+
+	      /* When inline clone exists, mark body to be preserved so when removing
+		 offline copy of the function we don't kill it.  */
+	      if (!cnode->alias && cnode->global.inlined_to)
+	        pointer_set_insert (body_needed_for_clonning, cnode->symbol.decl);
 	    }
 
-	  /* We can freely remove inline clones even if they are cloned, however if
-	     function is clone of real clone, we must keep it around in order to
-	     make materialize_clones produce function body with the changes
-	     applied.  */
-	  while (node->clone_of && !node->clone_of->symbol.aux
-	         && !gimple_has_body_p (node->symbol.decl))
+	  /* For non-inline clones, force their origins to the boundary and ensure
+	     that body is not removed.  */
+	  while (cnode->clone_of && !cnode->clone_of->symbol.aux
+	         && !gimple_has_body_p (cnode->symbol.decl))
 	    {
-	      bool noninline = node->clone_of->symbol.decl != node->symbol.decl;
-	      node = node->clone_of;
-	      if (noninline && !pointer_set_contains (reachable, node) && !node->symbol.aux)
+	      bool noninline = cnode->clone_of->symbol.decl != cnode->symbol.decl;
+	      cnode = cnode->clone_of;
+	      if (noninline && !cnode->symbol.aux)
 	      	{
-		  enqueue_cgraph_node (node, &first, reachable);
+	          pointer_set_insert (body_needed_for_clonning, cnode->symbol.decl);
+		  enqueue_node ((symtab_node)cnode, &first, reachable);
 		  break;
 		}
 	    }
 	}
-      if (first_varpool != (struct varpool_node *) (void *) 1)
-	{
-	  vnode = first_varpool;
-	  first_varpool = (struct varpool_node *)first_varpool->symbol.aux;
-	  vnode->symbol.aux = NULL;
-	  process_references (&vnode->symbol.ref_list, &first,
-			      &first_varpool, before_inlining_p,
-			      reachable);
-	  /* If any function in a comdat group is reachable, force
-	     all other functions in the same comdat group to be
-	     also reachable.  */
-	  if (vnode->symbol.same_comdat_group)
-	    {
-	      struct varpool_node *next;
-	      for (next = varpool (vnode->symbol.same_comdat_group);
-		   next != vnode;
-		   next = varpool (next->symbol.same_comdat_group))
-		if (!pointer_set_insert (reachable, next))
-		  enqueue_varpool_node (next, &first_varpool);
-	    }
-	}
     }
 
-  /* Remove unreachable nodes. 
-
-     Completely unreachable functions can be fully removed from the callgraph.
-     Extern inline functions that we decided to not inline need to become unanalyzed nodes of
-     callgraph (so we still have edges to them).  We remove function body then.
-
-     Also we need to care functions that are unreachable but we need to keep them around
-     for later clonning.  In this case we also turn them to unanalyzed nodes, but
-     keep the body around.  */
+  /* Remove unreachable functions.   */
   for (node = cgraph_first_function (); node; node = next)
     {
       next = cgraph_next_function (node);
-      if (node->symbol.aux && !pointer_set_contains (reachable, node))
-        {
-	  cgraph_node_remove_callees (node);
-	  ipa_remove_all_references (&node->symbol.ref_list);
-	  node->analyzed = false;
-	}
       if (!node->symbol.aux)
 	{
-	  struct cgraph_edge *e;
-	  bool found = false;
-	  int i;
-	  struct ipa_ref *ref;
-
-          node->global.inlined_to = NULL;
 	  if (file)
 	    fprintf (file, " %s", cgraph_node_name (node));
-	  /* See if there is reachable caller.  */
-	  for (e = node->callers; e && !found; e = e->next_caller)
-	    if (pointer_set_contains (reachable, e->caller))
-	      found = true;
-	  for (i = 0; (ipa_ref_list_referring_iterate (&node->symbol.ref_list,
-						      i, ref)
-		       && !found); i++)
-	    if (pointer_set_contains (reachable, ref->referring))
-	      found = true;
-
-	  /* If so, we need to keep node in the callgraph.  */
-	  if (found)
-	    {
-	      if (node->analyzed)
-		{
-		  struct cgraph_node *clone;
-
-		  /* If there are still clones, we must keep body around.
-		     Otherwise we can just remove the body but keep the clone.  */
-		  for (clone = node->clones; clone;
-		       clone = clone->next_sibling_clone)
-		    if (clone->symbol.aux)
-		      break;
-		  if (!clone)
-		    {
-		      cgraph_release_function_body (node);
-		      if (node->prev_sibling_clone)
-			node->prev_sibling_clone->next_sibling_clone = node->next_sibling_clone;
-		      else if (node->clone_of)
-			node->clone_of->clones = node->next_sibling_clone;
-		      if (node->next_sibling_clone)
-			node->next_sibling_clone->prev_sibling_clone = node->prev_sibling_clone;
-		      if (node->clone_of)
-			node->former_clone_of = node->clone_of->symbol.decl;
-		      node->clone_of = NULL;
-		      node->next_sibling_clone = NULL;
-		      node->prev_sibling_clone = NULL;
-		    }
-		  else
-		    gcc_assert (!clone->symbol.in_other_partition);
-		  node->analyzed = false;
-		  changed = true;
-		  cgraph_node_remove_callees (node);
-		  ipa_remove_all_references (&node->symbol.ref_list);
-		}
-	    }
-	  else
+	  cgraph_remove_node (node);
+	  changed = true;
+	}
+      else if (!pointer_set_contains (reachable, node))
+        {
+	  if (node->analyzed)
 	    {
-	      cgraph_remove_node (node);
+	      if (file)
+		fprintf (file, " %s", cgraph_node_name (node));
+	      cgraph_node_remove_callees (node);
+	      ipa_remove_all_references (&node->symbol.ref_list);
 	      changed = true;
 	    }
+	  if (!pointer_set_contains (body_needed_for_clonning, node->symbol.decl)
+	      && !DECL_ARTIFICIAL (node->symbol.decl))
+	    cgraph_release_function_body (node);
+	  node->analyzed = false;
 	}
     }
+
+  /* Inline clones might be kept around so their materializing allows further
+     cloning.  If the function the clone is inlined into is removed, we need
+     to turn it into normal cone.  */
   FOR_EACH_FUNCTION (node)
     {
-      /* Inline clones might be kept around so their materializing allows further
-         cloning.  If the function the clone is inlined into is removed, we need
-         to turn it into normal cone.  */
       if (node->global.inlined_to
 	  && !node->callers)
 	{
@@ -402,25 +368,38 @@ cgraph_remove_unreachable_nodes (bool before_inlining_p, FILE *file)
       node->symbol.aux = NULL;
     }
 
+  /* Remove unreachable variables.  */
   if (file)
-    fprintf (file, "\n");
-
-  if (file)
-    fprintf (file, "Reclaiming variables:");
+    fprintf (file, "\nReclaiming variables:");
   for (vnode = varpool_first_variable (); vnode; vnode = vnext)
     {
       vnext = varpool_next_variable (vnode);
-      if (!pointer_set_contains (reachable, vnode))
-        {
+      if (!vnode->symbol.aux)
+	{
 	  if (file)
 	    fprintf (file, " %s", varpool_node_name (vnode));
 	  varpool_remove_node (vnode);
 	  changed = true;
 	}
+      else if (!pointer_set_contains (reachable, vnode))
+        {
+	  if (vnode->analyzed)
+	    {
+	      if (file)
+		fprintf (file, " %s", varpool_node_name (vnode));
+	      changed = true;
+	    }
+	  vnode->analyzed = false;
+	  vnode->symbol.aux = NULL;
+	}
+      else
+	vnode->symbol.aux = NULL;
     }
 
-  /* Now update address_taken flags and try to promote functions to be local.  */
+  pointer_set_destroy (reachable);
+  pointer_set_destroy (body_needed_for_clonning);
 
+  /* Now update address_taken flags and try to promote functions to be local.  */
   if (file)
     fprintf (file, "\nClearing address taken flags:");
   FOR_EACH_DEFINED_FUNCTION (node)
@@ -444,18 +423,18 @@ cgraph_remove_unreachable_nodes (bool before_inlining_p, FILE *file)
   if (file)
     fprintf (file, "\n");
 
-  /* Rest of transformations are undesirable at -O0.  */
-  if (!optimize)
-    return changed;
-
 #ifdef ENABLE_CHECKING
   verify_symtab ();
 #endif
 
+  /* If we removed something, perhaps profile could be improved.  */
+  if (changed && optimize && inline_edge_summary_vec)
+    FOR_EACH_DEFINED_FUNCTION (node)
+      cgraph_propagate_frequency (node);
+
   /* Reclaim alias pairs for functions that have disappeared from the
      call graph.  */
   remove_unreachable_alias_pairs ();
-  pointer_set_destroy (reachable);
 
   return changed;
 }