1 /* Callgraph handling code.
2 Copyright (C) 2003, 2004, 2005, 2006, 2007, 2008
3 Free Software Foundation, Inc.
4 Contributed by Jan Hubicka
6 This file is part of GCC.
8 GCC is free software; you can redistribute it and/or modify it under
9 the terms of the GNU General Public License as published by the Free
10 Software Foundation; either version 3, or (at your option) any later
13 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
14 WARRANTY; without even the implied warranty of MERCHANTABILITY or
15 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
18 You should have received a copy of the GNU General Public License
19 along with GCC; see the file COPYING3. If not see
20 <http://www.gnu.org/licenses/>. */
22 /* This file contains basic routines manipulating call graph
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.
33 The mapping from declarations to call-graph nodes is done using hash table
34 based on DECL_UID. The call-graph nodes are created lazily using
35 cgraph_node function when called for unknown declaration.
37 The callgraph at the moment does not represent indirect calls or calls
38 from other compilation unit. Flag NEEDED is set for each node that may
39 be accessed in such an invisible way and it shall be considered an
40 entry point to the callgraph.
42 Interprocedural information:
44 Callgraph is place to store data needed for interprocedural optimization.
45 All data structures are divided into three components: local_info that
46 is produced while analyzing the function, global_info that is result
47 of global walking of the callgraph on the end of compilation and
48 rtl_info used by RTL backend to propagate data from already compiled
49 functions to their callers.
53 The function inlining information is decided in advance and maintained
54 in the callgraph as so called inline plan.
55 For each inlined call, the callee's node is cloned to represent the
56 new function copy produced by inliner.
57 Each inlined call gets a unique corresponding clone node of the callee
58 and the data structure is updated while inlining is performed, so
59 the clones are eliminated and their callee edges redirected to the
62 Each edge has "inline_failed" field. When the field is set to NULL,
63 the call will be inlined. When it is non-NULL it contains a reason
64 why inlining wasn't performed. */
68 #include "coretypes.h"
71 #include "tree-inline.h"
72 #include "langhooks.h"
79 #include "basic-block.h"
84 #include "tree-gimple.h"
85 #include "tree-dump.h"
86 #include "tree-flow.h"
88 static void cgraph_node_remove_callers (struct cgraph_node *node);
89 static inline void cgraph_edge_remove_caller (struct cgraph_edge *e);
90 static inline void cgraph_edge_remove_callee (struct cgraph_edge *e);
92 /* Hash table used to convert declarations into nodes. */
93 static GTY((param_is (struct cgraph_node))) htab_t cgraph_hash;
94 /* Hash table used to convert assembler names into nodes. */
95 static GTY((param_is (struct cgraph_node))) htab_t assembler_name_hash;
97 /* The linked list of cgraph nodes. */
98 struct cgraph_node *cgraph_nodes;
100 /* Queue of cgraph nodes scheduled to be lowered. */
101 struct cgraph_node *cgraph_nodes_queue;
103 /* Queue of cgraph nodes scheduled to be added into cgraph. This is a
104 secondary queue used during optimization to accommodate passes that
105 may generate new functions that need to be optimized and expanded. */
106 struct cgraph_node *cgraph_new_nodes;
108 /* Number of nodes in existence. */
111 /* Maximal uid used in cgraph nodes. */
114 /* Maximal uid used in cgraph edges. */
115 int cgraph_edge_max_uid;
117 /* Maximal pid used for profiling */
120 /* Set when whole unit has been analyzed so we can access global info. */
121 bool cgraph_global_info_ready = false;
123 /* What state callgraph is in right now. */
124 enum cgraph_state cgraph_state = CGRAPH_STATE_CONSTRUCTION;
126 /* Set when the cgraph is fully build and the basic flags are computed. */
127 bool cgraph_function_flags_ready = false;
129 /* Linked list of cgraph asm nodes. */
130 struct cgraph_asm_node *cgraph_asm_nodes;
132 /* Last node in cgraph_asm_nodes. */
133 static GTY(()) struct cgraph_asm_node *cgraph_asm_last_node;
135 /* The order index of the next cgraph node to be created. This is
136 used so that we can sort the cgraph nodes in order by when we saw
137 them, to support -fno-toplevel-reorder. */
140 /* List of hooks trigerred on cgraph_edge events. */
141 struct cgraph_edge_hook_list {
142 cgraph_edge_hook hook;
144 struct cgraph_edge_hook_list *next;
147 /* List of hooks trigerred on cgraph_node events. */
148 struct cgraph_node_hook_list {
149 cgraph_node_hook hook;
151 struct cgraph_node_hook_list *next;
154 /* List of hooks trigerred on events involving two cgraph_edges. */
155 struct cgraph_2edge_hook_list {
156 cgraph_2edge_hook hook;
158 struct cgraph_2edge_hook_list *next;
161 /* List of hooks trigerred on events involving two cgraph_nodes. */
162 struct cgraph_2node_hook_list {
163 cgraph_2node_hook hook;
165 struct cgraph_2node_hook_list *next;
168 /* List of hooks triggered when an edge is removed. */
169 struct cgraph_edge_hook_list *first_cgraph_edge_removal_hook;
170 /* List of hooks triggered when a node is removed. */
171 struct cgraph_node_hook_list *first_cgraph_node_removal_hook;
172 /* List of hooks triggered when an edge is duplicated. */
173 struct cgraph_2edge_hook_list *first_cgraph_edge_duplicated_hook;
174 /* List of hooks triggered when a node is duplicated. */
175 struct cgraph_2node_hook_list *first_cgraph_node_duplicated_hook;
178 /* Register HOOK to be called with DATA on each removed edge. */
179 struct cgraph_edge_hook_list *
180 cgraph_add_edge_removal_hook (cgraph_edge_hook hook, void *data)
182 struct cgraph_edge_hook_list *entry;
183 struct cgraph_edge_hook_list **ptr = &first_cgraph_edge_removal_hook;
185 entry = (struct cgraph_edge_hook_list *) xmalloc (sizeof (*entry));
195 /* Remove ENTRY from the list of hooks called on removing edges. */
197 cgraph_remove_edge_removal_hook (struct cgraph_edge_hook_list *entry)
199 struct cgraph_edge_hook_list **ptr = &first_cgraph_edge_removal_hook;
201 while (*ptr != entry)
206 /* Call all edge removal hooks. */
208 cgraph_call_edge_removal_hooks (struct cgraph_edge *e)
210 struct cgraph_edge_hook_list *entry = first_cgraph_edge_removal_hook;
213 entry->hook (e, entry->data);
218 /* Register HOOK to be called with DATA on each removed node. */
219 struct cgraph_node_hook_list *
220 cgraph_add_node_removal_hook (cgraph_node_hook hook, void *data)
222 struct cgraph_node_hook_list *entry;
223 struct cgraph_node_hook_list **ptr = &first_cgraph_node_removal_hook;
225 entry = (struct cgraph_node_hook_list *) xmalloc (sizeof (*entry));
235 /* Remove ENTRY from the list of hooks called on removing nodes. */
237 cgraph_remove_node_removal_hook (struct cgraph_node_hook_list *entry)
239 struct cgraph_node_hook_list **ptr = &first_cgraph_node_removal_hook;
241 while (*ptr != entry)
246 /* Call all node removal hooks. */
248 cgraph_call_node_removal_hooks (struct cgraph_node *node)
250 struct cgraph_node_hook_list *entry = first_cgraph_node_removal_hook;
253 entry->hook (node, entry->data);
258 /* Register HOOK to be called with DATA on each duplicated edge. */
259 struct cgraph_2edge_hook_list *
260 cgraph_add_edge_duplication_hook (cgraph_2edge_hook hook, void *data)
262 struct cgraph_2edge_hook_list *entry;
263 struct cgraph_2edge_hook_list **ptr = &first_cgraph_edge_duplicated_hook;
265 entry = (struct cgraph_2edge_hook_list *) xmalloc (sizeof (*entry));
275 /* Remove ENTRY from the list of hooks called on duplicating edges. */
277 cgraph_remove_edge_duplication_hook (struct cgraph_2edge_hook_list *entry)
279 struct cgraph_2edge_hook_list **ptr = &first_cgraph_edge_duplicated_hook;
281 while (*ptr != entry)
286 /* Call all edge duplication hooks. */
288 cgraph_call_edge_duplication_hooks (struct cgraph_edge *cs1,
289 struct cgraph_edge *cs2)
291 struct cgraph_2edge_hook_list *entry = first_cgraph_edge_duplicated_hook;
294 entry->hook (cs1, cs2, entry->data);
299 /* Register HOOK to be called with DATA on each duplicated node. */
300 struct cgraph_2node_hook_list *
301 cgraph_add_node_duplication_hook (cgraph_2node_hook hook, void *data)
303 struct cgraph_2node_hook_list *entry;
304 struct cgraph_2node_hook_list **ptr = &first_cgraph_node_duplicated_hook;
306 entry = (struct cgraph_2node_hook_list *) xmalloc (sizeof (*entry));
316 /* Remove ENTRY from the list of hooks called on duplicating nodes. */
318 cgraph_remove_node_duplication_hook (struct cgraph_2node_hook_list *entry)
320 struct cgraph_2node_hook_list **ptr = &first_cgraph_node_duplicated_hook;
322 while (*ptr != entry)
327 /* Call all node duplication hooks. */
329 cgraph_call_node_duplication_hooks (struct cgraph_node *node1,
330 struct cgraph_node *node2)
332 struct cgraph_2node_hook_list *entry = first_cgraph_node_duplicated_hook;
335 entry->hook (node1, node2, entry->data);
340 /* Returns a hash code for P. */
343 hash_node (const void *p)
345 const struct cgraph_node *n = (const struct cgraph_node *) p;
346 return (hashval_t) DECL_UID (n->decl);
349 /* Returns nonzero if P1 and P2 are equal. */
352 eq_node (const void *p1, const void *p2)
354 const struct cgraph_node *n1 = (const struct cgraph_node *) p1;
355 const struct cgraph_node *n2 = (const struct cgraph_node *) p2;
356 return DECL_UID (n1->decl) == DECL_UID (n2->decl);
359 /* Allocate new callgraph node and insert it into basic data structures. */
361 static struct cgraph_node *
362 cgraph_create_node (void)
364 struct cgraph_node *node;
366 node = GGC_CNEW (struct cgraph_node);
367 node->next = cgraph_nodes;
368 node->uid = cgraph_max_uid++;
370 node->order = cgraph_order++;
372 cgraph_nodes->previous = node;
373 node->previous = NULL;
374 node->global.estimated_growth = INT_MIN;
380 /* Return cgraph node assigned to DECL. Create new one when needed. */
383 cgraph_node (tree decl)
385 struct cgraph_node key, *node, **slot;
387 gcc_assert (TREE_CODE (decl) == FUNCTION_DECL);
390 cgraph_hash = htab_create_ggc (10, hash_node, eq_node, NULL);
394 slot = (struct cgraph_node **) htab_find_slot (cgraph_hash, &key, INSERT);
399 if (!node->master_clone)
400 node->master_clone = node;
404 node = cgraph_create_node ();
407 if (DECL_CONTEXT (decl) && TREE_CODE (DECL_CONTEXT (decl)) == FUNCTION_DECL)
409 node->origin = cgraph_node (DECL_CONTEXT (decl));
410 node->next_nested = node->origin->nested;
411 node->origin->nested = node;
412 node->master_clone = node;
415 /* This code can go away once flag_unit_at_a_mode is removed. */
416 if (assembler_name_hash)
418 tree name = DECL_ASSEMBLER_NAME (node->decl);
419 slot = ((struct cgraph_node **)
420 htab_find_slot_with_hash (assembler_name_hash, name,
421 decl_assembler_name_hash (name),
429 /* Insert already constructed node into hashtable. */
432 cgraph_insert_node_to_hashtable (struct cgraph_node *node)
434 struct cgraph_node **slot;
436 slot = (struct cgraph_node **) htab_find_slot (cgraph_hash, node, INSERT);
442 /* Returns a hash code for P. */
445 hash_node_by_assembler_name (const void *p)
447 const struct cgraph_node *n = (const struct cgraph_node *) p;
448 return (hashval_t) decl_assembler_name_hash (DECL_ASSEMBLER_NAME (n->decl));
451 /* Returns nonzero if P1 and P2 are equal. */
454 eq_assembler_name (const void *p1, const void *p2)
456 const struct cgraph_node *n1 = (const struct cgraph_node *) p1;
457 const_tree name = (const_tree)p2;
458 return (decl_assembler_name_equal (n1->decl, name));
461 /* Return the cgraph node that has ASMNAME for its DECL_ASSEMBLER_NAME.
462 Return NULL if there's no such node. */
465 cgraph_node_for_asm (tree asmname)
467 struct cgraph_node *node;
470 if (!assembler_name_hash)
472 assembler_name_hash =
473 htab_create_ggc (10, hash_node_by_assembler_name, eq_assembler_name,
475 for (node = cgraph_nodes; node; node = node->next)
476 if (!node->global.inlined_to)
478 tree name = DECL_ASSEMBLER_NAME (node->decl);
479 slot = htab_find_slot_with_hash (assembler_name_hash, name,
480 decl_assembler_name_hash (name),
482 /* We can have multiple declarations with same assembler name. For C++
483 it is __builtin_strlen and strlen, for instance. Do we need to
484 record them all? Original implementation marked just first one
485 so lets hope for the best. */
492 slot = htab_find_slot_with_hash (assembler_name_hash, asmname,
493 decl_assembler_name_hash (asmname),
497 return (struct cgraph_node *) *slot;
501 /* Returns a hash value for X (which really is a die_struct). */
504 edge_hash (const void *x)
506 return htab_hash_pointer (((const struct cgraph_edge *) x)->call_stmt);
509 /* Return nonzero if decl_id of die_struct X is the same as UID of decl *Y. */
512 edge_eq (const void *x, const void *y)
514 return ((const struct cgraph_edge *) x)->call_stmt == y;
517 /* Return callgraph edge representing CALL_EXPR statement. */
519 cgraph_edge (struct cgraph_node *node, tree call_stmt)
521 struct cgraph_edge *e, *e2;
524 if (node->call_site_hash)
525 return (struct cgraph_edge *)
526 htab_find_with_hash (node->call_site_hash, call_stmt,
527 htab_hash_pointer (call_stmt));
529 /* This loop may turn out to be performance problem. In such case adding
530 hashtables into call nodes with very many edges is probably best
531 solution. It is not good idea to add pointer into CALL_EXPR itself
532 because we want to make possible having multiple cgraph nodes representing
533 different clones of the same body before the body is actually cloned. */
534 for (e = node->callees; e; e= e->next_callee)
536 if (e->call_stmt == call_stmt)
542 node->call_site_hash = htab_create_ggc (120, edge_hash, edge_eq, NULL);
543 for (e2 = node->callees; e2; e2 = e2->next_callee)
546 slot = htab_find_slot_with_hash (node->call_site_hash,
548 htab_hash_pointer (e2->call_stmt),
557 /* Change call_stmt of edge E to NEW_STMT. */
560 cgraph_set_call_stmt (struct cgraph_edge *e, tree new_stmt)
562 if (e->caller->call_site_hash)
564 htab_remove_elt_with_hash (e->caller->call_site_hash,
566 htab_hash_pointer (e->call_stmt));
568 e->call_stmt = new_stmt;
569 if (e->caller->call_site_hash)
572 slot = htab_find_slot_with_hash (e->caller->call_site_hash,
575 (e->call_stmt), INSERT);
581 /* Create edge from CALLER to CALLEE in the cgraph. */
584 cgraph_create_edge (struct cgraph_node *caller, struct cgraph_node *callee,
585 tree call_stmt, gcov_type count, int freq, int nest)
587 struct cgraph_edge *edge = GGC_NEW (struct cgraph_edge);
588 #ifdef ENABLE_CHECKING
589 struct cgraph_edge *e;
591 for (e = caller->callees; e; e = e->next_callee)
592 gcc_assert (e->call_stmt != call_stmt);
595 gcc_assert (get_call_expr_in (call_stmt));
597 if (!DECL_SAVED_TREE (callee->decl))
598 edge->inline_failed = N_("function body not available");
599 else if (callee->local.redefined_extern_inline)
600 edge->inline_failed = N_("redefined extern inline functions are not "
601 "considered for inlining");
602 else if (callee->local.inlinable)
603 edge->inline_failed = N_("function not considered for inlining");
605 edge->inline_failed = N_("function not inlinable");
609 edge->caller = caller;
610 edge->callee = callee;
611 edge->call_stmt = call_stmt;
612 edge->prev_caller = NULL;
613 edge->next_caller = callee->callers;
615 callee->callers->prev_caller = edge;
616 edge->prev_callee = NULL;
617 edge->next_callee = caller->callees;
619 caller->callees->prev_callee = edge;
620 caller->callees = edge;
621 callee->callers = edge;
623 gcc_assert (count >= 0);
624 edge->frequency = freq;
625 gcc_assert (freq >= 0);
626 gcc_assert (freq <= CGRAPH_FREQ_MAX);
627 edge->loop_nest = nest;
628 edge->indirect_call = 0;
629 edge->uid = cgraph_edge_max_uid++;
630 if (caller->call_site_hash)
633 slot = htab_find_slot_with_hash (caller->call_site_hash,
644 /* Remove the edge E from the list of the callers of the callee. */
647 cgraph_edge_remove_callee (struct cgraph_edge *e)
650 e->prev_caller->next_caller = e->next_caller;
652 e->next_caller->prev_caller = e->prev_caller;
654 e->callee->callers = e->next_caller;
657 /* Remove the edge E from the list of the callees of the caller. */
660 cgraph_edge_remove_caller (struct cgraph_edge *e)
663 e->prev_callee->next_callee = e->next_callee;
665 e->next_callee->prev_callee = e->prev_callee;
667 e->caller->callees = e->next_callee;
668 if (e->caller->call_site_hash)
669 htab_remove_elt_with_hash (e->caller->call_site_hash,
671 htab_hash_pointer (e->call_stmt));
674 /* Remove the edge E in the cgraph. */
677 cgraph_remove_edge (struct cgraph_edge *e)
679 cgraph_call_edge_removal_hooks (e);
680 /* Remove from callers list of the callee. */
681 cgraph_edge_remove_callee (e);
683 /* Remove from callees list of the callers. */
684 cgraph_edge_remove_caller (e);
687 /* Redirect callee of E to N. The function does not update underlying
691 cgraph_redirect_edge_callee (struct cgraph_edge *e, struct cgraph_node *n)
693 /* Remove from callers list of the current callee. */
694 cgraph_edge_remove_callee (e);
696 /* Insert to callers list of the new callee. */
697 e->prev_caller = NULL;
699 n->callers->prev_caller = e;
700 e->next_caller = n->callers;
705 /* Update or remove corresponding cgraph edge if a call OLD_CALL
706 in OLD_STMT changed into NEW_STMT. */
709 cgraph_update_edges_for_call_stmt (tree old_stmt, tree old_call,
712 tree new_call = get_call_expr_in (new_stmt);
713 struct cgraph_node *node = cgraph_node (cfun->decl);
715 if (old_call != new_call)
717 struct cgraph_edge *e = cgraph_edge (node, old_stmt);
718 struct cgraph_edge *ne = NULL;
723 gcov_type count = e->count;
724 int frequency = e->frequency;
725 int loop_nest = e->loop_nest;
727 cgraph_remove_edge (e);
730 new_decl = get_callee_fndecl (new_call);
733 ne = cgraph_create_edge (node, cgraph_node (new_decl),
734 new_stmt, count, frequency,
736 gcc_assert (ne->inline_failed);
741 else if (old_stmt != new_stmt)
743 struct cgraph_edge *e = cgraph_edge (node, old_stmt);
746 cgraph_set_call_stmt (e, new_stmt);
750 /* Remove all callees from the node. */
753 cgraph_node_remove_callees (struct cgraph_node *node)
755 struct cgraph_edge *e;
757 /* It is sufficient to remove the edges from the lists of callers of
758 the callees. The callee list of the node can be zapped with one
760 for (e = node->callees; e; e = e->next_callee)
762 cgraph_call_edge_removal_hooks (e);
763 cgraph_edge_remove_callee (e);
765 node->callees = NULL;
766 if (node->call_site_hash)
768 htab_delete (node->call_site_hash);
769 node->call_site_hash = NULL;
773 /* Remove all callers from the node. */
776 cgraph_node_remove_callers (struct cgraph_node *node)
778 struct cgraph_edge *e;
780 /* It is sufficient to remove the edges from the lists of callees of
781 the callers. The caller list of the node can be zapped with one
783 for (e = node->callers; e; e = e->next_caller)
785 cgraph_call_edge_removal_hooks (e);
786 cgraph_edge_remove_caller (e);
788 node->callers = NULL;
791 /* Release memory used to represent body of function NODE. */
794 cgraph_release_function_body (struct cgraph_node *node)
796 if (DECL_STRUCT_FUNCTION (node->decl)
797 && DECL_STRUCT_FUNCTION (node->decl)->gimple_df)
799 tree old_decl = current_function_decl;
800 push_cfun (DECL_STRUCT_FUNCTION (node->decl));
801 current_function_decl = node->decl;
803 delete_tree_cfg_annotations ();
805 current_function_decl = old_decl;
808 DECL_SAVED_TREE (node->decl) = NULL;
809 DECL_STRUCT_FUNCTION (node->decl) = NULL;
810 DECL_INITIAL (node->decl) = error_mark_node;
813 /* Remove the node from cgraph. */
816 cgraph_remove_node (struct cgraph_node *node)
819 bool kill_body = false;
821 cgraph_call_node_removal_hooks (node);
822 cgraph_node_remove_callers (node);
823 cgraph_node_remove_callees (node);
825 /* Incremental inlining access removed nodes stored in the postorder list.
827 node->needed = node->reachable = false;
829 cgraph_remove_node (node->nested);
832 struct cgraph_node **node2 = &node->origin->nested;
834 while (*node2 != node)
835 node2 = &(*node2)->next_nested;
836 *node2 = node->next_nested;
839 node->previous->next = node->next;
841 cgraph_nodes = node->next;
843 node->next->previous = node->previous;
845 node->previous = NULL;
846 slot = htab_find_slot (cgraph_hash, node, NO_INSERT);
849 if (node->next_clone)
851 struct cgraph_node *new_node = node->next_clone;
852 struct cgraph_node *n;
854 /* Make the next clone be the master clone */
855 for (n = new_node; n; n = n->next_clone)
856 n->master_clone = new_node;
859 node->next_clone->prev_clone = NULL;
863 htab_clear_slot (cgraph_hash, slot);
869 node->prev_clone->next_clone = node->next_clone;
870 if (node->next_clone)
871 node->next_clone->prev_clone = node->prev_clone;
874 /* While all the clones are removed after being proceeded, the function
875 itself is kept in the cgraph even after it is compiled. Check whether
876 we are done with this body and reclaim it proactively if this is the case.
878 if (!kill_body && *slot)
880 struct cgraph_node *n = (struct cgraph_node *) *slot;
881 if (!n->next_clone && !n->global.inlined_to
882 && (cgraph_global_info_ready
883 && (TREE_ASM_WRITTEN (n->decl) || DECL_EXTERNAL (n->decl))))
886 if (assembler_name_hash)
888 tree name = DECL_ASSEMBLER_NAME (node->decl);
889 slot = htab_find_slot_with_hash (assembler_name_hash, name,
890 decl_assembler_name_hash (name),
892 /* Inline clones are not hashed. */
893 if (slot && *slot == node)
894 htab_clear_slot (assembler_name_hash, slot);
897 if (kill_body && flag_unit_at_a_time)
898 cgraph_release_function_body (node);
900 if (node->call_site_hash)
902 htab_delete (node->call_site_hash);
903 node->call_site_hash = NULL;
906 /* Do not free the structure itself so the walk over chain can continue. */
909 /* Notify finalize_compilation_unit that given node is reachable. */
912 cgraph_mark_reachable_node (struct cgraph_node *node)
914 if (!node->reachable && node->local.finalized)
916 notice_global_symbol (node->decl);
918 gcc_assert (!cgraph_global_info_ready);
920 node->next_needed = cgraph_nodes_queue;
921 cgraph_nodes_queue = node;
925 /* Likewise indicate that a node is needed, i.e. reachable via some
929 cgraph_mark_needed_node (struct cgraph_node *node)
932 cgraph_mark_reachable_node (node);
935 /* Return local info for the compiled function. */
937 struct cgraph_local_info *
938 cgraph_local_info (tree decl)
940 struct cgraph_node *node;
942 gcc_assert (TREE_CODE (decl) == FUNCTION_DECL);
943 node = cgraph_node (decl);
947 /* Return local info for the compiled function. */
949 struct cgraph_global_info *
950 cgraph_global_info (tree decl)
952 struct cgraph_node *node;
954 gcc_assert (TREE_CODE (decl) == FUNCTION_DECL && cgraph_global_info_ready);
955 node = cgraph_node (decl);
956 return &node->global;
959 /* Return local info for the compiled function. */
961 struct cgraph_rtl_info *
962 cgraph_rtl_info (tree decl)
964 struct cgraph_node *node;
966 gcc_assert (TREE_CODE (decl) == FUNCTION_DECL);
967 node = cgraph_node (decl);
968 if (decl != current_function_decl
969 && !TREE_ASM_WRITTEN (node->decl))
974 /* Return name of the node used in debug output. */
976 cgraph_node_name (struct cgraph_node *node)
978 return lang_hooks.decl_printable_name (node->decl, 2);
981 /* Names used to print out the availability enum. */
982 const char * const cgraph_availability_names[] =
983 {"unset", "not_available", "overwritable", "available", "local"};
986 /* Dump call graph node NODE to file F. */
989 dump_cgraph_node (FILE *f, struct cgraph_node *node)
991 struct cgraph_edge *edge;
992 fprintf (f, "%s/%i(%i):", cgraph_node_name (node), node->uid, node->pid);
993 if (node->global.inlined_to)
994 fprintf (f, " (inline copy in %s/%i)",
995 cgraph_node_name (node->global.inlined_to),
996 node->global.inlined_to->uid);
997 if (cgraph_function_flags_ready)
998 fprintf (f, " availability:%s",
999 cgraph_availability_names [cgraph_function_body_availability (node)]);
1000 if (node->master_clone && node->master_clone->uid != node->uid)
1001 fprintf (f, "(%i)", node->master_clone->uid);
1003 fprintf (f, " executed "HOST_WIDEST_INT_PRINT_DEC"x",
1004 (HOST_WIDEST_INT)node->count);
1005 if (node->local.inline_summary.self_insns)
1006 fprintf (f, " %i insns", node->local.inline_summary.self_insns);
1007 if (node->global.insns && node->global.insns
1008 != node->local.inline_summary.self_insns)
1009 fprintf (f, " (%i after inlining)", node->global.insns);
1010 if (node->local.inline_summary.estimated_self_stack_size)
1011 fprintf (f, " %i bytes stack usage", (int)node->local.inline_summary.estimated_self_stack_size);
1012 if (node->global.estimated_stack_size != node->local.inline_summary.estimated_self_stack_size)
1013 fprintf (f, " %i bytes after inlining", (int)node->global.estimated_stack_size);
1015 fprintf (f, " nested in: %s", cgraph_node_name (node->origin));
1017 fprintf (f, " needed");
1018 else if (node->reachable)
1019 fprintf (f, " reachable");
1020 if (DECL_SAVED_TREE (node->decl))
1021 fprintf (f, " tree");
1023 fprintf (f, " output");
1024 if (node->local.local)
1025 fprintf (f, " local");
1026 if (node->local.externally_visible)
1027 fprintf (f, " externally_visible");
1028 if (node->local.finalized)
1029 fprintf (f, " finalized");
1030 if (node->local.disregard_inline_limits)
1031 fprintf (f, " always_inline");
1032 else if (node->local.inlinable)
1033 fprintf (f, " inlinable");
1034 if (node->local.redefined_extern_inline)
1035 fprintf (f, " redefined_extern_inline");
1036 if (TREE_ASM_WRITTEN (node->decl))
1037 fprintf (f, " asm_written");
1039 fprintf (f, "\n called by: ");
1040 for (edge = node->callers; edge; edge = edge->next_caller)
1042 fprintf (f, "%s/%i ", cgraph_node_name (edge->caller),
1045 fprintf (f, "("HOST_WIDEST_INT_PRINT_DEC"x) ",
1046 (HOST_WIDEST_INT)edge->count);
1047 if (edge->frequency)
1048 fprintf (f, "(%.2f per call) ",
1049 edge->frequency / (double)CGRAPH_FREQ_BASE);
1050 if (!edge->inline_failed)
1051 fprintf(f, "(inlined) ");
1052 if (edge->indirect_call)
1053 fprintf(f, "(indirect) ");
1056 fprintf (f, "\n calls: ");
1057 for (edge = node->callees; edge; edge = edge->next_callee)
1059 fprintf (f, "%s/%i ", cgraph_node_name (edge->callee),
1061 if (!edge->inline_failed)
1062 fprintf(f, "(inlined) ");
1063 if (edge->indirect_call)
1064 fprintf(f, "(indirect) ");
1066 fprintf (f, "("HOST_WIDEST_INT_PRINT_DEC"x) ",
1067 (HOST_WIDEST_INT)edge->count);
1068 if (edge->frequency)
1069 fprintf (f, "(%.2f per call) ",
1070 edge->frequency / (double)CGRAPH_FREQ_BASE);
1071 if (edge->loop_nest)
1072 fprintf (f, "(nested in %i loops) ", edge->loop_nest);
1078 /* Dump call graph node NODE to stderr. */
1081 debug_cgraph_node (struct cgraph_node *node)
1083 dump_cgraph_node (stderr, node);
1087 /* Dump the callgraph to file F. */
1090 dump_cgraph (FILE *f)
1092 struct cgraph_node *node;
1094 fprintf (f, "callgraph:\n\n");
1095 for (node = cgraph_nodes; node; node = node->next)
1096 dump_cgraph_node (f, node);
1100 /* Dump the call graph to stderr. */
1105 dump_cgraph (stderr);
1109 /* Set the DECL_ASSEMBLER_NAME and update cgraph hashtables. */
1112 change_decl_assembler_name (tree decl, tree name)
1114 gcc_assert (!assembler_name_hash);
1115 if (!DECL_ASSEMBLER_NAME_SET_P (decl))
1117 SET_DECL_ASSEMBLER_NAME (decl, name);
1120 if (name == DECL_ASSEMBLER_NAME (decl))
1123 if (TREE_SYMBOL_REFERENCED (DECL_ASSEMBLER_NAME (decl))
1124 && DECL_RTL_SET_P (decl))
1125 warning (0, "%D renamed after being referenced in assembly", decl);
1127 SET_DECL_ASSEMBLER_NAME (decl, name);
1130 /* Add a top-level asm statement to the list. */
1132 struct cgraph_asm_node *
1133 cgraph_add_asm_node (tree asm_str)
1135 struct cgraph_asm_node *node;
1137 node = GGC_CNEW (struct cgraph_asm_node);
1138 node->asm_str = asm_str;
1139 node->order = cgraph_order++;
1141 if (cgraph_asm_nodes == NULL)
1142 cgraph_asm_nodes = node;
1144 cgraph_asm_last_node->next = node;
1145 cgraph_asm_last_node = node;
1149 /* Return true when the DECL can possibly be inlined. */
1151 cgraph_function_possibly_inlined_p (tree decl)
1153 if (!cgraph_global_info_ready)
1154 return (DECL_INLINE (decl) && !flag_really_no_inline);
1155 return DECL_POSSIBLY_INLINED (decl);
1158 /* Create clone of E in the node N represented by CALL_EXPR the callgraph. */
1159 struct cgraph_edge *
1160 cgraph_clone_edge (struct cgraph_edge *e, struct cgraph_node *n,
1161 tree call_stmt, gcov_type count_scale, int freq_scale,
1162 int loop_nest, bool update_original)
1164 struct cgraph_edge *new;
1165 gcov_type count = e->count * count_scale / REG_BR_PROB_BASE;
1166 gcov_type freq = e->frequency * (gcov_type) freq_scale / CGRAPH_FREQ_BASE;
1168 if (freq > CGRAPH_FREQ_MAX)
1169 freq = CGRAPH_FREQ_MAX;
1170 new = cgraph_create_edge (n, e->callee, call_stmt, count, freq,
1171 e->loop_nest + loop_nest);
1173 new->inline_failed = e->inline_failed;
1174 new->indirect_call = e->indirect_call;
1175 if (update_original)
1177 e->count -= new->count;
1181 cgraph_call_edge_duplication_hooks (e, new);
1185 /* Create node representing clone of N executed COUNT times. Decrease
1186 the execution counts from original node too.
1188 When UPDATE_ORIGINAL is true, the counts are subtracted from the original
1189 function's profile to reflect the fact that part of execution is handled
1191 struct cgraph_node *
1192 cgraph_clone_node (struct cgraph_node *n, gcov_type count, int freq, int loop_nest,
1193 bool update_original)
1195 struct cgraph_node *new = cgraph_create_node ();
1196 struct cgraph_edge *e;
1197 gcov_type count_scale;
1199 new->decl = n->decl;
1200 new->origin = n->origin;
1203 new->next_nested = new->origin->nested;
1204 new->origin->nested = new;
1206 new->analyzed = n->analyzed;
1207 new->local = n->local;
1208 new->global = n->global;
1210 new->master_clone = n->master_clone;
1213 count_scale = new->count * REG_BR_PROB_BASE / n->count;
1216 if (update_original)
1223 for (e = n->callees;e; e=e->next_callee)
1224 cgraph_clone_edge (e, new, e->call_stmt, count_scale, freq, loop_nest,
1227 new->next_clone = n->next_clone;
1228 new->prev_clone = n;
1229 n->next_clone = new;
1230 if (new->next_clone)
1231 new->next_clone->prev_clone = new;
1233 cgraph_call_node_duplication_hooks (n, new);
1237 /* Return true if N is an master_clone, (see cgraph_master_clone). */
1240 cgraph_is_master_clone (struct cgraph_node *n)
1242 return (n == cgraph_master_clone (n));
1245 struct cgraph_node *
1246 cgraph_master_clone (struct cgraph_node *n)
1248 enum availability avail = cgraph_function_body_availability (n);
1250 if (avail == AVAIL_NOT_AVAILABLE || avail == AVAIL_OVERWRITABLE)
1253 if (!n->master_clone)
1254 n->master_clone = cgraph_node (n->decl);
1256 return n->master_clone;
1259 /* NODE is no longer nested function; update cgraph accordingly. */
1261 cgraph_unnest_node (struct cgraph_node *node)
1263 struct cgraph_node **node2 = &node->origin->nested;
1264 gcc_assert (node->origin);
1266 while (*node2 != node)
1267 node2 = &(*node2)->next_nested;
1268 *node2 = node->next_nested;
1269 node->origin = NULL;
1272 /* Return function availability. See cgraph.h for description of individual
1275 cgraph_function_body_availability (struct cgraph_node *node)
1277 enum availability avail;
1278 gcc_assert (cgraph_function_flags_ready);
1279 if (!node->analyzed)
1280 avail = AVAIL_NOT_AVAILABLE;
1281 else if (node->local.local)
1282 avail = AVAIL_LOCAL;
1283 else if (node->local.externally_visible)
1284 avail = AVAIL_AVAILABLE;
1286 /* If the function can be overwritten, return OVERWRITABLE. Take
1287 care at least of two notable extensions - the COMDAT functions
1288 used to share template instantiations in C++ (this is symmetric
1289 to code cp_cannot_inline_tree_fn and probably shall be shared and
1290 the inlinability hooks completely eliminated).
1292 ??? Does the C++ one definition rule allow us to always return
1293 AVAIL_AVAILABLE here? That would be good reason to preserve this
1294 hook Similarly deal with extern inline functions - this is again
1295 necessary to get C++ shared functions having keyed templates
1296 right and in the C extension documentation we probably should
1297 document the requirement of both versions of function (extern
1298 inline and offline) having same side effect characteristics as
1299 good optimization is what this optimization is about. */
1301 else if (!(*targetm.binds_local_p) (node->decl)
1302 && !DECL_COMDAT (node->decl) && !DECL_EXTERNAL (node->decl))
1303 avail = AVAIL_OVERWRITABLE;
1304 else avail = AVAIL_AVAILABLE;
1309 /* Add the function FNDECL to the call graph.
1310 Unlike cgraph_finalize_function, this function is intended to be used
1311 by middle end and allows insertion of new function at arbitrary point
1312 of compilation. The function can be either in high, low or SSA form
1315 The function is assumed to be reachable and have address taken (so no
1316 API breaking optimizations are performed on it).
1318 Main work done by this function is to enqueue the function for later
1319 processing to avoid need the passes to be re-entrant. */
1322 cgraph_add_new_function (tree fndecl, bool lowered)
1324 struct cgraph_node *node;
1325 switch (cgraph_state)
1327 case CGRAPH_STATE_CONSTRUCTION:
1328 /* Just enqueue function to be processed at nearest occurrence. */
1329 node = cgraph_node (fndecl);
1330 node->next_needed = cgraph_new_nodes;
1332 node->lowered = true;
1333 cgraph_new_nodes = node;
1336 case CGRAPH_STATE_IPA:
1337 case CGRAPH_STATE_IPA_SSA:
1338 case CGRAPH_STATE_EXPANSION:
1339 /* Bring the function into finalized state and enqueue for later
1340 analyzing and compilation. */
1341 node = cgraph_node (fndecl);
1342 node->local.local = false;
1343 node->local.finalized = true;
1344 node->reachable = node->needed = true;
1345 if (!lowered && cgraph_state == CGRAPH_STATE_EXPANSION)
1347 push_cfun (DECL_STRUCT_FUNCTION (fndecl));
1348 current_function_decl = fndecl;
1349 tree_register_cfg_hooks ();
1350 tree_lowering_passes (fndecl);
1351 bitmap_obstack_initialize (NULL);
1352 if (!gimple_in_ssa_p (DECL_STRUCT_FUNCTION (fndecl)))
1353 execute_pass_list (pass_early_local_passes.pass.sub);
1354 bitmap_obstack_release (NULL);
1356 current_function_decl = NULL;
1361 node->lowered = true;
1362 node->next_needed = cgraph_new_nodes;
1363 cgraph_new_nodes = node;
1366 case CGRAPH_STATE_FINISHED:
1367 /* At the very end of compilation we have to do all the work up
1369 push_cfun (DECL_STRUCT_FUNCTION (fndecl));
1370 current_function_decl = fndecl;
1371 tree_register_cfg_hooks ();
1373 tree_lowering_passes (fndecl);
1374 bitmap_obstack_initialize (NULL);
1375 if (!gimple_in_ssa_p (DECL_STRUCT_FUNCTION (fndecl)))
1376 execute_pass_list (pass_early_local_passes.pass.sub);
1377 bitmap_obstack_release (NULL);
1378 tree_rest_of_compilation (fndecl);
1380 current_function_decl = NULL;
1385 #include "gt-cgraph.h"