[thirdparty/gcc.git] / gcc / cgraphunit.c

/* 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 ();
}
Commit	Line	Data
ae01b312	1	/* Callgraph handling code.
	2	Copyright (C) 2003 Free Software Foundation, Inc.
	3	Contributed by Jan Hubicka
	4
	5	This file is part of GCC.
	6
	7	GCC is free software; you can redistribute it and/or modify it under
	8	the terms of the GNU General Public License as published by the Free
	9	Software Foundation; either version 2, or (at your option) any later
	10	version.
	11
	12	GCC is distributed in the hope that it will be useful, but WITHOUT ANY
	13	WARRANTY; without even the implied warranty of MERCHANTABILITY or
	14	FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
	15	for more details.
	16
	17	You should have received a copy of the GNU General Public License
	18	along with GCC; see the file COPYING. If not, write to the Free
	19	Software Foundation, 59 Temple Place - Suite 330, Boston, MA
	20	02111-1307, USA. */
	21
	22	#include "config.h"
	23	#include "system.h"
	24	#include "coretypes.h"
	25	#include "tm.h"
	26	#include "tree.h"
	27	#include "tree-inline.h"
	28	#include "langhooks.h"
	29	#include "hashtab.h"
	30	#include "toplev.h"
	31	#include "flags.h"
	32	#include "ggc.h"
	33	#include "debug.h"
	34	#include "target.h"
	35	#include "cgraph.h"
	36
	37	static void cgraph_expand_functions PARAMS ((void));
	38	static void cgraph_mark_functions_to_output PARAMS ((void));
	39	static void cgraph_expand_function PARAMS ((struct cgraph_node *));
	40	static tree record_call_1 PARAMS ((tree , int , void *));
	41
	42	/* Analyze function once it is parsed. Set up the local information
	43	available - create cgraph edges for function calles via BODY. */
	44
	45	void
	46	cgraph_finalize_function (decl, body)
	47	tree decl;
	48	tree body ATTRIBUTE_UNUSED;
	49	{
	50	struct cgraph_node *node = cgraph_node (decl);
	51
	52	node->decl = decl;
	53
	54	/* Set TREE_UNINLINABLE flag. */
	55	tree_inlinable_function_p (decl);
	56
	57	(*debug_hooks->deferred_inline_function) (decl);
	58	}
	59
	60	static struct cgraph_node *queue = NULL;
	61
	62	/* Notify finalize_compilation_unit that given node is reachable
	63	or needed. */
	64	void
