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
;
238 DECL_SAVED_INSNS (node
->decl
) = NULL
;
239 DECL_ARGUMENTS (node
->decl
) = NULL
;
240 DECL_INITIAL (node
->decl
) = error_mark_node
;
242 htab_find_slot_with_hash (cgraph_hash
, DECL_ASSEMBLER_NAME (node
->decl
),
243 IDENTIFIER_HASH_VALUE (DECL_ASSEMBLER_NAME
244 (node
->decl
)), NO_INSERT
);
247 /* We use DECL_ASSEMBLER_NAME as key, which may not work in
248 all cases. See PR/15666. Gcc 3.5 uses DECL_UID as key,
249 which doesn't have this problem. */
250 if (!DECL_BUILT_IN (node
->decl
))
254 htab_clear_slot (cgraph_hash
, slot
);
255 /* Do not free the structure itself so the walk over chain can continue. */
258 /* Notify finalize_compilation_unit that given node is reachable. */
261 cgraph_mark_reachable_node (struct cgraph_node
*node
)
263 if (!node
->reachable
&& node
->local
.finalized
)
265 notice_global_symbol (node
->decl
);
268 node
->next_needed
= cgraph_nodes_queue
;
269 cgraph_nodes_queue
= node
;
271 /* At the moment frontend automatically emits all nested functions. */
274 struct cgraph_node
*node2
;
276 for (node2
= node
->nested
; node2
; node2
= node2
->next_nested
)
277 if (!node2
->reachable
)
278 cgraph_mark_reachable_node (node2
);
283 /* Likewise indicate that a node is needed, i.e. reachable via some
287 cgraph_mark_needed_node (struct cgraph_node
*node
)
290 cgraph_mark_reachable_node (node
);
293 /* Record call from CALLER to CALLEE. */
296 cgraph_record_call (tree caller
, tree callee
)
298 return create_edge (cgraph_node (caller
), cgraph_node (callee
));
302 cgraph_remove_call (tree caller
, tree callee
)
304 cgraph_remove_edge (cgraph_node (caller
), cgraph_node (callee
));
307 /* Return true when CALLER_DECL calls CALLEE_DECL. */
310 cgraph_calls_p (tree caller_decl
, tree callee_decl
)
312 struct cgraph_node
*caller
= cgraph_node (caller_decl
);
313 struct cgraph_node
*callee
= cgraph_node (callee_decl
);
314 struct cgraph_edge
*edge
;
316 for (edge
= callee
->callers
; edge
&& (edge
)->caller
!= caller
;
317 edge
= (edge
->next_caller
))
322 /* Return local info for the compiled function. */
324 struct cgraph_local_info
*
325 cgraph_local_info (tree decl
)
327 struct cgraph_node
*node
;
328 if (TREE_CODE (decl
) != FUNCTION_DECL
)
330 node
= cgraph_node (decl
);
334 /* Return local info for the compiled function. */
336 struct cgraph_global_info
*
337 cgraph_global_info (tree decl
)
339 struct cgraph_node
*node
;
340 if (TREE_CODE (decl
) != FUNCTION_DECL
|| !cgraph_global_info_ready
)
342 node
= cgraph_node (decl
);
343 return &node
->global
;
346 /* Return local info for the compiled function. */
348 struct cgraph_rtl_info
*
349 cgraph_rtl_info (tree decl
)
351 struct cgraph_node
*node
;
352 if (TREE_CODE (decl
) != FUNCTION_DECL
)
354 node
= cgraph_node (decl
);
355 if (decl
!= current_function_decl
356 && !TREE_ASM_WRITTEN (node
->decl
))
361 /* Return name of the node used in debug output. */
363 cgraph_node_name (struct cgraph_node
*node
)
365 return (*lang_hooks
.decl_printable_name
) (node
->decl
, 2);
368 /* Dump the callgraph. */
371 dump_cgraph (FILE *f
)
373 struct cgraph_node
*node
;
375 fprintf (f
, "callgraph:\n\n");
376 for (node
= cgraph_nodes
; node
; node
= node
->next
)
378 struct cgraph_edge
*edge
;
379 fprintf (f
, "%s:", cgraph_node_name (node
));
380 if (node
->local
.self_insns
)
381 fprintf (f
, " %i insns", node
->local
.self_insns
);
382 if (node
->global
.insns
&& node
->global
.insns
!= node
->local
.self_insns
)
383 fprintf (f
, " (%i after inlining)", node
->global
.insns
);
385 fprintf (f
, " nested in: %s", cgraph_node_name (node
->origin
));
387 fprintf (f
, " needed");
388 else if (node
->reachable
)
389 fprintf (f
, " reachable");
390 if (DECL_SAVED_TREE (node
->decl
))
391 fprintf (f
, " tree");
393 if (node
->local
.local
)
394 fprintf (f
, " local");
395 if (node
->local
.disregard_inline_limits
)
396 fprintf (f
, " always_inline");
397 else if (node
->local
.inlinable
)
398 fprintf (f
, " inlinable");
399 if (node
->global
.cloned_times
> 1)
400 fprintf (f
, " cloned %ix", node
->global
.cloned_times
);
402 fprintf (f
, "\n called by: ");
403 for (edge
= node
->callers
; edge
; edge
= edge
->next_caller
)
405 fprintf (f
, "%s ", cgraph_node_name (edge
->caller
));
406 if (!edge
->inline_failed
)
407 fprintf(f
, "(inlined) ");
410 fprintf (f
, "\n calls: ");
411 for (edge
= node
->callees
; edge
; edge
= edge
->next_callee
)
413 fprintf (f
, "%s ", cgraph_node_name (edge
->callee
));
414 if (!edge
->inline_failed
)
415 fprintf(f
, "(inlined) ");
421 /* Returns a hash code for P. */
424 cgraph_varpool_hash_node (const void *p
)
427 IDENTIFIER_HASH_VALUE (DECL_ASSEMBLER_NAME
428 (((struct cgraph_varpool_node
*) p
)->decl
)));
431 /* Returns nonzero if P1 and P2 are equal. */
434 eq_cgraph_varpool_node (const void *p1
, const void *p2
)
436 return ((DECL_ASSEMBLER_NAME (((struct cgraph_varpool_node
*) p1
)->decl
)) ==
440 /* Return cgraph_varpool node assigned to DECL. Create new one when needed. */
441 struct cgraph_varpool_node
*
442 cgraph_varpool_node (tree decl
)
444 struct cgraph_varpool_node
*node
;
445 struct cgraph_varpool_node
**slot
;
447 if (!DECL_P (decl
) || TREE_CODE (decl
) == FUNCTION_DECL
)
450 if (!cgraph_varpool_hash
)
451 cgraph_varpool_hash
= htab_create_ggc (10, cgraph_varpool_hash_node
,
452 eq_cgraph_varpool_node
, NULL
);
453 slot
= (struct cgraph_varpool_node
**)
454 htab_find_slot_with_hash (cgraph_varpool_hash
, DECL_ASSEMBLER_NAME (decl
),
455 IDENTIFIER_HASH_VALUE (DECL_ASSEMBLER_NAME (decl
)),
459 node
= ggc_alloc_cleared (sizeof (*node
));
461 cgraph_varpool_n_nodes
++;
462 cgraph_varpool_nodes
= node
;
467 /* Set the DECL_ASSEMBLER_NAME and update cgraph hashtables. */
469 change_decl_assembler_name (tree decl
, tree name
)
471 struct cgraph_node
*node
= NULL
;
472 struct cgraph_varpool_node
*vnode
= NULL
;
475 if (!DECL_ASSEMBLER_NAME_SET_P (decl
))
477 SET_DECL_ASSEMBLER_NAME (decl
, name
);
480 if (name
== DECL_ASSEMBLER_NAME (decl
))
483 if (TREE_SYMBOL_REFERENCED (DECL_ASSEMBLER_NAME (decl
))
484 && DECL_RTL_SET_P (decl
))
485 warning ("%D renamed after being referenced in assembly", decl
);
487 if (TREE_CODE (decl
) == FUNCTION_DECL
&& cgraph_hash
)
489 /* Take a look whether declaration is in the cgraph structure. */
491 htab_find_slot_with_hash (cgraph_hash
, DECL_ASSEMBLER_NAME (decl
),
492 IDENTIFIER_HASH_VALUE (DECL_ASSEMBLER_NAME
497 /* It is, verify that we are the canonical node for this decl. */
498 if (node
&& node
->decl
== decl
)
501 htab_clear_slot (cgraph_hash
, slot
);
506 if (TREE_CODE (decl
) == VAR_DECL
&& TREE_STATIC (decl
) && cgraph_varpool_hash
)
508 /* Take a look whether declaration is in the cgraph structure. */
510 htab_find_slot_with_hash (cgraph_varpool_hash
, DECL_ASSEMBLER_NAME (decl
),
511 IDENTIFIER_HASH_VALUE (DECL_ASSEMBLER_NAME
516 /* It is, verify that we are the canonical vnode for this decl. */
517 if (vnode
&& vnode
->decl
== decl
)
520 htab_clear_slot (cgraph_varpool_hash
, slot
);
525 SET_DECL_ASSEMBLER_NAME (decl
, name
);
529 htab_find_slot_with_hash (cgraph_hash
, name
,
530 IDENTIFIER_HASH_VALUE (name
), INSERT
);
538 htab_find_slot_with_hash (cgraph_varpool_hash
, name
,
539 IDENTIFIER_HASH_VALUE (name
), INSERT
);
546 /* Try to find existing function for identifier ID. */
547 struct cgraph_varpool_node
*
548 cgraph_varpool_node_for_identifier (tree id
)
550 struct cgraph_varpool_node
**slot
;
552 if (TREE_CODE (id
) != IDENTIFIER_NODE
)
555 if (!cgraph_varpool_hash
)
558 slot
= (struct cgraph_varpool_node
**)
559 htab_find_slot_with_hash (cgraph_varpool_hash
, id
,
560 IDENTIFIER_HASH_VALUE (id
), NO_INSERT
);
566 /* Notify finalize_compilation_unit that given node is reachable
569 cgraph_varpool_mark_needed_node (struct cgraph_varpool_node
*node
)
571 if (!node
->needed
&& node
->finalized
)
573 node
->next_needed
= cgraph_varpool_nodes_queue
;
574 cgraph_varpool_nodes_queue
= node
;
575 notice_global_symbol (node
->decl
);
581 cgraph_varpool_finalize_decl (tree decl
)
583 struct cgraph_varpool_node
*node
= cgraph_varpool_node (decl
);
585 /* The first declaration of a variable that comes through this function
586 decides whether it is global (in C, has external linkage)
587 or local (in C, has internal linkage). So do nothing more
588 if this function has already run. */
593 node
->next_needed
= cgraph_varpool_nodes_queue
;
594 cgraph_varpool_nodes_queue
= node
;
595 notice_global_symbol (decl
);
597 node
->finalized
= true;
599 if (/* Externally visible variables must be output. The exception are
600 COMDAT functions that must be output only when they are needed. */
601 (TREE_PUBLIC (decl
) && !DECL_COMDAT (decl
))
602 /* Function whose name is output to the assembler file must be produced.
603 It is possible to assemble the name later after finalizing the function
604 and the fact is noticed in assemble_name then. */
605 || (DECL_ASSEMBLER_NAME_SET_P (decl
)
606 && TREE_SYMBOL_REFERENCED (DECL_ASSEMBLER_NAME (decl
))))
608 cgraph_varpool_mark_needed_node (node
);
613 cgraph_varpool_assemble_pending_decls (void)
615 bool changed
= false;
617 while (cgraph_varpool_nodes_queue
)
619 tree decl
= cgraph_varpool_nodes_queue
->decl
;
620 struct cgraph_varpool_node
*node
= cgraph_varpool_nodes_queue
;
622 cgraph_varpool_nodes_queue
= cgraph_varpool_nodes_queue
->next_needed
;
623 if (!TREE_ASM_WRITTEN (decl
))
625 assemble_variable (decl
, 0, 1, 0);
628 node
->next_needed
= NULL
;
633 /* Return true when the DECL can possibly be inlined. */
635 cgraph_function_possibly_inlined_p (tree decl
)
637 if (!cgraph_global_info_ready
)
638 return (DECL_INLINE (decl
)
639 && (!flag_really_no_inline
640 || (*lang_hooks
.tree_inlining
.disregard_inline_limits
) (decl
)));
641 return cgraph_node (decl
)->global
.inlined
;
644 #include "gt-cgraph.h"