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"
85 #include "tree-dump.h"
86 #include "tree-flow.h"
87 #include "value-prof.h"
89 static void cgraph_node_remove_callers (struct cgraph_node *node);
90 static inline void cgraph_edge_remove_caller (struct cgraph_edge *e);
91 static inline void cgraph_edge_remove_callee (struct cgraph_edge *e);
93 /* Hash table used to convert declarations into nodes. */
94 static GTY((param_is (struct cgraph_node))) htab_t cgraph_hash;
95 /* Hash table used to convert assembler names into nodes. */
96 static GTY((param_is (struct cgraph_node))) htab_t assembler_name_hash;
98 /* The linked list of cgraph nodes. */
99 struct cgraph_node *cgraph_nodes;
101 /* Queue of cgraph nodes scheduled to be lowered. */
102 struct cgraph_node *cgraph_nodes_queue;
104 /* Queue of cgraph nodes scheduled to be added into cgraph. This is a
105 secondary queue used during optimization to accommodate passes that
106 may generate new functions that need to be optimized and expanded. */
107 struct cgraph_node *cgraph_new_nodes;
109 /* Number of nodes in existence. */
112 /* Maximal uid used in cgraph nodes. */
115 /* Maximal uid used in cgraph edges. */
116 int cgraph_edge_max_uid;
118 /* Maximal pid used for profiling */
121 /* Set when whole unit has been analyzed so we can access global info. */
122 bool cgraph_global_info_ready = false;
124 /* What state callgraph is in right now. */
125 enum cgraph_state cgraph_state = CGRAPH_STATE_CONSTRUCTION;
127 /* Set when the cgraph is fully build and the basic flags are computed. */
128 bool cgraph_function_flags_ready = false;
130 /* Linked list of cgraph asm nodes. */
131 struct cgraph_asm_node *cgraph_asm_nodes;
133 /* Last node in cgraph_asm_nodes. */
134 static GTY(()) struct cgraph_asm_node *cgraph_asm_last_node;
136 /* The order index of the next cgraph node to be created. This is
137 used so that we can sort the cgraph nodes in order by when we saw
138 them, to support -fno-toplevel-reorder. */
141 /* List of hooks trigerred on cgraph_edge events. */
142 struct cgraph_edge_hook_list {
143 cgraph_edge_hook hook;
145 struct cgraph_edge_hook_list *next;
148 /* List of hooks trigerred on cgraph_node events. */
149 struct cgraph_node_hook_list {
150 cgraph_node_hook hook;
152 struct cgraph_node_hook_list *next;
155 /* List of hooks trigerred on events involving two cgraph_edges. */
156 struct cgraph_2edge_hook_list {
157 cgraph_2edge_hook hook;
159 struct cgraph_2edge_hook_list *next;
162 /* List of hooks trigerred on events involving two cgraph_nodes. */
163 struct cgraph_2node_hook_list {
164 cgraph_2node_hook hook;
166 struct cgraph_2node_hook_list *next;
169 /* List of hooks triggered when an edge is removed. */
170 struct cgraph_edge_hook_list *first_cgraph_edge_removal_hook;
171 /* List of hooks triggered when a node is removed. */
172 struct cgraph_node_hook_list *first_cgraph_node_removal_hook;
173 /* List of hooks triggered when an edge is duplicated. */
174 struct cgraph_2edge_hook_list *first_cgraph_edge_duplicated_hook;
175 /* List of hooks triggered when a node is duplicated. */
176 struct cgraph_2node_hook_list *first_cgraph_node_duplicated_hook;
177 /* List of hooks triggered when an function is inserted. */
178 struct cgraph_node_hook_list *first_cgraph_function_insertion_hook;
180 /* Head of a linked list of unused (freed) call graph nodes.
181 Do not GTY((delete)) this list so UIDs gets reliably recycled. */
182 static GTY(()) struct cgraph_node *free_nodes;
183 /* Head of a linked list of unused (freed) call graph edges.
184 Do not GTY((delete)) this list so UIDs gets reliably recycled. */
185 static GTY(()) struct cgraph_edge *free_edges;
187 /* Macros to access the next item in the list of free cgraph nodes and
189 #define NEXT_FREE_NODE(NODE) (NODE)->next
190 #define NEXT_FREE_EDGE(EDGE) (EDGE)->prev_caller
192 /* Register HOOK to be called with DATA on each removed edge. */
193 struct cgraph_edge_hook_list *
194 cgraph_add_edge_removal_hook (cgraph_edge_hook hook, void *data)
196 struct cgraph_edge_hook_list *entry;
197 struct cgraph_edge_hook_list **ptr = &first_cgraph_edge_removal_hook;
199 entry = (struct cgraph_edge_hook_list *) xmalloc (sizeof (*entry));
209 /* Remove ENTRY from the list of hooks called on removing edges. */
211 cgraph_remove_edge_removal_hook (struct cgraph_edge_hook_list *entry)
213 struct cgraph_edge_hook_list **ptr = &first_cgraph_edge_removal_hook;
215 while (*ptr != entry)
221 /* Call all edge removal hooks. */
223 cgraph_call_edge_removal_hooks (struct cgraph_edge *e)
225 struct cgraph_edge_hook_list *entry = first_cgraph_edge_removal_hook;
228 entry->hook (e, entry->data);
233 /* Register HOOK to be called with DATA on each removed node. */
234 struct cgraph_node_hook_list *
235 cgraph_add_node_removal_hook (cgraph_node_hook hook, void *data)
237 struct cgraph_node_hook_list *entry;
238 struct cgraph_node_hook_list **ptr = &first_cgraph_node_removal_hook;
240 entry = (struct cgraph_node_hook_list *) xmalloc (sizeof (*entry));
250 /* Remove ENTRY from the list of hooks called on removing nodes. */
252 cgraph_remove_node_removal_hook (struct cgraph_node_hook_list *entry)
254 struct cgraph_node_hook_list **ptr = &first_cgraph_node_removal_hook;
256 while (*ptr != entry)
262 /* Call all node removal hooks. */
264 cgraph_call_node_removal_hooks (struct cgraph_node *node)
266 struct cgraph_node_hook_list *entry = first_cgraph_node_removal_hook;
269 entry->hook (node, entry->data);
274 /* Register HOOK to be called with DATA on each removed node. */
275 struct cgraph_node_hook_list *
276 cgraph_add_function_insertion_hook (cgraph_node_hook hook, void *data)
278 struct cgraph_node_hook_list *entry;
279 struct cgraph_node_hook_list **ptr = &first_cgraph_function_insertion_hook;
281 entry = (struct cgraph_node_hook_list *) xmalloc (sizeof (*entry));
291 /* Remove ENTRY from the list of hooks called on removing nodes. */
293 cgraph_remove_function_insertion_hook (struct cgraph_node_hook_list *entry)
295 struct cgraph_node_hook_list **ptr = &first_cgraph_function_insertion_hook;
297 while (*ptr != entry)
303 /* Call all node removal hooks. */
305 cgraph_call_function_insertion_hooks (struct cgraph_node *node)
307 struct cgraph_node_hook_list *entry = first_cgraph_function_insertion_hook;
310 entry->hook (node, entry->data);
315 /* Register HOOK to be called with DATA on each duplicated edge. */
316 struct cgraph_2edge_hook_list *
317 cgraph_add_edge_duplication_hook (cgraph_2edge_hook hook, void *data)
319 struct cgraph_2edge_hook_list *entry;
320 struct cgraph_2edge_hook_list **ptr = &first_cgraph_edge_duplicated_hook;
322 entry = (struct cgraph_2edge_hook_list *) xmalloc (sizeof (*entry));
332 /* Remove ENTRY from the list of hooks called on duplicating edges. */
334 cgraph_remove_edge_duplication_hook (struct cgraph_2edge_hook_list *entry)
336 struct cgraph_2edge_hook_list **ptr = &first_cgraph_edge_duplicated_hook;
338 while (*ptr != entry)
344 /* Call all edge duplication hooks. */
346 cgraph_call_edge_duplication_hooks (struct cgraph_edge *cs1,
347 struct cgraph_edge *cs2)
349 struct cgraph_2edge_hook_list *entry = first_cgraph_edge_duplicated_hook;
352 entry->hook (cs1, cs2, entry->data);
357 /* Register HOOK to be called with DATA on each duplicated node. */
358 struct cgraph_2node_hook_list *
359 cgraph_add_node_duplication_hook (cgraph_2node_hook hook, void *data)
361 struct cgraph_2node_hook_list *entry;
362 struct cgraph_2node_hook_list **ptr = &first_cgraph_node_duplicated_hook;
364 entry = (struct cgraph_2node_hook_list *) xmalloc (sizeof (*entry));
374 /* Remove ENTRY from the list of hooks called on duplicating nodes. */
376 cgraph_remove_node_duplication_hook (struct cgraph_2node_hook_list *entry)
378 struct cgraph_2node_hook_list **ptr = &first_cgraph_node_duplicated_hook;
380 while (*ptr != entry)
386 /* Call all node duplication hooks. */
388 cgraph_call_node_duplication_hooks (struct cgraph_node *node1,
389 struct cgraph_node *node2)
391 struct cgraph_2node_hook_list *entry = first_cgraph_node_duplicated_hook;
394 entry->hook (node1, node2, entry->data);
399 /* Returns a hash code for P. */
402 hash_node (const void *p)
404 const struct cgraph_node *n = (const struct cgraph_node *) p;
405 return (hashval_t) DECL_UID (n->decl);
408 /* Returns nonzero if P1 and P2 are equal. */
411 eq_node (const void *p1, const void *p2)
413 const struct cgraph_node *n1 = (const struct cgraph_node *) p1;
414 const struct cgraph_node *n2 = (const struct cgraph_node *) p2;
415 return DECL_UID (n1->decl) == DECL_UID (n2->decl);
418 /* Allocate new callgraph node and insert it into basic data structures. */
420 static struct cgraph_node *
421 cgraph_create_node (void)
423 struct cgraph_node *node;
428 free_nodes = NEXT_FREE_NODE (node);
432 node = GGC_CNEW (struct cgraph_node);
433 node->uid = cgraph_max_uid++;
436 node->next = cgraph_nodes;
438 node->order = cgraph_order++;
440 cgraph_nodes->previous = node;
441 node->previous = NULL;
442 node->global.estimated_growth = INT_MIN;
448 /* Return cgraph node assigned to DECL. Create new one when needed. */
451 cgraph_node (tree decl)
453 struct cgraph_node key, *node, **slot;
455 gcc_assert (TREE_CODE (decl) == FUNCTION_DECL);
458 cgraph_hash = htab_create_ggc (10, hash_node, eq_node, NULL);
462 slot = (struct cgraph_node **) htab_find_slot (cgraph_hash, &key, INSERT);
467 if (!node->master_clone)
468 node->master_clone = node;
472 node = cgraph_create_node ();
475 if (DECL_CONTEXT (decl) && TREE_CODE (DECL_CONTEXT (decl)) == FUNCTION_DECL)
477 node->origin = cgraph_node (DECL_CONTEXT (decl));
478 node->next_nested = node->origin->nested;
479 node->origin->nested = node;
480 node->master_clone = node;
482 if (assembler_name_hash)
485 tree name = DECL_ASSEMBLER_NAME (decl);
487 aslot = htab_find_slot_with_hash (assembler_name_hash, name,
488 decl_assembler_name_hash (name),
490 /* We can have multiple declarations with same assembler name. For C++
491 it is __builtin_strlen and strlen, for instance. Do we need to
492 record them all? Original implementation marked just first one
493 so lets hope for the best. */
500 /* Insert already constructed node into hashtable. */
503 cgraph_insert_node_to_hashtable (struct cgraph_node *node)
505 struct cgraph_node **slot;
507 slot = (struct cgraph_node **) htab_find_slot (cgraph_hash, node, INSERT);
513 /* Returns a hash code for P. */
516 hash_node_by_assembler_name (const void *p)
518 const struct cgraph_node *n = (const struct cgraph_node *) p;
519 return (hashval_t) decl_assembler_name_hash (DECL_ASSEMBLER_NAME (n->decl));
522 /* Returns nonzero if P1 and P2 are equal. */
525 eq_assembler_name (const void *p1, const void *p2)
527 const struct cgraph_node *n1 = (const struct cgraph_node *) p1;
528 const_tree name = (const_tree)p2;
529 return (decl_assembler_name_equal (n1->decl, name));
532 /* Return the cgraph node that has ASMNAME for its DECL_ASSEMBLER_NAME.
533 Return NULL if there's no such node. */
536 cgraph_node_for_asm (tree asmname)
538 struct cgraph_node *node;
541 if (!assembler_name_hash)
543 assembler_name_hash =
544 htab_create_ggc (10, hash_node_by_assembler_name, eq_assembler_name,
546 for (node = cgraph_nodes; node; node = node->next)
547 if (!node->global.inlined_to)
549 tree name = DECL_ASSEMBLER_NAME (node->decl);
550 slot = htab_find_slot_with_hash (assembler_name_hash, name,
551 decl_assembler_name_hash (name),
553 /* We can have multiple declarations with same assembler name. For C++
554 it is __builtin_strlen and strlen, for instance. Do we need to
555 record them all? Original implementation marked just first one
556 so lets hope for the best. */
563 slot = htab_find_slot_with_hash (assembler_name_hash, asmname,
564 decl_assembler_name_hash (asmname),
568 return (struct cgraph_node *) *slot;
572 /* Returns a hash value for X (which really is a die_struct). */
575 edge_hash (const void *x)
577 return htab_hash_pointer (((const struct cgraph_edge *) x)->call_stmt);
580 /* Return nonzero if decl_id of die_struct X is the same as UID of decl *Y. */
583 edge_eq (const void *x, const void *y)
585 return ((const struct cgraph_edge *) x)->call_stmt == y;
589 /* Return the callgraph edge representing the GIMPLE_CALL statement
593 cgraph_edge (struct cgraph_node *node, gimple call_stmt)
595 struct cgraph_edge *e, *e2;
598 if (node->call_site_hash)
599 return (struct cgraph_edge *)
600 htab_find_with_hash (node->call_site_hash, call_stmt,
601 htab_hash_pointer (call_stmt));
603 /* This loop may turn out to be performance problem. In such case adding
604 hashtables into call nodes with very many edges is probably best
605 solution. It is not good idea to add pointer into CALL_EXPR itself
606 because we want to make possible having multiple cgraph nodes representing
607 different clones of the same body before the body is actually cloned. */
608 for (e = node->callees; e; e= e->next_callee)
610 if (e->call_stmt == call_stmt)
617 node->call_site_hash = htab_create_ggc (120, edge_hash, edge_eq, NULL);
618 for (e2 = node->callees; e2; e2 = e2->next_callee)
621 slot = htab_find_slot_with_hash (node->call_site_hash,
623 htab_hash_pointer (e2->call_stmt),
634 /* Change field call_smt of edge E to NEW_STMT. */
637 cgraph_set_call_stmt (struct cgraph_edge *e, gimple new_stmt)
639 if (e->caller->call_site_hash)
641 htab_remove_elt_with_hash (e->caller->call_site_hash,
643 htab_hash_pointer (e->call_stmt));
645 e->call_stmt = new_stmt;
646 if (e->caller->call_site_hash)
649 slot = htab_find_slot_with_hash (e->caller->call_site_hash,
652 (e->call_stmt), INSERT);
658 /* Create edge from CALLER to CALLEE in the cgraph. */
661 cgraph_create_edge (struct cgraph_node *caller, struct cgraph_node *callee,
662 gimple call_stmt, gcov_type count, int freq, int nest)
664 struct cgraph_edge *edge;
666 #ifdef ENABLE_CHECKING
667 /* This is rather pricely check possibly trigerring construction of call stmt
669 gcc_assert (!cgraph_edge (caller, call_stmt));
672 gcc_assert (is_gimple_call (call_stmt));
677 free_edges = NEXT_FREE_EDGE (edge);
681 edge = GGC_NEW (struct cgraph_edge);
682 edge->uid = cgraph_edge_max_uid++;
685 if (!callee->analyzed)
686 edge->inline_failed = N_("function body not available");
687 else if (callee->local.redefined_extern_inline)
688 edge->inline_failed = N_("redefined extern inline functions are not "
689 "considered for inlining");
690 else if (callee->local.inlinable)
691 edge->inline_failed = N_("function not considered for inlining");
693 edge->inline_failed = N_("function not inlinable");
697 edge->caller = caller;
698 edge->callee = callee;
699 edge->call_stmt = call_stmt;
700 edge->prev_caller = NULL;
701 edge->next_caller = callee->callers;
703 callee->callers->prev_caller = edge;
704 edge->prev_callee = NULL;
705 edge->next_callee = caller->callees;
707 caller->callees->prev_callee = edge;
708 caller->callees = edge;
709 callee->callers = edge;
711 gcc_assert (count >= 0);
712 edge->frequency = freq;
713 gcc_assert (freq >= 0);
714 gcc_assert (freq <= CGRAPH_FREQ_MAX);
715 edge->loop_nest = nest;
716 edge->indirect_call = 0;
717 if (caller->call_site_hash)
720 slot = htab_find_slot_with_hash (caller->call_site_hash,
731 /* Remove the edge E from the list of the callers of the callee. */
734 cgraph_edge_remove_callee (struct cgraph_edge *e)
737 e->prev_caller->next_caller = e->next_caller;
739 e->next_caller->prev_caller = e->prev_caller;
741 e->callee->callers = e->next_caller;
744 /* Remove the edge E from the list of the callees of the caller. */
747 cgraph_edge_remove_caller (struct cgraph_edge *e)
750 e->prev_callee->next_callee = e->next_callee;
752 e->next_callee->prev_callee = e->prev_callee;
754 e->caller->callees = e->next_callee;
755 if (e->caller->call_site_hash)
756 htab_remove_elt_with_hash (e->caller->call_site_hash,
758 htab_hash_pointer (e->call_stmt));
761 /* Put the edge onto the free list. */
764 cgraph_free_edge (struct cgraph_edge *e)
768 /* Clear out the edge so we do not dangle pointers. */
769 memset (e, 0, sizeof (*e));
771 NEXT_FREE_EDGE (e) = free_edges;
775 /* Remove the edge E in the cgraph. */
778 cgraph_remove_edge (struct cgraph_edge *e)
780 /* Call all edge removal hooks. */
781 cgraph_call_edge_removal_hooks (e);
783 /* Remove from callers list of the callee. */
784 cgraph_edge_remove_callee (e);
786 /* Remove from callees list of the callers. */
787 cgraph_edge_remove_caller (e);
789 /* Put the edge onto the free list. */
790 cgraph_free_edge (e);
793 /* Redirect callee of E to N. The function does not update underlying
797 cgraph_redirect_edge_callee (struct cgraph_edge *e, struct cgraph_node *n)
799 /* Remove from callers list of the current callee. */
800 cgraph_edge_remove_callee (e);
802 /* Insert to callers list of the new callee. */
803 e->prev_caller = NULL;
805 n->callers->prev_caller = e;
806 e->next_caller = n->callers;
812 /* Update or remove the corresponding cgraph edge if a GIMPLE_CALL
813 OLD_STMT changed into NEW_STMT. */
816 cgraph_update_edges_for_call_stmt (gimple old_stmt, gimple new_stmt)
818 tree new_call = (is_gimple_call (new_stmt)) ? gimple_call_fn (new_stmt) : 0;
819 tree old_call = (is_gimple_call (old_stmt)) ? gimple_call_fn (old_stmt) : 0;
820 struct cgraph_node *node = cgraph_node (cfun->decl);
822 if (old_call != new_call)
824 struct cgraph_edge *e = cgraph_edge (node, old_stmt);
825 struct cgraph_edge *ne = NULL;
830 gcov_type count = e->count;
831 int frequency = e->frequency;
832 int loop_nest = e->loop_nest;
834 cgraph_remove_edge (e);
837 new_decl = gimple_call_fndecl (new_stmt);
840 ne = cgraph_create_edge (node, cgraph_node (new_decl),
841 new_stmt, count, frequency,
843 gcc_assert (ne->inline_failed);
848 else if (old_stmt != new_stmt)
850 struct cgraph_edge *e = cgraph_edge (node, old_stmt);
853 cgraph_set_call_stmt (e, new_stmt);
858 /* Remove all callees from the node. */
861 cgraph_node_remove_callees (struct cgraph_node *node)
863 struct cgraph_edge *e, *f;
865 /* It is sufficient to remove the edges from the lists of callers of
866 the callees. The callee list of the node can be zapped with one
868 for (e = node->callees; e; e = f)
871 cgraph_call_edge_removal_hooks (e);
872 cgraph_edge_remove_callee (e);
873 cgraph_free_edge (e);
875 node->callees = NULL;
876 if (node->call_site_hash)
878 htab_delete (node->call_site_hash);
879 node->call_site_hash = NULL;
883 /* Remove all callers from the node. */
886 cgraph_node_remove_callers (struct cgraph_node *node)
888 struct cgraph_edge *e, *f;
890 /* It is sufficient to remove the edges from the lists of callees of
891 the callers. The caller list of the node can be zapped with one
893 for (e = node->callers; e; e = f)
896 cgraph_call_edge_removal_hooks (e);
897 cgraph_edge_remove_caller (e);
898 cgraph_free_edge (e);
900 node->callers = NULL;
903 /* Release memory used to represent body of function NODE. */
906 cgraph_release_function_body (struct cgraph_node *node)
908 if (DECL_STRUCT_FUNCTION (node->decl))
910 tree old_decl = current_function_decl;
911 push_cfun (DECL_STRUCT_FUNCTION (node->decl));
914 current_function_decl = node->decl;
916 delete_tree_cfg_annotations ();
918 current_function_decl = old_decl;
922 gcc_assert (dom_computed[0] == DOM_NONE);
923 gcc_assert (dom_computed[1] == DOM_NONE);
926 if (cfun->value_histograms)
928 gcc_assert (!current_loops);
930 gimple_set_body (node->decl, NULL);
931 VEC_free (ipa_opt_pass, heap,
932 DECL_STRUCT_FUNCTION (node->decl)->ipa_transforms_to_apply);
933 /* Struct function hangs a lot of data that would leak if we didn't
934 removed all pointers to it. */
935 ggc_free (DECL_STRUCT_FUNCTION (node->decl));
936 DECL_STRUCT_FUNCTION (node->decl) = NULL;
938 DECL_SAVED_TREE (node->decl) = NULL;
939 DECL_INITIAL (node->decl) = error_mark_node;
942 /* Remove the node from cgraph. */
945 cgraph_remove_node (struct cgraph_node *node)
948 bool kill_body = false;
949 struct cgraph_node *n;
952 cgraph_call_node_removal_hooks (node);
953 cgraph_node_remove_callers (node);
954 cgraph_node_remove_callees (node);
956 /* Incremental inlining access removed nodes stored in the postorder list.
958 node->needed = node->reachable = false;
959 for (n = node->nested; n; n = n->next_nested)
964 struct cgraph_node **node2 = &node->origin->nested;
966 while (*node2 != node)
967 node2 = &(*node2)->next_nested;
968 *node2 = node->next_nested;
971 node->previous->next = node->next;
973 cgraph_nodes = node->next;
975 node->next->previous = node->previous;
977 node->previous = NULL;
978 slot = htab_find_slot (cgraph_hash, node, NO_INSERT);
981 if (node->next_clone)
983 struct cgraph_node *new_node = node->next_clone;
984 struct cgraph_node *n;
986 /* Make the next clone be the master clone */
987 for (n = new_node; n; n = n->next_clone)
988 n->master_clone = new_node;
991 node->next_clone->prev_clone = NULL;
995 htab_clear_slot (cgraph_hash, slot);
1001 node->prev_clone->next_clone = node->next_clone;
1002 if (node->next_clone)
1003 node->next_clone->prev_clone = node->prev_clone;
1006 /* While all the clones are removed after being proceeded, the function
1007 itself is kept in the cgraph even after it is compiled. Check whether
1008 we are done with this body and reclaim it proactively if this is the case.
1010 if (!kill_body && *slot)
1012 struct cgraph_node *n = (struct cgraph_node *) *slot;
1013 if (!n->next_clone && !n->global.inlined_to
1014 && (cgraph_global_info_ready
1015 && (TREE_ASM_WRITTEN (n->decl) || DECL_EXTERNAL (n->decl))))
1018 if (assembler_name_hash)
1020 tree name = DECL_ASSEMBLER_NAME (node->decl);
1021 slot = htab_find_slot_with_hash (assembler_name_hash, name,
1022 decl_assembler_name_hash (name),
1024 /* Inline clones are not hashed. */
1025 if (slot && *slot == node)
1026 htab_clear_slot (assembler_name_hash, slot);
1030 cgraph_release_function_body (node);
1032 if (node->call_site_hash)
1034 htab_delete (node->call_site_hash);
1035 node->call_site_hash = NULL;
1039 /* Clear out the node to NULL all pointers and add the node to the free
1041 memset (node, 0, sizeof(*node));
1043 NEXT_FREE_NODE (node) = free_nodes;
1047 /* Notify finalize_compilation_unit that given node is reachable. */
1050 cgraph_mark_reachable_node (struct cgraph_node *node)
1052 if (!node->reachable && node->local.finalized)
1054 notice_global_symbol (node->decl);
1055 node->reachable = 1;
1056 gcc_assert (!cgraph_global_info_ready);
1058 node->next_needed = cgraph_nodes_queue;
1059 cgraph_nodes_queue = node;
1063 /* Likewise indicate that a node is needed, i.e. reachable via some
1067 cgraph_mark_needed_node (struct cgraph_node *node)
1070 cgraph_mark_reachable_node (node);
1073 /* Return local info for the compiled function. */
1075 struct cgraph_local_info *
1076 cgraph_local_info (tree decl)
1078 struct cgraph_node *node;
1080 gcc_assert (TREE_CODE (decl) == FUNCTION_DECL);
1081 node = cgraph_node (decl);
1082 return &node->local;
1085 /* Return local info for the compiled function. */
1087 struct cgraph_global_info *
1088 cgraph_global_info (tree decl)
1090 struct cgraph_node *node;
1092 gcc_assert (TREE_CODE (decl) == FUNCTION_DECL && cgraph_global_info_ready);
1093 node = cgraph_node (decl);
1094 return &node->global;
1097 /* Return local info for the compiled function. */
1099 struct cgraph_rtl_info *
1100 cgraph_rtl_info (tree decl)
1102 struct cgraph_node *node;
1104 gcc_assert (TREE_CODE (decl) == FUNCTION_DECL);
1105 node = cgraph_node (decl);
1106 if (decl != current_function_decl
1107 && !TREE_ASM_WRITTEN (node->decl))
1112 /* Return name of the node used in debug output. */
1114 cgraph_node_name (struct cgraph_node *node)
1116 return lang_hooks.decl_printable_name (node->decl, 2);
1119 /* Names used to print out the availability enum. */
1120 const char * const cgraph_availability_names[] =
1121 {"unset", "not_available", "overwritable", "available", "local"};
1124 /* Dump call graph node NODE to file F. */
1127 dump_cgraph_node (FILE *f, struct cgraph_node *node)
1129 struct cgraph_edge *edge;
1130 fprintf (f, "%s/%i(%i):", cgraph_node_name (node), node->uid, node->pid);
1131 if (node->global.inlined_to)
1132 fprintf (f, " (inline copy in %s/%i)",
1133 cgraph_node_name (node->global.inlined_to),
1134 node->global.inlined_to->uid);
1135 if (cgraph_function_flags_ready)
1136 fprintf (f, " availability:%s",
1137 cgraph_availability_names [cgraph_function_body_availability (node)]);
1138 if (node->master_clone && node->master_clone->uid != node->uid)
1139 fprintf (f, "(%i)", node->master_clone->uid);
1141 fprintf (f, " executed "HOST_WIDEST_INT_PRINT_DEC"x",
1142 (HOST_WIDEST_INT)node->count);
1143 if (node->local.inline_summary.self_insns)
1144 fprintf (f, " %i insns", node->local.inline_summary.self_insns);
1145 if (node->global.insns && node->global.insns
1146 != node->local.inline_summary.self_insns)
1147 fprintf (f, " (%i after inlining)", node->global.insns);
1148 if (node->local.inline_summary.estimated_self_stack_size)
1149 fprintf (f, " %i bytes stack usage", (int)node->local.inline_summary.estimated_self_stack_size);
1150 if (node->global.estimated_stack_size != node->local.inline_summary.estimated_self_stack_size)
1151 fprintf (f, " %i bytes after inlining", (int)node->global.estimated_stack_size);
1153 fprintf (f, " nested in: %s", cgraph_node_name (node->origin));
1155 fprintf (f, " needed");
1156 else if (node->reachable)
1157 fprintf (f, " reachable");
1158 if (gimple_has_body_p (node->decl))
1159 fprintf (f, " body");
1161 fprintf (f, " output");
1162 if (node->local.local)
1163 fprintf (f, " local");
1164 if (node->local.externally_visible)
1165 fprintf (f, " externally_visible");
1166 if (node->local.finalized)
1167 fprintf (f, " finalized");
1168 if (node->local.disregard_inline_limits)
1169 fprintf (f, " always_inline");
1170 else if (node->local.inlinable)
1171 fprintf (f, " inlinable");
1172 if (node->local.redefined_extern_inline)
1173 fprintf (f, " redefined_extern_inline");
1174 if (TREE_ASM_WRITTEN (node->decl))
1175 fprintf (f, " asm_written");
1177 fprintf (f, "\n called by: ");
1178 for (edge = node->callers; edge; edge = edge->next_caller)
1180 fprintf (f, "%s/%i ", cgraph_node_name (edge->caller),
1183 fprintf (f, "("HOST_WIDEST_INT_PRINT_DEC"x) ",
1184 (HOST_WIDEST_INT)edge->count);
1185 if (edge->frequency)
1186 fprintf (f, "(%.2f per call) ",
1187 edge->frequency / (double)CGRAPH_FREQ_BASE);
1188 if (!edge->inline_failed)
1189 fprintf(f, "(inlined) ");
1190 if (edge->indirect_call)
1191 fprintf(f, "(indirect) ");
1194 fprintf (f, "\n calls: ");
1195 for (edge = node->callees; edge; edge = edge->next_callee)
1197 fprintf (f, "%s/%i ", cgraph_node_name (edge->callee),
1199 if (!edge->inline_failed)
1200 fprintf(f, "(inlined) ");
1201 if (edge->indirect_call)
1202 fprintf(f, "(indirect) ");
1204 fprintf (f, "("HOST_WIDEST_INT_PRINT_DEC"x) ",
1205 (HOST_WIDEST_INT)edge->count);
1206 if (edge->frequency)
1207 fprintf (f, "(%.2f per call) ",
1208 edge->frequency / (double)CGRAPH_FREQ_BASE);
1209 if (edge->loop_nest)
1210 fprintf (f, "(nested in %i loops) ", edge->loop_nest);
1216 /* Dump call graph node NODE to stderr. */
1219 debug_cgraph_node (struct cgraph_node *node)
1221 dump_cgraph_node (stderr, node);
1225 /* Dump the callgraph to file F. */
1228 dump_cgraph (FILE *f)
1230 struct cgraph_node *node;
1232 fprintf (f, "callgraph:\n\n");
1233 for (node = cgraph_nodes; node; node = node->next)
1234 dump_cgraph_node (f, node);
1238 /* Dump the call graph to stderr. */
1243 dump_cgraph (stderr);
1247 /* Set the DECL_ASSEMBLER_NAME and update cgraph hashtables. */
1250 change_decl_assembler_name (tree decl, tree name)
1252 gcc_assert (!assembler_name_hash);
1253 if (!DECL_ASSEMBLER_NAME_SET_P (decl))
1255 SET_DECL_ASSEMBLER_NAME (decl, name);
1258 if (name == DECL_ASSEMBLER_NAME (decl))
1261 if (TREE_SYMBOL_REFERENCED (DECL_ASSEMBLER_NAME (decl))
1262 && DECL_RTL_SET_P (decl))
1263 warning (0, "%D renamed after being referenced in assembly", decl);
1265 SET_DECL_ASSEMBLER_NAME (decl, name);
1268 /* Add a top-level asm statement to the list. */
1270 struct cgraph_asm_node *
1271 cgraph_add_asm_node (tree asm_str)
1273 struct cgraph_asm_node *node;
1275 node = GGC_CNEW (struct cgraph_asm_node);
1276 node->asm_str = asm_str;
1277 node->order = cgraph_order++;
1279 if (cgraph_asm_nodes == NULL)
1280 cgraph_asm_nodes = node;
1282 cgraph_asm_last_node->next = node;
1283 cgraph_asm_last_node = node;
1287 /* Return true when the DECL can possibly be inlined. */
1289 cgraph_function_possibly_inlined_p (tree decl)
1291 if (!cgraph_global_info_ready)
1292 return !DECL_UNINLINABLE (decl);
1293 return DECL_POSSIBLY_INLINED (decl);
1296 /* Create clone of E in the node N represented by CALL_EXPR the callgraph. */
1297 struct cgraph_edge *
1298 cgraph_clone_edge (struct cgraph_edge *e, struct cgraph_node *n,
1299 gimple call_stmt, gcov_type count_scale, int freq_scale,
1300 int loop_nest, bool update_original)
1302 struct cgraph_edge *new_edge;
1303 gcov_type count = e->count * count_scale / REG_BR_PROB_BASE;
1304 gcov_type freq = e->frequency * (gcov_type) freq_scale / CGRAPH_FREQ_BASE;
1306 if (freq > CGRAPH_FREQ_MAX)
1307 freq = CGRAPH_FREQ_MAX;
1308 new_edge = cgraph_create_edge (n, e->callee, call_stmt, count, freq,
1309 e->loop_nest + loop_nest);
1311 new_edge->inline_failed = e->inline_failed;
1312 new_edge->indirect_call = e->indirect_call;
1313 if (update_original)
1315 e->count -= new_edge->count;
1319 cgraph_call_edge_duplication_hooks (e, new_edge);
1323 /* Create node representing clone of N executed COUNT times. Decrease
1324 the execution counts from original node too.
1326 When UPDATE_ORIGINAL is true, the counts are subtracted from the original
1327 function's profile to reflect the fact that part of execution is handled
1329 struct cgraph_node *
1330 cgraph_clone_node (struct cgraph_node *n, gcov_type count, int freq,
1331 int loop_nest, bool update_original)
1333 struct cgraph_node *new_node = cgraph_create_node ();
1334 struct cgraph_edge *e;
1335 gcov_type count_scale;
1337 new_node->decl = n->decl;
1338 new_node->origin = n->origin;
1339 if (new_node->origin)
1341 new_node->next_nested = new_node->origin->nested;
1342 new_node->origin->nested = new_node;
1344 new_node->analyzed = n->analyzed;
1345 new_node->local = n->local;
1346 new_node->global = n->global;
1347 new_node->rtl = n->rtl;
1348 new_node->master_clone = n->master_clone;
1349 new_node->count = count;
1352 if (new_node->count > n->count)
1353 count_scale = REG_BR_PROB_BASE;
1355 count_scale = new_node->count * REG_BR_PROB_BASE / n->count;
1359 if (update_original)
1366 for (e = n->callees;e; e=e->next_callee)
1367 cgraph_clone_edge (e, new_node, e->call_stmt, count_scale, freq, loop_nest,
1370 new_node->next_clone = n->next_clone;
1371 new_node->prev_clone = n;
1372 n->next_clone = new_node;
1373 if (new_node->next_clone)
1374 new_node->next_clone->prev_clone = new_node;
1376 cgraph_call_node_duplication_hooks (n, new_node);
1380 /* Return true if N is an master_clone, (see cgraph_master_clone). */
1383 cgraph_is_master_clone (struct cgraph_node *n)
1385 return (n == cgraph_master_clone (n));
1388 struct cgraph_node *
1389 cgraph_master_clone (struct cgraph_node *n)
1391 enum availability avail = cgraph_function_body_availability (n);
1393 if (avail == AVAIL_NOT_AVAILABLE || avail == AVAIL_OVERWRITABLE)
1396 if (!n->master_clone)
1397 n->master_clone = cgraph_node (n->decl);
1399 return n->master_clone;
1402 /* NODE is no longer nested function; update cgraph accordingly. */
1404 cgraph_unnest_node (struct cgraph_node *node)
1406 struct cgraph_node **node2 = &node->origin->nested;
1407 gcc_assert (node->origin);
1409 while (*node2 != node)
1410 node2 = &(*node2)->next_nested;
1411 *node2 = node->next_nested;
1412 node->origin = NULL;
1415 /* Return function availability. See cgraph.h for description of individual
1418 cgraph_function_body_availability (struct cgraph_node *node)
1420 enum availability avail;
1421 gcc_assert (cgraph_function_flags_ready);
1422 if (!node->analyzed)
1423 avail = AVAIL_NOT_AVAILABLE;
1424 else if (node->local.local)
1425 avail = AVAIL_LOCAL;
1426 else if (node->local.externally_visible)
1427 avail = AVAIL_AVAILABLE;
1429 /* If the function can be overwritten, return OVERWRITABLE. Take
1430 care at least of two notable extensions - the COMDAT functions
1431 used to share template instantiations in C++ (this is symmetric
1432 to code cp_cannot_inline_tree_fn and probably shall be shared and
1433 the inlinability hooks completely eliminated).
1435 ??? Does the C++ one definition rule allow us to always return
1436 AVAIL_AVAILABLE here? That would be good reason to preserve this
1437 hook Similarly deal with extern inline functions - this is again
1438 necessary to get C++ shared functions having keyed templates
1439 right and in the C extension documentation we probably should
1440 document the requirement of both versions of function (extern
1441 inline and offline) having same side effect characteristics as
1442 good optimization is what this optimization is about. */
1444 else if (!(*targetm.binds_local_p) (node->decl)
1445 && !DECL_COMDAT (node->decl) && !DECL_EXTERNAL (node->decl))
1446 avail = AVAIL_OVERWRITABLE;
1447 else avail = AVAIL_AVAILABLE;
1452 /* Add the function FNDECL to the call graph.
1453 Unlike cgraph_finalize_function, this function is intended to be used
1454 by middle end and allows insertion of new function at arbitrary point
1455 of compilation. The function can be either in high, low or SSA form
1458 The function is assumed to be reachable and have address taken (so no
1459 API breaking optimizations are performed on it).
1461 Main work done by this function is to enqueue the function for later
1462 processing to avoid need the passes to be re-entrant. */
1465 cgraph_add_new_function (tree fndecl, bool lowered)
1467 struct cgraph_node *node;
1468 switch (cgraph_state)
1470 case CGRAPH_STATE_CONSTRUCTION:
1471 /* Just enqueue function to be processed at nearest occurrence. */
1472 node = cgraph_node (fndecl);
1473 node->next_needed = cgraph_new_nodes;
1475 node->lowered = true;
1476 cgraph_new_nodes = node;
1479 case CGRAPH_STATE_IPA:
1480 case CGRAPH_STATE_IPA_SSA:
1481 case CGRAPH_STATE_EXPANSION:
1482 /* Bring the function into finalized state and enqueue for later
1483 analyzing and compilation. */
1484 node = cgraph_node (fndecl);
1485 node->local.local = false;
1486 node->local.finalized = true;
1487 node->reachable = node->needed = true;
1488 if (!lowered && cgraph_state == CGRAPH_STATE_EXPANSION)
1490 push_cfun (DECL_STRUCT_FUNCTION (fndecl));
1491 current_function_decl = fndecl;
1492 gimple_register_cfg_hooks ();
1493 tree_lowering_passes (fndecl);
1494 bitmap_obstack_initialize (NULL);
1495 if (!gimple_in_ssa_p (DECL_STRUCT_FUNCTION (fndecl)))
1496 execute_pass_list (pass_early_local_passes.pass.sub);
1497 bitmap_obstack_release (NULL);
1499 current_function_decl = NULL;
1504 node->lowered = true;
1505 node->next_needed = cgraph_new_nodes;
1506 cgraph_new_nodes = node;
1509 case CGRAPH_STATE_FINISHED:
1510 /* At the very end of compilation we have to do all the work up
1512 push_cfun (DECL_STRUCT_FUNCTION (fndecl));
1513 current_function_decl = fndecl;
1514 gimple_register_cfg_hooks ();
1516 tree_lowering_passes (fndecl);
1517 bitmap_obstack_initialize (NULL);
1518 if (!gimple_in_ssa_p (DECL_STRUCT_FUNCTION (fndecl)))
1519 execute_pass_list (pass_early_local_passes.pass.sub);
1520 bitmap_obstack_release (NULL);
1521 tree_rest_of_compilation (fndecl);
1523 current_function_decl = NULL;
1528 #include "gt-cgraph.h"