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

/* Callgraph construction.
   Copyright (C) 2003, 2004, 2005, 2006, 2007, 2008, 2009
   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 3, 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 COPYING3.  If not see
<http://www.gnu.org/licenses/>.  */

#include "config.h"
#include "system.h"
#include "coretypes.h"
#include "tm.h"
#include "tree.h"
#include "tree-flow.h"
#include "langhooks.h"
#include "pointer-set.h"
#include "cgraph.h"
#include "intl.h"
#include "gimple.h"
#include "tree-pass.h"

/* Walk tree and record all calls and references to functions/variables.
   Called via walk_tree: TP is pointer to tree to be examined.  */

static tree
record_reference (tree *tp, int *walk_subtrees, void *data ATTRIBUTE_UNUSED)
{
  tree t = *tp;
  tree decl;

  switch (TREE_CODE (t))
    {
    case VAR_DECL:
      if (TREE_STATIC (t) || DECL_EXTERNAL (t))
	{
	  varpool_mark_needed_node (varpool_node (t));
	  if (lang_hooks.callgraph.analyze_expr)
	    return lang_hooks.callgraph.analyze_expr (tp, walk_subtrees);
	}
      break;

    case FDESC_EXPR:
    case ADDR_EXPR:
      /* Record dereferences to the functions.  This makes the
	 functions reachable unconditionally.  */
      decl = TREE_OPERAND (*tp, 0);
      if (TREE_CODE (decl) == FUNCTION_DECL)
	cgraph_mark_address_taken_node (cgraph_node (decl));
      break;

    default:
      /* Save some cycles by not walking types and declaration as we
	 won't find anything useful there anyway.  */
      if (IS_TYPE_OR_DECL_P (*tp))
	{
	  *walk_subtrees = 0;
	  break;
	}

      if ((unsigned int) TREE_CODE (t) >= LAST_AND_UNUSED_TREE_CODE)
	return lang_hooks.callgraph.analyze_expr (tp, walk_subtrees);
      break;
    }

  return NULL_TREE;
}

/* Reset inlining information of all incoming call edges of NODE.  */

void
reset_inline_failed (struct cgraph_node *node)
{
  struct cgraph_edge *e;

  for (e = node->callers; e; e = e->next_caller)
    {
      e->callee->global.inlined_to = NULL;
      if (!node->analyzed)
	e->inline_failed = CIF_BODY_NOT_AVAILABLE;
      else if (node->local.redefined_extern_inline)
	e->inline_failed = CIF_REDEFINED_EXTERN_INLINE;
      else if (!node->local.inlinable)
	e->inline_failed = CIF_FUNCTION_NOT_INLINABLE;
      else if (e->call_stmt_cannot_inline_p)
	e->inline_failed = CIF_MISMATCHED_ARGUMENTS;
      else
	e->inline_failed = CIF_FUNCTION_NOT_CONSIDERED;
    }
}

/* Computes the frequency of the call statement so that it can be stored in
   cgraph_edge.  BB is the basic block of the call statement.  */
int
compute_call_stmt_bb_frequency (tree decl, basic_block bb)
{
  int entry_freq = ENTRY_BLOCK_PTR->frequency;
  int freq = bb->frequency;

  if (profile_status_for_function (DECL_STRUCT_FUNCTION (decl)) == PROFILE_ABSENT)
    return CGRAPH_FREQ_BASE;

  if (!entry_freq)
    entry_freq = 1, freq++;

  freq = freq * CGRAPH_FREQ_BASE / entry_freq;
  if (freq > CGRAPH_FREQ_MAX)
    freq = CGRAPH_FREQ_MAX;

  return freq;
}

/* Create cgraph edges for function calls.
   Also look for functions and variables having addresses taken.  */

