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"
38 /* The known declarations must not get garbage collected. Callgraph
39 datastructures should not get saved via PCH code since this would
40 make it difficult to extend into intra-module optimizer later. So
41 we store only the references into the array to prevent gabrage
42 collector from deleting live data. */
43 static GTY(()) varray_type known_decls;
45 /* Hash table used to convert declarations into nodes. */
46 static htab_t cgraph_hash = 0;
48 /* The linked list of cgraph nodes. */
49 struct cgraph_node *cgraph_nodes;
51 /* Queue of cgraph nodes scheduled to be lowered. */
52 struct cgraph_node *cgraph_nodes_queue;
54 /* Number of nodes in existence. */
57 /* Set when whole unit has been analyzed so we can access global info. */
58 bool cgraph_global_info_ready = false;
60 /* Hash table used to convert declarations into nodes. */
61 static htab_t cgraph_varpool_hash = 0;
63 /* Queue of cgraph nodes scheduled to be lowered and output. */
64 struct cgraph_varpool_node *cgraph_varpool_nodes_queue;
66 /* Number of nodes in existence. */
67 int cgraph_varpool_n_nodes;
69 static struct cgraph_edge *create_edge PARAMS ((struct cgraph_node *,
70 struct cgraph_node *));
71 static void cgraph_remove_edge PARAMS ((struct cgraph_node *, struct cgraph_node *));
72 static hashval_t hash_node PARAMS ((const void *));
73 static int eq_node PARAMS ((const void *, const void *));
75 /* Returns a hash code for P. */
82 htab_hash_pointer (DECL_ASSEMBLER_NAME
83 (((struct cgraph_node *) p)->decl));
86 /* Returns nonzero if P1 and P2 are equal. */
93 return ((DECL_ASSEMBLER_NAME (((struct cgraph_node *) p1)->decl)) ==
97 /* Return cgraph node assigned to DECL. Create new one when needed. */
102 struct cgraph_node *node;
103 struct cgraph_node **slot;
105 if (TREE_CODE (decl) != FUNCTION_DECL)
110 cgraph_hash = htab_create (10, hash_node, eq_node, NULL);
111 VARRAY_TREE_INIT (known_decls, 32, "known_decls");
115 (struct cgraph_node **) htab_find_slot_with_hash (cgraph_hash,
116 DECL_ASSEMBLER_NAME (decl),
122 node = xcalloc (sizeof (*node), 1);
124 node->next = cgraph_nodes;
126 cgraph_nodes->previous = node;
127 node->previous = NULL;
131 if (DECL_CONTEXT (decl) && TREE_CODE (DECL_CONTEXT (decl)) == FUNCTION_DECL)
133 node->origin = cgraph_node (DECL_CONTEXT (decl));
134 node->next_nested = node->origin->nested;
135 node->origin->nested = node;
137 VARRAY_PUSH_TREE (known_decls, decl);
141 /* Try to find existing function for identifier ID. */
143 cgraph_node_for_identifier (id)
146 struct cgraph_node **slot;
148 if (TREE_CODE (id) != IDENTIFIER_NODE)
155 (struct cgraph_node **) htab_find_slot_with_hash (cgraph_hash, id,
156 htab_hash_pointer (id), 0);
162 /* Create edge from CALLER to CALLEE in the cgraph. */
164 static struct cgraph_edge *
165 create_edge (caller, callee)
166 struct cgraph_node *caller, *callee;
168 struct cgraph_edge *edge = xmalloc (sizeof (struct cgraph_edge));
170 edge->caller = caller;
171 edge->callee = callee;
172 edge->next_caller = callee->callers;
173 edge->next_callee = caller->callees;
174 caller->callees = edge;
175 callee->callers = edge;
179 /* Remove the edge from CALLER to CALLEE in the cgraph. */
182 cgraph_remove_edge (caller, callee)
183 struct cgraph_node *caller, *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 (node)
205 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;
228 /* Do not free the structure itself so the walk over chain can continue. */
231 /* Notify finalize_compilation_unit that given node is reachable
234 cgraph_mark_needed_node (node, needed)
235 struct cgraph_node *node;
242 if (!node->reachable)
245 if (DECL_SAVED_TREE (node->decl))
247 node->aux = cgraph_nodes_queue;
248 cgraph_nodes_queue = node;
254 /* Record call from CALLER to CALLEE */
257 cgraph_record_call (caller, callee)
260 return create_edge (cgraph_node (caller), cgraph_node (callee));
264 cgraph_remove_call (caller, callee)
267 cgraph_remove_edge (cgraph_node (caller), cgraph_node (callee));
270 /* Return true when CALLER_DECL calls CALLEE_DECL. */
273 cgraph_calls_p (caller_decl, callee_decl)
274 tree caller_decl, callee_decl;
276 struct cgraph_node *caller = cgraph_node (caller_decl);
277 struct cgraph_node *callee = cgraph_node (callee_decl);
278 struct cgraph_edge *edge;
280 for (edge = callee->callers; edge && (edge)->caller != caller;
281 edge = (edge->next_caller))
286 /* Return local info for the compiled function. */
288 struct cgraph_local_info *
289 cgraph_local_info (decl)
292 struct cgraph_node *node;
293 if (TREE_CODE (decl) != FUNCTION_DECL)
295 node = cgraph_node (decl);
299 /* Return local info for the compiled function. */
301 struct cgraph_global_info *
302 cgraph_global_info (decl)
305 struct cgraph_node *node;
306 if (TREE_CODE (decl) != FUNCTION_DECL || !cgraph_global_info_ready)
308 node = cgraph_node (decl);
309 return &node->global;
312 /* Return local info for the compiled function. */
314 struct cgraph_rtl_info *
315 cgraph_rtl_info (decl)
318 struct cgraph_node *node;
319 if (TREE_CODE (decl) != FUNCTION_DECL)
321 node = cgraph_node (decl);
322 if (decl != current_function_decl
323 && !TREE_ASM_WRITTEN (node->decl))
329 /* Dump the callgraph. */
335 struct cgraph_node *node;
337 fprintf (f, "\nCallgraph:\n\n");
338 for (node = cgraph_nodes; node; node = node->next)
340 struct cgraph_edge *edge;
341 fprintf (f, "%s", IDENTIFIER_POINTER (DECL_NAME (node->decl)));
343 fprintf (f, " nested in: %s",
344 IDENTIFIER_POINTER (DECL_NAME (node->origin->decl)));
346 fprintf (f, " needed");
347 else if (node->reachable)
348 fprintf (f, " reachable");
349 if (DECL_SAVED_TREE (node->decl))
350 fprintf (f, " tree");
352 fprintf (f, "\n called by :");
353 for (edge = node->callers; edge; edge = edge->next_caller)
355 IDENTIFIER_POINTER (DECL_NAME (edge->caller->decl)));
357 fprintf (f, "\n calls: ");
358 for (edge = node->callees; edge; edge = edge->next_callee)
360 IDENTIFIER_POINTER (DECL_NAME (edge->callee->decl)));
365 /* Returns a hash code for P. */
368 cgraph_varpool_hash_node (const PTR p)
371 htab_hash_pointer (DECL_ASSEMBLER_NAME
372 (((struct cgraph_varpool_node *) p)->decl));
375 /* Returns non-zero if P1 and P2 are equal. */
378 eq_cgraph_varpool_node (const PTR p1, const PTR p2)
380 return ((DECL_ASSEMBLER_NAME (((struct cgraph_varpool_node *) p1)->decl)) ==
384 /* Return cgraph_varpool node assigned to DECL. Create new one when needed. */
385 struct cgraph_varpool_node *
386 cgraph_varpool_node (tree decl)
388 struct cgraph_varpool_node *node;
389 struct cgraph_varpool_node **slot;
391 if (!DECL_P (decl) || TREE_CODE (decl) == FUNCTION_DECL)
394 if (!cgraph_varpool_hash)
396 cgraph_varpool_hash = htab_create (10, cgraph_varpool_hash_node, eq_cgraph_varpool_node, NULL);
397 VARRAY_TREE_INIT (known_decls, 32, "known_decls");
401 (struct cgraph_varpool_node **) htab_find_slot_with_hash (cgraph_varpool_hash,
402 DECL_ASSEMBLER_NAME (decl),
408 node = xcalloc (sizeof (*node), 1);
410 cgraph_varpool_n_nodes++;
412 VARRAY_PUSH_TREE (known_decls, decl);
416 /* Try to find existing function for identifier ID. */
417 struct cgraph_varpool_node *
418 cgraph_varpool_node_for_identifier (tree id)
420 struct cgraph_varpool_node **slot;
422 if (TREE_CODE (id) != IDENTIFIER_NODE)
425 if (!cgraph_varpool_hash)
429 (struct cgraph_varpool_node **) htab_find_slot_with_hash (cgraph_varpool_hash, id,
430 htab_hash_pointer (id), 0);
436 /* Notify finalize_compilation_unit that given node is reachable
439 cgraph_varpool_mark_needed_node (struct cgraph_varpool_node *node)
441 if (!node->needed && node->finalized)
443 node->aux = cgraph_varpool_nodes_queue;
444 cgraph_varpool_nodes_queue = node;
450 cgraph_varpool_finalize_decl (tree decl)
452 struct cgraph_varpool_node *node = cgraph_varpool_node (decl);
454 if (node->needed && !node->finalized)
456 node->aux = cgraph_varpool_nodes_queue;
457 cgraph_varpool_nodes_queue = node;
459 node->finalized = true;
461 if (/* Externally visible variables must be output. The exception are
462 COMDAT functions that must be output only when they are needed. */
463 (TREE_PUBLIC (decl) && !DECL_COMDAT (decl))
464 /* Function whose name is output to the assembler file must be produced.
465 It is possible to assemble the name later after finalizing the function
466 and the fact is noticed in assemble_name then. */
467 || (DECL_ASSEMBLER_NAME_SET_P (decl)
468 && TREE_SYMBOL_REFERENCED (DECL_ASSEMBLER_NAME (decl))))
470 cgraph_varpool_mark_needed_node (node);
475 cgraph_varpool_assemble_pending_decls ()
477 bool changed = false;
479 while (cgraph_varpool_nodes_queue)
481 tree decl = cgraph_varpool_nodes_queue->decl;
482 struct cgraph_varpool_node *node = cgraph_varpool_nodes_queue;
484 cgraph_varpool_nodes_queue = cgraph_varpool_nodes_queue->aux;
485 if (!TREE_ASM_WRITTEN (decl))
487 assemble_variable (decl, 0, 1, 0);
496 #include "gt-cgraph.h"