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
.inlinable
)
163 edge
->inline_failed
= N_("function not considered for inlining");
165 edge
->inline_failed
= N_("function not inlinable");
167 /* At the moment we don't associate calls with specific CALL_EXPRs
168 as we probably ought to, so we must preserve inline_call flags to
169 be the same in all copies of the same edge. */
170 if (cgraph_global_info_ready
)
171 for (edge2
= caller
->callees
; edge2
; edge2
= edge2
->next_callee
)
172 if (edge2
->callee
== callee
)
174 edge
->inline_failed
= edge2
->inline_failed
;
178 edge
->caller
= caller
;
179 edge
->callee
= callee
;
180 edge
->next_caller
= callee
->callers
;
181 edge
->next_callee
= caller
->callees
;
182 caller
->callees
= edge
;
183 callee
->callers
= edge
;
187 /* Remove the edge from CALLER to CALLEE in the cgraph. */
190 cgraph_remove_edge (struct cgraph_node
*caller
, struct cgraph_node
*callee
)
192 struct cgraph_edge
**edge
, **edge2
;
194 for (edge
= &callee
->callers
; *edge
&& (*edge
)->caller
!= caller
;
195 edge
= &((*edge
)->next_caller
))
199 *edge
= (*edge
)->next_caller
;
200 for (edge2
= &caller
->callees
; *edge2
&& (*edge2
)->callee
!= callee
;
201 edge2
= &(*edge2
)->next_callee
)
205 *edge2
= (*edge2
)->next_callee
;
208 /* Remove the node from cgraph. */
211 cgraph_remove_node (struct cgraph_node
*node
)
214 while (node
->callers
)
215 cgraph_remove_edge (node
->callers
->caller
, node
);
216 while (node
->callees
)
217 cgraph_remove_edge (node
, node
->callees
->callee
);
219 cgraph_remove_node (node
->nested
);
222 struct cgraph_node
**node2
= &node
->origin
->nested
;
224 while (*node2
!= node
)
225 node2
= &(*node2
)->next_nested
;
226 *node2
= node
->next_nested
;
229 node
->previous
->next
= node
->next
;
233 node
->next
->previous
= node
->previous
;
234 DECL_SAVED_TREE (node
->decl
) = NULL
;
236 htab_find_slot_with_hash (cgraph_hash
, DECL_ASSEMBLER_NAME (node
->decl
),
237 IDENTIFIER_HASH_VALUE (DECL_ASSEMBLER_NAME
238 (node
->decl
)), NO_INSERT
);
239 htab_clear_slot (cgraph_hash
, slot
);
240 /* Do not free the structure itself so the walk over chain can continue. */
243 /* Notify finalize_compilation_unit that given node is reachable. */
246 cgraph_mark_reachable_node (struct cgraph_node
*node
)
248 if (!node
->reachable
&& node
->local
.finalized
)
250 notice_global_symbol (node
->decl
);
253 node
->next_needed
= cgraph_nodes_queue
;
254 cgraph_nodes_queue
= node
;
256 /* At the moment frontend automatically emits all nested functions. */
259 struct cgraph_node
*node2
;
261 for (node2
= node
->nested
; node2
; node2
= node2
->next_nested
)
262 if (!node2
->reachable
)
263 cgraph_mark_reachable_node (node2
);
268 /* Likewise indicate that a node is needed, i.e. reachable via some
272 cgraph_mark_needed_node (struct cgraph_node
*node
)
275 cgraph_mark_reachable_node (node
);
278 /* Record call from CALLER to CALLEE. */
281 cgraph_record_call (tree caller
, tree callee
)
283 return create_edge (cgraph_node (caller
), cgraph_node (callee
));
287 cgraph_remove_call (tree caller
, tree callee
)
289 cgraph_remove_edge (cgraph_node (caller
), cgraph_node (callee
));
292 /* Return true when CALLER_DECL calls CALLEE_DECL. */
295 cgraph_calls_p (tree caller_decl
, tree callee_decl
)
297 struct cgraph_node
*caller
= cgraph_node (caller_decl
);
298 struct cgraph_node
*callee
= cgraph_node (callee_decl
);
299 struct cgraph_edge
*edge
;
301 for (edge
= callee
->callers
; edge
&& (edge
)->caller
!= caller
;
302 edge
= (edge
->next_caller
))
307 /* Return local info for the compiled function. */
309 struct cgraph_local_info
*
310 cgraph_local_info (tree decl
)
312 struct cgraph_node
*node
;
313 if (TREE_CODE (decl
) != FUNCTION_DECL
)
315 node
= cgraph_node (decl
);
319 /* Return local info for the compiled function. */
321 struct cgraph_global_info
*
322 cgraph_global_info (tree decl
)
324 struct cgraph_node
*node
;
325 if (TREE_CODE (decl
) != FUNCTION_DECL
|| !cgraph_global_info_ready
)
327 node
= cgraph_node (decl
);
328 return &node
->global
;
331 /* Return local info for the compiled function. */
333 struct cgraph_rtl_info
*
334 cgraph_rtl_info (tree decl
)
336 struct cgraph_node
*node
;
337 if (TREE_CODE (decl
) != FUNCTION_DECL
)
339 node
= cgraph_node (decl
);
340 if (decl
!= current_function_decl
341 && !TREE_ASM_WRITTEN (node
->decl
))
346 /* Return name of the node used in debug output. */
348 cgraph_node_name (struct cgraph_node
*node
)
350 return (*lang_hooks
.decl_printable_name
) (node
->decl
, 2);
353 /* Dump the callgraph. */
356 dump_cgraph (FILE *f
)
358 struct cgraph_node
*node
;
360 fprintf (f
, "callgraph:\n\n");
361 for (node
= cgraph_nodes
; node
; node
= node
->next
)
363 struct cgraph_edge
*edge
;
364 fprintf (f
, "%s:", cgraph_node_name (node
));
365 if (node
->local
.self_insns
)
366 fprintf (f
, " %i insns", node
->local
.self_insns
);
367 if (node
->global
.insns
&& node
->global
.insns
!= node
->local
.self_insns
)
368 fprintf (f
, " (%i after inlining)", node
->global
.insns
);
370 fprintf (f
, " nested in: %s", cgraph_node_name (node
->origin
));
372 fprintf (f
, " needed");
373 else if (node
->reachable
)
374 fprintf (f
, " reachable");
375 if (DECL_SAVED_TREE (node
->decl
))
376 fprintf (f
, " tree");
378 if (node
->local
.local
)
379 fprintf (f
, " local");
380 if (node
->local
.disregard_inline_limits
)
381 fprintf (f
, " always_inline");
382 else if (node
->local
.inlinable
)
383 fprintf (f
, " inlinable");
384 if (node
->global
.cloned_times
> 1)
385 fprintf (f
, " cloned %ix", node
->global
.cloned_times
);
387 fprintf (f
, "\n called by: ");
388 for (edge
= node
->callers
; edge
; edge
= edge
->next_caller
)
390 fprintf (f
, "%s ", cgraph_node_name (edge
->caller
));
391 if (!edge
->inline_failed
)
392 fprintf(f
, "(inlined) ");
395 fprintf (f
, "\n calls: ");
396 for (edge
= node
->callees
; edge
; edge
= edge
->next_callee
)
398 fprintf (f
, "%s ", cgraph_node_name (edge
->callee
));
399 if (!edge
->inline_failed
)
400 fprintf(f
, "(inlined) ");
406 /* Returns a hash code for P. */
409 cgraph_varpool_hash_node (const void *p
)
412 IDENTIFIER_HASH_VALUE (DECL_ASSEMBLER_NAME
413 (((struct cgraph_varpool_node
*) p
)->decl
)));
416 /* Returns nonzero if P1 and P2 are equal. */
419 eq_cgraph_varpool_node (const void *p1
, const void *p2
)
421 return ((DECL_ASSEMBLER_NAME (((struct cgraph_varpool_node
*) p1
)->decl
)) ==
425 /* Return cgraph_varpool node assigned to DECL. Create new one when needed. */
426 struct cgraph_varpool_node
*
427 cgraph_varpool_node (tree decl
)
429 struct cgraph_varpool_node
*node
;
430 struct cgraph_varpool_node
**slot
;
432 if (!DECL_P (decl
) || TREE_CODE (decl
) == FUNCTION_DECL
)
435 if (!cgraph_varpool_hash
)
436 cgraph_varpool_hash
= htab_create_ggc (10, cgraph_varpool_hash_node
,
437 eq_cgraph_varpool_node
, NULL
);
438 slot
= (struct cgraph_varpool_node
**)
439 htab_find_slot_with_hash (cgraph_varpool_hash
, DECL_ASSEMBLER_NAME (decl
),
440 IDENTIFIER_HASH_VALUE (DECL_ASSEMBLER_NAME (decl
)),
444 node
= ggc_alloc_cleared (sizeof (*node
));
446 cgraph_varpool_n_nodes
++;
447 cgraph_varpool_nodes
= node
;
452 /* Set the DECL_ASSEMBLER_NAME and update cgraph hashtables. */
454 change_decl_assembler_name (tree decl
, tree name
)
456 struct cgraph_node
*node
= NULL
;
457 struct cgraph_varpool_node
*vnode
= NULL
;
460 if (!DECL_ASSEMBLER_NAME_SET_P (decl
))
462 SET_DECL_ASSEMBLER_NAME (decl
, name
);
465 if (name
== DECL_ASSEMBLER_NAME (decl
))
468 if (TREE_SYMBOL_REFERENCED (DECL_ASSEMBLER_NAME (decl
))
469 && DECL_RTL_SET_P (decl
))
470 warning ("%D renamed after being referenced in assembly", decl
);
472 if (TREE_CODE (decl
) == FUNCTION_DECL
&& cgraph_hash
)
474 /* Take a look whether declaration is in the cgraph structure. */
476 htab_find_slot_with_hash (cgraph_hash
, DECL_ASSEMBLER_NAME (decl
),
477 IDENTIFIER_HASH_VALUE (DECL_ASSEMBLER_NAME
482 /* It is, verify that we are the canonical node for this decl. */
483 if (node
&& node
->decl
== decl
)
486 htab_clear_slot (cgraph_hash
, slot
);
491 if (TREE_CODE (decl
) == VAR_DECL
&& TREE_STATIC (decl
) && cgraph_varpool_hash
)
493 /* Take a look whether declaration is in the cgraph structure. */
495 htab_find_slot_with_hash (cgraph_varpool_hash
, DECL_ASSEMBLER_NAME (decl
),
496 IDENTIFIER_HASH_VALUE (DECL_ASSEMBLER_NAME
501 /* It is, verify that we are the canonical vnode for this decl. */
502 if (vnode
&& vnode
->decl
== decl
)
505 htab_clear_slot (cgraph_varpool_hash
, slot
);
510 SET_DECL_ASSEMBLER_NAME (decl
, name
);
514 htab_find_slot_with_hash (cgraph_hash
, name
,
515 IDENTIFIER_HASH_VALUE (name
), INSERT
);
523 htab_find_slot_with_hash (cgraph_varpool_hash
, name
,
524 IDENTIFIER_HASH_VALUE (name
), INSERT
);
531 /* Try to find existing function for identifier ID. */
532 struct cgraph_varpool_node
*
533 cgraph_varpool_node_for_identifier (tree id
)
535 struct cgraph_varpool_node
**slot
;
537 if (TREE_CODE (id
) != IDENTIFIER_NODE
)
540 if (!cgraph_varpool_hash
)
543 slot
= (struct cgraph_varpool_node
**)
544 htab_find_slot_with_hash (cgraph_varpool_hash
, id
,
545 IDENTIFIER_HASH_VALUE (id
), NO_INSERT
);
551 /* Notify finalize_compilation_unit that given node is reachable
554 cgraph_varpool_mark_needed_node (struct cgraph_varpool_node
*node
)
556 if (!node
->needed
&& node
->finalized
)
558 node
->next_needed
= cgraph_varpool_nodes_queue
;
559 cgraph_varpool_nodes_queue
= node
;
560 notice_global_symbol (node
->decl
);
566 cgraph_varpool_finalize_decl (tree decl
)
568 struct cgraph_varpool_node
*node
= cgraph_varpool_node (decl
);
570 /* The first declaration of a variable that comes through this function
571 decides whether it is global (in C, has external linkage)
572 or local (in C, has internal linkage). So do nothing more
573 if this function has already run. */
578 node
->next_needed
= cgraph_varpool_nodes_queue
;
579 cgraph_varpool_nodes_queue
= node
;
580 notice_global_symbol (decl
);
582 node
->finalized
= true;
584 if (/* Externally visible variables must be output. The exception are
585 COMDAT functions that must be output only when they are needed. */
586 (TREE_PUBLIC (decl
) && !DECL_COMDAT (decl
))
587 /* Function whose name is output to the assembler file must be produced.
588 It is possible to assemble the name later after finalizing the function
589 and the fact is noticed in assemble_name then. */
590 || (DECL_ASSEMBLER_NAME_SET_P (decl
)
591 && TREE_SYMBOL_REFERENCED (DECL_ASSEMBLER_NAME (decl
))))
593 cgraph_varpool_mark_needed_node (node
);
598 cgraph_varpool_assemble_pending_decls (void)
600 bool changed
= false;
602 while (cgraph_varpool_nodes_queue
)
604 tree decl
= cgraph_varpool_nodes_queue
->decl
;
605 struct cgraph_varpool_node
*node
= cgraph_varpool_nodes_queue
;
607 cgraph_varpool_nodes_queue
= cgraph_varpool_nodes_queue
->next_needed
;
608 if (!TREE_ASM_WRITTEN (decl
))
610 assemble_variable (decl
, 0, 1, 0);
613 node
->next_needed
= NULL
;
618 /* Return true when the DECL can possibly be inlined. */
620 cgraph_function_possibly_inlined_p (tree decl
)
622 if (!cgraph_global_info_ready
)
623 return (DECL_INLINE (decl
)
624 && (!flag_really_no_inline
625 || (*lang_hooks
.tree_inlining
.disregard_inline_limits
) (decl
)));
626 return cgraph_node (decl
)->global
.inlined
;
629 #include "gt-cgraph.h"