static unsigned int
build_cgraph_edges (void)
{
  basic_block bb;
  struct cgraph_node *node = cgraph_node (current_function_decl);
  struct pointer_set_t *visited_nodes = pointer_set_create ();
  gimple_stmt_iterator gsi;
  tree step;

  /* Create the callgraph edges and record the nodes referenced by the function.
     body.  */
  FOR_EACH_BB (bb)
    for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
      {
	gimple stmt = gsi_stmt (gsi);
	tree decl;

	if (is_gimple_call (stmt) && (decl = gimple_call_fndecl (stmt)))
	  {
	    size_t i;
	    size_t n = gimple_call_num_args (stmt);
	    cgraph_create_edge (node, cgraph_node (decl), stmt,
				bb->count, compute_call_stmt_bb_frequency (current_function_decl, bb),
				bb->loop_depth);
	    for (i = 0; i < n; i++)
	      walk_tree (gimple_call_arg_ptr (stmt, i), record_reference,
			 node, visited_nodes);
	    if (gimple_call_lhs (stmt))
	      walk_tree (gimple_call_lhs_ptr (stmt), record_reference, node,
		         visited_nodes);
	  }
	else
	  {
	    struct walk_stmt_info wi;
	    memset (&wi, 0, sizeof (wi));
	    wi.info = node;
	    wi.pset = visited_nodes;
	    walk_gimple_op (stmt, record_reference, &wi);
	    if (gimple_code (stmt) == GIMPLE_OMP_PARALLEL
		&& gimple_omp_parallel_child_fn (stmt))
	      {
		tree fn = gimple_omp_parallel_child_fn (stmt);
		cgraph_mark_needed_node (cgraph_node (fn));
	      }
	    if (gimple_code (stmt) == GIMPLE_OMP_TASK)
	      {
		tree fn = gimple_omp_task_child_fn (stmt);
		if (fn)
		  cgraph_mark_needed_node (cgraph_node (fn));
		fn = gimple_omp_task_copy_fn (stmt);
		if (fn)
		  cgraph_mark_needed_node (cgraph_node (fn));
	      }
	  }
      }

  /* Look for initializers of constant variables and private statics.  */
  for (step = cfun->local_decls;
       step;
       step = TREE_CHAIN (step))
    {
      tree decl = TREE_VALUE (step);
      if (TREE_CODE (decl) == VAR_DECL
	  && (TREE_STATIC (decl) && !DECL_EXTERNAL (decl)))
	varpool_finalize_decl (decl);
      else if (TREE_CODE (decl) == VAR_DECL && DECL_INITIAL (decl))
	walk_tree (&DECL_INITIAL (decl), record_reference, node, visited_nodes);
    }

  pointer_set_destroy (visited_nodes);
  return 0;
}

struct gimple_opt_pass pass_build_cgraph_edges =
{
 {
  GIMPLE_PASS,
  NULL,					/* name */
  NULL,					/* gate */
  build_cgraph_edges,			/* execute */
  NULL,					/* sub */
  NULL,					/* next */
  0,					/* static_pass_number */
  TV_NONE,				/* tv_id */
  PROP_cfg,				/* properties_required */
  0,					/* properties_provided */
  0,					/* properties_destroyed */
  0,					/* todo_flags_start */
  0					/* todo_flags_finish */
 }
};

/* Record references to functions and other variables present in the
   initial value of DECL, a variable.  */

void
record_references_in_initializer (tree decl)
{
  struct pointer_set_t *visited_nodes = pointer_set_create ();
  walk_tree (&DECL_INITIAL (decl), record_reference, NULL, visited_nodes);
  pointer_set_destroy (visited_nodes);
}

/* Rebuild cgraph edges for current function node.  This needs to be run after
   passes that don't update the cgraph.  */

unsigned int
rebuild_cgraph_edges (void)
{
  basic_block bb;
  struct cgraph_node *node = cgraph_node (current_function_decl);
  gimple_stmt_iterator gsi;

  cgraph_node_remove_callees (node);

  node->count = ENTRY_BLOCK_PTR->count;

  FOR_EACH_BB (bb)
    for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
      {
	gimple stmt = gsi_stmt (gsi);
	tree decl;

	if (is_gimple_call (stmt) && (decl = gimple_call_fndecl (stmt)))
	  cgraph_create_edge (node, cgraph_node (decl), stmt,
			      bb->count,
			      compute_call_stmt_bb_frequency
			        (current_function_decl, bb),
			      bb->loop_depth);

      }
  gcc_assert (!node->global.inlined_to);

  return 0;
}

struct gimple_opt_pass pass_rebuild_cgraph_edges =
{
 {
  GIMPLE_PASS,
  NULL,					/* name */
  NULL,					/* gate */
  rebuild_cgraph_edges,			/* execute */
  NULL,					/* sub */
  NULL,					/* next */
  0,					/* static_pass_number */
  TV_NONE,				/* tv_id */
  PROP_cfg,				/* properties_required */
  0,					/* properties_provided */
  0,					/* properties_destroyed */
  0,					/* todo_flags_start */
  0,					/* todo_flags_finish */
 }
};


static unsigned int
remove_cgraph_callee_edges (void)
{
  cgraph_node_remove_callees (cgraph_node (current_function_decl));
  return 0;
}

