* expmed.c (expand_divmod): Undo sign extensions for unsigned operands

	* cfgcleanup.c (try_forward_edges):  Don't check loop structures
	when not optimizing.
	(cleanup_cfg): Do not iterate trought delete_trivially_dead_insns
	when not expensive.
	* toplev.c (rest_of_compilation):  Duplicate loop headers only when
	optimizing;  Delete trivially dead insns early; fix optimize check.

	* Makefile.in (c-decl.o, c-objc-common.o, cgraph.o, tree-inline.o): Add
	dependency on cgraph.h
	* c-decl.c: Include cgraph.h
	(finish_function): Update call of tree_inlinable_function_p.
	* c-objc-common.c: Include cgraph.h
	* cgraph.h: New file.
	* cgraphunit.c: New file.
	* cgraph.c (cgraph_node, cgraph_edge): Move into cgraph.h
	(cgraph_nodes, cgraph_n_nodes): Globalize.
	(cgraph_finalize_function, cgraph_finalize_compilation_unit
	cgraph_create_edges, cgraph_optimize, cgraph_mark_needed_node):
	Move into cgraphunit.c
	* tree-inline.c: Include cgraph.h
	* tree-inline.c: Include cgraph.h


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

1 files changed, 360 insertions, 0 deletions

diff --git a/gcc/cgraphunit.c b/gcc/cgraphunit.c
new file mode 100644
index 00000000000..0a12ddad856
--- /dev/null
+++ b/gcc/cgraphunit.c
@@ -0,0 +1,360 @@
+/* Callgraph handling code.
+   Copyright (C) 2003 Free Software Foundation, Inc.
+   Contributed by Jan Hubicka
+
+This file is part of GCC.
+
+GCC is free software; you can redistribute it and/or modify it under
+the terms of the GNU General Public License as published by the Free
+Software Foundation; either version 2, or (at your option) any later
+version.
+
+GCC is distributed in the hope that it will be useful, but WITHOUT ANY
+WARRANTY; without even the implied warranty of MERCHANTABILITY or
+FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
+for more details.
+
+You should have received a copy of the GNU General Public License
+along with GCC; see the file COPYING.  If not, write to the Free
+Software Foundation, 59 Temple Place - Suite 330, Boston, MA
+02111-1307, USA.  */
+
+#include "config.h"
+#include "system.h"
+#include "coretypes.h"
+#include "tm.h"
+#include "tree.h"
+#include "tree-inline.h"
+#include "langhooks.h"
+#include "hashtab.h"
+#include "toplev.h"
+#include "flags.h"
+#include "ggc.h"
+#include "debug.h"
+#include "target.h"
+#include "cgraph.h"
+
+static void cgraph_expand_functions PARAMS ((void));
+static void cgraph_mark_functions_to_output PARAMS ((void));
+static void cgraph_expand_function PARAMS ((struct cgraph_node *));
+static tree record_call_1 PARAMS ((tree *, int *, void *));
+
+/* Analyze function once it is parsed.  Set up the local information
+   available - create cgraph edges for function calles via BODY.  */
+
+void
+cgraph_finalize_function (decl, body)
+     tree decl;
+     tree body ATTRIBUTE_UNUSED;
+{
+  struct cgraph_node *node = cgraph_node (decl);
+
+  node->decl = decl;
+
+  /* Set TREE_UNINLINABLE flag.  */
+  tree_inlinable_function_p (decl);
+
+  (*debug_hooks->deferred_inline_function) (decl);
+}
+
+static struct cgraph_node *queue = NULL;
+
+/* Notify finalize_compilation_unit that given node is reachable
+   or needed.  */
+void
+cgraph_mark_needed_node (node, needed)
+     struct cgraph_node *node;
+     int needed;
+{
+  if (needed)
+    {
+      if (DECL_SAVED_TREE (node->decl))
+        announce_function (node->decl);
+      node->needed = 1;
+    }
+  if (!node->reachable)
+    {
+      node->reachable = 1;
+      if (DECL_SAVED_TREE (node->decl))
+	{
+	  node->aux = queue;
+	  queue = node;
+        }
+    }
+}
+
+/* Walk tree and record all calls.  Called via walk_tree.  */
+static tree
+record_call_1 (tp, walk_subtrees, data)
+     tree *tp;
+     int *walk_subtrees;
+     void *data;
+{
+  /* Record dereferences to the functions.  This makes the functions
+     reachable unconditionally.  */
+  if (TREE_CODE (*tp) == ADDR_EXPR)
+    {
+      tree decl = TREE_OPERAND (*tp, 0);
+      if (TREE_CODE (decl) == FUNCTION_DECL)
+        cgraph_mark_needed_node (cgraph_node (decl), 1);
+    }
+  else if (TREE_CODE (*tp) == CALL_EXPR)
+    {
+      tree decl = TREE_OPERAND (*tp, 0);
+      if (TREE_CODE (decl) == ADDR_EXPR)
+	decl = TREE_OPERAND (decl, 0);
+      if (TREE_CODE (decl) == FUNCTION_DECL)
+	{
+	  if (DECL_BUILT_IN (decl))
+	    return NULL;
+	  cgraph_record_call (data, decl);
+	  walk_tree (&TREE_OPERAND (*tp, 1), record_call_1, data, NULL);
+	  *walk_subtrees = 0;
+	}
+    }
+  return NULL;
+}
+
+/* Create cgraph edges for function calles via BODY.  */
+
+void
+cgraph_create_edges (decl, body)
+     tree decl;
+     tree body;
+{
+  walk_tree (&body, record_call_1, decl, NULL);
+}
+
+/* Analyze the whole compilation unit once it is parsed completely.  */
+
+void
+cgraph_finalize_compilation_unit ()
+{
+  struct cgraph_node *node;
+  struct cgraph_edge *edge;
+
+  /* Collect entry points to the unit.  */
+
+  if (!quiet_flag)
+    fprintf (stderr, "\n\nUnit entry points:");
+
+  for (node = cgraph_nodes; node; node = node->next)
+    {
+      tree decl = node->decl;
+
+      if (!DECL_SAVED_TREE (decl))
+	continue;
+      if ((TREE_PUBLIC (decl) && !DECL_COMDAT (decl) && !DECL_EXTERNAL (decl))
+	  || (DECL_ASSEMBLER_NAME_SET_P (decl)
+	      && TREE_SYMBOL_REFERENCED (DECL_ASSEMBLER_NAME (decl))))
+	{
+          cgraph_mark_needed_node (node, 1);
+	}
+    }
+
+  /*  Propagate reachability flag and lower representation of all reachable
+      functions.  In the future, lowering will introduce new functions and
+      new entry points on the way (by template instantiation and virtual
+      method table generation for instance).  */
+  while (queue)
+    {
+      tree decl = queue->decl;
+
+      node = queue;
+      queue = queue->aux;
+      if (node->lowered || !node->reachable || !DECL_SAVED_TREE (decl))
+	abort ();
+
+      /* At the moment frontend automatically emits all nested functions.  */
+      if (node->nested)
+	{
+	  struct cgraph_node *node2;
+
+	  for (node2 = node->nested; node2; node2 = node2->next_nested)
+	    if (!node2->reachable)
+	      cgraph_mark_needed_node (node2, 0);
+	}
+
+      if (lang_hooks.callgraph.lower_function)
+	(*lang_hooks.callgraph.lower_function) (decl);
+      /* First kill forward declaration so reverse inling works properly.  */
+      cgraph_create_edges (decl, DECL_SAVED_TREE (decl));
+
+      for (edge = node->callees; edge; edge = edge->next_callee)
+	{
+	  if (!edge->callee->reachable)
+            cgraph_mark_needed_node (edge->callee, 0);
+	}
+      node->lowered = true;
+    }
+  if (!quiet_flag)
+    fprintf (stderr, "\n\nReclaiming functions:");
+
+  for (node = cgraph_nodes; node; node = node->next)
+    {
+      tree decl = node->decl;
+
+      if (!node->reachable && DECL_SAVED_TREE (decl))
+	{
+	  DECL_SAVED_TREE (decl) = NULL;
+	  announce_function (decl);
+	}
+    }
+  ggc_collect ();
+}
+
+/* Figure out what functions we want to assemble.  */
+
+static void
+cgraph_mark_functions_to_output ()
+{
+  struct cgraph_node *node;
+
+  /* Figure out functions we want to assemble.  */
+  for (node = cgraph_nodes; node; node = node->next)
+    {
+      tree decl = node->decl;
+
+      if (DECL_SAVED_TREE (decl)
+	  && (node->needed
+	      || (DECL_UNINLINABLE (decl) && node->reachable)
+	      || TREE_SYMBOL_REFERENCED (DECL_ASSEMBLER_NAME (decl)))
+	  && !TREE_ASM_WRITTEN (decl) && !node->origin
+	  && !DECL_EXTERNAL (decl))
+	node->output = 1;
+    }
+}
+
+/* Expand function specified by NODE.  */
+static void
+cgraph_expand_function (node)
+     struct cgraph_node *node;
+{
+  tree decl = node->decl;
+
+  announce_function (decl);
+  if (flag_inline_trees)
+    optimize_inline_calls (decl);
+  (*lang_hooks.callgraph.expand_function) (decl);
+  if (DECL_UNINLINABLE (decl))
+    DECL_SAVED_TREE (decl) = NULL;
+  current_function_decl = NULL;
+}
+
+
+/* Expand all functions that must be output. 
+  
+   Attempt to topologically sort the nodes so function is output when
+   all called functions are already assembled to allow data to be propagated
+   accross the callgraph.  Use stack to get smaller distance between function
+   and it's callees (later we may use more sophisticated algorithm for
+   function reordering, we will likely want to use subsections to make output
+   functions to appear in top-down order, not bottom-up they are assembled).  */
+
+static void
+cgraph_expand_functions ()
+{
+  struct cgraph_node *node, *node2;
+  struct cgraph_node **stack =
+    xcalloc (sizeof (struct cgraph_node *), cgraph_n_nodes);
+  struct cgraph_node **order =
+    xcalloc (sizeof (struct cgraph_node *), cgraph_n_nodes);
+  int stack_size = 0;
+  int order_pos = 0;
+  struct cgraph_edge *edge, last;
+  int i;
+
+  cgraph_mark_functions_to_output ();
+
+  /*  We have to deal with cycles nicely, so use depth first traversal
+      algorithm.  Ignore the fact that some functions won't need to be output
+      and put them into order as well, so we get dependencies right trought inlined
+      functions.  */
+  for (node = cgraph_nodes; node; node = node->next)
+    node->aux = NULL;
+  for (node = cgraph_nodes; node; node = node->next)
+    if (node->output && !node->aux)
+      {
+	node2 = node;
+	if (!node->callers)
+	  node->aux = &last;
+	else
+	  node->aux = node->callers;
+	while (node2)
+	  {
+	    while (node2->aux != &last)
+	      {
+		edge = node2->aux;
+		if (edge->next_caller)
+		  node2->aux = edge->next_caller;
+		else
+		  node2->aux = &last;
+		if (!edge->caller->aux)
+		  {
+		    if (!edge->caller->callers)
+		      edge->caller->aux = &last;
+		    else
+		      edge->caller->aux = edge->caller->callers;
+		    stack[stack_size++] = node2;
+		    node2 = edge->caller;
+		    break;
+		  }
+	      }
+	    if (node2->aux == &last)
+	      {
+		order[order_pos++] = node2;
+		if (stack_size)
+		  node2 = stack[--stack_size];
+		else
+		  node2 = NULL;
+	      }
+	  }
+      }
+  for (i = order_pos - 1; i >=0; i--)
+    {
+      node = order[i];
+      if (node->output)
+	{
+	  if (!node->reachable)
+	    abort ();
+	  node->output = 0;
+	  cgraph_expand_function (node);
+	}
+    }
+  free (stack);
+  free (order);
+}
+
+/* Perform simple optimizations based on callgraph.  */
+
+void
+cgraph_optimize ()
+{
+  struct cgraph_node *node;
+  bool changed = true;
+  struct cgraph_edge *edge;
+
+  if (!quiet_flag)
+    fprintf (stderr, "\n\nAssembling functions:");
+
+  /* Output everything.  
+     ??? Our inline heuristic may decide to not inline functions previously
+     marked as inlinable thus adding new function bodies that must be output.
+     Later we should move all inlining decisions to callgraph code to make
+     this impossible.  */
+  cgraph_expand_functions ();
+  while (changed)
+    {
+      changed = false;
+      for (node = cgraph_nodes; node; node = node->next)
+	{
+	  if (!node->needed)
+	    continue;
+
+	  for (edge = node->callees; edge; edge = edge->next_callee)
+	    if (!edge->callee->needed)
+	      changed = edge->callee->needed = true;
+	}
+    }
+  cgraph_expand_functions ();
+}