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
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 /* Number of nodes in existence. */
124 int cgraph_varpool_n_nodes
;
126 /* The linked list of cgraph varpool nodes. */
127 static GTY(()) struct cgraph_varpool_node
*cgraph_varpool_nodes
;
129 static hashval_t
hash_node (const void *);
130 static int eq_node (const void *, const void *);
132 /* Returns a hash code for P. */
135 hash_node (const void *p
)
137 const struct cgraph_node
*n
= p
;
138 return (hashval_t
) DECL_UID (n
->decl
);
141 /* Returns nonzero if P1 and P2 are equal. */
144 eq_node (const void *p1
, const void *p2
)
146 const struct cgraph_node
*n1
= p1
, *n2
= p2
;
147 return DECL_UID (n1
->decl
) == DECL_UID (n2
->decl
);
150 /* Allocate new callgraph node and insert it into basic data structures. */
151 static struct cgraph_node
*
152 cgraph_create_node (void)
154 struct cgraph_node
*node
;
156 node
= ggc_alloc_cleared (sizeof (*node
));
157 node
->next
= cgraph_nodes
;
158 node
->uid
= cgraph_max_uid
++;
160 cgraph_nodes
->previous
= node
;
161 node
->previous
= NULL
;
167 /* Return cgraph node assigned to DECL. Create new one when needed. */
169 cgraph_node (tree decl
)
171 struct cgraph_node key
, *node
, **slot
;
173 gcc_assert (TREE_CODE (decl
) == FUNCTION_DECL
);
176 cgraph_hash
= htab_create_ggc (10, hash_node
, eq_node
, NULL
);
180 slot
= (struct cgraph_node
**) htab_find_slot (cgraph_hash
, &key
, INSERT
);
185 node
= cgraph_create_node ();
188 if (DECL_CONTEXT (decl
) && TREE_CODE (DECL_CONTEXT (decl
)) == FUNCTION_DECL
)
190 node
->origin
= cgraph_node (DECL_CONTEXT (decl
));
191 node
->next_nested
= node
->origin
->nested
;
192 node
->origin
->nested
= node
;
197 /* Compare ASMNAME with the DECL_ASSEMBLER_NAME of DECL. */
200 decl_assembler_name_equal (tree decl
, tree asmname
)
202 tree decl_asmname
= DECL_ASSEMBLER_NAME (decl
);
204 if (decl_asmname
== asmname
)
207 /* If the target assembler name was set by the user, things are trickier.
208 We have a leading '*' to begin with. After that, it's arguable what
209 is the correct thing to do with -fleading-underscore. Arguably, we've
210 historically been doing the wrong thing in assemble_alias by always
211 printing the leading underscore. Since we're not changing that, make
212 sure user_label_prefix follows the '*' before matching. */
213 if (IDENTIFIER_POINTER (decl_asmname
)[0] == '*')
215 const char *decl_str
= IDENTIFIER_POINTER (decl_asmname
) + 1;
216 size_t ulp_len
= strlen (user_label_prefix
);
220 else if (strncmp (decl_str
, user_label_prefix
, ulp_len
) == 0)
225 return strcmp (decl_str
, IDENTIFIER_POINTER (asmname
)) == 0;
232 /* Return the cgraph node that has ASMNAME for its DECL_ASSEMBLER_NAME.
233 Return NULL if there's no such node. */
236 cgraph_node_for_asm (tree asmname
)
238 struct cgraph_node
*node
;
240 for (node
= cgraph_nodes
; node
; node
= node
->next
)
241 if (decl_assembler_name_equal (node
->decl
, asmname
))
247 /* Return callgraph edge representing CALL_EXPR. */
249 cgraph_edge (struct cgraph_node
*node
, tree call_expr
)
251 struct cgraph_edge
*e
;
253 /* This loop may turn out to be performance problem. In such case adding
254 hashtables into call nodes with very many edges is probably best
255 solution. It is not good idea to add pointer into CALL_EXPR itself
256 because we want to make possible having multiple cgraph nodes representing
257 different clones of the same body before the body is actually cloned. */
258 for (e
= node
->callees
; e
; e
= e
->next_callee
)
259 if (e
->call_expr
== call_expr
)
264 /* Create edge from CALLER to CALLEE in the cgraph. */
267 cgraph_create_edge (struct cgraph_node
*caller
, struct cgraph_node
*callee
,
270 struct cgraph_edge
*edge
= ggc_alloc (sizeof (struct cgraph_edge
));
271 #ifdef ENABLE_CHECKING
272 struct cgraph_edge
*e
;
274 for (e
= caller
->callees
; e
; e
= e
->next_callee
)
275 gcc_assert (e
->call_expr
!= call_expr
);
278 gcc_assert (TREE_CODE (call_expr
) == CALL_EXPR
);
280 if (!DECL_SAVED_TREE (callee
->decl
))
281 edge
->inline_failed
= N_("function body not available");
282 else if (callee
->local
.redefined_extern_inline
)
283 edge
->inline_failed
= N_("redefined extern inline functions are not "
284 "considered for inlining");
285 else if (callee
->local
.inlinable
)
286 edge
->inline_failed
= N_("function not considered for inlining");
288 edge
->inline_failed
= N_("function not inlinable");
292 edge
->caller
= caller
;
293 edge
->callee
= callee
;
294 edge
->call_expr
= call_expr
;
295 edge
->next_caller
= callee
->callers
;
296 edge
->next_callee
= caller
->callees
;
297 caller
->callees
= edge
;
298 callee
->callers
= edge
;
302 /* Remove the edge E the cgraph. */
305 cgraph_remove_edge (struct cgraph_edge
*e
)
307 struct cgraph_edge
**edge
, **edge2
;
309 for (edge
= &e
->callee
->callers
; *edge
&& *edge
!= e
;
310 edge
= &((*edge
)->next_caller
))
313 *edge
= (*edge
)->next_caller
;
314 for (edge2
= &e
->caller
->callees
; *edge2
&& *edge2
!= e
;
315 edge2
= &(*edge2
)->next_callee
)
318 *edge2
= (*edge2
)->next_callee
;
321 /* Redirect callee of E to N. The function does not update underlying
325 cgraph_redirect_edge_callee (struct cgraph_edge
*e
, struct cgraph_node
*n
)
327 struct cgraph_edge
**edge
;
329 for (edge
= &e
->callee
->callers
; *edge
&& *edge
!= e
;
330 edge
= &((*edge
)->next_caller
))
333 *edge
= (*edge
)->next_caller
;
335 e
->next_caller
= n
->callers
;
339 /* Remove the node from cgraph. */
342 cgraph_remove_node (struct cgraph_node
*node
)
347 while (node
->callers
)
348 cgraph_remove_edge (node
->callers
);
349 while (node
->callees
)
350 cgraph_remove_edge (node
->callees
);
352 cgraph_remove_node (node
->nested
);
355 struct cgraph_node
**node2
= &node
->origin
->nested
;
357 while (*node2
!= node
)
358 node2
= &(*node2
)->next_nested
;
359 *node2
= node
->next_nested
;
362 node
->previous
->next
= node
->next
;
364 cgraph_nodes
= node
->next
;
366 node
->next
->previous
= node
->previous
;
367 slot
= htab_find_slot (cgraph_hash
, node
, NO_INSERT
);
370 if (node
->next_clone
)
371 *slot
= node
->next_clone
;
374 htab_clear_slot (cgraph_hash
, slot
);
375 if (!dump_enabled_p (TDI_tree_all
))
377 DECL_SAVED_TREE (node
->decl
) = NULL
;
378 DECL_STRUCT_FUNCTION (node
->decl
) = NULL
;
385 struct cgraph_node
*n
;
387 for (n
= *slot
; n
->next_clone
!= node
; n
= n
->next_clone
)
389 n
->next_clone
= node
->next_clone
;
392 /* Work out whether we still need a function body (either there is inline
393 clone or there is out of line function whose body is not written). */
394 if (check_dead
&& flag_unit_at_a_time
)
396 struct cgraph_node
*n
;
398 for (n
= *slot
; n
; n
= n
->next_clone
)
399 if (n
->global
.inlined_to
400 || (!n
->global
.inlined_to
401 && !TREE_ASM_WRITTEN (n
->decl
) && !DECL_EXTERNAL (n
->decl
)))
403 if (!n
&& !dump_enabled_p (TDI_tree_all
))
405 DECL_SAVED_TREE (node
->decl
) = NULL
;
406 DECL_STRUCT_FUNCTION (node
->decl
) = NULL
;
407 DECL_INITIAL (node
->decl
) = error_mark_node
;
411 /* Do not free the structure itself so the walk over chain can continue. */
414 /* Notify finalize_compilation_unit that given node is reachable. */
417 cgraph_mark_reachable_node (struct cgraph_node
*node
)
419 if (!node
->reachable
&& node
->local
.finalized
)
421 notice_global_symbol (node
->decl
);
424 node
->next_needed
= cgraph_nodes_queue
;
425 cgraph_nodes_queue
= node
;
429 /* Likewise indicate that a node is needed, i.e. reachable via some
433 cgraph_mark_needed_node (struct cgraph_node
*node
)
436 cgraph_mark_reachable_node (node
);
439 /* Return local info for the compiled function. */
441 struct cgraph_local_info
*
442 cgraph_local_info (tree decl
)
444 struct cgraph_node
*node
;
446 gcc_assert (TREE_CODE (decl
) == FUNCTION_DECL
);
447 node
= cgraph_node (decl
);
451 /* Return local info for the compiled function. */
453 struct cgraph_global_info
*
454 cgraph_global_info (tree decl
)
456 struct cgraph_node
*node
;
458 gcc_assert (TREE_CODE (decl
) == FUNCTION_DECL
&& cgraph_global_info_ready
);
459 node
= cgraph_node (decl
);
460 return &node
->global
;
463 /* Return local info for the compiled function. */
465 struct cgraph_rtl_info
*
466 cgraph_rtl_info (tree decl
)
468 struct cgraph_node
*node
;
470 gcc_assert (TREE_CODE (decl
) == FUNCTION_DECL
);
471 node
= cgraph_node (decl
);
472 if (decl
!= current_function_decl
473 && !TREE_ASM_WRITTEN (node
->decl
))
478 /* Return name of the node used in debug output. */
480 cgraph_node_name (struct cgraph_node
*node
)
482 return lang_hooks
.decl_printable_name (node
->decl
, 2);
485 /* Dump given cgraph node. */
487 dump_cgraph_node (FILE *f
, struct cgraph_node
*node
)
489 struct cgraph_edge
*edge
;
490 fprintf (f
, "%s/%i:", cgraph_node_name (node
), node
->uid
);
491 if (node
->global
.inlined_to
)
492 fprintf (f
, " (inline copy in %s/%i)",
493 cgraph_node_name (node
->global
.inlined_to
),
494 node
->global
.inlined_to
->uid
);
495 if (node
->local
.self_insns
)
496 fprintf (f
, " %i insns", node
->local
.self_insns
);
497 if (node
->global
.insns
&& node
->global
.insns
!= node
->local
.self_insns
)
498 fprintf (f
, " (%i after inlining)", node
->global
.insns
);
500 fprintf (f
, " nested in: %s", cgraph_node_name (node
->origin
));
502 fprintf (f
, " needed");
503 else if (node
->reachable
)
504 fprintf (f
, " reachable");
505 if (DECL_SAVED_TREE (node
->decl
))
506 fprintf (f
, " tree");
508 fprintf (f
, " output");
509 if (node
->local
.local
)
510 fprintf (f
, " local");
511 if (node
->local
.disregard_inline_limits
)
512 fprintf (f
, " always_inline");
513 else if (node
->local
.inlinable
)
514 fprintf (f
, " inlinable");
515 if (TREE_ASM_WRITTEN (node
->decl
))
516 fprintf (f
, " asm_written");
518 fprintf (f
, "\n called by: ");
519 for (edge
= node
->callers
; edge
; edge
= edge
->next_caller
)
521 fprintf (f
, "%s/%i ", cgraph_node_name (edge
->caller
),
523 if (!edge
->inline_failed
)
524 fprintf(f
, "(inlined) ");
527 fprintf (f
, "\n calls: ");
528 for (edge
= node
->callees
; edge
; edge
= edge
->next_callee
)
530 fprintf (f
, "%s/%i ", cgraph_node_name (edge
->callee
),
532 if (!edge
->inline_failed
)
533 fprintf(f
, "(inlined) ");
538 /* Dump the callgraph. */
541 dump_cgraph (FILE *f
)
543 struct cgraph_node
*node
;
545 fprintf (f
, "callgraph:\n\n");
546 for (node
= cgraph_nodes
; node
; node
= node
->next
)
547 dump_cgraph_node (f
, node
);
550 /* Returns a hash code for P. */
553 hash_varpool_node (const void *p
)
555 const struct cgraph_varpool_node
*n
= p
;
556 return (hashval_t
) DECL_UID (n
->decl
);
559 /* Returns nonzero if P1 and P2 are equal. */
562 eq_varpool_node (const void *p1
, const void *p2
)
564 const struct cgraph_varpool_node
*n1
= p1
, *n2
= p2
;
565 return DECL_UID (n1
->decl
) == DECL_UID (n2
->decl
);
568 /* Return cgraph_varpool node assigned to DECL. Create new one when needed. */
569 struct cgraph_varpool_node
*
570 cgraph_varpool_node (tree decl
)
572 struct cgraph_varpool_node key
, *node
, **slot
;
574 gcc_assert (DECL_P (decl
) && TREE_CODE (decl
) != FUNCTION_DECL
);
576 if (!cgraph_varpool_hash
)
577 cgraph_varpool_hash
= htab_create_ggc (10, hash_varpool_node
,
578 eq_varpool_node
, NULL
);
580 slot
= (struct cgraph_varpool_node
**)
581 htab_find_slot (cgraph_varpool_hash
, &key
, INSERT
);
584 node
= ggc_alloc_cleared (sizeof (*node
));
586 node
->next
= cgraph_varpool_nodes
;
587 cgraph_varpool_n_nodes
++;
588 cgraph_varpool_nodes
= node
;
593 struct cgraph_varpool_node
*
594 cgraph_varpool_node_for_asm (tree asmname
)
596 struct cgraph_varpool_node
*node
;
598 for (node
= cgraph_varpool_nodes
; node
; node
= node
->next
)
599 if (decl_assembler_name_equal (node
->decl
, asmname
))
605 /* Set the DECL_ASSEMBLER_NAME and update cgraph hashtables. */
607 change_decl_assembler_name (tree decl
, tree name
)
609 if (!DECL_ASSEMBLER_NAME_SET_P (decl
))
611 SET_DECL_ASSEMBLER_NAME (decl
, name
);
614 if (name
== DECL_ASSEMBLER_NAME (decl
))
617 if (TREE_SYMBOL_REFERENCED (DECL_ASSEMBLER_NAME (decl
))
618 && DECL_RTL_SET_P (decl
))
619 warning ("%D renamed after being referenced in assembly", decl
);
621 SET_DECL_ASSEMBLER_NAME (decl
, name
);
624 /* Notify finalize_compilation_unit that given node is reachable
627 cgraph_varpool_mark_needed_node (struct cgraph_varpool_node
*node
)
629 if (!node
->needed
&& node
->finalized
)
631 node
->next_needed
= cgraph_varpool_nodes_queue
;
632 cgraph_varpool_nodes_queue
= node
;
633 notice_global_symbol (node
->decl
);
639 cgraph_varpool_finalize_decl (tree decl
)
641 struct cgraph_varpool_node
*node
= cgraph_varpool_node (decl
);
643 /* The first declaration of a variable that comes through this function
644 decides whether it is global (in C, has external linkage)
645 or local (in C, has internal linkage). So do nothing more
646 if this function has already run. */
651 node
->next_needed
= cgraph_varpool_nodes_queue
;
652 cgraph_varpool_nodes_queue
= node
;
653 notice_global_symbol (decl
);
655 node
->finalized
= true;
657 if (/* Externally visible variables must be output. The exception are
658 COMDAT functions that must be output only when they are needed. */
659 (TREE_PUBLIC (decl
) && !DECL_COMDAT (decl
))
660 /* Function whose name is output to the assembler file must be produced.
661 It is possible to assemble the name later after finalizing the function
662 and the fact is noticed in assemble_name then. */
663 || (DECL_ASSEMBLER_NAME_SET_P (decl
)
664 && TREE_SYMBOL_REFERENCED (DECL_ASSEMBLER_NAME (decl
))))
666 cgraph_varpool_mark_needed_node (node
);
671 cgraph_varpool_assemble_pending_decls (void)
673 bool changed
= false;
675 while (cgraph_varpool_nodes_queue
)
677 tree decl
= cgraph_varpool_nodes_queue
->decl
;
678 struct cgraph_varpool_node
*node
= cgraph_varpool_nodes_queue
;
680 cgraph_varpool_nodes_queue
= cgraph_varpool_nodes_queue
->next_needed
;
681 if (!TREE_ASM_WRITTEN (decl
))
683 assemble_variable (decl
, 0, 1, 0);
686 node
->next_needed
= NULL
;
691 /* Return true when the DECL can possibly be inlined. */
693 cgraph_function_possibly_inlined_p (tree decl
)
695 if (!cgraph_global_info_ready
)
696 return (DECL_INLINE (decl
) && !flag_really_no_inline
);
697 return DECL_POSSIBLY_INLINED (decl
);
700 /* Create clone of E in the node N represented by CALL_EXPR the callgraph. */
702 cgraph_clone_edge (struct cgraph_edge
*e
, struct cgraph_node
*n
, tree call_expr
)
704 struct cgraph_edge
*new = cgraph_create_edge (n
, e
->callee
, call_expr
);
706 new->inline_failed
= e
->inline_failed
;
710 /* Create node representing clone of N. */
712 cgraph_clone_node (struct cgraph_node
*n
)
714 struct cgraph_node
*new = cgraph_create_node ();
715 struct cgraph_edge
*e
;
718 new->origin
= n
->origin
;
721 new->next_nested
= new->origin
->nested
;
722 new->origin
->nested
= new;
724 new->analyzed
= n
->analyzed
;
725 new->local
= n
->local
;
726 new->global
= n
->global
;
729 for (e
= n
->callees
;e
; e
=e
->next_callee
)
730 cgraph_clone_edge (e
, new, e
->call_expr
);
732 new->next_clone
= n
->next_clone
;
738 /* NODE is no longer nested function; update cgraph accordingly. */
740 cgraph_unnest_node (struct cgraph_node
*node
)
742 struct cgraph_node
**node2
= &node
->origin
->nested
;
743 gcc_assert (node
->origin
);
745 while (*node2
!= node
)
746 node2
= &(*node2
)->next_nested
;
747 *node2
= node
->next_nested
;
750 #include "gt-cgraph.h"