1 /* Callgraph handling code.
2 Copyright (C) 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010
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-dump.h"
85 #include "tree-flow.h"
86 #include "value-prof.h"
88 #include "diagnostic.h"
91 static void cgraph_node_remove_callers (struct cgraph_node *node);
92 static inline void cgraph_edge_remove_caller (struct cgraph_edge *e);
93 static inline void cgraph_edge_remove_callee (struct cgraph_edge *e);
95 /* Hash table used to convert declarations into nodes. */
96 static GTY((param_is (struct cgraph_node))) htab_t cgraph_hash;
97 /* Hash table used to convert assembler names into nodes. */
98 static GTY((param_is (struct cgraph_node))) htab_t assembler_name_hash;
100 /* The linked list of cgraph nodes. */
101 struct cgraph_node *cgraph_nodes;
103 /* Queue of cgraph nodes scheduled to be lowered. */
104 struct cgraph_node *cgraph_nodes_queue;
106 /* Queue of cgraph nodes scheduled to be added into cgraph. This is a
107 secondary queue used during optimization to accommodate passes that
108 may generate new functions that need to be optimized and expanded. */
109 struct cgraph_node *cgraph_new_nodes;
111 /* Number of nodes in existence. */
114 /* Maximal uid used in cgraph nodes. */
117 /* Maximal uid used in cgraph edges. */
118 int cgraph_edge_max_uid;
120 /* Maximal pid used for profiling */
123 /* Set when whole unit has been analyzed so we can access global info. */
124 bool cgraph_global_info_ready = false;
126 /* What state callgraph is in right now. */
127 enum cgraph_state cgraph_state = CGRAPH_STATE_CONSTRUCTION;
129 /* Set when the cgraph is fully build and the basic flags are computed. */
130 bool cgraph_function_flags_ready = false;
132 /* Linked list of cgraph asm nodes. */
133 struct cgraph_asm_node *cgraph_asm_nodes;
135 /* Last node in cgraph_asm_nodes. */
136 static GTY(()) struct cgraph_asm_node *cgraph_asm_last_node;
138 /* The order index of the next cgraph node to be created. This is
139 used so that we can sort the cgraph nodes in order by when we saw
140 them, to support -fno-toplevel-reorder. */
143 /* List of hooks trigerred on cgraph_edge events. */
144 struct cgraph_edge_hook_list {
145 cgraph_edge_hook hook;
147 struct cgraph_edge_hook_list *next;
150 /* List of hooks trigerred on cgraph_node events. */
151 struct cgraph_node_hook_list {
152 cgraph_node_hook hook;
154 struct cgraph_node_hook_list *next;
157 /* List of hooks trigerred on events involving two cgraph_edges. */
158 struct cgraph_2edge_hook_list {
159 cgraph_2edge_hook hook;
161 struct cgraph_2edge_hook_list *next;
164 /* List of hooks trigerred on events involving two cgraph_nodes. */
165 struct cgraph_2node_hook_list {
166 cgraph_2node_hook hook;
168 struct cgraph_2node_hook_list *next;
171 /* List of hooks triggered when an edge is removed. */
172 struct cgraph_edge_hook_list *first_cgraph_edge_removal_hook;
173 /* List of hooks triggered when a node is removed. */
174 struct cgraph_node_hook_list *first_cgraph_node_removal_hook;
175 /* List of hooks triggered when an edge is duplicated. */
176 struct cgraph_2edge_hook_list *first_cgraph_edge_duplicated_hook;
177 /* List of hooks triggered when a node is duplicated. */
178 struct cgraph_2node_hook_list *first_cgraph_node_duplicated_hook;
179 /* List of hooks triggered when an function is inserted. */
180 struct cgraph_node_hook_list *first_cgraph_function_insertion_hook;
182 /* Head of a linked list of unused (freed) call graph nodes.
183 Do not GTY((delete)) this list so UIDs gets reliably recycled. */
184 static GTY(()) struct cgraph_node *free_nodes;
185 /* Head of a linked list of unused (freed) call graph edges.
186 Do not GTY((delete)) this list so UIDs gets reliably recycled. */
187 static GTY(()) struct cgraph_edge *free_edges;
189 /* Macros to access the next item in the list of free cgraph nodes and
191 #define NEXT_FREE_NODE(NODE) (NODE)->next
192 #define NEXT_FREE_EDGE(EDGE) (EDGE)->prev_caller
194 /* Register HOOK to be called with DATA on each removed edge. */
195 struct cgraph_edge_hook_list *
196 cgraph_add_edge_removal_hook (cgraph_edge_hook hook, void *data)
198 struct cgraph_edge_hook_list *entry;
199 struct cgraph_edge_hook_list **ptr = &first_cgraph_edge_removal_hook;
201 entry = (struct cgraph_edge_hook_list *) xmalloc (sizeof (*entry));
211 /* Remove ENTRY from the list of hooks called on removing edges. */
213 cgraph_remove_edge_removal_hook (struct cgraph_edge_hook_list *entry)
215 struct cgraph_edge_hook_list **ptr = &first_cgraph_edge_removal_hook;
217 while (*ptr != entry)
223 /* Call all edge removal hooks. */
225 cgraph_call_edge_removal_hooks (struct cgraph_edge *e)
227 struct cgraph_edge_hook_list *entry = first_cgraph_edge_removal_hook;
230 entry->hook (e, entry->data);
235 /* Register HOOK to be called with DATA on each removed node. */
236 struct cgraph_node_hook_list *
237 cgraph_add_node_removal_hook (cgraph_node_hook hook, void *data)
239 struct cgraph_node_hook_list *entry;
240 struct cgraph_node_hook_list **ptr = &first_cgraph_node_removal_hook;
242 entry = (struct cgraph_node_hook_list *) xmalloc (sizeof (*entry));
252 /* Remove ENTRY from the list of hooks called on removing nodes. */
254 cgraph_remove_node_removal_hook (struct cgraph_node_hook_list *entry)
256 struct cgraph_node_hook_list **ptr = &first_cgraph_node_removal_hook;
258 while (*ptr != entry)
264 /* Call all node removal hooks. */
266 cgraph_call_node_removal_hooks (struct cgraph_node *node)
268 struct cgraph_node_hook_list *entry = first_cgraph_node_removal_hook;
271 entry->hook (node, entry->data);
276 /* Register HOOK to be called with DATA on each inserted node. */
277 struct cgraph_node_hook_list *
278 cgraph_add_function_insertion_hook (cgraph_node_hook hook, void *data)
280 struct cgraph_node_hook_list *entry;
281 struct cgraph_node_hook_list **ptr = &first_cgraph_function_insertion_hook;
283 entry = (struct cgraph_node_hook_list *) xmalloc (sizeof (*entry));
293 /* Remove ENTRY from the list of hooks called on inserted nodes. */
295 cgraph_remove_function_insertion_hook (struct cgraph_node_hook_list *entry)
297 struct cgraph_node_hook_list **ptr = &first_cgraph_function_insertion_hook;
299 while (*ptr != entry)
305 /* Call all node insertion hooks. */
307 cgraph_call_function_insertion_hooks (struct cgraph_node *node)
309 struct cgraph_node_hook_list *entry = first_cgraph_function_insertion_hook;
312 entry->hook (node, entry->data);
317 /* Register HOOK to be called with DATA on each duplicated edge. */
318 struct cgraph_2edge_hook_list *
319 cgraph_add_edge_duplication_hook (cgraph_2edge_hook hook, void *data)
321 struct cgraph_2edge_hook_list *entry;
322 struct cgraph_2edge_hook_list **ptr = &first_cgraph_edge_duplicated_hook;
324 entry = (struct cgraph_2edge_hook_list *) xmalloc (sizeof (*entry));
334 /* Remove ENTRY from the list of hooks called on duplicating edges. */
336 cgraph_remove_edge_duplication_hook (struct cgraph_2edge_hook_list *entry)
338 struct cgraph_2edge_hook_list **ptr = &first_cgraph_edge_duplicated_hook;
340 while (*ptr != entry)
346 /* Call all edge duplication hooks. */
348 cgraph_call_edge_duplication_hooks (struct cgraph_edge *cs1,
349 struct cgraph_edge *cs2)
351 struct cgraph_2edge_hook_list *entry = first_cgraph_edge_duplicated_hook;
354 entry->hook (cs1, cs2, entry->data);
359 /* Register HOOK to be called with DATA on each duplicated node. */
360 struct cgraph_2node_hook_list *
361 cgraph_add_node_duplication_hook (cgraph_2node_hook hook, void *data)
363 struct cgraph_2node_hook_list *entry;
364 struct cgraph_2node_hook_list **ptr = &first_cgraph_node_duplicated_hook;
366 entry = (struct cgraph_2node_hook_list *) xmalloc (sizeof (*entry));
376 /* Remove ENTRY from the list of hooks called on duplicating nodes. */
378 cgraph_remove_node_duplication_hook (struct cgraph_2node_hook_list *entry)
380 struct cgraph_2node_hook_list **ptr = &first_cgraph_node_duplicated_hook;
382 while (*ptr != entry)
388 /* Call all node duplication hooks. */
390 cgraph_call_node_duplication_hooks (struct cgraph_node *node1,
391 struct cgraph_node *node2)
393 struct cgraph_2node_hook_list *entry = first_cgraph_node_duplicated_hook;
396 entry->hook (node1, node2, entry->data);
401 /* Returns a hash code for P. */
404 hash_node (const void *p)
406 const struct cgraph_node *n = (const struct cgraph_node *) p;
407 return (hashval_t) DECL_UID (n->decl);
411 /* Returns nonzero if P1 and P2 are equal. */
414 eq_node (const void *p1, const void *p2)
416 const struct cgraph_node *n1 = (const struct cgraph_node *) p1;
417 const struct cgraph_node *n2 = (const struct cgraph_node *) p2;
418 return DECL_UID (n1->decl) == DECL_UID (n2->decl);
421 /* Allocate new callgraph node. */
423 static inline struct cgraph_node *
424 cgraph_allocate_node (void)
426 struct cgraph_node *node;
431 free_nodes = NEXT_FREE_NODE (node);
435 node = GGC_CNEW (struct cgraph_node);
436 node->uid = cgraph_max_uid++;
442 /* Allocate new callgraph node and insert it into basic data structures. */
444 static struct cgraph_node *
445 cgraph_create_node (void)
447 struct cgraph_node *node = cgraph_allocate_node ();
449 node->next = cgraph_nodes;
451 node->order = cgraph_order++;
453 cgraph_nodes->previous = node;
454 node->previous = NULL;
455 node->global.estimated_growth = INT_MIN;
456 node->frequency = NODE_FREQUENCY_NORMAL;
462 /* Return cgraph node assigned to DECL. Create new one when needed. */
465 cgraph_node (tree decl)
467 struct cgraph_node key, *node, **slot;
469 gcc_assert (TREE_CODE (decl) == FUNCTION_DECL);
472 cgraph_hash = htab_create_ggc (10, hash_node, eq_node, NULL);
476 slot = (struct cgraph_node **) htab_find_slot (cgraph_hash, &key, INSERT);
481 if (node->same_body_alias)
482 node = node->same_body;
486 node = cgraph_create_node ();
489 if (DECL_CONTEXT (decl) && TREE_CODE (DECL_CONTEXT (decl)) == FUNCTION_DECL)
491 node->origin = cgraph_node (DECL_CONTEXT (decl));
492 node->next_nested = node->origin->nested;
493 node->origin->nested = node;
495 if (assembler_name_hash)
498 tree name = DECL_ASSEMBLER_NAME (decl);
500 aslot = htab_find_slot_with_hash (assembler_name_hash, name,
501 decl_assembler_name_hash (name),
503 /* We can have multiple declarations with same assembler name. For C++
504 it is __builtin_strlen and strlen, for instance. Do we need to
505 record them all? Original implementation marked just first one
506 so lets hope for the best. */
513 /* Mark ALIAS as an alias to DECL. */
515 static struct cgraph_node *
516 cgraph_same_body_alias_1 (tree alias, tree decl)
518 struct cgraph_node key, *alias_node, *decl_node, **slot;
520 gcc_assert (TREE_CODE (decl) == FUNCTION_DECL);
521 gcc_assert (TREE_CODE (alias) == FUNCTION_DECL);
522 decl_node = cgraph_node (decl);
526 slot = (struct cgraph_node **) htab_find_slot (cgraph_hash, &key, INSERT);
528 /* If the cgraph_node has been already created, fail. */
532 alias_node = cgraph_allocate_node ();
533 alias_node->decl = alias;
534 alias_node->same_body_alias = 1;
535 alias_node->same_body = decl_node;
536 alias_node->previous = NULL;
537 if (decl_node->same_body)
538 decl_node->same_body->previous = alias_node;
539 alias_node->next = decl_node->same_body;
540 alias_node->thunk.alias = decl;
541 decl_node->same_body = alias_node;
546 /* Attempt to mark ALIAS as an alias to DECL. Return TRUE if successful.
547 Same body aliases are output whenever the body of DECL is output,
548 and cgraph_node (ALIAS) transparently returns cgraph_node (DECL). */
551 cgraph_same_body_alias (tree alias, tree decl)
553 #ifndef ASM_OUTPUT_DEF
554 /* If aliases aren't supported by the assembler, fail. */
558 /*gcc_assert (!assembler_name_hash);*/
560 return cgraph_same_body_alias_1 (alias, decl) != NULL;
564 cgraph_add_thunk (tree alias, tree decl, bool this_adjusting,
565 HOST_WIDE_INT fixed_offset, HOST_WIDE_INT virtual_value,
569 struct cgraph_node *node = cgraph_get_node (alias);
573 gcc_assert (node->local.finalized);
574 gcc_assert (!node->same_body);
575 cgraph_remove_node (node);
578 node = cgraph_same_body_alias_1 (alias, decl);
580 #ifdef ENABLE_CHECKING
581 gcc_assert (!virtual_offset
582 || tree_int_cst_equal (virtual_offset, size_int (virtual_value)));
584 node->thunk.fixed_offset = fixed_offset;
585 node->thunk.this_adjusting = this_adjusting;
586 node->thunk.virtual_value = virtual_value;
587 node->thunk.virtual_offset_p = virtual_offset != NULL;
588 node->thunk.alias = real_alias;
589 node->thunk.thunk_p = true;
592 /* Returns the cgraph node assigned to DECL or NULL if no cgraph node
596 cgraph_get_node (tree decl)
598 struct cgraph_node key, *node = NULL, **slot;
600 gcc_assert (TREE_CODE (decl) == FUNCTION_DECL);
607 slot = (struct cgraph_node **) htab_find_slot (cgraph_hash, &key,
613 if (node->same_body_alias)
614 node = node->same_body;
619 /* Insert already constructed node into hashtable. */
622 cgraph_insert_node_to_hashtable (struct cgraph_node *node)
624 struct cgraph_node **slot;
626 slot = (struct cgraph_node **) htab_find_slot (cgraph_hash, node, INSERT);
632 /* Returns a hash code for P. */
635 hash_node_by_assembler_name (const void *p)
637 const struct cgraph_node *n = (const struct cgraph_node *) p;
638 return (hashval_t) decl_assembler_name_hash (DECL_ASSEMBLER_NAME (n->decl));
641 /* Returns nonzero if P1 and P2 are equal. */
644 eq_assembler_name (const void *p1, const void *p2)
646 const struct cgraph_node *n1 = (const struct cgraph_node *) p1;
647 const_tree name = (const_tree)p2;
648 return (decl_assembler_name_equal (n1->decl, name));
651 /* Return the cgraph node that has ASMNAME for its DECL_ASSEMBLER_NAME.
652 Return NULL if there's no such node. */
655 cgraph_node_for_asm (tree asmname)
657 struct cgraph_node *node;
660 if (!assembler_name_hash)
662 assembler_name_hash =
663 htab_create_ggc (10, hash_node_by_assembler_name, eq_assembler_name,
665 for (node = cgraph_nodes; node; node = node->next)
666 if (!node->global.inlined_to)
668 tree name = DECL_ASSEMBLER_NAME (node->decl);
669 slot = htab_find_slot_with_hash (assembler_name_hash, name,
670 decl_assembler_name_hash (name),
672 /* We can have multiple declarations with same assembler name. For C++
673 it is __builtin_strlen and strlen, for instance. Do we need to
674 record them all? Original implementation marked just first one
675 so lets hope for the best. */
680 struct cgraph_node *alias;
682 for (alias = node->same_body; alias; alias = alias->next)
685 name = DECL_ASSEMBLER_NAME (alias->decl);
686 hash = decl_assembler_name_hash (name);
687 slot = htab_find_slot_with_hash (assembler_name_hash, name,
696 slot = htab_find_slot_with_hash (assembler_name_hash, asmname,
697 decl_assembler_name_hash (asmname),
702 node = (struct cgraph_node *) *slot;
703 if (node->same_body_alias)
704 node = node->same_body;
710 /* Returns a hash value for X (which really is a die_struct). */
713 edge_hash (const void *x)
715 return htab_hash_pointer (((const struct cgraph_edge *) x)->call_stmt);
718 /* Return nonzero if decl_id of die_struct X is the same as UID of decl *Y. */
721 edge_eq (const void *x, const void *y)
723 return ((const struct cgraph_edge *) x)->call_stmt == y;
727 /* Return the callgraph edge representing the GIMPLE_CALL statement
731 cgraph_edge (struct cgraph_node *node, gimple call_stmt)
733 struct cgraph_edge *e, *e2;
736 if (node->call_site_hash)
737 return (struct cgraph_edge *)
738 htab_find_with_hash (node->call_site_hash, call_stmt,
739 htab_hash_pointer (call_stmt));
741 /* This loop may turn out to be performance problem. In such case adding
742 hashtables into call nodes with very many edges is probably best
743 solution. It is not good idea to add pointer into CALL_EXPR itself
744 because we want to make possible having multiple cgraph nodes representing
745 different clones of the same body before the body is actually cloned. */
746 for (e = node->callees; e; e= e->next_callee)
748 if (e->call_stmt == call_stmt)
755 node->call_site_hash = htab_create_ggc (120, edge_hash, edge_eq, NULL);
756 for (e2 = node->callees; e2; e2 = e2->next_callee)
759 slot = htab_find_slot_with_hash (node->call_site_hash,
761 htab_hash_pointer (e2->call_stmt),
772 /* Change field call_stmt of edge E to NEW_STMT. */
775 cgraph_set_call_stmt (struct cgraph_edge *e, gimple new_stmt)
777 if (e->caller->call_site_hash)
779 htab_remove_elt_with_hash (e->caller->call_site_hash,
781 htab_hash_pointer (e->call_stmt));
783 e->call_stmt = new_stmt;
784 push_cfun (DECL_STRUCT_FUNCTION (e->caller->decl));
785 e->can_throw_external = stmt_can_throw_external (new_stmt);
787 if (e->caller->call_site_hash)
790 slot = htab_find_slot_with_hash (e->caller->call_site_hash,
793 (e->call_stmt), INSERT);
799 /* Like cgraph_set_call_stmt but walk the clone tree and update all
800 clones sharing the same function body. */
803 cgraph_set_call_stmt_including_clones (struct cgraph_node *orig,
804 gimple old_stmt, gimple new_stmt)
806 struct cgraph_node *node;
807 struct cgraph_edge *edge = cgraph_edge (orig, old_stmt);
810 cgraph_set_call_stmt (edge, new_stmt);
816 struct cgraph_edge *edge = cgraph_edge (node, old_stmt);
818 cgraph_set_call_stmt (edge, new_stmt);
821 else if (node->next_sibling_clone)
822 node = node->next_sibling_clone;
825 while (node != orig && !node->next_sibling_clone)
826 node = node->clone_of;
828 node = node->next_sibling_clone;
833 /* Like cgraph_create_edge walk the clone tree and update all clones sharing
834 same function body. If clones already have edge for OLD_STMT; only
835 update the edge same way as cgraph_set_call_stmt_including_clones does.
837 TODO: COUNT and LOOP_DEPTH should be properly distributed based on relative
838 frequencies of the clones. */
841 cgraph_create_edge_including_clones (struct cgraph_node *orig,
842 struct cgraph_node *callee,
844 gimple stmt, gcov_type count,
845 int freq, int loop_depth,
846 cgraph_inline_failed_t reason)
848 struct cgraph_node *node;
849 struct cgraph_edge *edge;
851 if (!cgraph_edge (orig, stmt))
853 edge = cgraph_create_edge (orig, callee, stmt, count, freq, loop_depth);
854 edge->inline_failed = reason;
861 struct cgraph_edge *edge = cgraph_edge (node, old_stmt);
863 /* It is possible that clones already contain the edge while
864 master didn't. Either we promoted indirect call into direct
865 call in the clone or we are processing clones of unreachable
866 master where edges has been rmeoved. */
868 cgraph_set_call_stmt (edge, stmt);
869 else if (!cgraph_edge (node, stmt))
871 edge = cgraph_create_edge (node, callee, stmt, count,
873 edge->inline_failed = reason;
878 else if (node->next_sibling_clone)
879 node = node->next_sibling_clone;
882 while (node != orig && !node->next_sibling_clone)
883 node = node->clone_of;
885 node = node->next_sibling_clone;
890 /* Give initial reasons why inlining would fail on EDGE. This gets either
891 nullified or usually overwritten by more precise reasons later. */
894 initialize_inline_failed (struct cgraph_edge *e)
896 struct cgraph_node *callee = e->callee;
898 if (!callee->analyzed)
899 e->inline_failed = CIF_BODY_NOT_AVAILABLE;
900 else if (callee->local.redefined_extern_inline)
901 e->inline_failed = CIF_REDEFINED_EXTERN_INLINE;
902 else if (!callee->local.inlinable)
903 e->inline_failed = CIF_FUNCTION_NOT_INLINABLE;
904 else if (e->call_stmt && gimple_call_cannot_inline_p (e->call_stmt))
905 e->inline_failed = CIF_MISMATCHED_ARGUMENTS;
907 e->inline_failed = CIF_FUNCTION_NOT_CONSIDERED;
910 /* Create edge from CALLER to CALLEE in the cgraph. */
913 cgraph_create_edge (struct cgraph_node *caller, struct cgraph_node *callee,
914 gimple call_stmt, gcov_type count, int freq, int nest)
916 struct cgraph_edge *edge;
919 /* LTO does not actually have access to the call_stmt since these
920 have not been loaded yet. */
923 #ifdef ENABLE_CHECKING
924 /* This is rather pricely check possibly trigerring construction of
925 call stmt hashtable. */
926 gcc_assert (!cgraph_edge (caller, call_stmt));
929 gcc_assert (is_gimple_call (call_stmt));
935 free_edges = NEXT_FREE_EDGE (edge);
939 edge = GGC_NEW (struct cgraph_edge);
940 edge->uid = cgraph_edge_max_uid++;
945 edge->caller = caller;
946 edge->callee = callee;
947 edge->call_stmt = call_stmt;
948 push_cfun (DECL_STRUCT_FUNCTION (caller->decl));
949 edge->can_throw_external
950 = call_stmt ? stmt_can_throw_external (call_stmt) : false;
952 edge->prev_caller = NULL;
953 edge->next_caller = callee->callers;
955 callee->callers->prev_caller = edge;
956 edge->prev_callee = NULL;
957 edge->next_callee = caller->callees;
959 caller->callees->prev_callee = edge;
960 caller->callees = edge;
961 callee->callers = edge;
963 gcc_assert (count >= 0);
964 edge->frequency = freq;
965 gcc_assert (freq >= 0);
966 gcc_assert (freq <= CGRAPH_FREQ_MAX);
967 edge->loop_nest = nest;
968 edge->indirect_call = 0;
969 edge->call_stmt_cannot_inline_p =
970 (call_stmt ? gimple_call_cannot_inline_p (call_stmt) : false);
971 if (call_stmt && caller->call_site_hash)
974 slot = htab_find_slot_with_hash (caller->call_site_hash,
983 initialize_inline_failed (edge);
988 /* Remove the edge E from the list of the callers of the callee. */
991 cgraph_edge_remove_callee (struct cgraph_edge *e)
994 e->prev_caller->next_caller = e->next_caller;
996 e->next_caller->prev_caller = e->prev_caller;
998 e->callee->callers = e->next_caller;
1001 /* Remove the edge E from the list of the callees of the caller. */
1004 cgraph_edge_remove_caller (struct cgraph_edge *e)
1007 e->prev_callee->next_callee = e->next_callee;
1009 e->next_callee->prev_callee = e->prev_callee;
1010 if (!e->prev_callee)
1011 e->caller->callees = e->next_callee;
1012 if (e->caller->call_site_hash)
1013 htab_remove_elt_with_hash (e->caller->call_site_hash,
1015 htab_hash_pointer (e->call_stmt));
1018 /* Put the edge onto the free list. */
1021 cgraph_free_edge (struct cgraph_edge *e)
1025 /* Clear out the edge so we do not dangle pointers. */
1026 memset (e, 0, sizeof (*e));
1028 NEXT_FREE_EDGE (e) = free_edges;
1032 /* Remove the edge E in the cgraph. */
1035 cgraph_remove_edge (struct cgraph_edge *e)
1037 /* Call all edge removal hooks. */
1038 cgraph_call_edge_removal_hooks (e);
1040 /* Remove from callers list of the callee. */
1041 cgraph_edge_remove_callee (e);
1043 /* Remove from callees list of the callers. */
1044 cgraph_edge_remove_caller (e);
1046 /* Put the edge onto the free list. */
1047 cgraph_free_edge (e);
1050 /* Redirect callee of E to N. The function does not update underlying
1054 cgraph_redirect_edge_callee (struct cgraph_edge *e, struct cgraph_node *n)
1056 /* Remove from callers list of the current callee. */
1057 cgraph_edge_remove_callee (e);
1059 /* Insert to callers list of the new callee. */
1060 e->prev_caller = NULL;
1062 n->callers->prev_caller = e;
1063 e->next_caller = n->callers;
1069 /* Update or remove the corresponding cgraph edge if a GIMPLE_CALL
1070 OLD_STMT changed into NEW_STMT. OLD_CALL is gimple_call_fndecl
1071 of OLD_STMT if it was previously call statement. */
1074 cgraph_update_edges_for_call_stmt_node (struct cgraph_node *node,
1075 gimple old_stmt, tree old_call, gimple new_stmt)
1077 tree new_call = (is_gimple_call (new_stmt)) ? gimple_call_fndecl (new_stmt) : 0;
1079 /* We are seeing indirect calls, then there is nothing to update. */
1080 if (!new_call && !old_call)
1082 /* See if we turned indirect call into direct call or folded call to one builtin
1083 into different bultin. */
1084 if (old_call != new_call)
1086 struct cgraph_edge *e = cgraph_edge (node, old_stmt);
1087 struct cgraph_edge *ne = NULL;
1094 /* See if the call is already there. It might be because of indirect
1095 inlining already found it. */
1096 if (new_call && e->callee->decl == new_call)
1099 /* Otherwise remove edge and create new one; we can't simply redirect
1100 since function has changed, so inline plan and other information
1101 attached to edge is invalid. */
1103 frequency = e->frequency;
1104 loop_nest = e->loop_nest;
1105 cgraph_remove_edge (e);
1109 /* We are seeing new direct call; compute profile info based on BB. */
1110 basic_block bb = gimple_bb (new_stmt);
1112 frequency = compute_call_stmt_bb_frequency (current_function_decl,
1114 loop_nest = bb->loop_depth;
1119 ne = cgraph_create_edge (node, cgraph_node (new_call),
1120 new_stmt, count, frequency,
1122 gcc_assert (ne->inline_failed);
1125 /* We only updated the call stmt; update pointer in cgraph edge.. */
1126 else if (old_stmt != new_stmt)
1127 cgraph_set_call_stmt (cgraph_edge (node, old_stmt), new_stmt);
1130 /* Update or remove the corresponding cgraph edge if a GIMPLE_CALL
1131 OLD_STMT changed into NEW_STMT. OLD_DECL is gimple_call_fndecl
1132 of OLD_STMT before it was updated (updating can happen inplace). */
1135 cgraph_update_edges_for_call_stmt (gimple old_stmt, tree old_decl, gimple new_stmt)
1137 struct cgraph_node *orig = cgraph_node (cfun->decl);
1138 struct cgraph_node *node;
1140 cgraph_update_edges_for_call_stmt_node (orig, old_stmt, old_decl, new_stmt);
1142 for (node = orig->clones; node != orig;)
1144 cgraph_update_edges_for_call_stmt_node (node, old_stmt, old_decl, new_stmt);
1146 node = node->clones;
1147 else if (node->next_sibling_clone)
1148 node = node->next_sibling_clone;
1151 while (node != orig && !node->next_sibling_clone)
1152 node = node->clone_of;
1154 node = node->next_sibling_clone;
1160 /* Remove all callees from the node. */
1163 cgraph_node_remove_callees (struct cgraph_node *node)
1165 struct cgraph_edge *e, *f;
1167 /* It is sufficient to remove the edges from the lists of callers of
1168 the callees. The callee list of the node can be zapped with one
1170 for (e = node->callees; e; e = f)
1173 cgraph_call_edge_removal_hooks (e);
1174 cgraph_edge_remove_callee (e);
1175 cgraph_free_edge (e);
1177 node->callees = NULL;
1178 if (node->call_site_hash)
1180 htab_delete (node->call_site_hash);
1181 node->call_site_hash = NULL;
1185 /* Remove all callers from the node. */
1188 cgraph_node_remove_callers (struct cgraph_node *node)
1190 struct cgraph_edge *e, *f;
1192 /* It is sufficient to remove the edges from the lists of callees of
1193 the callers. The caller list of the node can be zapped with one
1195 for (e = node->callers; e; e = f)
1198 cgraph_call_edge_removal_hooks (e);
1199 cgraph_edge_remove_caller (e);
1200 cgraph_free_edge (e);
1202 node->callers = NULL;
1205 /* Release memory used to represent body of function NODE. */
1208 cgraph_release_function_body (struct cgraph_node *node)
1210 if (DECL_STRUCT_FUNCTION (node->decl))
1212 tree old_decl = current_function_decl;
1213 push_cfun (DECL_STRUCT_FUNCTION (node->decl));
1214 if (cfun->gimple_df)
1216 current_function_decl = node->decl;
1218 delete_tree_cfg_annotations ();
1220 current_function_decl = old_decl;
1224 gcc_assert (dom_computed[0] == DOM_NONE);
1225 gcc_assert (dom_computed[1] == DOM_NONE);
1228 if (cfun->value_histograms)
1230 gcc_assert (!current_loops);
1232 gimple_set_body (node->decl, NULL);
1233 VEC_free (ipa_opt_pass, heap,
1234 node->ipa_transforms_to_apply);
1235 /* Struct function hangs a lot of data that would leak if we didn't
1236 removed all pointers to it. */
1237 ggc_free (DECL_STRUCT_FUNCTION (node->decl));
1238 DECL_STRUCT_FUNCTION (node->decl) = NULL;
1240 DECL_SAVED_TREE (node->decl) = NULL;
1241 /* If the node is abstract and needed, then do not clear DECL_INITIAL
1242 of its associated function function declaration because it's
1243 needed to emit debug info later. */
1244 if (!node->abstract_and_needed)
1245 DECL_INITIAL (node->decl) = error_mark_node;
1248 /* Remove same body alias node. */
1251 cgraph_remove_same_body_alias (struct cgraph_node *node)
1254 int uid = node->uid;
1256 gcc_assert (node->same_body_alias);
1258 node->previous->next = node->next;
1260 node->same_body->same_body = node->next;
1262 node->next->previous = node->previous;
1264 node->previous = NULL;
1265 slot = htab_find_slot (cgraph_hash, node, NO_INSERT);
1267 htab_clear_slot (cgraph_hash, slot);
1268 if (assembler_name_hash)
1270 tree name = DECL_ASSEMBLER_NAME (node->decl);
1271 slot = htab_find_slot_with_hash (assembler_name_hash, name,
1272 decl_assembler_name_hash (name),
1274 if (slot && *slot == node)
1275 htab_clear_slot (assembler_name_hash, slot);
1278 /* Clear out the node to NULL all pointers and add the node to the free
1280 memset (node, 0, sizeof(*node));
1282 NEXT_FREE_NODE (node) = free_nodes;
1286 /* Remove the node from cgraph. */
1289 cgraph_remove_node (struct cgraph_node *node)
1292 bool kill_body = false;
1293 struct cgraph_node *n;
1294 int uid = node->uid;
1296 cgraph_call_node_removal_hooks (node);
1297 cgraph_node_remove_callers (node);
1298 cgraph_node_remove_callees (node);
1299 VEC_free (ipa_opt_pass, heap,
1300 node->ipa_transforms_to_apply);
1302 /* Incremental inlining access removed nodes stored in the postorder list.
1304 node->needed = node->reachable = false;
1305 for (n = node->nested; n; n = n->next_nested)
1307 node->nested = NULL;
1310 struct cgraph_node **node2 = &node->origin->nested;
1312 while (*node2 != node)
1313 node2 = &(*node2)->next_nested;
1314 *node2 = node->next_nested;
1317 node->previous->next = node->next;
1319 cgraph_nodes = node->next;
1321 node->next->previous = node->previous;
1323 node->previous = NULL;
1324 slot = htab_find_slot (cgraph_hash, node, NO_INSERT);
1327 struct cgraph_node *next_inline_clone;
1329 for (next_inline_clone = node->clones;
1330 next_inline_clone && next_inline_clone->decl != node->decl;
1331 next_inline_clone = next_inline_clone->next_sibling_clone)
1334 /* If there is inline clone of the node being removed, we need
1335 to put it into the position of removed node and reorganize all
1336 other clones to be based on it. */
1337 if (next_inline_clone)
1339 struct cgraph_node *n;
1340 struct cgraph_node *new_clones;
1342 *slot = next_inline_clone;
1344 /* Unlink inline clone from the list of clones of removed node. */
1345 if (next_inline_clone->next_sibling_clone)
1346 next_inline_clone->next_sibling_clone->prev_sibling_clone
1347 = next_inline_clone->prev_sibling_clone;
1348 if (next_inline_clone->prev_sibling_clone)
1350 gcc_assert (node->clones != next_inline_clone);
1351 next_inline_clone->prev_sibling_clone->next_sibling_clone
1352 = next_inline_clone->next_sibling_clone;
1356 gcc_assert (node->clones == next_inline_clone);
1357 node->clones = next_inline_clone->next_sibling_clone;
1360 new_clones = node->clones;
1361 node->clones = NULL;
1363 /* Copy clone info. */
1364 next_inline_clone->clone = node->clone;
1366 /* Now place it into clone tree at same level at NODE. */
1367 next_inline_clone->clone_of = node->clone_of;
1368 next_inline_clone->prev_sibling_clone = NULL;
1369 next_inline_clone->next_sibling_clone = NULL;
1372 if (node->clone_of->clones)
1373 node->clone_of->clones->prev_sibling_clone = next_inline_clone;
1374 next_inline_clone->next_sibling_clone = node->clone_of->clones;
1375 node->clone_of->clones = next_inline_clone;
1378 /* Merge the clone list. */
1381 if (!next_inline_clone->clones)
1382 next_inline_clone->clones = new_clones;
1385 n = next_inline_clone->clones;
1386 while (n->next_sibling_clone)
1387 n = n->next_sibling_clone;
1388 n->next_sibling_clone = new_clones;
1389 new_clones->prev_sibling_clone = n;
1393 /* Update clone_of pointers. */
1397 n->clone_of = next_inline_clone;
1398 n = n->next_sibling_clone;
1403 htab_clear_slot (cgraph_hash, slot);
1408 if (node->prev_sibling_clone)
1409 node->prev_sibling_clone->next_sibling_clone = node->next_sibling_clone;
1410 else if (node->clone_of)
1411 node->clone_of->clones = node->next_sibling_clone;
1412 if (node->next_sibling_clone)
1413 node->next_sibling_clone->prev_sibling_clone = node->prev_sibling_clone;
1416 struct cgraph_node *n, *next;
1420 for (n = node->clones; n->next_sibling_clone; n = n->next_sibling_clone)
1421 n->clone_of = node->clone_of;
1422 n->clone_of = node->clone_of;
1423 n->next_sibling_clone = node->clone_of->clones;
1424 if (node->clone_of->clones)
1425 node->clone_of->clones->prev_sibling_clone = n;
1426 node->clone_of->clones = node->clones;
1430 /* We are removing node with clones. this makes clones inconsistent,
1431 but assume they will be removed subsequently and just keep clone
1432 tree intact. This can happen in unreachable function removal since
1433 we remove unreachable functions in random order, not by bottom-up
1434 walk of clone trees. */
1435 for (n = node->clones; n; n = next)
1437 next = n->next_sibling_clone;
1438 n->next_sibling_clone = NULL;
1439 n->prev_sibling_clone = NULL;
1445 while (node->same_body)
1446 cgraph_remove_same_body_alias (node->same_body);
1448 if (node->same_comdat_group)
1450 struct cgraph_node *prev;
1451 for (prev = node->same_comdat_group;
1452 prev->same_comdat_group != node;
1453 prev = prev->same_comdat_group)
1455 if (node->same_comdat_group == prev)
1456 prev->same_comdat_group = NULL;
1458 prev->same_comdat_group = node->same_comdat_group;
1459 node->same_comdat_group = NULL;
1462 /* While all the clones are removed after being proceeded, the function
1463 itself is kept in the cgraph even after it is compiled. Check whether
1464 we are done with this body and reclaim it proactively if this is the case.
1466 if (!kill_body && *slot)
1468 struct cgraph_node *n = (struct cgraph_node *) *slot;
1469 if (!n->clones && !n->clone_of && !n->global.inlined_to
1470 && (cgraph_global_info_ready
1471 && (TREE_ASM_WRITTEN (n->decl) || DECL_EXTERNAL (n->decl)
1472 || n->in_other_partition)))
1475 if (assembler_name_hash)
1477 tree name = DECL_ASSEMBLER_NAME (node->decl);
1478 slot = htab_find_slot_with_hash (assembler_name_hash, name,
1479 decl_assembler_name_hash (name),
1481 /* Inline clones are not hashed. */
1482 if (slot && *slot == node)
1483 htab_clear_slot (assembler_name_hash, slot);
1487 cgraph_release_function_body (node);
1489 if (node->call_site_hash)
1491 htab_delete (node->call_site_hash);
1492 node->call_site_hash = NULL;
1496 /* Clear out the node to NULL all pointers and add the node to the free
1498 memset (node, 0, sizeof(*node));
1500 NEXT_FREE_NODE (node) = free_nodes;
1504 /* Remove the node from cgraph. */
1507 cgraph_remove_node_and_inline_clones (struct cgraph_node *node)
1509 struct cgraph_edge *e, *next;
1510 for (e = node->callees; e; e = next)
1512 next = e->next_callee;
1513 if (!e->inline_failed)
1514 cgraph_remove_node_and_inline_clones (e->callee);
1516 cgraph_remove_node (node);
1519 /* Notify finalize_compilation_unit that given node is reachable. */
1522 cgraph_mark_reachable_node (struct cgraph_node *node)
1524 if (!node->reachable && node->local.finalized)
1526 notice_global_symbol (node->decl);
1527 node->reachable = 1;
1528 gcc_assert (!cgraph_global_info_ready);
1530 node->next_needed = cgraph_nodes_queue;
1531 cgraph_nodes_queue = node;
1535 /* Likewise indicate that a node is needed, i.e. reachable via some
1539 cgraph_mark_needed_node (struct cgraph_node *node)
1542 gcc_assert (!node->global.inlined_to);
1543 cgraph_mark_reachable_node (node);
1546 /* Likewise indicate that a node is having address taken. */
1549 cgraph_mark_address_taken_node (struct cgraph_node *node)
1551 node->address_taken = 1;
1552 cgraph_mark_needed_node (node);
1555 /* Return local info for the compiled function. */
1557 struct cgraph_local_info *
1558 cgraph_local_info (tree decl)
1560 struct cgraph_node *node;
1562 gcc_assert (TREE_CODE (decl) == FUNCTION_DECL);
1563 node = cgraph_node (decl);
1564 return &node->local;
1567 /* Return local info for the compiled function. */
1569 struct cgraph_global_info *
1570 cgraph_global_info (tree decl)
1572 struct cgraph_node *node;
1574 gcc_assert (TREE_CODE (decl) == FUNCTION_DECL && cgraph_global_info_ready);
1575 node = cgraph_node (decl);
1576 return &node->global;
1579 /* Return local info for the compiled function. */
1581 struct cgraph_rtl_info *
1582 cgraph_rtl_info (tree decl)
1584 struct cgraph_node *node;
1586 gcc_assert (TREE_CODE (decl) == FUNCTION_DECL);
1587 node = cgraph_node (decl);
1588 if (decl != current_function_decl
1589 && !TREE_ASM_WRITTEN (node->decl))
1594 /* Return a string describing the failure REASON. */
1597 cgraph_inline_failed_string (cgraph_inline_failed_t reason)
1600 #define DEFCIFCODE(code, string) string,
1602 static const char *cif_string_table[CIF_N_REASONS] = {
1603 #include "cif-code.def"
1606 /* Signedness of an enum type is implementation defined, so cast it
1607 to unsigned before testing. */
1608 gcc_assert ((unsigned) reason < CIF_N_REASONS);
1609 return cif_string_table[reason];
1612 /* Return name of the node used in debug output. */
1614 cgraph_node_name (struct cgraph_node *node)
1616 return lang_hooks.decl_printable_name (node->decl, 2);
1619 /* Names used to print out the availability enum. */
1620 const char * const cgraph_availability_names[] =
1621 {"unset", "not_available", "overwritable", "available", "local"};
1624 /* Dump call graph node NODE to file F. */
1627 dump_cgraph_node (FILE *f, struct cgraph_node *node)
1629 struct cgraph_edge *edge;
1630 fprintf (f, "%s/%i(%i)", cgraph_node_name (node), node->uid,
1632 dump_addr (f, " @", (void *)node);
1633 if (DECL_ASSEMBLER_NAME_SET_P (node->decl))
1634 fprintf (f, " (asm: %s)", IDENTIFIER_POINTER (DECL_ASSEMBLER_NAME (node->decl)));
1635 if (node->global.inlined_to)
1636 fprintf (f, " (inline copy in %s/%i)",
1637 cgraph_node_name (node->global.inlined_to),
1638 node->global.inlined_to->uid);
1640 fprintf (f, " (clone of %s/%i)",
1641 cgraph_node_name (node->clone_of),
1642 node->clone_of->uid);
1643 if (cgraph_function_flags_ready)
1644 fprintf (f, " availability:%s",
1645 cgraph_availability_names [cgraph_function_body_availability (node)]);
1647 fprintf (f, " analyzed");
1648 if (node->in_other_partition)
1649 fprintf (f, " in_other_partition");
1651 fprintf (f, " executed "HOST_WIDEST_INT_PRINT_DEC"x",
1652 (HOST_WIDEST_INT)node->count);
1653 if (node->local.inline_summary.self_time)
1654 fprintf (f, " %i time, %i benefit", node->local.inline_summary.self_time,
1655 node->local.inline_summary.time_inlining_benefit);
1656 if (node->global.time && node->global.time
1657 != node->local.inline_summary.self_time)
1658 fprintf (f, " (%i after inlining)", node->global.time);
1659 if (node->local.inline_summary.self_size)
1660 fprintf (f, " %i size, %i benefit", node->local.inline_summary.self_size,
1661 node->local.inline_summary.size_inlining_benefit);
1662 if (node->global.size && node->global.size
1663 != node->local.inline_summary.self_size)
1664 fprintf (f, " (%i after inlining)", node->global.size);
1665 if (node->local.inline_summary.estimated_self_stack_size)
1666 fprintf (f, " %i bytes stack usage", (int)node->local.inline_summary.estimated_self_stack_size);
1667 if (node->global.estimated_stack_size != node->local.inline_summary.estimated_self_stack_size)
1668 fprintf (f, " %i bytes after inlining", (int)node->global.estimated_stack_size);
1670 fprintf (f, " nested in: %s", cgraph_node_name (node->origin));
1672 fprintf (f, " needed");
1673 if (node->address_taken)
1674 fprintf (f, " address_taken");
1675 else if (node->reachable)
1676 fprintf (f, " reachable");
1677 else if (node->reachable_from_other_partition)
1678 fprintf (f, " reachable_from_other_partition");
1679 if (gimple_has_body_p (node->decl))
1680 fprintf (f, " body");
1682 fprintf (f, " process");
1683 if (node->local.local)
1684 fprintf (f, " local");
1685 if (node->local.externally_visible)
1686 fprintf (f, " externally_visible");
1687 if (node->local.finalized)
1688 fprintf (f, " finalized");
1689 if (node->local.disregard_inline_limits)
1690 fprintf (f, " always_inline");
1691 else if (node->local.inlinable)
1692 fprintf (f, " inlinable");
1693 if (node->local.redefined_extern_inline)
1694 fprintf (f, " redefined_extern_inline");
1695 if (TREE_ASM_WRITTEN (node->decl))
1696 fprintf (f, " asm_written");
1698 fprintf (f, "\n called by: ");
1699 for (edge = node->callers; edge; edge = edge->next_caller)
1701 fprintf (f, "%s/%i ", cgraph_node_name (edge->caller),
1704 fprintf (f, "("HOST_WIDEST_INT_PRINT_DEC"x) ",
1705 (HOST_WIDEST_INT)edge->count);
1706 if (edge->frequency)
1707 fprintf (f, "(%.2f per call) ",
1708 edge->frequency / (double)CGRAPH_FREQ_BASE);
1709 if (!edge->inline_failed)
1710 fprintf(f, "(inlined) ");
1711 if (edge->indirect_call)
1712 fprintf(f, "(indirect) ");
1713 if (edge->can_throw_external)
1714 fprintf(f, "(can throw external) ");
1717 fprintf (f, "\n calls: ");
1718 for (edge = node->callees; edge; edge = edge->next_callee)
1720 fprintf (f, "%s/%i ", cgraph_node_name (edge->callee),
1722 if (!edge->inline_failed)
1723 fprintf(f, "(inlined) ");
1724 if (edge->indirect_call)
1725 fprintf(f, "(indirect) ");
1727 fprintf (f, "("HOST_WIDEST_INT_PRINT_DEC"x) ",
1728 (HOST_WIDEST_INT)edge->count);
1729 if (edge->frequency)
1730 fprintf (f, "(%.2f per call) ",
1731 edge->frequency / (double)CGRAPH_FREQ_BASE);
1732 if (edge->loop_nest)
1733 fprintf (f, "(nested in %i loops) ", edge->loop_nest);
1734 if (edge->can_throw_external)
1735 fprintf(f, "(can throw external) ");
1739 if (node->same_body)
1741 struct cgraph_node *n;
1742 fprintf (f, " aliases & thunks:");
1743 for (n = node->same_body; n; n = n->next)
1745 fprintf (f, " %s/%i", cgraph_node_name (n), n->uid);
1746 if (n->thunk.thunk_p)
1748 fprintf (f, " (thunk of %s fixed ofset %i virtual value %i has "
1749 "virtual offset %i",
1750 lang_hooks.decl_printable_name (n->thunk.alias, 2),
1751 (int)n->thunk.fixed_offset,
1752 (int)n->thunk.virtual_value,
1753 (int)n->thunk.virtual_offset_p);
1762 /* Dump call graph node NODE to stderr. */
1765 debug_cgraph_node (struct cgraph_node *node)
1767 dump_cgraph_node (stderr, node);
1771 /* Dump the callgraph to file F. */
1774 dump_cgraph (FILE *f)
1776 struct cgraph_node *node;
1778 fprintf (f, "callgraph:\n\n");
1779 for (node = cgraph_nodes; node; node = node->next)
1780 dump_cgraph_node (f, node);
1784 /* Dump the call graph to stderr. */
1789 dump_cgraph (stderr);
1793 /* Set the DECL_ASSEMBLER_NAME and update cgraph hashtables. */
1796 change_decl_assembler_name (tree decl, tree name)
1798 gcc_assert (!assembler_name_hash);
1799 if (!DECL_ASSEMBLER_NAME_SET_P (decl))
1801 SET_DECL_ASSEMBLER_NAME (decl, name);
1804 if (name == DECL_ASSEMBLER_NAME (decl))
1807 if (TREE_SYMBOL_REFERENCED (DECL_ASSEMBLER_NAME (decl))
1808 && DECL_RTL_SET_P (decl))
1809 warning (0, "%D renamed after being referenced in assembly", decl);
1811 SET_DECL_ASSEMBLER_NAME (decl, name);
1814 /* Add a top-level asm statement to the list. */
1816 struct cgraph_asm_node *
1817 cgraph_add_asm_node (tree asm_str)
1819 struct cgraph_asm_node *node;
1821 node = GGC_CNEW (struct cgraph_asm_node);
1822 node->asm_str = asm_str;
1823 node->order = cgraph_order++;
1825 if (cgraph_asm_nodes == NULL)
1826 cgraph_asm_nodes = node;
1828 cgraph_asm_last_node->next = node;
1829 cgraph_asm_last_node = node;
1833 /* Return true when the DECL can possibly be inlined. */
1835 cgraph_function_possibly_inlined_p (tree decl)
1837 if (!cgraph_global_info_ready)
1838 return !DECL_UNINLINABLE (decl);
1839 return DECL_POSSIBLY_INLINED (decl);
1842 /* Create clone of E in the node N represented by CALL_EXPR the callgraph. */
1843 struct cgraph_edge *
1844 cgraph_clone_edge (struct cgraph_edge *e, struct cgraph_node *n,
1845 gimple call_stmt, unsigned stmt_uid, gcov_type count_scale,
1846 int freq_scale, int loop_nest, bool update_original)
1848 struct cgraph_edge *new_edge;
1849 gcov_type count = e->count * count_scale / REG_BR_PROB_BASE;
1852 /* We do not want to ignore loop nest after frequency drops to 0. */
1855 freq = e->frequency * (gcov_type) freq_scale / CGRAPH_FREQ_BASE;
1856 if (freq > CGRAPH_FREQ_MAX)
1857 freq = CGRAPH_FREQ_MAX;
1858 new_edge = cgraph_create_edge (n, e->callee, call_stmt, count, freq,
1859 e->loop_nest + loop_nest);
1861 new_edge->inline_failed = e->inline_failed;
1862 new_edge->indirect_call = e->indirect_call;
1863 new_edge->lto_stmt_uid = stmt_uid;
1864 if (update_original)
1866 e->count -= new_edge->count;
1870 cgraph_call_edge_duplication_hooks (e, new_edge);
1874 /* Create node representing clone of N executed COUNT times. Decrease
1875 the execution counts from original node too.
1877 When UPDATE_ORIGINAL is true, the counts are subtracted from the original
1878 function's profile to reflect the fact that part of execution is handled
1880 struct cgraph_node *
1881 cgraph_clone_node (struct cgraph_node *n, gcov_type count, int freq,
1882 int loop_nest, bool update_original,
1883 VEC(cgraph_edge_p,heap) *redirect_callers)
1885 struct cgraph_node *new_node = cgraph_create_node ();
1886 struct cgraph_edge *e;
1887 gcov_type count_scale;
1890 new_node->decl = n->decl;
1891 new_node->origin = n->origin;
1892 if (new_node->origin)
1894 new_node->next_nested = new_node->origin->nested;
1895 new_node->origin->nested = new_node;
1897 new_node->analyzed = n->analyzed;
1898 new_node->local = n->local;
1899 new_node->local.externally_visible = false;
1900 new_node->global = n->global;
1901 new_node->rtl = n->rtl;
1902 new_node->count = count;
1903 new_node->frequency = n->frequency;
1904 new_node->clone = n->clone;
1905 new_node->clone.tree_map = 0;
1908 if (new_node->count > n->count)
1909 count_scale = REG_BR_PROB_BASE;
1911 count_scale = new_node->count * REG_BR_PROB_BASE / n->count;
1915 if (update_original)
1922 for (i = 0; VEC_iterate (cgraph_edge_p, redirect_callers, i, e); i++)
1924 /* Redirect calls to the old version node to point to its new
1926 cgraph_redirect_edge_callee (e, new_node);
1930 for (e = n->callees;e; e=e->next_callee)
1931 cgraph_clone_edge (e, new_node, e->call_stmt, e->lto_stmt_uid,
1932 count_scale, freq, loop_nest, update_original);
1934 new_node->next_sibling_clone = n->clones;
1936 n->clones->prev_sibling_clone = new_node;
1937 n->clones = new_node;
1938 new_node->clone_of = n;
1940 cgraph_call_node_duplication_hooks (n, new_node);
1944 /* Create a new name for omp child function. Returns an identifier. */
1946 static GTY(()) unsigned int clone_fn_id_num;
1949 clone_function_name (tree decl)
1951 tree name = DECL_ASSEMBLER_NAME (decl);
1952 size_t len = IDENTIFIER_LENGTH (name);
1953 char *tmp_name, *prefix;
1955 prefix = XALLOCAVEC (char, len + strlen ("_clone") + 1);
1956 memcpy (prefix, IDENTIFIER_POINTER (name), len);
1957 strcpy (prefix + len, "_clone");
1958 #ifndef NO_DOT_IN_LABEL
1960 #elif !defined NO_DOLLAR_IN_LABEL
1963 ASM_FORMAT_PRIVATE_NAME (tmp_name, prefix, clone_fn_id_num++);
1964 return get_identifier (tmp_name);
1967 /* Create callgraph node clone with new declaration. The actual body will
1968 be copied later at compilation stage.
1970 TODO: after merging in ipa-sra use function call notes instead of args_to_skip
1973 struct cgraph_node *
1974 cgraph_create_virtual_clone (struct cgraph_node *old_node,
1975 VEC(cgraph_edge_p,heap) *redirect_callers,
1976 VEC(ipa_replace_map_p,gc) *tree_map,
1977 bitmap args_to_skip)
1979 tree old_decl = old_node->decl;
1980 struct cgraph_node *new_node = NULL;
1982 struct cgraph_node key, **slot;
1984 gcc_assert (tree_versionable_function_p (old_decl));
1986 /* Make a new FUNCTION_DECL tree node */
1988 new_decl = copy_node (old_decl);
1990 new_decl = build_function_decl_skip_args (old_decl, args_to_skip);
1991 DECL_STRUCT_FUNCTION (new_decl) = NULL;
1993 /* Generate a new name for the new version. */
1994 DECL_NAME (new_decl) = clone_function_name (old_decl);
1995 SET_DECL_ASSEMBLER_NAME (new_decl, DECL_NAME (new_decl));
1996 SET_DECL_RTL (new_decl, NULL);
1998 new_node = cgraph_clone_node (old_node, old_node->count,
1999 CGRAPH_FREQ_BASE, 0, false,
2001 new_node->decl = new_decl;
2002 /* Update the properties.
2003 Make clone visible only within this translation unit. Make sure
2004 that is not weak also.
2005 ??? We cannot use COMDAT linkage because there is no
2006 ABI support for this. */
2007 DECL_EXTERNAL (new_node->decl) = 0;
2008 DECL_COMDAT_GROUP (new_node->decl) = 0;
2009 TREE_PUBLIC (new_node->decl) = 0;
2010 DECL_COMDAT (new_node->decl) = 0;
2011 DECL_WEAK (new_node->decl) = 0;
2012 new_node->clone.tree_map = tree_map;
2013 new_node->clone.args_to_skip = args_to_skip;
2015 new_node->clone.combined_args_to_skip = old_node->clone.combined_args_to_skip;
2016 else if (old_node->clone.combined_args_to_skip)
2018 int newi = 0, oldi = 0;
2020 bitmap new_args_to_skip = BITMAP_GGC_ALLOC ();
2021 struct cgraph_node *orig_node;
2022 for (orig_node = old_node; orig_node->clone_of; orig_node = orig_node->clone_of)
2024 for (arg = DECL_ARGUMENTS (orig_node->decl); arg; arg = TREE_CHAIN (arg), oldi++)
2026 if (bitmap_bit_p (old_node->clone.combined_args_to_skip, oldi))
2028 bitmap_set_bit (new_args_to_skip, oldi);
2031 if (bitmap_bit_p (args_to_skip, newi))
2032 bitmap_set_bit (new_args_to_skip, oldi);
2035 new_node->clone.combined_args_to_skip = new_args_to_skip;
2038 new_node->clone.combined_args_to_skip = args_to_skip;
2039 new_node->local.externally_visible = 0;
2040 new_node->local.local = 1;
2041 new_node->lowered = true;
2042 new_node->reachable = true;
2044 key.decl = new_decl;
2045 slot = (struct cgraph_node **) htab_find_slot (cgraph_hash, &key, INSERT);
2046 gcc_assert (!*slot);
2048 if (assembler_name_hash)
2051 tree name = DECL_ASSEMBLER_NAME (new_decl);
2053 aslot = htab_find_slot_with_hash (assembler_name_hash, name,
2054 decl_assembler_name_hash (name),
2056 gcc_assert (!*aslot);
2063 /* NODE is no longer nested function; update cgraph accordingly. */
2065 cgraph_unnest_node (struct cgraph_node *node)
2067 struct cgraph_node **node2 = &node->origin->nested;
2068 gcc_assert (node->origin);
2070 while (*node2 != node)
2071 node2 = &(*node2)->next_nested;
2072 *node2 = node->next_nested;
2073 node->origin = NULL;
2076 /* Return function availability. See cgraph.h for description of individual
2079 cgraph_function_body_availability (struct cgraph_node *node)
2081 enum availability avail;
2082 gcc_assert (cgraph_function_flags_ready);
2083 if (!node->analyzed)
2084 avail = AVAIL_NOT_AVAILABLE;
2085 else if (node->local.local)
2086 avail = AVAIL_LOCAL;
2087 else if (!node->local.externally_visible)
2088 avail = AVAIL_AVAILABLE;
2089 /* Inline functions are safe to be analyzed even if their sybol can
2090 be overwritten at runtime. It is not meaningful to enfore any sane
2091 behaviour on replacing inline function by different body. */
2092 else if (DECL_DECLARED_INLINE_P (node->decl))
2093 avail = AVAIL_AVAILABLE;
2095 /* If the function can be overwritten, return OVERWRITABLE. Take
2096 care at least of two notable extensions - the COMDAT functions
2097 used to share template instantiations in C++ (this is symmetric
2098 to code cp_cannot_inline_tree_fn and probably shall be shared and
2099 the inlinability hooks completely eliminated).
2101 ??? Does the C++ one definition rule allow us to always return
2102 AVAIL_AVAILABLE here? That would be good reason to preserve this
2105 else if (DECL_REPLACEABLE_P (node->decl) && !DECL_EXTERNAL (node->decl))
2106 avail = AVAIL_OVERWRITABLE;
2107 else avail = AVAIL_AVAILABLE;
2112 /* Add the function FNDECL to the call graph.
2113 Unlike cgraph_finalize_function, this function is intended to be used
2114 by middle end and allows insertion of new function at arbitrary point
2115 of compilation. The function can be either in high, low or SSA form
2118 The function is assumed to be reachable and have address taken (so no
2119 API breaking optimizations are performed on it).
2121 Main work done by this function is to enqueue the function for later
2122 processing to avoid need the passes to be re-entrant. */
2125 cgraph_add_new_function (tree fndecl, bool lowered)
2127 struct cgraph_node *node;
2128 switch (cgraph_state)
2130 case CGRAPH_STATE_CONSTRUCTION:
2131 /* Just enqueue function to be processed at nearest occurrence. */
2132 node = cgraph_node (fndecl);
2133 node->next_needed = cgraph_new_nodes;
2135 node->lowered = true;
2136 cgraph_new_nodes = node;
2139 case CGRAPH_STATE_IPA:
2140 case CGRAPH_STATE_IPA_SSA:
2141 case CGRAPH_STATE_EXPANSION:
2142 /* Bring the function into finalized state and enqueue for later
2143 analyzing and compilation. */
2144 node = cgraph_node (fndecl);
2145 node->local.local = false;
2146 node->local.finalized = true;
2147 node->reachable = node->needed = true;
2148 if (!lowered && cgraph_state == CGRAPH_STATE_EXPANSION)
2150 push_cfun (DECL_STRUCT_FUNCTION (fndecl));
2151 current_function_decl = fndecl;
2152 gimple_register_cfg_hooks ();
2153 tree_lowering_passes (fndecl);
2154 bitmap_obstack_initialize (NULL);
2155 if (!gimple_in_ssa_p (DECL_STRUCT_FUNCTION (fndecl)))
2156 execute_pass_list (pass_early_local_passes.pass.sub);
2157 bitmap_obstack_release (NULL);
2159 current_function_decl = NULL;
2164 node->lowered = true;
2165 node->next_needed = cgraph_new_nodes;
2166 cgraph_new_nodes = node;
2169 case CGRAPH_STATE_FINISHED:
2170 /* At the very end of compilation we have to do all the work up
2172 push_cfun (DECL_STRUCT_FUNCTION (fndecl));
2173 current_function_decl = fndecl;
2174 gimple_register_cfg_hooks ();
2176 tree_lowering_passes (fndecl);
2177 bitmap_obstack_initialize (NULL);
2178 if (!gimple_in_ssa_p (DECL_STRUCT_FUNCTION (fndecl)))
2179 execute_pass_list (pass_early_local_passes.pass.sub);
2180 bitmap_obstack_release (NULL);
2181 tree_rest_of_compilation (fndecl);
2183 current_function_decl = NULL;
2187 /* Set a personality if required and we already passed EH lowering. */
2189 && (function_needs_eh_personality (DECL_STRUCT_FUNCTION (fndecl))
2190 == eh_personality_lang))
2191 DECL_FUNCTION_PERSONALITY (fndecl) = lang_hooks.eh_personality ();
2194 /* Return true if NODE can be made local for API change.
2195 Extern inline functions and C++ COMDAT functions can be made local
2196 at the expense of possible code size growth if function is used in multiple
2197 compilation units. */
2199 cgraph_node_can_be_local_p (struct cgraph_node *node)
2201 return (!node->needed
2202 && ((DECL_COMDAT (node->decl) && !node->same_comdat_group)
2203 || !node->local.externally_visible));
2206 /* Make DECL local. FIXME: We shouldn't need to mess with rtl this early,
2207 but other code such as notice_global_symbol generates rtl. */
2209 cgraph_make_decl_local (tree decl)
2213 if (TREE_CODE (decl) == VAR_DECL)
2214 DECL_COMMON (decl) = 0;
2215 else if (TREE_CODE (decl) == FUNCTION_DECL)
2217 DECL_COMDAT (decl) = 0;
2218 DECL_COMDAT_GROUP (decl) = 0;
2219 DECL_WEAK (decl) = 0;
2220 DECL_EXTERNAL (decl) = 0;
2224 TREE_PUBLIC (decl) = 0;
2225 if (!DECL_RTL_SET_P (decl))
2228 /* Update rtl flags. */
2229 make_decl_rtl (decl);
2231 rtl = DECL_RTL (decl);
2235 symbol = XEXP (rtl, 0);
2236 if (GET_CODE (symbol) != SYMBOL_REF)
2239 SYMBOL_REF_WEAK (symbol) = DECL_WEAK (decl);
2242 /* Bring NODE local. */
2244 cgraph_make_node_local (struct cgraph_node *node)
2246 gcc_assert (cgraph_node_can_be_local_p (node));
2247 if (DECL_COMDAT (node->decl) || DECL_EXTERNAL (node->decl))
2249 struct cgraph_node *alias;
2250 cgraph_make_decl_local (node->decl);
2252 for (alias = node->same_body; alias; alias = alias->next)
2253 cgraph_make_decl_local (alias->decl);
2255 node->local.externally_visible = false;
2256 node->local.local = true;
2257 gcc_assert (cgraph_function_body_availability (node) == AVAIL_LOCAL);
2261 /* Set TREE_NOTHROW on NODE's decl and on same_body aliases of NODE
2262 if any to NOTHROW. */
2265 cgraph_set_nothrow_flag (struct cgraph_node *node, bool nothrow)
2267 struct cgraph_node *alias;
2268 TREE_NOTHROW (node->decl) = nothrow;
2269 for (alias = node->same_body; alias; alias = alias->next)
2270 TREE_NOTHROW (alias->decl) = nothrow;
2273 /* Set TREE_READONLY on NODE's decl and on same_body aliases of NODE
2274 if any to READONLY. */
2277 cgraph_set_readonly_flag (struct cgraph_node *node, bool readonly)
2279 struct cgraph_node *alias;
2280 TREE_READONLY (node->decl) = readonly;
2281 for (alias = node->same_body; alias; alias = alias->next)
2282 TREE_READONLY (alias->decl) = readonly;
2285 /* Set DECL_PURE_P on NODE's decl and on same_body aliases of NODE
2289 cgraph_set_pure_flag (struct cgraph_node *node, bool pure)
2291 struct cgraph_node *alias;
2292 DECL_PURE_P (node->decl) = pure;
2293 for (alias = node->same_body; alias; alias = alias->next)
2294 DECL_PURE_P (alias->decl) = pure;
2297 /* Set DECL_LOOPING_CONST_OR_PURE_P on NODE's decl and on
2298 same_body aliases of NODE if any to LOOPING_CONST_OR_PURE. */
2301 cgraph_set_looping_const_or_pure_flag (struct cgraph_node *node,
2302 bool looping_const_or_pure)
2304 struct cgraph_node *alias;
2305 DECL_LOOPING_CONST_OR_PURE_P (node->decl) = looping_const_or_pure;
2306 for (alias = node->same_body; alias; alias = alias->next)
2307 DECL_LOOPING_CONST_OR_PURE_P (alias->decl) = looping_const_or_pure;
2310 #include "gt-cgraph.h"