1 /* Callgraph handling code.
2 Copyright (C) 2003, 2004, 2005 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
22 /* This file contains basic routines manipulating call graph and variable pool
26 The call-graph is data structure designed for intra-procedural optimization
27 but it is also used in non-unit-at-a-time compilation to allow easier code
30 The call-graph consist of nodes and edges represented via linked lists.
31 Each function (external or not) corresponds to the unique node (in
32 contrast to tree DECL nodes where we can have multiple nodes for each
35 The mapping from declarations to call-graph nodes is done using hash table
36 based on DECL_ASSEMBLER_NAME, so it is essential for assembler name to
37 not change once the declaration is inserted into the call-graph.
38 The call-graph nodes are created lazily using cgraph_node function when
39 called for unknown declaration.
41 When built, there is one edge for each direct call. It is possible that
42 the reference will be later optimized out. The call-graph is built
43 conservatively in order to make conservative data flow analysis possible.
45 The callgraph at the moment does not represent indirect calls or calls
46 from other compilation unit. Flag NEEDED is set for each node that may
47 be accessed in such an invisible way and it shall be considered an
48 entry point to the callgraph.
50 Intraprocedural information:
52 Callgraph is place to store data needed for intraprocedural optimization.
53 All data structures are divided into three components: local_info that
54 is produced while analyzing the function, global_info that is result
55 of global walking of the callgraph on the end of compilation and
56 rtl_info used by RTL backend to propagate data from already compiled
57 functions to their callers.
61 The function inlining information is decided in advance and maintained
62 in the callgraph as so called inline plan.
63 For each inlined call, the callee's node is cloned to represent the
64 new function copy produced by inliner.
65 Each inlined call gets a unique corresponding clone node of the callee
66 and the data structure is updated while inlining is performed, so
67 the clones are eliminated and their callee edges redirected to the
70 Each edge has "inline_failed" field. When the field is set to NULL,
71 the call will be inlined. When it is non-NULL it contains a reason
72 why inlining wasn't performed.
75 The varpool data structure:
77 Varpool is used to maintain variables in similar manner as call-graph
78 is used for functions. Most of the API is symmetric replacing cgraph
79 function prefix by cgraph_varpool */
84 #include "coretypes.h"
87 #include "langhooks.h"
99 /* Hash table used to convert declarations into nodes. */
100 static GTY((param_is (struct cgraph_node
))) htab_t cgraph_hash
;
102 /* The linked list of cgraph nodes. */
103 struct cgraph_node
*cgraph_nodes
;
105 /* Queue of cgraph nodes scheduled to be lowered. */
106 struct cgraph_node
*cgraph_nodes_queue
;
108 /* Number of nodes in existence. */
111 /* Maximal uid used in cgraph nodes. */
114 /* Set when whole unit has been analyzed so we can access global info. */
115 bool cgraph_global_info_ready
= false;
117 /* Hash table used to convert declarations into nodes. */
118 static GTY((param_is (struct cgraph_varpool_node
))) htab_t cgraph_varpool_hash
;
120 /* Queue of cgraph nodes scheduled to be lowered and output. */
121 struct cgraph_varpool_node
*cgraph_varpool_nodes_queue
;
123 /* The linked list of cgraph varpool nodes. */
124 static GTY(()) struct cgraph_varpool_node
*cgraph_varpool_nodes
;
126 static hashval_t
hash_node (const void *);
127 static int eq_node (const void *, const void *);
129 /* Returns a hash code for P. */
132 hash_node (const void *p
)
134 const struct cgraph_node
*n
= p
;
135 return (hashval_t
) DECL_UID (n
->decl
);
138 /* Returns nonzero if P1 and P2 are equal. */
141 eq_node (const void *p1
, const void *p2
)
143 const struct cgraph_node
*n1
= p1
, *n2
= p2
;
144 return DECL_UID (n1
->decl
) == DECL_UID (n2
->decl
);
147 /* Allocate new callgraph node and insert it into basic data structures. */
148 static struct cgraph_node
*
149 cgraph_create_node (void)
151 struct cgraph_node
*node
;
153 node
= ggc_alloc_cleared (sizeof (*node
));
154 node
->next
= cgraph_nodes
;
155 node
->uid
= cgraph_max_uid
++;
157 cgraph_nodes
->previous
= node
;
158 node
->previous
= NULL
;
164 /* Return cgraph node assigned to DECL. Create new one when needed. */
166 cgraph_node (tree decl
)
168 struct cgraph_node key
, *node
, **slot
;
170 gcc_assert (TREE_CODE (decl
) == FUNCTION_DECL
);
173 cgraph_hash
= htab_create_ggc (10, hash_node
, eq_node
, NULL
);
177 slot
= (struct cgraph_node
**) htab_find_slot (cgraph_hash
, &key
, INSERT
);
182 node
= cgraph_create_node ();
185 if (DECL_CONTEXT (decl
) && TREE_CODE (DECL_CONTEXT (decl
)) == FUNCTION_DECL
)
187 node
->origin
= cgraph_node (DECL_CONTEXT (decl
));
188 node
->next_nested
= node
->origin
->nested
;
189 node
->origin
->nested
= node
;
194 /* Compare ASMNAME with the DECL_ASSEMBLER_NAME of DECL. */
197 decl_assembler_name_equal (tree decl
, tree asmname
)
199 tree decl_asmname
= DECL_ASSEMBLER_NAME (decl
);
201 if (decl_asmname
== asmname
)
204 /* If the target assembler name was set by the user, things are trickier.
205 We have a leading '*' to begin with. After that, it's arguable what
206 is the correct thing to do with -fleading-underscore. Arguably, we've
207 historically been doing the wrong thing in assemble_alias by always
208 printing the leading underscore. Since we're not changing that, make
209 sure user_label_prefix follows the '*' before matching. */
210 if (IDENTIFIER_POINTER (decl_asmname
)[0] == '*')
212 const char *decl_str
= IDENTIFIER_POINTER (decl_asmname
) + 1;
213 size_t ulp_len
= strlen (user_label_prefix
);
217 else if (strncmp (decl_str
, user_label_prefix
, ulp_len
) == 0)
222 return strcmp (decl_str
, IDENTIFIER_POINTER (asmname
)) == 0;
229 /* Return the cgraph node that has ASMNAME for its DECL_ASSEMBLER_NAME.
230 Return NULL if there's no such node. */
233 cgraph_node_for_asm (tree asmname
)
235 struct cgraph_node
*node
;
237 for (node
= cgraph_nodes
; node
; node
= node
->next
)
238 if (decl_assembler_name_equal (node
->decl
, asmname
))
244 /* Return callgraph edge representing CALL_EXPR. */
246 cgraph_edge (struct cgraph_node
*node
, tree call_expr
)
248 struct cgraph_edge
*e
;
250 /* This loop may turn out to be performance problem. In such case adding
251 hashtables into call nodes with very many edges is probably best
252 solution. It is not good idea to add pointer into CALL_EXPR itself
253 because we want to make possible having multiple cgraph nodes representing
254 different clones of the same body before the body is actually cloned. */
255 for (e
= node
->callees
; e
; e
= e
->next_callee
)
256 if (e
->call_expr
== call_expr
)
261 /* Create edge from CALLER to CALLEE in the cgraph. */
264 cgraph_create_edge (struct cgraph_node
*caller
, struct cgraph_node
*callee
,
267 struct cgraph_edge
*edge
= ggc_alloc (sizeof (struct cgraph_edge
));
268 #ifdef ENABLE_CHECKING
269 struct cgraph_edge
*e
;
271 for (e
= caller
->callees
; e
; e
= e
->next_callee
)
272 gcc_assert (e
->call_expr
!= call_expr
);
275 gcc_assert (TREE_CODE (call_expr
) == CALL_EXPR
);
277 if (!DECL_SAVED_TREE (callee
->decl
))
278 edge
->inline_failed
= N_("function body not available");
279 else if (callee
->local
.redefined_extern_inline
)
280 edge
->inline_failed
= N_("redefined extern inline functions are not "
281 "considered for inlining");
282 else if (callee
->local
.inlinable
)
283 edge
->inline_failed
= N_("function not considered for inlining");
285 edge
->inline_failed
= N_("function not inlinable");
289 edge
->caller
= caller
;
290 edge
->callee
= callee
;
291 edge
->call_expr
= call_expr
;
292 edge
->next_caller
= callee
->callers
;
293 edge
->next_callee
= caller
->callees
;
294 caller
->callees
= edge
;
295 callee
->callers
= edge
;
299 /* Remove the edge E the cgraph. */
302 cgraph_remove_edge (struct cgraph_edge
*e
)
304 struct cgraph_edge
**edge
, **edge2
;
306 for (edge
= &e
->callee
->callers
; *edge
&& *edge
!= e
;
307 edge
= &((*edge
)->next_caller
))
310 *edge
= (*edge
)->next_caller
;
311 for (edge2
= &e
->caller
->callees
; *edge2
&& *edge2
!= e
;
312 edge2
= &(*edge2
)->next_callee
)
315 *edge2
= (*edge2
)->next_callee
;
318 /* Redirect callee of E to N. The function does not update underlying
322 cgraph_redirect_edge_callee (struct cgraph_edge
*e
, struct cgraph_node
*n
)
324 struct cgraph_edge
**edge
;
326 for (edge
= &e
->callee
->callers
; *edge
&& *edge
!= e
;
327 edge
= &((*edge
)->next_caller
))
330 *edge
= (*edge
)->next_caller
;
332 e
->next_caller
= n
->callers
;
336 /* Remove the node from cgraph. */
339 cgraph_remove_node (struct cgraph_node
*node
)
344 while (node
->callers
)
345 cgraph_remove_edge (node
->callers
);
346 while (node
->callees
)
347 cgraph_remove_edge (node
->callees
);
349 cgraph_remove_node (node
->nested
);
352 struct cgraph_node
**node2
= &node
->origin
->nested
;
354 while (*node2
!= node
)
355 node2
= &(*node2
)->next_nested
;
356 *node2
= node
->next_nested
;
359 node
->previous
->next
= node
->next
;
361 cgraph_nodes
= node
->next
;
363 node
->next
->previous
= node
->previous
;
364 slot
= htab_find_slot (cgraph_hash
, node
, NO_INSERT
);
367 if (node
->next_clone
)
368 *slot
= node
->next_clone
;
371 htab_clear_slot (cgraph_hash
, slot
);
372 if (!dump_enabled_p (TDI_tree_all
))
374 DECL_SAVED_TREE (node
->decl
) = NULL
;
375 DECL_STRUCT_FUNCTION (node
->decl
) = NULL
;
382 struct cgraph_node
*n
;
384 for (n
= *slot
; n
->next_clone
!= node
; n
= n
->next_clone
)
386 n
->next_clone
= node
->next_clone
;
389 /* Work out whether we still need a function body (either there is inline
390 clone or there is out of line function whose body is not written). */
391 if (check_dead
&& flag_unit_at_a_time
)
393 struct cgraph_node
*n
;
395 for (n
= *slot
; n
; n
= n
->next_clone
)
396 if (n
->global
.inlined_to
397 || (!n
->global
.inlined_to
398 && !TREE_ASM_WRITTEN (n
->decl
) && !DECL_EXTERNAL (n
->decl
)))
400 if (!n
&& !dump_enabled_p (TDI_tree_all
))
402 DECL_SAVED_TREE (node
->decl
) = NULL
;
403 DECL_STRUCT_FUNCTION (node
->decl
) = NULL
;
404 DECL_INITIAL (node
->decl
) = error_mark_node
;
408 /* Do not free the structure itself so the walk over chain can continue. */
411 /* Notify finalize_compilation_unit that given node is reachable. */
414 cgraph_mark_reachable_node (struct cgraph_node
*node
)
416 if (!node
->reachable
&& node
->local
.finalized
)
418 notice_global_symbol (node
->decl
);
421 node
->next_needed
= cgraph_nodes_queue
;
422 cgraph_nodes_queue
= node
;
426 /* Likewise indicate that a node is needed, i.e. reachable via some
430 cgraph_mark_needed_node (struct cgraph_node
*node
)
433 cgraph_mark_reachable_node (node
);
436 /* Return local info for the compiled function. */
438 struct cgraph_local_info
*
439 cgraph_local_info (tree decl
)
441 struct cgraph_node
*node
;
443 gcc_assert (TREE_CODE (decl
) == FUNCTION_DECL
);
444 node
= cgraph_node (decl
);
448 /* Return local info for the compiled function. */
450 struct cgraph_global_info
*
451 cgraph_global_info (tree decl
)
453 struct cgraph_node
*node
;
455 gcc_assert (TREE_CODE (decl
) == FUNCTION_DECL
&& cgraph_global_info_ready
);
456 node
= cgraph_node (decl
);
457 return &node
->global
;
460 /* Return local info for the compiled function. */
462 struct cgraph_rtl_info
*
463 cgraph_rtl_info (tree decl
)
465 struct cgraph_node
*node
;
467 gcc_assert (TREE_CODE (decl
) == FUNCTION_DECL
);
468 node
= cgraph_node (decl
);
469 if (decl
!= current_function_decl
470 && !TREE_ASM_WRITTEN (node
->decl
))
475 /* Return name of the node used in debug output. */
477 cgraph_node_name (struct cgraph_node
*node
)
479 return lang_hooks
.decl_printable_name (node
->decl
, 2);
482 /* Dump given cgraph node. */
484 dump_cgraph_node (FILE *f
, struct cgraph_node
*node
)
486 struct cgraph_edge
*edge
;
487 fprintf (f
, "%s/%i:", cgraph_node_name (node
), node
->uid
);
488 if (node
->global
.inlined_to
)
489 fprintf (f
, " (inline copy in %s/%i)",
490 cgraph_node_name (node
->global
.inlined_to
),
491 node
->global
.inlined_to
->uid
);
492 if (node
->local
.self_insns
)
493 fprintf (f
, " %i insns", node
->local
.self_insns
);
494 if (node
->global
.insns
&& node
->global
.insns
!= node
->local
.self_insns
)
495 fprintf (f
, " (%i after inlining)", node
->global
.insns
);
497 fprintf (f
, " nested in: %s", cgraph_node_name (node
->origin
));
499 fprintf (f
, " needed");
500 else if (node
->reachable
)
501 fprintf (f
, " reachable");
502 if (DECL_SAVED_TREE (node
->decl
))
503 fprintf (f
, " tree");
505 fprintf (f
, " output");
506 if (node
->local
.local
)
507 fprintf (f
, " local");
508 if (node
->local
.disregard_inline_limits
)
509 fprintf (f
, " always_inline");
510 else if (node
->local
.inlinable
)
511 fprintf (f
, " inlinable");
512 if (TREE_ASM_WRITTEN (node
->decl
))
513 fprintf (f
, " asm_written");
515 fprintf (f
, "\n called by: ");
516 for (edge
= node
->callers
; edge
; edge
= edge
->next_caller
)
518 fprintf (f
, "%s/%i ", cgraph_node_name (edge
->caller
),
520 if (!edge
->inline_failed
)
521 fprintf(f
, "(inlined) ");
524 fprintf (f
, "\n calls: ");
525 for (edge
= node
->callees
; edge
; edge
= edge
->next_callee
)
527 fprintf (f
, "%s/%i ", cgraph_node_name (edge
->callee
),
529 if (!edge
->inline_failed
)
530 fprintf(f
, "(inlined) ");
535 /* Dump the callgraph. */
538 dump_cgraph (FILE *f
)
540 struct cgraph_node
*node
;
542 fprintf (f
, "callgraph:\n\n");
543 for (node
= cgraph_nodes
; node
; node
= node
->next
)
544 dump_cgraph_node (f
, node
);
547 /* Returns a hash code for P. */
550 hash_varpool_node (const void *p
)
552 const struct cgraph_varpool_node
*n
= p
;
553 return (hashval_t
) DECL_UID (n
->decl
);
556 /* Returns nonzero if P1 and P2 are equal. */
559 eq_varpool_node (const void *p1
, const void *p2
)
561 const struct cgraph_varpool_node
*n1
= p1
, *n2
= p2
;
562 return DECL_UID (n1
->decl
) == DECL_UID (n2
->decl
);
565 /* Return cgraph_varpool node assigned to DECL. Create new one when needed. */
566 struct cgraph_varpool_node
*
567 cgraph_varpool_node (tree decl
)
569 struct cgraph_varpool_node key
, *node
, **slot
;
571 gcc_assert (DECL_P (decl
) && TREE_CODE (decl
) != FUNCTION_DECL
);
573 if (!cgraph_varpool_hash
)
574 cgraph_varpool_hash
= htab_create_ggc (10, hash_varpool_node
,
575 eq_varpool_node
, NULL
);
577 slot
= (struct cgraph_varpool_node
**)
578 htab_find_slot (cgraph_varpool_hash
, &key
, INSERT
);
581 node
= ggc_alloc_cleared (sizeof (*node
));
583 node
->next
= cgraph_varpool_nodes
;
584 cgraph_varpool_nodes
= node
;
589 struct cgraph_varpool_node
*
590 cgraph_varpool_node_for_asm (tree asmname
)
592 struct cgraph_varpool_node
*node
;
594 for (node
= cgraph_varpool_nodes
; node
; node
= node
->next
)
595 if (decl_assembler_name_equal (node
->decl
, asmname
))
601 /* Set the DECL_ASSEMBLER_NAME and update cgraph hashtables. */
603 change_decl_assembler_name (tree decl
, tree name
)
605 if (!DECL_ASSEMBLER_NAME_SET_P (decl
))
607 SET_DECL_ASSEMBLER_NAME (decl
, name
);
610 if (name
== DECL_ASSEMBLER_NAME (decl
))
613 if (TREE_SYMBOL_REFERENCED (DECL_ASSEMBLER_NAME (decl
))
614 && DECL_RTL_SET_P (decl
))
615 warning ("%D renamed after being referenced in assembly", decl
);
617 SET_DECL_ASSEMBLER_NAME (decl
, name
);
620 /* Notify finalize_compilation_unit that given node is reachable
623 cgraph_varpool_mark_needed_node (struct cgraph_varpool_node
*node
)
625 if (!node
->needed
&& node
->finalized
)
627 node
->next_needed
= cgraph_varpool_nodes_queue
;
628 cgraph_varpool_nodes_queue
= node
;
629 notice_global_symbol (node
->decl
);
635 cgraph_varpool_finalize_decl (tree decl
)
637 struct cgraph_varpool_node
*node
= cgraph_varpool_node (decl
);
639 /* The first declaration of a variable that comes through this function
640 decides whether it is global (in C, has external linkage)
641 or local (in C, has internal linkage). So do nothing more
642 if this function has already run. */
647 node
->next_needed
= cgraph_varpool_nodes_queue
;
648 cgraph_varpool_nodes_queue
= node
;
649 notice_global_symbol (decl
);
651 node
->finalized
= true;
653 if (/* Externally visible variables must be output. The exception are
654 COMDAT functions that must be output only when they are needed. */
655 (TREE_PUBLIC (decl
) && !DECL_COMDAT (decl
))
656 /* Function whose name is output to the assembler file must be produced.
657 It is possible to assemble the name later after finalizing the function
658 and the fact is noticed in assemble_name then. */
659 || (DECL_ASSEMBLER_NAME_SET_P (decl
)
660 && TREE_SYMBOL_REFERENCED (DECL_ASSEMBLER_NAME (decl
))))
662 cgraph_varpool_mark_needed_node (node
);
667 cgraph_varpool_assemble_pending_decls (void)
669 bool changed
= false;
671 while (cgraph_varpool_nodes_queue
)
673 tree decl
= cgraph_varpool_nodes_queue
->decl
;
674 struct cgraph_varpool_node
*node
= cgraph_varpool_nodes_queue
;
676 cgraph_varpool_nodes_queue
= cgraph_varpool_nodes_queue
->next_needed
;
677 if (!TREE_ASM_WRITTEN (decl
))
679 assemble_variable (decl
, 0, 1, 0);
682 node
->next_needed
= NULL
;
687 /* Return true when the DECL can possibly be inlined. */
689 cgraph_function_possibly_inlined_p (tree decl
)
691 if (!cgraph_global_info_ready
)
692 return (DECL_INLINE (decl
) && !flag_really_no_inline
);
693 return DECL_POSSIBLY_INLINED (decl
);
696 /* Create clone of E in the node N represented by CALL_EXPR the callgraph. */
698 cgraph_clone_edge (struct cgraph_edge
*e
, struct cgraph_node
*n
, tree call_expr
)
700 struct cgraph_edge
*new = cgraph_create_edge (n
, e
->callee
, call_expr
);
702 new->inline_failed
= e
->inline_failed
;
706 /* Create node representing clone of N. */
708 cgraph_clone_node (struct cgraph_node
*n
)
710 struct cgraph_node
*new = cgraph_create_node ();
711 struct cgraph_edge
*e
;
714 new->origin
= n
->origin
;
717 new->next_nested
= new->origin
->nested
;
718 new->origin
->nested
= new;
720 new->analyzed
= n
->analyzed
;
721 new->local
= n
->local
;
722 new->global
= n
->global
;
725 for (e
= n
->callees
;e
; e
=e
->next_callee
)
726 cgraph_clone_edge (e
, new, e
->call_expr
);
728 new->next_clone
= n
->next_clone
;
734 /* NODE is no longer nested function; update cgraph accordingly. */
736 cgraph_unnest_node (struct cgraph_node
*node
)
738 struct cgraph_node
**node2
= &node
->origin
->nested
;
739 gcc_assert (node
->origin
);
741 while (*node2
!= node
)
742 node2
= &(*node2
)->next_nested
;
743 *node2
= node
->next_nested
;
746 #include "gt-cgraph.h"