struct gimple_opt_pass pass_remove_cgraph_callee_edges =
{
 {
  GIMPLE_PASS,
  NULL,					/* name */
  NULL,					/* gate */
  remove_cgraph_callee_edges,		/* execute */
  NULL,					/* sub */
  NULL,					/* next */
  0,					/* static_pass_number */
  TV_NONE,				/* tv_id */
  0,					/* properties_required */
  0,					/* properties_provided */
  0,					/* properties_destroyed */
  0,					/* todo_flags_start */
  0,					/* todo_flags_finish */
 }
};
Commit	Line	Data
e7c352d1	1	/* Callgraph construction.
0b1615c1	2	Copyright (C) 2003, 2004, 2005, 2006, 2007, 2008, 2009
75a70cf9	3	Free Software Foundation, Inc.
e7c352d1	4	Contributed by Jan Hubicka
	5
	6	This file is part of GCC.
	7
	8	GCC is free software; you can redistribute it and/or modify it under
	9	the terms of the GNU General Public License as published by the Free
8c4c00c1	10	Software Foundation; either version 3, or (at your option) any later
e7c352d1	11	version.
	12
	13	GCC is distributed in the hope that it will be useful, but WITHOUT ANY
	14	WARRANTY; without even the implied warranty of MERCHANTABILITY or
	15	FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
	16	for more details.
	17
	18	You should have received a copy of the GNU General Public License
8c4c00c1	19	along with GCC; see the file COPYING3. If not see
8c4c00c1	20	<http://www.gnu.org/licenses/>. */
e7c352d1	21
	22	#include "config.h"
	23	#include "system.h"
	24	#include "coretypes.h"
	25	#include "tm.h"
	26	#include "tree.h"
	27	#include "tree-flow.h"
	28	#include "langhooks.h"
	29	#include "pointer-set.h"
	30	#include "cgraph.h"
	31	#include "intl.h"
75a70cf9	32	#include "gimple.h"
e7c352d1	33	#include "tree-pass.h"
	34
	35	/* Walk tree and record all calls and references to functions/variables.
	36	Called via walk_tree: TP is pointer to tree to be examined. */
	37
	38	static tree
e83c4efa	39	record_reference (tree tp, int walk_subtrees, void *data ATTRIBUTE_UNUSED)
e7c352d1	40	{
e7c352d1	41	tree t = *tp;
6329636b	42	tree decl;
e7c352d1	43
	44	switch (TREE_CODE (t))
	45	{
	46	case VAR_DECL:
	47	if (TREE_STATIC (t) \|\| DECL_EXTERNAL (t))
	48	{
	49	varpool_mark_needed_node (varpool_node (t));
	50	if (lang_hooks.callgraph.analyze_expr)
e83c4efa	51	return lang_hooks.callgraph.analyze_expr (tp, walk_subtrees);
e7c352d1	52	}
	53	break;
	54
	55	case FDESC_EXPR:
	56	case ADDR_EXPR:
6329636b	57	/* Record dereferences to the functions. This makes the
	58	functions reachable unconditionally. */
	59	decl = TREE_OPERAND (*tp, 0);
	60	if (TREE_CODE (decl) == FUNCTION_DECL)
2cb64f78	61	cgraph_mark_address_taken_node (cgraph_node (decl));
e7c352d1	62	break;
	63
	64	default:
	65	/* Save some cycles by not walking types and declaration as we
	66	won't find anything useful there anyway. */
	67	if (IS_TYPE_OR_DECL_P (*tp))
	68	{
	69	*walk_subtrees = 0;
	70	break;
	71	}
	72
	73	if ((unsigned int) TREE_CODE (t) >= LAST_AND_UNUSED_TREE_CODE)
e83c4efa	74	return lang_hooks.callgraph.analyze_expr (tp, walk_subtrees);
e7c352d1	75	break;
	76	}
	77
	78	return NULL_TREE;
	79	}
	80
7bfefa9d	81	/* Reset inlining information of all incoming call edges of NODE. */
	82
	83	void
	84	reset_inline_failed (struct cgraph_node *node)
	85	{
	86	struct cgraph_edge *e;
	87
	88	for (e = node->callers; e; e = e->next_caller)
	89	{
	90	e->callee->global.inlined_to = NULL;
	91	if (!node->analyzed)
	92	e->inline_failed = CIF_BODY_NOT_AVAILABLE;
	93	else if (node->local.redefined_extern_inline)
	94	e->inline_failed = CIF_REDEFINED_EXTERN_INLINE;
	95	else if (!node->local.inlinable)
	96	e->inline_failed = CIF_FUNCTION_NOT_INLINABLE;
	97	else if (e->call_stmt_cannot_inline_p)
	98	e->inline_failed = CIF_MISMATCHED_ARGUMENTS;
	99	else
	100	e->inline_failed = CIF_FUNCTION_NOT_CONSIDERED;
	101	}
	102	}
	103
