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 /* Return callgraph edge representing CALL_EXPR. */
199 cgraph_edge (struct cgraph_node
*node
, tree call_expr
)
201 struct cgraph_edge
*e
;
203 /* This loop may turn out to be performance problem. In such case adding
204 hashtables into call nodes with very many edges is probably best
205 solution. It is not good idea to add pointer into CALL_EXPR itself
206 because we want to make possible having multiple cgraph nodes representing
207 different clones of the same body before the body is actually cloned. */
208 for (e
= node
->callees
; e
; e
= e
->next_callee
)
209 if (e
->call_expr
== call_expr
)
214 /* Create edge from CALLER to CALLEE in the cgraph. */
217 cgraph_create_edge (struct cgraph_node
*caller
, struct cgraph_node
*callee
,
220 struct cgraph_edge
*edge
= ggc_alloc (sizeof (struct cgraph_edge
));
221 #ifdef ENABLE_CHECKING
222 struct cgraph_edge
*e
;
224 for (e
= caller
->callees
; e
; e
= e
->next_callee
)
225 gcc_assert (e
->call_expr
!= call_expr
);
228 gcc_assert (TREE_CODE (call_expr
) == CALL_EXPR
);
230 if (!DECL_SAVED_TREE (callee
->decl
))
231 edge
->inline_failed
= N_("function body not available");
232 else if (callee
->local
.redefined_extern_inline
)
233 edge
->inline_failed
= N_("redefined extern inline functions are not "
234 "considered for inlining");
235 else if (callee
->local
.inlinable
)
236 edge
->inline_failed
= N_("function not considered for inlining");
238 edge
->inline_failed
= N_("function not inlinable");
242 edge
->caller
= caller
;
243 edge
->callee
= callee
;
244 edge
->call_expr
= call_expr
;
245 edge
->next_caller
= callee
->callers
;
246 edge
->next_callee
= caller
->callees
;
247 caller
->callees
= edge
;
248 callee
->callers
= edge
;
252 /* Remove the edge E the cgraph. */
255 cgraph_remove_edge (struct cgraph_edge
*e
)
257 struct cgraph_edge
**edge
, **edge2
;
259 for (edge
= &e
->callee
->callers
; *edge
&& *edge
!= e
;
260 edge
= &((*edge
)->next_caller
))
263 *edge
= (*edge
)->next_caller
;
264 for (edge2
= &e
->caller
->callees
; *edge2
&& *edge2
!= e
;
265 edge2
= &(*edge2
)->next_callee
)
268 *edge2
= (*edge2
)->next_callee
;
271 /* Redirect callee of E to N. The function does not update underlying
275 cgraph_redirect_edge_callee (struct cgraph_edge
*e
, struct cgraph_node
*n
)
277 struct cgraph_edge
**edge
;
279 for (edge
= &e
->callee
->callers
; *edge
&& *edge
!= e
;
280 edge
= &((*edge
)->next_caller
))
283 *edge
= (*edge
)->next_caller
;
285 e
->next_caller
= n
->callers
;
289 /* Remove the node from cgraph. */
292 cgraph_remove_node (struct cgraph_node
*node
)
297 while (node
->callers
)
298 cgraph_remove_edge (node
->callers
);
299 while (node
->callees
)
300 cgraph_remove_edge (node
->callees
);
302 cgraph_remove_node (node
->nested
);
305 struct cgraph_node
**node2
= &node
->origin
->nested
;
307 while (*node2
!= node
)
308 node2
= &(*node2
)->next_nested
;
309 *node2
= node
->next_nested
;
312 node
->previous
->next
= node
->next
;
314 cgraph_nodes
= node
->next
;
316 node
->next
->previous
= node
->previous
;
317 slot
= htab_find_slot (cgraph_hash
, node
, NO_INSERT
);
320 if (node
->next_clone
)
321 *slot
= node
->next_clone
;
324 htab_clear_slot (cgraph_hash
, slot
);
325 if (!dump_enabled_p (TDI_tree_all
))
327 DECL_SAVED_TREE (node
->decl
) = NULL
;
328 DECL_STRUCT_FUNCTION (node
->decl
) = NULL
;
335 struct cgraph_node
*n
;
337 for (n
= *slot
; n
->next_clone
!= node
; n
= n
->next_clone
)
339 n
->next_clone
= node
->next_clone
;
342 /* Work out whether we still need a function body (either there is inline
343 clone or there is out of line function whose body is not written). */
344 if (check_dead
&& flag_unit_at_a_time
)
346 struct cgraph_node
*n
;
348 for (n
= *slot
; n
; n
= n
->next_clone
)
349 if (n
->global
.inlined_to
350 || (!n
->global
.inlined_to
351 && !TREE_ASM_WRITTEN (n
->decl
) && !DECL_EXTERNAL (n
->decl
)))
353 if (!n
&& !dump_enabled_p (TDI_tree_all
))
355 DECL_SAVED_TREE (node
->decl
) = NULL
;
356 DECL_STRUCT_FUNCTION (node
->decl
) = NULL
;
357 DECL_INITIAL (node
->decl
) = error_mark_node
;
361 /* Do not free the structure itself so the walk over chain can continue. */
364 /* Notify finalize_compilation_unit that given node is reachable. */
367 cgraph_mark_reachable_node (struct cgraph_node
*node
)
369 if (!node
->reachable
&& node
->local
.finalized
)
371 notice_global_symbol (node
->decl
);
374 node
->next_needed
= cgraph_nodes_queue
;
375 cgraph_nodes_queue
= node
;
379 /* Likewise indicate that a node is needed, i.e. reachable via some
383 cgraph_mark_needed_node (struct cgraph_node
*node
)
386 cgraph_mark_reachable_node (node
);
389 /* Return local info for the compiled function. */
391 struct cgraph_local_info
*
392 cgraph_local_info (tree decl
)
394 struct cgraph_node
*node
;
396 gcc_assert (TREE_CODE (decl
) == FUNCTION_DECL
);
397 node
= cgraph_node (decl
);
401 /* Return local info for the compiled function. */
403 struct cgraph_global_info
*
404 cgraph_global_info (tree decl
)
406 struct cgraph_node
*node
;
408 gcc_assert (TREE_CODE (decl
) == FUNCTION_DECL
&& cgraph_global_info_ready
);
409 node
= cgraph_node (decl
);
410 return &node
->global
;
413 /* Return local info for the compiled function. */
415 struct cgraph_rtl_info
*
416 cgraph_rtl_info (tree decl
)
418 struct cgraph_node
*node
;
420 gcc_assert (TREE_CODE (decl
) == FUNCTION_DECL
);
421 node
= cgraph_node (decl
);
422 if (decl
!= current_function_decl
423 && !TREE_ASM_WRITTEN (node
->decl
))
428 /* Return name of the node used in debug output. */
430 cgraph_node_name (struct cgraph_node
*node
)
432 return lang_hooks
.decl_printable_name (node
->decl
, 2);
435 /* Dump given cgraph node. */
437 dump_cgraph_node (FILE *f
, struct cgraph_node
*node
)
439 struct cgraph_edge
*edge
;
440 fprintf (f
, "%s/%i:", cgraph_node_name (node
), node
->uid
);
441 if (node
->global
.inlined_to
)
442 fprintf (f
, " (inline copy in %s/%i)",
443 cgraph_node_name (node
->global
.inlined_to
),
444 node
->global
.inlined_to
->uid
);
445 if (node
->local
.self_insns
)
446 fprintf (f
, " %i insns", node
->local
.self_insns
);
447 if (node
->global
.insns
&& node
->global
.insns
!= node
->local
.self_insns
)
448 fprintf (f
, " (%i after inlining)", node
->global
.insns
);
450 fprintf (f
, " nested in: %s", cgraph_node_name (node
->origin
));
452 fprintf (f
, " needed");
453 else if (node
->reachable
)
454 fprintf (f
, " reachable");
455 if (DECL_SAVED_TREE (node
->decl
))
456 fprintf (f
, " tree");
458 fprintf (f
, " output");
459 if (node
->local
.local
)
460 fprintf (f
, " local");
461 if (node
->local
.disregard_inline_limits
)
462 fprintf (f
, " always_inline");
463 else if (node
->local
.inlinable
)
464 fprintf (f
, " inlinable");
465 if (TREE_ASM_WRITTEN (node
->decl
))
466 fprintf (f
, " asm_written");
468 fprintf (f
, "\n called by: ");
469 for (edge
= node
->callers
; edge
; edge
= edge
->next_caller
)
471 fprintf (f
, "%s/%i ", cgraph_node_name (edge
->caller
),
473 if (!edge
->inline_failed
)
474 fprintf(f
, "(inlined) ");
477 fprintf (f
, "\n calls: ");
478 for (edge
= node
->callees
; edge
; edge
= edge
->next_callee
)
480 fprintf (f
, "%s/%i ", cgraph_node_name (edge
->callee
),
482 if (!edge
->inline_failed
)
483 fprintf(f
, "(inlined) ");
488 /* Dump the callgraph. */
491 dump_cgraph (FILE *f
)
493 struct cgraph_node
*node
;
495 fprintf (f
, "callgraph:\n\n");
496 for (node
= cgraph_nodes
; node
; node
= node
->next
)
497 dump_cgraph_node (f
, node
);
500 /* Returns a hash code for P. */
503 hash_varpool_node (const void *p
)
505 const struct cgraph_varpool_node
*n
= p
;
506 return (hashval_t
) DECL_UID (n
->decl
);
509 /* Returns nonzero if P1 and P2 are equal. */
512 eq_varpool_node (const void *p1
, const void *p2
)
514 const struct cgraph_varpool_node
*n1
= p1
, *n2
= p2
;
515 return DECL_UID (n1
->decl
) == DECL_UID (n2
->decl
);
518 /* Return cgraph_varpool node assigned to DECL. Create new one when needed. */
519 struct cgraph_varpool_node
*
520 cgraph_varpool_node (tree decl
)
522 struct cgraph_varpool_node key
, *node
, **slot
;
524 gcc_assert (DECL_P (decl
) && TREE_CODE (decl
) != FUNCTION_DECL
);
526 if (!cgraph_varpool_hash
)
527 cgraph_varpool_hash
= htab_create_ggc (10, hash_varpool_node
,
528 eq_varpool_node
, NULL
);
530 slot
= (struct cgraph_varpool_node
**)
531 htab_find_slot (cgraph_varpool_hash
, &key
, INSERT
);
534 node
= ggc_alloc_cleared (sizeof (*node
));
536 cgraph_varpool_n_nodes
++;
537 cgraph_varpool_nodes
= node
;
542 /* Set the DECL_ASSEMBLER_NAME and update cgraph hashtables. */
544 change_decl_assembler_name (tree decl
, tree name
)
546 if (!DECL_ASSEMBLER_NAME_SET_P (decl
))
548 SET_DECL_ASSEMBLER_NAME (decl
, name
);
551 if (name
== DECL_ASSEMBLER_NAME (decl
))
554 if (TREE_SYMBOL_REFERENCED (DECL_ASSEMBLER_NAME (decl
))
555 && DECL_RTL_SET_P (decl
))
556 warning ("%D renamed after being referenced in assembly", decl
);
558 SET_DECL_ASSEMBLER_NAME (decl
, name
);
561 /* Notify finalize_compilation_unit that given node is reachable
564 cgraph_varpool_mark_needed_node (struct cgraph_varpool_node
*node
)
566 if (!node
->needed
&& node
->finalized
)
568 node
->next_needed
= cgraph_varpool_nodes_queue
;
569 cgraph_varpool_nodes_queue
= node
;
570 notice_global_symbol (node
->decl
);
576 cgraph_varpool_finalize_decl (tree decl
)
578 struct cgraph_varpool_node
*node
= cgraph_varpool_node (decl
);
580 /* The first declaration of a variable that comes through this function
581 decides whether it is global (in C, has external linkage)
582 or local (in C, has internal linkage). So do nothing more
583 if this function has already run. */
588 node
->next_needed
= cgraph_varpool_nodes_queue
;
589 cgraph_varpool_nodes_queue
= node
;
590 notice_global_symbol (decl
);
592 node
->finalized
= true;
594 if (/* Externally visible variables must be output. The exception are
595 COMDAT functions that must be output only when they are needed. */
596 (TREE_PUBLIC (decl
) && !DECL_COMDAT (decl
))
597 /* Function whose name is output to the assembler file must be produced.
598 It is possible to assemble the name later after finalizing the function
599 and the fact is noticed in assemble_name then. */
600 || (DECL_ASSEMBLER_NAME_SET_P (decl
)
601 && TREE_SYMBOL_REFERENCED (DECL_ASSEMBLER_NAME (decl
))))
603 cgraph_varpool_mark_needed_node (node
);
608 cgraph_varpool_assemble_pending_decls (void)
610 bool changed
= false;
612 while (cgraph_varpool_nodes_queue
)
614 tree decl
= cgraph_varpool_nodes_queue
->decl
;
615 struct cgraph_varpool_node
*node
= cgraph_varpool_nodes_queue
;
617 cgraph_varpool_nodes_queue
= cgraph_varpool_nodes_queue
->next_needed
;
618 if (!TREE_ASM_WRITTEN (decl
))
620 assemble_variable (decl
, 0, 1, 0);
623 node
->next_needed
= NULL
;
628 /* Return true when the DECL can possibly be inlined. */
630 cgraph_function_possibly_inlined_p (tree decl
)
632 if (!cgraph_global_info_ready
)
633 return (DECL_INLINE (decl
) && !flag_really_no_inline
);
634 return DECL_POSSIBLY_INLINED (decl
);
637 /* Create clone of E in the node N represented by CALL_EXPR the callgraph. */
639 cgraph_clone_edge (struct cgraph_edge
*e
, struct cgraph_node
*n
, tree call_expr
)
641 struct cgraph_edge
*new = cgraph_create_edge (n
, e
->callee
, call_expr
);
643 new->inline_failed
= e
->inline_failed
;
647 /* Create node representing clone of N. */
649 cgraph_clone_node (struct cgraph_node
*n
)
651 struct cgraph_node
*new = cgraph_create_node ();
652 struct cgraph_edge
*e
;
655 new->origin
= n
->origin
;
658 new->next_nested
= new->origin
->nested
;
659 new->origin
->nested
= new;
661 new->analyzed
= n
->analyzed
;
662 new->local
= n
->local
;
663 new->global
= n
->global
;
666 for (e
= n
->callees
;e
; e
=e
->next_callee
)
667 cgraph_clone_edge (e
, new, e
->call_expr
);
669 new->next_clone
= n
->next_clone
;
675 /* NODE is no longer nested function; update cgraph accordingly. */
677 cgraph_unnest_node (struct cgraph_node
*node
)
679 struct cgraph_node
**node2
= &node
->origin
->nested
;
680 gcc_assert (node
->origin
);
682 while (*node2
!= node
)
683 node2
= &(*node2
)->next_nested
;
684 *node2
= node
->next_nested
;
687 #include "gt-cgraph.h"