1 /* Callgraph handling code.
2 Copyright (C) 2003, 2004 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"
40 /* Hash table used to convert declarations into nodes. */
41 static GTY((param_is (struct cgraph_node
))) htab_t cgraph_hash
;
43 /* The linked list of cgraph nodes. */
44 struct cgraph_node
*cgraph_nodes
;
46 /* Queue of cgraph nodes scheduled to be lowered. */
47 struct cgraph_node
*cgraph_nodes_queue
;
49 /* Number of nodes in existence. */
52 /* Maximal uid used in cgraph nodes. */
55 /* Set when whole unit has been analyzed so we can access global info. */
56 bool cgraph_global_info_ready
= false;
58 /* Hash table used to convert declarations into nodes. */
59 static GTY((param_is (struct cgraph_varpool_node
))) htab_t cgraph_varpool_hash
;
61 /* Queue of cgraph nodes scheduled to be lowered and output. */
62 struct cgraph_varpool_node
*cgraph_varpool_nodes_queue
;
64 /* Number of nodes in existence. */
65 int cgraph_varpool_n_nodes
;
67 /* The linked list of cgraph varpool nodes. */
68 static GTY(()) struct cgraph_varpool_node
*cgraph_varpool_nodes
;
70 static struct cgraph_edge
*create_edge (struct cgraph_node
*,
71 struct cgraph_node
*);
72 static hashval_t
hash_node (const void *);
73 static int eq_node (const void *, const void *);
75 /* Returns a hash code for P. */
78 hash_node (const void *p
)
81 IDENTIFIER_HASH_VALUE (DECL_ASSEMBLER_NAME
82 (((struct cgraph_node
*) p
)->decl
)));
85 /* Returns nonzero if P1 and P2 are equal. */
88 eq_node (const void *p1
, const void *p2
)
90 return ((DECL_ASSEMBLER_NAME (((struct cgraph_node
*) p1
)->decl
)) ==
94 /* Return cgraph node assigned to DECL. Create new one when needed. */
96 cgraph_node (tree decl
)
98 struct cgraph_node
*node
;
99 struct cgraph_node
**slot
;
101 if (TREE_CODE (decl
) != FUNCTION_DECL
)
105 cgraph_hash
= htab_create_ggc (10, hash_node
, eq_node
, NULL
);
107 slot
= (struct cgraph_node
**)
108 htab_find_slot_with_hash (cgraph_hash
, DECL_ASSEMBLER_NAME (decl
),
109 IDENTIFIER_HASH_VALUE
110 (DECL_ASSEMBLER_NAME (decl
)), INSERT
);
113 node
= ggc_alloc_cleared (sizeof (*node
));
115 node
->next
= cgraph_nodes
;
116 node
->uid
= cgraph_max_uid
++;
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 (tree id
)
136 struct cgraph_node
**slot
;
138 if (TREE_CODE (id
) != IDENTIFIER_NODE
)
144 slot
= (struct cgraph_node
**)
145 htab_find_slot_with_hash (cgraph_hash
, id
,
146 IDENTIFIER_HASH_VALUE (id
), NO_INSERT
);
152 /* Create edge from CALLER to CALLEE in the cgraph. */
154 static struct cgraph_edge
*
155 create_edge (struct cgraph_node
*caller
, struct cgraph_node
*callee
)
157 struct cgraph_edge
*edge
= ggc_alloc (sizeof (struct cgraph_edge
));
158 struct cgraph_edge
*edge2
;
160 if (!DECL_SAVED_TREE (callee
->decl
))
161 edge
->inline_failed
= N_("function body not available");
162 else if (callee
->local
.redefined_extern_inline
)
163 edge
->inline_failed
= N_("redefined extern inline functions are not "
164 "considered for inlining");
165 else if (callee
->local
.inlinable
)
166 edge
->inline_failed
= N_("function not considered for inlining");
168 edge
->inline_failed
= N_("function not inlinable");
170 /* At the moment we don't associate calls with specific CALL_EXPRs
171 as we probably ought to, so we must preserve inline_call flags to
172 be the same in all copies of the same edge. */
173 if (cgraph_global_info_ready
)
174 for (edge2
= caller
->callees
; edge2
; edge2
= edge2
->next_callee
)
175 if (edge2
->callee
== callee
)
177 edge
->inline_failed
= edge2
->inline_failed
;
181 edge
->caller
= caller
;
182 edge
->callee
= callee
;
183 edge
->next_caller
= callee
->callers
;
184 edge
->next_callee
= caller
->callees
;
185 caller
->callees
= edge
;
186 callee
->callers
= edge
;
190 /* Remove the edge from CALLER to CALLEE in the cgraph. */
193 cgraph_remove_edge (struct cgraph_node
*caller
, struct cgraph_node
*callee
)
195 struct cgraph_edge
**edge
, **edge2
;
197 for (edge
= &callee
->callers
; *edge
&& (*edge
)->caller
!= caller
;
198 edge
= &((*edge
)->next_caller
))
202 *edge
= (*edge
)->next_caller
;
203 for (edge2
= &caller
->callees
; *edge2
&& (*edge2
)->callee
!= callee
;
204 edge2
= &(*edge2
)->next_callee
)
208 *edge2
= (*edge2
)->next_callee
;
211 /* Remove the node from cgraph. */
214 cgraph_remove_node (struct cgraph_node
*node
)
217 while (node
->callers
)
218 cgraph_remove_edge (node
->callers
->caller
, node
);
219 while (node
->callees
)
220 cgraph_remove_edge (node
, node
->callees
->callee
);
222 cgraph_remove_node (node
->nested
);
225 struct cgraph_node
**node2
= &node
->origin
->nested
;
227 while (*node2
!= node
)
228 node2
= &(*node2
)->next_nested
;
229 *node2
= node
->next_nested
;
232 node
->previous
->next
= node
->next
;
234 cgraph_nodes
= node
->next
;
236 node
->next
->previous
= node
->previous
;
237 DECL_SAVED_TREE (node
->decl
) = NULL
;
239 htab_find_slot_with_hash (cgraph_hash
, DECL_ASSEMBLER_NAME (node
->decl
),
240 IDENTIFIER_HASH_VALUE (DECL_ASSEMBLER_NAME
241 (node
->decl
)), NO_INSERT
);
242 htab_clear_slot (cgraph_hash
, slot
);
243 /* Do not free the structure itself so the walk over chain can continue. */
246 /* Notify finalize_compilation_unit that given node is reachable. */
249 cgraph_mark_reachable_node (struct cgraph_node
*node
)
251 if (!node
->reachable
&& node
->local
.finalized
)
253 notice_global_symbol (node
->decl
);
256 node
->next_needed
= cgraph_nodes_queue
;
257 cgraph_nodes_queue
= node
;
259 /* At the moment frontend automatically emits all nested functions. */
262 struct cgraph_node
*node2
;
264 for (node2
= node
->nested
; node2
; node2
= node2
->next_nested
)
265 if (!node2
->reachable
)
266 cgraph_mark_reachable_node (node2
);
271 /* Likewise indicate that a node is needed, i.e. reachable via some
275 cgraph_mark_needed_node (struct cgraph_node
*node
)
278 cgraph_mark_reachable_node (node
);
281 /* Record call from CALLER to CALLEE. */
284 cgraph_record_call (tree caller
, tree callee
)
286 return create_edge (cgraph_node (caller
), cgraph_node (callee
));
290 cgraph_remove_call (tree caller
, tree callee
)
292 cgraph_remove_edge (cgraph_node (caller
), cgraph_node (callee
));
295 /* Return true when CALLER_DECL calls CALLEE_DECL. */
298 cgraph_calls_p (tree caller_decl
, tree callee_decl
)
300 struct cgraph_node
*caller
= cgraph_node (caller_decl
);
301 struct cgraph_node
*callee
= cgraph_node (callee_decl
);
302 struct cgraph_edge
*edge
;
304 for (edge
= callee
->callers
; edge
&& (edge
)->caller
!= caller
;
305 edge
= (edge
->next_caller
))
310 /* Return local info for the compiled function. */
312 struct cgraph_local_info
*
313 cgraph_local_info (tree decl
)
315 struct cgraph_node
*node
;
316 if (TREE_CODE (decl
) != FUNCTION_DECL
)
318 node
= cgraph_node (decl
);
322 /* Return local info for the compiled function. */
324 struct cgraph_global_info
*
325 cgraph_global_info (tree decl
)
327 struct cgraph_node
*node
;
328 if (TREE_CODE (decl
) != FUNCTION_DECL
|| !cgraph_global_info_ready
)
330 node
= cgraph_node (decl
);
331 return &node
->global
;
334 /* Return local info for the compiled function. */
336 struct cgraph_rtl_info
*
337 cgraph_rtl_info (tree decl
)
339 struct cgraph_node
*node
;
340 if (TREE_CODE (decl
) != FUNCTION_DECL
)
342 node
= cgraph_node (decl
);
343 if (decl
!= current_function_decl
344 && !TREE_ASM_WRITTEN (node
->decl
))
349 /* Return name of the node used in debug output. */
351 cgraph_node_name (struct cgraph_node
*node
)
353 return (*lang_hooks
.decl_printable_name
) (node
->decl
, 2);
356 /* Dump the callgraph. */
359 dump_cgraph (FILE *f
)
361 struct cgraph_node
*node
;
363 fprintf (f
, "callgraph:\n\n");
364 for (node
= cgraph_nodes
; node
; node
= node
->next
)
366 struct cgraph_edge
*edge
;
367 fprintf (f
, "%s:", cgraph_node_name (node
));
368 if (node
->local
.self_insns
)
369 fprintf (f
, " %i insns", node
->local
.self_insns
);
370 if (node
->global
.insns
&& node
->global
.insns
!= node
->local
.self_insns
)
371 fprintf (f
, " (%i after inlining)", node
->global
.insns
);
373 fprintf (f
, " nested in: %s", cgraph_node_name (node
->origin
));
375 fprintf (f
, " needed");
376 else if (node
->reachable
)
377 fprintf (f
, " reachable");
378 if (DECL_SAVED_TREE (node
->decl
))
379 fprintf (f
, " tree");
381 if (node
->local
.local
)
382 fprintf (f
, " local");
383 if (node
->local
.disregard_inline_limits
)
384 fprintf (f
, " always_inline");
385 else if (node
->local
.inlinable
)
386 fprintf (f
, " inlinable");
387 if (node
->global
.cloned_times
> 1)
388 fprintf (f
, " cloned %ix", node
->global
.cloned_times
);
390 fprintf (f
, "\n called by: ");
391 for (edge
= node
->callers
; edge
; edge
= edge
->next_caller
)
393 fprintf (f
, "%s ", cgraph_node_name (edge
->caller
));
394 if (!edge
->inline_failed
)
395 fprintf(f
, "(inlined) ");
398 fprintf (f
, "\n calls: ");
399 for (edge
= node
->callees
; edge
; edge
= edge
->next_callee
)
401 fprintf (f
, "%s ", cgraph_node_name (edge
->callee
));
402 if (!edge
->inline_failed
)
403 fprintf(f
, "(inlined) ");
409 /* Returns a hash code for P. */
412 cgraph_varpool_hash_node (const void *p
)
415 IDENTIFIER_HASH_VALUE (DECL_ASSEMBLER_NAME
416 (((struct cgraph_varpool_node
*) p
)->decl
)));
419 /* Returns nonzero if P1 and P2 are equal. */
422 eq_cgraph_varpool_node (const void *p1
, const void *p2
)
424 return ((DECL_ASSEMBLER_NAME (((struct cgraph_varpool_node
*) p1
)->decl
)) ==
428 /* Return cgraph_varpool node assigned to DECL. Create new one when needed. */
429 struct cgraph_varpool_node
*
430 cgraph_varpool_node (tree decl
)
432 struct cgraph_varpool_node
*node
;
433 struct cgraph_varpool_node
**slot
;
435 if (!DECL_P (decl
) || TREE_CODE (decl
) == FUNCTION_DECL
)
438 if (!cgraph_varpool_hash
)
439 cgraph_varpool_hash
= htab_create_ggc (10, cgraph_varpool_hash_node
,
440 eq_cgraph_varpool_node
, NULL
);
441 slot
= (struct cgraph_varpool_node
**)
442 htab_find_slot_with_hash (cgraph_varpool_hash
, DECL_ASSEMBLER_NAME (decl
),
443 IDENTIFIER_HASH_VALUE (DECL_ASSEMBLER_NAME (decl
)),
447 node
= ggc_alloc_cleared (sizeof (*node
));
449 cgraph_varpool_n_nodes
++;
450 cgraph_varpool_nodes
= node
;
455 /* Set the DECL_ASSEMBLER_NAME and update cgraph hashtables. */
457 change_decl_assembler_name (tree decl
, tree name
)
459 struct cgraph_node
*node
= NULL
;
460 struct cgraph_varpool_node
*vnode
= NULL
;
463 if (!DECL_ASSEMBLER_NAME_SET_P (decl
))
465 SET_DECL_ASSEMBLER_NAME (decl
, name
);
468 if (name
== DECL_ASSEMBLER_NAME (decl
))
471 if (TREE_SYMBOL_REFERENCED (DECL_ASSEMBLER_NAME (decl
))
472 && DECL_RTL_SET_P (decl
))
473 warning ("%D renamed after being referenced in assembly", decl
);
475 if (TREE_CODE (decl
) == FUNCTION_DECL
&& cgraph_hash
)
477 /* Take a look whether declaration is in the cgraph structure. */
479 htab_find_slot_with_hash (cgraph_hash
, DECL_ASSEMBLER_NAME (decl
),
480 IDENTIFIER_HASH_VALUE (DECL_ASSEMBLER_NAME
485 /* It is, verify that we are the canonical node for this decl. */
486 if (node
&& node
->decl
== decl
)
489 htab_clear_slot (cgraph_hash
, slot
);
494 if (TREE_CODE (decl
) == VAR_DECL
&& TREE_STATIC (decl
) && cgraph_varpool_hash
)
496 /* Take a look whether declaration is in the cgraph structure. */
498 htab_find_slot_with_hash (cgraph_varpool_hash
, DECL_ASSEMBLER_NAME (decl
),
499 IDENTIFIER_HASH_VALUE (DECL_ASSEMBLER_NAME
504 /* It is, verify that we are the canonical vnode for this decl. */
505 if (vnode
&& vnode
->decl
== decl
)
508 htab_clear_slot (cgraph_varpool_hash
, slot
);
513 SET_DECL_ASSEMBLER_NAME (decl
, name
);
517 htab_find_slot_with_hash (cgraph_hash
, name
,
518 IDENTIFIER_HASH_VALUE (name
), INSERT
);
526 htab_find_slot_with_hash (cgraph_varpool_hash
, name
,
527 IDENTIFIER_HASH_VALUE (name
), INSERT
);
534 /* Try to find existing function for identifier ID. */
535 struct cgraph_varpool_node
*
536 cgraph_varpool_node_for_identifier (tree id
)
538 struct cgraph_varpool_node
**slot
;
540 if (TREE_CODE (id
) != IDENTIFIER_NODE
)
543 if (!cgraph_varpool_hash
)
546 slot
= (struct cgraph_varpool_node
**)
547 htab_find_slot_with_hash (cgraph_varpool_hash
, id
,
548 IDENTIFIER_HASH_VALUE (id
), NO_INSERT
);
554 /* Notify finalize_compilation_unit that given node is reachable
557 cgraph_varpool_mark_needed_node (struct cgraph_varpool_node
*node
)
559 if (!node
->needed
&& node
->finalized
)
561 node
->next_needed
= cgraph_varpool_nodes_queue
;
562 cgraph_varpool_nodes_queue
= node
;
563 notice_global_symbol (node
->decl
);
569 cgraph_varpool_finalize_decl (tree decl
)
571 struct cgraph_varpool_node
*node
= cgraph_varpool_node (decl
);
573 /* The first declaration of a variable that comes through this function
574 decides whether it is global (in C, has external linkage)
575 or local (in C, has internal linkage). So do nothing more
576 if this function has already run. */
581 node
->next_needed
= cgraph_varpool_nodes_queue
;
582 cgraph_varpool_nodes_queue
= node
;
583 notice_global_symbol (decl
);
585 node
->finalized
= true;
587 if (/* Externally visible variables must be output. The exception are
588 COMDAT functions that must be output only when they are needed. */
589 (TREE_PUBLIC (decl
) && !DECL_COMDAT (decl
))
590 /* Function whose name is output to the assembler file must be produced.
591 It is possible to assemble the name later after finalizing the function
592 and the fact is noticed in assemble_name then. */
593 || (DECL_ASSEMBLER_NAME_SET_P (decl
)
594 && TREE_SYMBOL_REFERENCED (DECL_ASSEMBLER_NAME (decl
))))
596 cgraph_varpool_mark_needed_node (node
);
601 cgraph_varpool_assemble_pending_decls (void)
603 bool changed
= false;
605 while (cgraph_varpool_nodes_queue
)
607 tree decl
= cgraph_varpool_nodes_queue
->decl
;
608 struct cgraph_varpool_node
*node
= cgraph_varpool_nodes_queue
;
610 cgraph_varpool_nodes_queue
= cgraph_varpool_nodes_queue
->next_needed
;
611 if (!TREE_ASM_WRITTEN (decl
))
613 assemble_variable (decl
, 0, 1, 0);
616 node
->next_needed
= NULL
;
621 /* Return true when the DECL can possibly be inlined. */
623 cgraph_function_possibly_inlined_p (tree decl
)
625 if (!cgraph_global_info_ready
)
626 return (DECL_INLINE (decl
)
627 && (!flag_really_no_inline
628 || (*lang_hooks
.tree_inlining
.disregard_inline_limits
) (decl
)));
629 return cgraph_node (decl
)->global
.inlined
;
632 #include "gt-cgraph.h"