f8daee9b	104	/* Computes the frequency of the call statement so that it can be stored in
	105	cgraph_edge. BB is the basic block of the call statement. */
	106	int
ccf4ab6b	107	compute_call_stmt_bb_frequency (tree decl, basic_block bb)
f8daee9b	108	{
f8daee9b	109	int entry_freq = ENTRY_BLOCK_PTR->frequency;
9f694a82	110	int freq = bb->frequency;
f8daee9b	111
ccf4ab6b	112	if (profile_status_for_function (DECL_STRUCT_FUNCTION (decl)) == PROFILE_ABSENT)
	113	return CGRAPH_FREQ_BASE;
	114
f8daee9b	115	if (!entry_freq)
9f694a82	116	entry_freq = 1, freq++;
f8daee9b	117
9f694a82	118	freq = freq * CGRAPH_FREQ_BASE / entry_freq;
f8daee9b	119	if (freq > CGRAPH_FREQ_MAX)
	120	freq = CGRAPH_FREQ_MAX;
	121
	122	return freq;
	123	}
	124
e7c352d1	125	/* Create cgraph edges for function calls.
	126	Also look for functions and variables having addresses taken. */
	127
	128	static unsigned int
	129	build_cgraph_edges (void)
	130	{
	131	basic_block bb;
	132	struct cgraph_node *node = cgraph_node (current_function_decl);
	133	struct pointer_set_t *visited_nodes = pointer_set_create ();
75a70cf9	134	gimple_stmt_iterator gsi;
e7c352d1	135	tree step;
	136
	137	/* Create the callgraph edges and record the nodes referenced by the function.
	138	body. */
	139	FOR_EACH_BB (bb)
75a70cf9	140	for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
e7c352d1	141	{
75a70cf9	142	gimple stmt = gsi_stmt (gsi);
e7c352d1	143	tree decl;
e7c352d1	144
75a70cf9	145	if (is_gimple_call (stmt) && (decl = gimple_call_fndecl (stmt)))
e7c352d1	146	{
75a70cf9	147	size_t i;
75a70cf9	148	size_t n = gimple_call_num_args (stmt);
e7c352d1	149	cgraph_create_edge (node, cgraph_node (decl), stmt,
ccf4ab6b	150	bb->count, compute_call_stmt_bb_frequency (current_function_decl, bb),
e7c352d1	151	bb->loop_depth);
c2f47e15	152	for (i = 0; i < n; i++)
75a70cf9	153	walk_tree (gimple_call_arg_ptr (stmt, i), record_reference,
	154	node, visited_nodes);
	155	if (gimple_call_lhs (stmt))
	156	walk_tree (gimple_call_lhs_ptr (stmt), record_reference, node,
	157	visited_nodes);
e7c352d1	158	}
e7c352d1	159	else
75a70cf9	160	{
	161	struct walk_stmt_info wi;
	162	memset (&wi, 0, sizeof (wi));
	163	wi.info = node;
	164	wi.pset = visited_nodes;
	165	walk_gimple_op (stmt, record_reference, &wi);
	166	if (gimple_code (stmt) == GIMPLE_OMP_PARALLEL
	167	&& gimple_omp_parallel_child_fn (stmt))
	168	{
	169	tree fn = gimple_omp_parallel_child_fn (stmt);
	170	cgraph_mark_needed_node (cgraph_node (fn));
	171	}
	172	if (gimple_code (stmt) == GIMPLE_OMP_TASK)
	173	{
	174	tree fn = gimple_omp_task_child_fn (stmt);
	175	if (fn)
	176	cgraph_mark_needed_node (cgraph_node (fn));
	177	fn = gimple_omp_task_copy_fn (stmt);
	178	if (fn)
	179	cgraph_mark_needed_node (cgraph_node (fn));
	180	}
	181	}
e7c352d1	182	}
	183
	184	/* Look for initializers of constant variables and private statics. */
edb7afe8	185	for (step = cfun->local_decls;
e7c352d1	186	step;
	187	step = TREE_CHAIN (step))
	188	{
	189	tree decl = TREE_VALUE (step);
	190	if (TREE_CODE (decl) == VAR_DECL
6329636b	191	&& (TREE_STATIC (decl) && !DECL_EXTERNAL (decl)))
e7c352d1	192	varpool_finalize_decl (decl);
	193	else if (TREE_CODE (decl) == VAR_DECL && DECL_INITIAL (decl))
	194	walk_tree (&DECL_INITIAL (decl), record_reference, node, visited_nodes);
	195	}
	196
	197	pointer_set_destroy (visited_nodes);
e7c352d1	198	return 0;
	199	}
	200
