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 /* Set when whole unit has been analyzed so we can access global info. */
52 bool cgraph_global_info_ready
= false;
54 /* Hash table used to convert declarations into nodes. */
55 static GTY((param_is (struct cgraph_varpool_node
))) htab_t cgraph_varpool_hash
;
57 /* Queue of cgraph nodes scheduled to be lowered and output. */
58 struct cgraph_varpool_node
*cgraph_varpool_nodes_queue
;
60 /* Number of nodes in existence. */
61 int cgraph_varpool_n_nodes
;
63 /* The linked list of cgraph varpool nodes. */
64 static GTY(()) struct cgraph_varpool_node
*cgraph_varpool_nodes
;
66 static struct cgraph_edge
*create_edge
PARAMS ((struct cgraph_node
*,
67 struct cgraph_node
*));
68 static void cgraph_remove_edge
PARAMS ((struct cgraph_node
*, struct cgraph_node
*));
69 static hashval_t hash_node
PARAMS ((const void *));
70 static int eq_node
PARAMS ((const void *, const void *));
72 /* Returns a hash code for P. */
79 IDENTIFIER_HASH_VALUE (DECL_ASSEMBLER_NAME
80 (((struct cgraph_node
*) p
)->decl
)));
83 /* Returns nonzero if P1 and P2 are equal. */
90 return ((DECL_ASSEMBLER_NAME (((struct cgraph_node
*) p1
)->decl
)) ==
94 /* Return cgraph node assigned to DECL. Create new one when needed. */
99 struct cgraph_node
*node
;
100 struct cgraph_node
**slot
;
102 if (TREE_CODE (decl
) != FUNCTION_DECL
)
106 cgraph_hash
= htab_create_ggc (10, hash_node
, eq_node
, NULL
);
108 slot
= (struct cgraph_node
**)
109 htab_find_slot_with_hash (cgraph_hash
, DECL_ASSEMBLER_NAME (decl
),
110 IDENTIFIER_HASH_VALUE
111 (DECL_ASSEMBLER_NAME (decl
)), 1);
114 node
= ggc_alloc_cleared (sizeof (*node
));
116 node
->next
= cgraph_nodes
;
118 cgraph_nodes
->previous
= node
;
119 node
->previous
= NULL
;
123 if (DECL_CONTEXT (decl
) && TREE_CODE (DECL_CONTEXT (decl
)) == FUNCTION_DECL
)
125 node
->origin
= cgraph_node (DECL_CONTEXT (decl
));
126 node
->next_nested
= node
->origin
->nested
;
127 node
->origin
->nested
= node
;
132 /* Try to find existing function for identifier ID. */
134 cgraph_node_for_identifier (id
)
137 struct cgraph_node
**slot
;
139 if (TREE_CODE (id
) != IDENTIFIER_NODE
)
145 slot
= (struct cgraph_node
**)
146 htab_find_slot_with_hash (cgraph_hash
, id
,
147 IDENTIFIER_HASH_VALUE (id
), 0);
153 /* Create edge from CALLER to CALLEE in the cgraph. */
155 static struct cgraph_edge
*
156 create_edge (caller
, callee
)
157 struct cgraph_node
*caller
, *callee
;
159 struct cgraph_edge
*edge
= ggc_alloc (sizeof (struct cgraph_edge
));
161 edge
->caller
= caller
;
162 edge
->callee
= callee
;
163 edge
->next_caller
= callee
->callers
;
164 edge
->next_callee
= caller
->callees
;
165 caller
->callees
= edge
;
166 callee
->callers
= edge
;
170 /* Remove the edge from CALLER to CALLEE in the cgraph. */
173 cgraph_remove_edge (caller
, callee
)
174 struct cgraph_node
*caller
, *callee
;
176 struct cgraph_edge
**edge
, **edge2
;
178 for (edge
= &callee
->callers
; *edge
&& (*edge
)->caller
!= caller
;
179 edge
= &((*edge
)->next_caller
))
183 *edge
= (*edge
)->next_caller
;
184 for (edge2
= &caller
->callees
; *edge2
&& (*edge2
)->callee
!= callee
;
185 edge2
= &(*edge2
)->next_callee
)
189 *edge2
= (*edge2
)->next_callee
;
192 /* Remove the node from cgraph. */
195 cgraph_remove_node (node
)
196 struct cgraph_node
*node
;
198 while (node
->callers
)
199 cgraph_remove_edge (node
->callers
->caller
, node
);
200 while (node
->callees
)
201 cgraph_remove_edge (node
, node
->callees
->callee
);
203 cgraph_remove_node (node
->nested
);
206 struct cgraph_node
**node2
= &node
->origin
->nested
;
208 while (*node2
!= node
)
209 node2
= &(*node2
)->next_nested
;
210 *node2
= node
->next_nested
;
213 node
->previous
->next
= node
->next
;
217 node
->next
->previous
= node
->previous
;
218 DECL_SAVED_TREE (node
->decl
) = NULL
;
219 /* Do not free the structure itself so the walk over chain can continue. */
222 /* Notify finalize_compilation_unit that given node is reachable
225 cgraph_mark_needed_node (node
, needed
)
226 struct cgraph_node
*node
;
233 if (!node
->reachable
)
236 if (DECL_SAVED_TREE (node
->decl
))
238 node
->next_needed
= cgraph_nodes_queue
;
239 cgraph_nodes_queue
= node
;
245 /* Record call from CALLER to CALLEE */
248 cgraph_record_call (caller
, callee
)
251 return create_edge (cgraph_node (caller
), cgraph_node (callee
));
255 cgraph_remove_call (caller
, callee
)
258 cgraph_remove_edge (cgraph_node (caller
), cgraph_node (callee
));
261 /* Return true when CALLER_DECL calls CALLEE_DECL. */
264 cgraph_calls_p (caller_decl
, callee_decl
)
265 tree caller_decl
, callee_decl
;
267 struct cgraph_node
*caller
= cgraph_node (caller_decl
);
268 struct cgraph_node
*callee
= cgraph_node (callee_decl
);
269 struct cgraph_edge
*edge
;
271 for (edge
= callee
->callers
; edge
&& (edge
)->caller
!= caller
;
272 edge
= (edge
->next_caller
))
277 /* Return local info for the compiled function. */
279 struct cgraph_local_info
*
280 cgraph_local_info (decl
)
283 struct cgraph_node
*node
;
284 if (TREE_CODE (decl
) != FUNCTION_DECL
)
286 node
= cgraph_node (decl
);
290 /* Return local info for the compiled function. */
292 struct cgraph_global_info
*
293 cgraph_global_info (decl
)
296 struct cgraph_node
*node
;
297 if (TREE_CODE (decl
) != FUNCTION_DECL
|| !cgraph_global_info_ready
)
299 node
= cgraph_node (decl
);
300 return &node
->global
;
303 /* Return local info for the compiled function. */
305 struct cgraph_rtl_info
*
306 cgraph_rtl_info (decl
)
309 struct cgraph_node
*node
;
310 if (TREE_CODE (decl
) != FUNCTION_DECL
)
312 node
= cgraph_node (decl
);
313 if (decl
!= current_function_decl
314 && !TREE_ASM_WRITTEN (node
->decl
))
319 /* Return name of the node used in debug output. */
321 cgraph_node_name (node
)
322 struct cgraph_node
*node
;
324 return (*lang_hooks
.decl_printable_name
) (node
->decl
, 2);
327 /* Dump the callgraph. */
333 struct cgraph_node
*node
;
335 fprintf (f
, "\nCallgraph:\n\n");
336 for (node
= cgraph_nodes
; node
; node
= node
->next
)
338 struct cgraph_edge
*edge
;
339 fprintf (f
, "%s", cgraph_node_name (node
));
341 fprintf (f
, " nested in: %s", cgraph_node_name (node
->origin
));
343 fprintf (f
, " needed");
344 else if (node
->reachable
)
345 fprintf (f
, " reachable");
346 if (DECL_SAVED_TREE (node
->decl
))
347 fprintf (f
, " tree");
349 fprintf (f
, "\n called by :");
350 for (edge
= node
->callers
; edge
; edge
= edge
->next_caller
)
351 fprintf (f
, "%s ", cgraph_node_name (edge
->caller
));
353 fprintf (f
, "\n calls: ");
354 for (edge
= node
->callees
; edge
; edge
= edge
->next_callee
)
355 fprintf (f
, "%s ", cgraph_node_name (edge
->callee
));
360 /* Returns a hash code for P. */
363 cgraph_varpool_hash_node (const PTR p
)
366 IDENTIFIER_HASH_VALUE (DECL_ASSEMBLER_NAME
367 (((struct cgraph_varpool_node
*) p
)->decl
)));
370 /* Returns nonzero if P1 and P2 are equal. */
373 eq_cgraph_varpool_node (const PTR p1
, const PTR p2
)
375 return ((DECL_ASSEMBLER_NAME (((struct cgraph_varpool_node
*) p1
)->decl
)) ==
379 /* Return cgraph_varpool node assigned to DECL. Create new one when needed. */
380 struct cgraph_varpool_node
*
381 cgraph_varpool_node (tree decl
)
383 struct cgraph_varpool_node
*node
;
384 struct cgraph_varpool_node
**slot
;
386 if (!DECL_P (decl
) || TREE_CODE (decl
) == FUNCTION_DECL
)
389 if (!cgraph_varpool_hash
)
390 cgraph_varpool_hash
= htab_create_ggc (10, cgraph_varpool_hash_node
,
391 eq_cgraph_varpool_node
, NULL
);
394 slot
= (struct cgraph_varpool_node
**)
395 htab_find_slot_with_hash (cgraph_varpool_hash
, DECL_ASSEMBLER_NAME (decl
),
396 IDENTIFIER_HASH_VALUE (DECL_ASSEMBLER_NAME (decl
)),
400 node
= ggc_alloc_cleared (sizeof (*node
));
402 cgraph_varpool_n_nodes
++;
403 cgraph_varpool_nodes
= node
;
408 /* Try to find existing function for identifier ID. */
409 struct cgraph_varpool_node
*
410 cgraph_varpool_node_for_identifier (tree id
)
412 struct cgraph_varpool_node
**slot
;
414 if (TREE_CODE (id
) != IDENTIFIER_NODE
)
417 if (!cgraph_varpool_hash
)
420 slot
= (struct cgraph_varpool_node
**)
421 htab_find_slot_with_hash (cgraph_varpool_hash
, id
,
422 IDENTIFIER_HASH_VALUE (id
), 0);
428 /* Notify finalize_compilation_unit that given node is reachable
431 cgraph_varpool_mark_needed_node (struct cgraph_varpool_node
*node
)
433 if (!node
->needed
&& node
->finalized
)
435 node
->next_needed
= cgraph_varpool_nodes_queue
;
436 cgraph_varpool_nodes_queue
= node
;
442 cgraph_varpool_finalize_decl (tree decl
)
444 struct cgraph_varpool_node
*node
= cgraph_varpool_node (decl
);
446 if (node
->needed
&& !node
->finalized
)
448 node
->next_needed
= cgraph_varpool_nodes_queue
;
449 cgraph_varpool_nodes_queue
= node
;
451 node
->finalized
= true;
453 if (/* Externally visible variables must be output. The exception are
454 COMDAT functions that must be output only when they are needed. */
455 (TREE_PUBLIC (decl
) && !DECL_COMDAT (decl
))
456 /* Function whose name is output to the assembler file must be produced.
457 It is possible to assemble the name later after finalizing the function
458 and the fact is noticed in assemble_name then. */
459 || (DECL_ASSEMBLER_NAME_SET_P (decl
)
460 && TREE_SYMBOL_REFERENCED (DECL_ASSEMBLER_NAME (decl
))))
462 cgraph_varpool_mark_needed_node (node
);
467 cgraph_varpool_assemble_pending_decls ()
469 bool changed
= false;
471 while (cgraph_varpool_nodes_queue
)
473 tree decl
= cgraph_varpool_nodes_queue
->decl
;
474 struct cgraph_varpool_node
*node
= cgraph_varpool_nodes_queue
;
476 cgraph_varpool_nodes_queue
= cgraph_varpool_nodes_queue
->next_needed
;
477 if (!TREE_ASM_WRITTEN (decl
))
479 assemble_variable (decl
, 0, 1, 0);
482 node
->next_needed
= NULL
;
488 #include "gt-cgraph.h"