1 /* Callgraph handling code.
2 Copyright (C) 2003 Free Software Foundation, Inc.
3 Contributed by Jan Hubicka
5 This file is part of GCC.
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
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
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
24 #include "coretypes.h"
27 #include "langhooks.h"
39 /* Hash table used to convert declarations into nodes. */
40 static GTY((param_is (struct cgraph_node))) htab_t cgraph_hash;
42 /* The linked list of cgraph nodes. */
43 struct cgraph_node *cgraph_nodes;
45 /* Queue of cgraph nodes scheduled to be lowered. */
46 struct cgraph_node *cgraph_nodes_queue;
48 /* Number of nodes in existence. */
51 /* Maximal uid used in cgraph nodes. */
54 /* Set when whole unit has been analyzed so we can access global info. */
55 bool cgraph_global_info_ready = false;
57 /* Hash table used to convert declarations into nodes. */
58 static GTY((param_is (struct cgraph_varpool_node))) htab_t cgraph_varpool_hash;
60 /* Queue of cgraph nodes scheduled to be lowered and output. */
61 struct cgraph_varpool_node *cgraph_varpool_nodes_queue;
63 /* Number of nodes in existence. */
64 int cgraph_varpool_n_nodes;
66 /* The linked list of cgraph varpool nodes. */
67 static GTY(()) struct cgraph_varpool_node *cgraph_varpool_nodes;
69 static struct cgraph_edge *create_edge (struct cgraph_node *,
70 struct cgraph_node *);
71 static hashval_t hash_node (const void *);
72 static int eq_node (const void *, const void *);
74 /* Returns a hash code for P. */
77 hash_node (const void *p)
80 IDENTIFIER_HASH_VALUE (DECL_ASSEMBLER_NAME
81 (((struct cgraph_node *) p)->decl)));
84 /* Returns nonzero if P1 and P2 are equal. */
87 eq_node (const void *p1, const void *p2)
89 return ((DECL_ASSEMBLER_NAME (((struct cgraph_node *) p1)->decl)) ==
93 /* Return cgraph node assigned to DECL. Create new one when needed. */
95 cgraph_node (tree decl)
97 struct cgraph_node *node;
98 struct cgraph_node **slot;
100 if (TREE_CODE (decl) != FUNCTION_DECL)
104 cgraph_hash = htab_create_ggc (10, hash_node, eq_node, NULL);
106 slot = (struct cgraph_node **)
107 htab_find_slot_with_hash (cgraph_hash, DECL_ASSEMBLER_NAME (decl),
108 IDENTIFIER_HASH_VALUE
109 (DECL_ASSEMBLER_NAME (decl)), 1);
112 node = ggc_alloc_cleared (sizeof (*node));
114 node->next = cgraph_nodes;
115 node->uid = cgraph_max_uid++;
117 cgraph_nodes->previous = node;
118 node->previous = NULL;
122 if (DECL_CONTEXT (decl) && TREE_CODE (DECL_CONTEXT (decl)) == FUNCTION_DECL)
124 node->origin = cgraph_node (DECL_CONTEXT (decl));
125 node->next_nested = node->origin->nested;
126 node->origin->nested = node;
131 /* Try to find existing function for identifier ID. */
133 cgraph_node_for_identifier (tree id)
135 struct cgraph_node **slot;
137 if (TREE_CODE (id) != IDENTIFIER_NODE)
143 slot = (struct cgraph_node **)
144 htab_find_slot_with_hash (cgraph_hash, id,
145 IDENTIFIER_HASH_VALUE (id), 0);
151 /* Create edge from CALLER to CALLEE in the cgraph. */
153 static struct cgraph_edge *
154 create_edge (struct cgraph_node *caller, struct cgraph_node *callee)
156 struct cgraph_edge *edge = ggc_alloc (sizeof (struct cgraph_edge));
157 struct cgraph_edge *edge2;
159 edge->inline_call = false;
160 /* At the moment we don't associate calls with specific CALL_EXPRs
161 as we probably ought to, so we must preserve inline_call flags to
162 be the same in all copies of the same edge. */
163 if (cgraph_global_info_ready)
164 for (edge2 = caller->callees; edge2; edge2 = edge2->next_callee)
165 if (edge2->callee == callee)
167 edge->inline_call = edge2->inline_call;
171 edge->caller = caller;
172 edge->callee = callee;
173 edge->next_caller = callee->callers;
174 edge->next_callee = caller->callees;
175 caller->callees = edge;
176 callee->callers = edge;
180 /* Remove the edge from CALLER to CALLEE in the cgraph. */
183 cgraph_remove_edge (struct cgraph_node *caller, struct cgraph_node *callee)
185 struct cgraph_edge **edge, **edge2;
187 for (edge = &callee->callers; *edge && (*edge)->caller != caller;
188 edge = &((*edge)->next_caller))
192 *edge = (*edge)->next_caller;
193 for (edge2 = &caller->callees; *edge2 && (*edge2)->callee != callee;
194 edge2 = &(*edge2)->next_callee)
198 *edge2 = (*edge2)->next_callee;
201 /* Remove the node from cgraph. */
204 cgraph_remove_node (struct cgraph_node *node)
207 while (node->callers)
208 cgraph_remove_edge (node->callers->caller, node);
209 while (node->callees)
210 cgraph_remove_edge (node, node->callees->callee);
212 cgraph_remove_node (node->nested);
215 struct cgraph_node **node2 = &node->origin->nested;
217 while (*node2 != node)
218 node2 = &(*node2)->next_nested;
219 *node2 = node->next_nested;
222 node->previous->next = node->next;
226 node->next->previous = node->previous;
227 DECL_SAVED_TREE (node->decl) = NULL;
229 htab_find_slot_with_hash (cgraph_hash, DECL_ASSEMBLER_NAME (node->decl),
230 IDENTIFIER_HASH_VALUE (DECL_ASSEMBLER_NAME
232 htab_clear_slot (cgraph_hash, slot);
233 /* Do not free the structure itself so the walk over chain can continue. */
236 /* Notify finalize_compilation_unit that given node is reachable. */
239 cgraph_mark_reachable_node (struct cgraph_node *node)
241 if (!node->reachable && node->local.finalized)
243 notice_global_symbol (node->decl);
246 node->next_needed = cgraph_nodes_queue;
247 cgraph_nodes_queue = node;
249 /* At the moment frontend automatically emits all nested functions. */
252 struct cgraph_node *node2;
254 for (node2 = node->nested; node2; node2 = node2->next_nested)
255 if (!node2->reachable)
256 cgraph_mark_reachable_node (node2);
261 /* Likewise indicate that a node is needed, i.e. reachable via some
265 cgraph_mark_needed_node (struct cgraph_node *node)
268 cgraph_mark_reachable_node (node);
271 /* Record call from CALLER to CALLEE */
274 cgraph_record_call (tree caller, tree callee)
276 return create_edge (cgraph_node (caller), cgraph_node (callee));
280 cgraph_remove_call (tree caller, tree callee)
282 cgraph_remove_edge (cgraph_node (caller), cgraph_node (callee));
285 /* Return true when CALLER_DECL calls CALLEE_DECL. */
288 cgraph_calls_p (tree caller_decl, tree callee_decl)
290 struct cgraph_node *caller = cgraph_node (caller_decl);
291 struct cgraph_node *callee = cgraph_node (callee_decl);
292 struct cgraph_edge *edge;
294 for (edge = callee->callers; edge && (edge)->caller != caller;
295 edge = (edge->next_caller))
300 /* Return local info for the compiled function. */
302 struct cgraph_local_info *
303 cgraph_local_info (tree decl)
305 struct cgraph_node *node;
306 if (TREE_CODE (decl) != FUNCTION_DECL)
308 node = cgraph_node (decl);
312 /* Return local info for the compiled function. */
314 struct cgraph_global_info *
315 cgraph_global_info (tree decl)
317 struct cgraph_node *node;
318 if (TREE_CODE (decl) != FUNCTION_DECL || !cgraph_global_info_ready)
320 node = cgraph_node (decl);
321 return &node->global;
324 /* Return local info for the compiled function. */
326 struct cgraph_rtl_info *
327 cgraph_rtl_info (tree decl)
329 struct cgraph_node *node;
330 if (TREE_CODE (decl) != FUNCTION_DECL)
332 node = cgraph_node (decl);
333 if (decl != current_function_decl
334 && !TREE_ASM_WRITTEN (node->decl))
339 /* Return name of the node used in debug output. */
341 cgraph_node_name (struct cgraph_node *node)
343 return (*lang_hooks.decl_printable_name) (node->decl, 2);
346 /* Dump the callgraph. */
349 dump_cgraph (FILE *f)
351 struct cgraph_node *node;
353 fprintf (f, "callgraph:\n\n");
354 for (node = cgraph_nodes; node; node = node->next)
356 struct cgraph_edge *edge;
357 fprintf (f, "%s:", cgraph_node_name (node));
358 if (node->local.self_insns)
359 fprintf (f, " %i insns", node->local.self_insns);
360 if (node->global.insns && node->global.insns != node->local.self_insns)
361 fprintf (f, " (%i after inlining)", node->global.insns);
363 fprintf (f, " nested in: %s", cgraph_node_name (node->origin));
365 fprintf (f, " needed");
366 else if (node->reachable)
367 fprintf (f, " reachable");
368 if (DECL_SAVED_TREE (node->decl))
369 fprintf (f, " tree");
371 if (node->local.local)
372 fprintf (f, " local");
373 if (node->local.disregard_inline_limits)
374 fprintf (f, " always_inline");
375 else if (node->local.inlinable)
376 fprintf (f, " inlinable");
377 if (node->global.cloned_times > 1)
378 fprintf (f, " cloned %ix", node->global.cloned_times);
380 fprintf (f, "\n called by: ");
381 for (edge = node->callers; edge; edge = edge->next_caller)
383 fprintf (f, "%s ", cgraph_node_name (edge->caller));
384 if (edge->inline_call)
385 fprintf(f, "(inlined) ");
388 fprintf (f, "\n calls: ");
389 for (edge = node->callees; edge; edge = edge->next_callee)
391 fprintf (f, "%s ", cgraph_node_name (edge->callee));
392 if (edge->inline_call)
393 fprintf(f, "(inlined) ");
399 /* Returns a hash code for P. */
402 cgraph_varpool_hash_node (const void *p)
405 IDENTIFIER_HASH_VALUE (DECL_ASSEMBLER_NAME
406 (((struct cgraph_varpool_node *) p)->decl)));
409 /* Returns nonzero if P1 and P2 are equal. */
412 eq_cgraph_varpool_node (const void *p1, const void *p2)
414 return ((DECL_ASSEMBLER_NAME (((struct cgraph_varpool_node *) p1)->decl)) ==
418 /* Return cgraph_varpool node assigned to DECL. Create new one when needed. */
419 struct cgraph_varpool_node *
420 cgraph_varpool_node (tree decl)
422 struct cgraph_varpool_node *node;
423 struct cgraph_varpool_node **slot;
425 if (!DECL_P (decl) || TREE_CODE (decl) == FUNCTION_DECL)
428 if (!cgraph_varpool_hash)
429 cgraph_varpool_hash = htab_create_ggc (10, cgraph_varpool_hash_node,
430 eq_cgraph_varpool_node, NULL);
433 slot = (struct cgraph_varpool_node **)
434 htab_find_slot_with_hash (cgraph_varpool_hash, DECL_ASSEMBLER_NAME (decl),
435 IDENTIFIER_HASH_VALUE (DECL_ASSEMBLER_NAME (decl)),
439 node = ggc_alloc_cleared (sizeof (*node));
441 cgraph_varpool_n_nodes++;
442 cgraph_varpool_nodes = node;
447 /* Try to find existing function for identifier ID. */
448 struct cgraph_varpool_node *
449 cgraph_varpool_node_for_identifier (tree id)
451 struct cgraph_varpool_node **slot;
453 if (TREE_CODE (id) != IDENTIFIER_NODE)
456 if (!cgraph_varpool_hash)
459 slot = (struct cgraph_varpool_node **)
460 htab_find_slot_with_hash (cgraph_varpool_hash, id,
461 IDENTIFIER_HASH_VALUE (id), 0);
467 /* Notify finalize_compilation_unit that given node is reachable
470 cgraph_varpool_mark_needed_node (struct cgraph_varpool_node *node)
472 if (!node->needed && node->finalized)
474 node->next_needed = cgraph_varpool_nodes_queue;
475 cgraph_varpool_nodes_queue = node;
476 notice_global_symbol (node->decl);
482 cgraph_varpool_finalize_decl (tree decl)
484 struct cgraph_varpool_node *node = cgraph_varpool_node (decl);
486 /* The first declaration of a variable that comes through this function
487 decides whether it is global (in C, has external linkage)
488 or local (in C, has internal linkage). So do nothing more
489 if this function has already run. */
494 node->next_needed = cgraph_varpool_nodes_queue;
495 cgraph_varpool_nodes_queue = node;
496 notice_global_symbol (decl);
498 node->finalized = true;
500 if (/* Externally visible variables must be output. The exception are
501 COMDAT functions that must be output only when they are needed. */
502 (TREE_PUBLIC (decl) && !DECL_COMDAT (decl))
503 /* Function whose name is output to the assembler file must be produced.
504 It is possible to assemble the name later after finalizing the function
505 and the fact is noticed in assemble_name then. */
506 || (DECL_ASSEMBLER_NAME_SET_P (decl)
507 && TREE_SYMBOL_REFERENCED (DECL_ASSEMBLER_NAME (decl))))
509 cgraph_varpool_mark_needed_node (node);
514 cgraph_varpool_assemble_pending_decls (void)
516 bool changed = false;
518 while (cgraph_varpool_nodes_queue)
520 tree decl = cgraph_varpool_nodes_queue->decl;
521 struct cgraph_varpool_node *node = cgraph_varpool_nodes_queue;
523 cgraph_varpool_nodes_queue = cgraph_varpool_nodes_queue->next_needed;
524 if (!TREE_ASM_WRITTEN (decl))
526 assemble_variable (decl, 0, 1, 0);
529 node->next_needed = NULL;
535 #include "gt-cgraph.h"