20099e35	201	struct gimple_opt_pass pass_build_cgraph_edges =
e7c352d1	202	{
20099e35	203	{
20099e35	204	GIMPLE_PASS,
e7c352d1	205	NULL, /* name */
	206	NULL, /* gate */
	207	build_cgraph_edges, /* execute */
	208	NULL, /* sub */
	209	NULL, /* next */
	210	0, /* static_pass_number */
0b1615c1	211	TV_NONE, /* tv_id */
e7c352d1	212	PROP_cfg, /* properties_required */
	213	0, /* properties_provided */
	214	0, /* properties_destroyed */
	215	0, /* todo_flags_start */
20099e35	216	0 /* todo_flags_finish */
20099e35	217	}
e7c352d1	218	};
	219
	220	/* Record references to functions and other variables present in the
	221	initial value of DECL, a variable. */
	222
	223	void
	224	record_references_in_initializer (tree decl)
	225	{
	226	struct pointer_set_t *visited_nodes = pointer_set_create ();
	227	walk_tree (&DECL_INITIAL (decl), record_reference, NULL, visited_nodes);
	228	pointer_set_destroy (visited_nodes);
	229	}
	230
	231	/* Rebuild cgraph edges for current function node. This needs to be run after
	232	passes that don't update the cgraph. */
	233
79acaae1	234	unsigned int
e7c352d1	235	rebuild_cgraph_edges (void)
	236	{
	237	basic_block bb;
	238	struct cgraph_node *node = cgraph_node (current_function_decl);
75a70cf9	239	gimple_stmt_iterator gsi;
e7c352d1	240
	241	cgraph_node_remove_callees (node);
	242
	243	node->count = ENTRY_BLOCK_PTR->count;
	244
	245	FOR_EACH_BB (bb)
75a70cf9	246	for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
e7c352d1	247	{
75a70cf9	248	gimple stmt = gsi_stmt (gsi);
e7c352d1	249	tree decl;
e7c352d1	250
75a70cf9	251	if (is_gimple_call (stmt) && (decl = gimple_call_fndecl (stmt)))
f8daee9b	252	cgraph_create_edge (node, cgraph_node (decl), stmt,
ccf4ab6b	253	bb->count,
	254	compute_call_stmt_bb_frequency
	255	(current_function_decl, bb),
f8daee9b	256	bb->loop_depth);
75a70cf9	257
e7c352d1	258	}
e7c352d1	259	gcc_assert (!node->global.inlined_to);
69428266	260
e7c352d1	261	return 0;
	262	}
	263
20099e35	264	struct gimple_opt_pass pass_rebuild_cgraph_edges =
e7c352d1	265	{
20099e35	266	{
20099e35	267	GIMPLE_PASS,
e7c352d1	268	NULL, /* name */
	269	NULL, /* gate */
	270	rebuild_cgraph_edges, /* execute */
	271	NULL, /* sub */
	272	NULL, /* next */
	273	0, /* static_pass_number */
0b1615c1	274	TV_NONE, /* tv_id */
e7c352d1	275	PROP_cfg, /* properties_required */
	276	0, /* properties_provided */
	277	0, /* properties_destroyed */
	278	0, /* todo_flags_start */
	279	0, /* todo_flags_finish */
20099e35	280	}
e7c352d1	281	};
ba3a7ba0	282
	283
	284	static unsigned int
	285	remove_cgraph_callee_edges (void)
	286	{
	287	cgraph_node_remove_callees (cgraph_node (current_function_decl));
	288	return 0;
	289	}
	290
	291	struct gimple_opt_pass pass_remove_cgraph_callee_edges =
	292	{
	293	{
	294	GIMPLE_PASS,
	295	NULL, /* name */
	296	NULL, /* gate */
	297	remove_cgraph_callee_edges, /* execute */
	298	NULL, /* sub */
	299	NULL, /* next */
	300	0, /* static_pass_number */
0b1615c1	301	TV_NONE, /* tv_id */
ba3a7ba0	302	0, /* properties_required */
	303	0, /* properties_provided */
	304	0, /* properties_destroyed */
	305	0, /* todo_flags_start */
	306	0, /* todo_flags_finish */
	307	}
	308	};