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 a 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 inlininer.
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 /* We destructively update callgraph during inlining and thus we need to
103 keep information on whether inlining happened separately. */
104 htab_t cgraph_inline_hash;
106 /* The linked list of cgraph nodes. */
107 struct cgraph_node *cgraph_nodes;
109 /* Queue of cgraph nodes scheduled to be lowered. */
110 struct cgraph_node *cgraph_nodes_queue;
112 /* Number of nodes in existence. */
115 /* Maximal uid used in cgraph nodes. */
118 /* Set when whole unit has been analyzed so we can access global info. */
119 bool cgraph_global_info_ready = false;
121 /* Hash table used to convert declarations into nodes. */
122 static GTY((param_is (struct cgraph_varpool_node))) htab_t cgraph_varpool_hash;
124 /* Queue of cgraph nodes scheduled to be lowered and output. */
125 struct cgraph_varpool_node *cgraph_varpool_nodes_queue;
127 /* Number of nodes in existence. */
128 int cgraph_varpool_n_nodes;
130 /* The linked list of cgraph varpool nodes. */
131 static GTY(()) struct cgraph_varpool_node *cgraph_varpool_nodes;
133 static hashval_t hash_node (const void *);
134 static int eq_node (const void *, const void *);
136 /* Returns a hash code for P. */
139 hash_node (const void *p)
142 IDENTIFIER_HASH_VALUE (DECL_ASSEMBLER_NAME
143 (((struct cgraph_node *) p)->decl)));
146 /* Returns nonzero if P1 and P2 are equal. */
149 eq_node (const void *p1, const void *p2)
151 return ((DECL_ASSEMBLER_NAME (((struct cgraph_node *) p1)->decl)) ==
155 /* Allocate new callgraph node and insert it into basic data structures. */
156 static struct cgraph_node *
157 cgraph_create_node (void)
159 struct cgraph_node *node;
161 node = ggc_alloc_cleared (sizeof (*node));
162 node->next = cgraph_nodes;
163 node->uid = cgraph_max_uid++;
165 cgraph_nodes->previous = node;
166 node->previous = NULL;
172 /* Return cgraph node assigned to DECL. Create new one when needed. */
174 cgraph_node (tree decl)
176 struct cgraph_node *node;
177 struct cgraph_node **slot;
179 if (TREE_CODE (decl) != FUNCTION_DECL)
183 cgraph_hash = htab_create_ggc (10, hash_node, eq_node, NULL);
185 slot = (struct cgraph_node **)
186 htab_find_slot_with_hash (cgraph_hash, DECL_ASSEMBLER_NAME (decl),
187 IDENTIFIER_HASH_VALUE
188 (DECL_ASSEMBLER_NAME (decl)), INSERT);
192 node = cgraph_create_node ();
195 if (DECL_CONTEXT (decl) && TREE_CODE (DECL_CONTEXT (decl)) == FUNCTION_DECL)
197 node->origin = cgraph_node (DECL_CONTEXT (decl));
198 node->next_nested = node->origin->nested;
199 node->origin->nested = node;
204 /* Return callgraph edge representing CALL_EXPR. */
206 cgraph_edge (struct cgraph_node *node, tree call_expr)
208 struct cgraph_edge *e;
210 /* This loop may turn out to be performance problem. In such case adding
211 hashtables into call nodes with very many edges is probably best
212 solution. It is not good idea to add pointer into CALL_EXPR itself
213 because we want to make possible having multiple cgraph nodes representing
214 different clones of the same body before the body is actually cloned. */
215 for (e = node->callees; e; e= e->next_callee)
216 if (e->call_expr == call_expr)
221 /* Try to find existing function for identifier ID. */
223 cgraph_node_for_identifier (tree id)
225 struct cgraph_node **slot;
227 if (TREE_CODE (id) != IDENTIFIER_NODE)
233 slot = (struct cgraph_node **)
234 htab_find_slot_with_hash (cgraph_hash, id,
235 IDENTIFIER_HASH_VALUE (id), NO_INSERT);
241 /* Create edge from CALLER to CALLEE in the cgraph. */
244 cgraph_create_edge (struct cgraph_node *caller, struct cgraph_node *callee,
247 struct cgraph_edge *edge = ggc_alloc (sizeof (struct cgraph_edge));
248 #ifdef ENABLE_CHECKING
249 struct cgraph_edge *e;
251 for (e = caller->callees; e; e = e->next_callee)
252 if (e->call_expr == call_expr)
256 if (TREE_CODE (call_expr) != CALL_EXPR)
259 if (!DECL_SAVED_TREE (callee->decl))
260 edge->inline_failed = N_("function body not available");
261 else if (callee->local.redefined_extern_inline)
262 edge->inline_failed = N_("redefined extern inline functions are not "
263 "considered for inlining");
264 else if (callee->local.inlinable)
265 edge->inline_failed = N_("function not considered for inlining");
267 edge->inline_failed = N_("function not inlinable");
271 edge->caller = caller;
272 edge->callee = callee;
273 edge->call_expr = call_expr;
274 edge->next_caller = callee->callers;
275 edge->next_callee = caller->callees;
276 caller->callees = edge;
277 callee->callers = edge;
281 /* Remove the edge E the cgraph. */
284 cgraph_remove_edge (struct cgraph_edge *e)
286 struct cgraph_edge **edge, **edge2;
288 for (edge = &e->callee->callers; *edge && *edge != e;
289 edge = &((*edge)->next_caller))
293 *edge = (*edge)->next_caller;
294 for (edge2 = &e->caller->callees; *edge2 && *edge2 != e;
295 edge2 = &(*edge2)->next_callee)
299 *edge2 = (*edge2)->next_callee;
302 /* Redirect callee of E to N. The function does not update underlying
306 cgraph_redirect_edge_callee (struct cgraph_edge *e, struct cgraph_node *n)
308 struct cgraph_edge **edge;
310 for (edge = &e->callee->callers; *edge && *edge != e;
311 edge = &((*edge)->next_caller))
315 *edge = (*edge)->next_caller;
317 e->next_caller = n->callers;
321 /* Remove the node from cgraph. */
324 cgraph_remove_node (struct cgraph_node *node)
329 while (node->callers)
330 cgraph_remove_edge (node->callers);
331 while (node->callees)
332 cgraph_remove_edge (node->callees);
334 cgraph_remove_node (node->nested);
337 struct cgraph_node **node2 = &node->origin->nested;
339 while (*node2 != node)
340 node2 = &(*node2)->next_nested;
341 *node2 = node->next_nested;
344 node->previous->next = node->next;
346 cgraph_nodes = node->next;
348 node->next->previous = node->previous;
350 htab_find_slot_with_hash (cgraph_hash, DECL_ASSEMBLER_NAME (node->decl),
351 IDENTIFIER_HASH_VALUE (DECL_ASSEMBLER_NAME
352 (node->decl)), NO_INSERT);
355 if (node->next_clone)
356 *slot = node->next_clone;
359 htab_clear_slot (cgraph_hash, slot);
360 if (!dump_enabled_p (TDI_all))
362 DECL_SAVED_TREE (node->decl) = NULL;
363 DECL_STRUCT_FUNCTION (node->decl) = NULL;
370 struct cgraph_node *n;
372 for (n = *slot; n->next_clone != node; n = n->next_clone)
374 n->next_clone = node->next_clone;
377 /* Work out whether we still need a function body (either there is inline
378 clone or there is out of line function whose body is not written). */
379 if (check_dead && flag_unit_at_a_time)
381 struct cgraph_node *n;
383 for (n = *slot; n; n = n->next_clone)
384 if (n->global.inlined_to
385 || (!n->global.inlined_to
386 && !TREE_ASM_WRITTEN (n->decl) && !DECL_EXTERNAL (n->decl)))
388 if (!n && !dump_enabled_p (TDI_all))
390 DECL_SAVED_TREE (node->decl) = NULL;
391 DECL_STRUCT_FUNCTION (node->decl) = NULL;
395 /* Do not free the structure itself so the walk over chain can continue. */
398 /* Notify finalize_compilation_unit that given node is reachable. */
401 cgraph_mark_reachable_node (struct cgraph_node *node)
403 if (!node->reachable && node->local.finalized)
405 notice_global_symbol (node->decl);
408 node->next_needed = cgraph_nodes_queue;
409 cgraph_nodes_queue = node;
413 /* Likewise indicate that a node is needed, i.e. reachable via some
417 cgraph_mark_needed_node (struct cgraph_node *node)
420 cgraph_mark_reachable_node (node);
423 /* Return true when CALLER_DECL calls CALLEE_DECL. */
426 cgraph_calls_p (tree caller_decl, tree callee_decl)
428 struct cgraph_node *caller = cgraph_node (caller_decl);
429 struct cgraph_node *callee = cgraph_node (callee_decl);
430 struct cgraph_edge *edge;
432 for (edge = callee->callers; edge && (edge)->caller != caller;
433 edge = (edge->next_caller))
438 /* Return local info for the compiled function. */
440 struct cgraph_local_info *
441 cgraph_local_info (tree decl)
443 struct cgraph_node *node;
444 if (TREE_CODE (decl) != FUNCTION_DECL)
446 node = cgraph_node (decl);
450 /* Return local info for the compiled function. */
452 struct cgraph_global_info *
453 cgraph_global_info (tree decl)
455 struct cgraph_node *node;
456 if (TREE_CODE (decl) != FUNCTION_DECL || !cgraph_global_info_ready)
458 node = cgraph_node (decl);
459 return &node->global;
462 /* Return local info for the compiled function. */
464 struct cgraph_rtl_info *
465 cgraph_rtl_info (tree decl)
467 struct cgraph_node *node;
468 if (TREE_CODE (decl) != FUNCTION_DECL)
470 node = cgraph_node (decl);
471 if (decl != current_function_decl
472 && !TREE_ASM_WRITTEN (node->decl))
477 /* Return name of the node used in debug output. */
479 cgraph_node_name (struct cgraph_node *node)
481 return lang_hooks.decl_printable_name (node->decl, 2);
484 /* Dump given cgraph node. */
486 dump_cgraph_node (FILE *f, struct cgraph_node *node)
488 struct cgraph_edge *edge;
489 fprintf (f, "%s/%i:", cgraph_node_name (node), node->uid);
490 if (node->global.inlined_to)
491 fprintf (f, " (inline copy in %s/%i)",
492 cgraph_node_name (node->global.inlined_to),
493 node->global.inlined_to->uid);
494 if (node->local.self_insns)
495 fprintf (f, " %i insns", node->local.self_insns);
496 if (node->global.insns && node->global.insns != node->local.self_insns)
497 fprintf (f, " (%i after inlining)", node->global.insns);
499 fprintf (f, " nested in: %s", cgraph_node_name (node->origin));
501 fprintf (f, " needed");
502 else if (node->reachable)
503 fprintf (f, " reachable");
504 if (DECL_SAVED_TREE (node->decl))
505 fprintf (f, " tree");
507 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 cgraph_varpool_hash_node (const void *p)
556 IDENTIFIER_HASH_VALUE (DECL_ASSEMBLER_NAME
557 (((struct cgraph_varpool_node *) p)->decl)));
560 /* Returns nonzero if P1 and P2 are equal. */
563 eq_cgraph_varpool_node (const void *p1, const void *p2)
565 return ((DECL_ASSEMBLER_NAME (((struct cgraph_varpool_node *) p1)->decl)) ==
569 /* Return cgraph_varpool node assigned to DECL. Create new one when needed. */
570 struct cgraph_varpool_node *
571 cgraph_varpool_node (tree decl)
573 struct cgraph_varpool_node *node;
574 struct cgraph_varpool_node **slot;
576 if (!DECL_P (decl) || TREE_CODE (decl) == FUNCTION_DECL)
579 if (!cgraph_varpool_hash)
580 cgraph_varpool_hash = htab_create_ggc (10, cgraph_varpool_hash_node,
581 eq_cgraph_varpool_node, NULL);
582 slot = (struct cgraph_varpool_node **)
583 htab_find_slot_with_hash (cgraph_varpool_hash, DECL_ASSEMBLER_NAME (decl),
584 IDENTIFIER_HASH_VALUE (DECL_ASSEMBLER_NAME (decl)),
588 node = ggc_alloc_cleared (sizeof (*node));
590 cgraph_varpool_n_nodes++;
591 cgraph_varpool_nodes = node;
596 /* Set the DECL_ASSEMBLER_NAME and update cgraph hashtables. */
598 change_decl_assembler_name (tree decl, tree name)
600 struct cgraph_node *node = NULL;
601 struct cgraph_varpool_node *vnode = NULL;
604 if (!DECL_ASSEMBLER_NAME_SET_P (decl))
606 SET_DECL_ASSEMBLER_NAME (decl, name);
609 if (name == DECL_ASSEMBLER_NAME (decl))
612 if (TREE_SYMBOL_REFERENCED (DECL_ASSEMBLER_NAME (decl))
613 && DECL_RTL_SET_P (decl))
614 warning ("%D renamed after being referenced in assembly", decl);
616 if (TREE_CODE (decl) == FUNCTION_DECL && cgraph_hash)
618 /* Take a look whether declaration is in the cgraph structure. */
620 htab_find_slot_with_hash (cgraph_hash, DECL_ASSEMBLER_NAME (decl),
621 IDENTIFIER_HASH_VALUE (DECL_ASSEMBLER_NAME
626 /* It is, verify that we are the canonical node for this decl. */
627 if (node && node->decl == decl)
630 htab_clear_slot (cgraph_hash, slot);
635 if (TREE_CODE (decl) == VAR_DECL && TREE_STATIC (decl) && cgraph_varpool_hash)
637 /* Take a look whether declaration is in the cgraph structure. */
639 htab_find_slot_with_hash (cgraph_varpool_hash, DECL_ASSEMBLER_NAME (decl),
640 IDENTIFIER_HASH_VALUE (DECL_ASSEMBLER_NAME
645 /* It is, verify that we are the canonical vnode for this decl. */
646 if (vnode && vnode->decl == decl)
649 htab_clear_slot (cgraph_varpool_hash, slot);
654 SET_DECL_ASSEMBLER_NAME (decl, name);
658 htab_find_slot_with_hash (cgraph_hash, name,
659 IDENTIFIER_HASH_VALUE (name), INSERT);
667 htab_find_slot_with_hash (cgraph_varpool_hash, name,
668 IDENTIFIER_HASH_VALUE (name), INSERT);
675 /* Try to find existing function for identifier ID. */
676 struct cgraph_varpool_node *
677 cgraph_varpool_node_for_identifier (tree id)
679 struct cgraph_varpool_node **slot;
681 if (TREE_CODE (id) != IDENTIFIER_NODE)
684 if (!cgraph_varpool_hash)
687 slot = (struct cgraph_varpool_node **)
688 htab_find_slot_with_hash (cgraph_varpool_hash, id,
689 IDENTIFIER_HASH_VALUE (id), NO_INSERT);
695 /* Notify finalize_compilation_unit that given node is reachable
698 cgraph_varpool_mark_needed_node (struct cgraph_varpool_node *node)
700 if (!node->needed && node->finalized)
702 node->next_needed = cgraph_varpool_nodes_queue;
703 cgraph_varpool_nodes_queue = node;
704 notice_global_symbol (node->decl);
710 cgraph_varpool_finalize_decl (tree decl)
712 struct cgraph_varpool_node *node = cgraph_varpool_node (decl);
714 /* The first declaration of a variable that comes through this function
715 decides whether it is global (in C, has external linkage)
716 or local (in C, has internal linkage). So do nothing more
717 if this function has already run. */
722 node->next_needed = cgraph_varpool_nodes_queue;
723 cgraph_varpool_nodes_queue = node;
724 notice_global_symbol (decl);
726 node->finalized = true;
728 if (/* Externally visible variables must be output. The exception are
729 COMDAT functions that must be output only when they are needed. */
730 (TREE_PUBLIC (decl) && !DECL_COMDAT (decl))
731 /* Function whose name is output to the assembler file must be produced.
732 It is possible to assemble the name later after finalizing the function
733 and the fact is noticed in assemble_name then. */
734 || (DECL_ASSEMBLER_NAME_SET_P (decl)
735 && TREE_SYMBOL_REFERENCED (DECL_ASSEMBLER_NAME (decl))))
737 cgraph_varpool_mark_needed_node (node);
742 cgraph_varpool_assemble_pending_decls (void)
744 bool changed = false;
746 while (cgraph_varpool_nodes_queue)
748 tree decl = cgraph_varpool_nodes_queue->decl;
749 struct cgraph_varpool_node *node = cgraph_varpool_nodes_queue;
751 cgraph_varpool_nodes_queue = cgraph_varpool_nodes_queue->next_needed;
752 if (!TREE_ASM_WRITTEN (decl))
754 assemble_variable (decl, 0, 1, 0);
757 node->next_needed = NULL;
762 /* Return true when the DECL can possibly be inlined. */
764 cgraph_function_possibly_inlined_p (tree decl)
766 if (!cgraph_global_info_ready)
767 return (DECL_INLINE (decl) && !flag_really_no_inline);
768 if (!cgraph_inline_hash)
770 return (htab_find_slot (cgraph_inline_hash, DECL_ASSEMBLER_NAME (decl),
774 /* Create clone of E in the node N represented by CALL_EXPR the callgraph. */
776 cgraph_clone_edge (struct cgraph_edge *e, struct cgraph_node *n, tree call_expr)
778 struct cgraph_edge *new = cgraph_create_edge (n, e->callee, call_expr);
780 new->inline_failed = e->inline_failed;
784 /* Create node representing clone of N. */
786 cgraph_clone_node (struct cgraph_node *n)
788 struct cgraph_node *new = cgraph_create_node ();
789 struct cgraph_edge *e;
792 new->origin = n->origin;
795 new->next_nested = new->origin->nested;
796 new->origin->nested = new;
798 new->analyzed = n->analyzed;
799 new->local = n->local;
800 new->global = n->global;
803 for (e = n->callees;e; e=e->next_callee)
804 cgraph_clone_edge (e, new, e->call_expr);
806 new->next_clone = n->next_clone;
811 #include "gt-cgraph.h"