65	cgraph_mark_needed_node (node, needed)
66	struct cgraph_node *node;
67	int needed;
68	{
69	if (needed)
70	{
71	if (DECL_SAVED_TREE (node->decl))
72	announce_function (node->decl);
73	node->needed = 1;
74	}
75	if (!node->reachable)
76	{
77	node->reachable = 1;
78	if (DECL_SAVED_TREE (node->decl))
79	{
80	node->aux = queue;
81	queue = node;
82	}
83	}
84	}
85
86	/* Walk tree and record all calls. Called via walk_tree. */
87	static tree
88	record_call_1 (tp, walk_subtrees, data)
89	tree *tp;
90	int *walk_subtrees;
91	void *data;
92	{
93	/* Record dereferences to the functions. This makes the functions
94	reachable unconditionally. */
95	if (TREE_CODE (*tp) == ADDR_EXPR)
96	{
97	tree decl = TREE_OPERAND (*tp, 0);
98	if (TREE_CODE (decl) == FUNCTION_DECL)
99	cgraph_mark_needed_node (cgraph_node (decl), 1);
100	}
101	else if (TREE_CODE (*tp) == CALL_EXPR)
102	{
103	tree decl = TREE_OPERAND (*tp, 0);
104	if (TREE_CODE (decl) == ADDR_EXPR)
105	decl = TREE_OPERAND (decl, 0);
106	if (TREE_CODE (decl) == FUNCTION_DECL)
107	{
108	if (DECL_BUILT_IN (decl))
109	return NULL;
110	cgraph_record_call (data, decl);
111	walk_tree (&TREE_OPERAND (*tp, 1), record_call_1, data, NULL);
112	*walk_subtrees = 0;
113	}
114	}
115	return NULL;
116	}
117
118	/* Create cgraph edges for function calles via BODY. */
119
120	void
121	cgraph_create_edges (decl, body)
122	tree decl;
123	tree body;
124	{
125	walk_tree (&body, record_call_1, decl, NULL);
126	}
127
128	/* Analyze the whole compilation unit once it is parsed completely. */
129
130	void
131	cgraph_finalize_compilation_unit ()
132	{
133	struct cgraph_node *node;
134	struct cgraph_edge *edge;
135
136	/* Collect entry points to the unit. */
137
138	if (!quiet_flag)
139	fprintf (stderr, "\n\nUnit entry points:");
140
141	for (node = cgraph_nodes; node; node = node->next)
142	{
143	tree decl = node->decl;
144
145	if (!DECL_SAVED_TREE (decl))
146	continue;
147	if ((TREE_PUBLIC (decl) && !DECL_COMDAT (decl) && !DECL_EXTERNAL (decl))
148	\|\| (DECL_ASSEMBLER_NAME_SET_P (decl)
149	&& TREE_SYMBOL_REFERENCED (DECL_ASSEMBLER_NAME (decl))))
150	{
151	cgraph_mark_needed_node (node, 1);
152	}
153	}
154
155	/* Propagate reachability flag and lower representation of all reachable
156	functions. In the future, lowering will introduce new functions and
157	new entry points on the way (by template instantiation and virtual
158	method table generation for instance). */
159	while (queue)
160	{
161	tree decl = queue->decl;
162
163	node = queue;
164	queue = queue->aux;
165	if (node->lowered \|\| !node->reachable \|\| !DECL_SAVED_TREE (decl))
166	abort ();
167
168	/* At the moment frontend automatically emits all nested functions. */
169	if (node->nested)
170	{
171	struct cgraph_node *node2;
172
173	for (node2 = node->nested; node2; node2 = node2->next_nested)
174	if (!node2->reachable)
175	cgraph_mark_needed_node (node2, 0);
176	}
177
178	if (lang_hooks.callgraph.lower_function)
179	(*lang_hooks.callgraph.lower_function) (decl);
180	/* First kill forward declaration so reverse inling works properly. */
181	cgraph_create_edges (decl, DECL_SAVED_TREE (decl));
182
183	for (edge = node->callees; edge; edge = edge->next_callee)
184	{
185	if (!edge->callee->reachable)
186	cgraph_mark_needed_node (edge->callee, 0);
187	}
188	node->lowered = true;
189	}
190	if (!quiet_flag)
191	fprintf (stderr, "\n\nReclaiming functions:");
192
193	for (node = cgraph_nodes; node; node = node->next)
194	{
195	tree decl = node->decl;
196
197	if (!node->reachable && DECL_SAVED_TREE (decl))
198	{
199	DECL_SAVED_TREE (decl) = NULL;
200	announce_function (decl);
201	}
202	}
203	ggc_collect ();
204	}
205
206	/* Figure out what functions we want to assemble. */
207
208	static void
209	cgraph_mark_functions_to_output ()
210	{
211	struct cgraph_node *node;
212
213	/* Figure out functions we want to assemble. */
214	for (node = cgraph_nodes; node; node = node->next)
215	{
216	tree decl = node->decl;
217
218	if (DECL_SAVED_TREE (decl)
219	&& (node->needed
220	\|\| (DECL_UNINLINABLE (decl) && node->reachable)
221	\|\| TREE_SYMBOL_REFERENCED (DECL_ASSEMBLER_NAME (decl)))
222	&& !TREE_ASM_WRITTEN (decl) && !node->origin
223	&& !DECL_EXTERNAL (decl))
224	node->output = 1;
225	}
226	}
227
228	/* Expand function specified by NODE. */
229	static void
230	cgraph_expand_function (node)
231	struct cgraph_node *node;
232	{
233	tree decl = node->decl;
234
235	announce_function (decl);
236	if (flag_inline_trees)
237	optimize_inline_calls (decl);
238	(*lang_hooks.callgraph.expand_function) (decl);
239	if (DECL_UNINLINABLE (decl))
240	DECL_SAVED_TREE (decl) = NULL;
241	current_function_decl = NULL;
242	}
243
244
245	/* Expand all functions that must be output.
246
247	Attempt to topologically sort the nodes so function is output when
248	all called functions are already assembled to allow data to be propagated
249	accross the callgraph. Use stack to get smaller distance between function
250	and it's callees (later we may use more sophisticated algorithm for
251	function reordering, we will likely want to use subsections to make output
252	functions to appear in top-down order, not bottom-up they are assembled). */
253
254	static void
255	cgraph_expand_functions ()
256	{
257	struct cgraph_node node, node2;
258	struct cgraph_node **stack =
259	xcalloc (sizeof (struct cgraph_node *), cgraph_n_nodes);
260	struct cgraph_node **order =
261	xcalloc (sizeof (struct cgraph_node *), cgraph_n_nodes);
262	int stack_size = 0;
263	int order_pos = 0;
264	struct cgraph_edge *edge, last;
265	int i;
266
267	cgraph_mark_functions_to_output ();
268
269	/* We have to deal with cycles nicely, so use depth first traversal
270	algorithm. Ignore the fact that some functions won't need to be output
271	and put them into order as well, so we get dependencies right trought inlined
272	functions. */
273	for (node = cgraph_nodes; node; node = node->next)
274	node->aux = NULL;
275	for (node = cgraph_nodes; node; node = node->next)
276	if (node->output && !node->aux)
277	{
278	node2 = node;
279	if (!node->callers)
280	node->aux = &last;
281	else
282	node->aux = node->callers;
283	while (node2)
284	{
285	while (node2->aux != &last)
286	{
287	edge = node2->aux;
288	if (edge->next_caller)
289	node2->aux = edge->next_caller;
290	else
291	node2->aux = &last;
292	if (!edge->caller->aux)
293	{
294	if (!edge->caller->callers)
295	edge->caller->aux = &last;
296	else
297	edge->caller->aux = edge->caller->callers;
298	stack[stack_size++] = node2;
299	node2 = edge->caller;
300	break;
301	}
302	}
303	if (node2->aux == &last)
304	{
305	order[order_pos++] = node2;
306	if (stack_size)
307	node2 = stack[--stack_size];
308	else
309	node2 = NULL;
310	}
311	}
312	}
313	for (i = order_pos - 1; i >=0; i--)
314	{
315	node = order[i];
316	if (node->output)
317	{
318	if (!node->reachable)
319	abort ();
320	node->output = 0;
321	cgraph_expand_function (node);
322	}
323	}
324	free (stack);
325	free (order);
326	}
327
328	/* Perform simple optimizations based on callgraph. */
329
330	void
331	cgraph_optimize ()
332	{
333	struct cgraph_node *node;
334	bool changed = true;
335	struct cgraph_edge *edge;
336
337	if (!quiet_flag)
338	fprintf (stderr, "\n\nAssembling functions:");
339
340	/* Output everything.
341	??? Our inline heuristic may decide to not inline functions previously
342	marked as inlinable thus adding new function bodies that must be output.
343	Later we should move all inlining decisions to callgraph code to make
344	this impossible. */
345	cgraph_expand_functions ();
346	while (changed)
347	{
348	changed = false;
349	for (node = cgraph_nodes; node; node = node->next)
350	{
351	if (!node->needed)
352	continue;
353
354	for (edge = node->callees; edge; edge = edge->next_callee)
355	if (!edge->callee->needed)
356	changed = edge->callee->needed = true;
357	}
358	}
359	cgraph_expand_functions ();
360	}