* gcc.dg/torture/tls/tls-reload-1.c: Add tls options.
[official-gcc.git] / gcc / cgraph.c
blob444b4f0e957c2df78cae4ba1fb45e911a06b3d4f
1 /* Callgraph handling code.
2 Copyright (C) 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010,
3 2011, 2012 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
11 version.
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
16 for more details.
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
24 The call-graph is a data structure designed for intra-procedural optimization.
25 It represents a multi-graph where nodes are functions and edges are call sites. */
27 #include "config.h"
28 #include "system.h"
29 #include "coretypes.h"
30 #include "tm.h"
31 #include "tree.h"
32 #include "tree-inline.h"
33 #include "langhooks.h"
34 #include "hashtab.h"
35 #include "toplev.h"
36 #include "flags.h"
37 #include "ggc.h"
38 #include "debug.h"
39 #include "target.h"
40 #include "basic-block.h"
41 #include "cgraph.h"
42 #include "intl.h"
43 #include "gimple.h"
44 #include "timevar.h"
45 #include "dumpfile.h"
46 #include "tree-flow.h"
47 #include "value-prof.h"
48 #include "except.h"
49 #include "diagnostic-core.h"
50 #include "rtl.h"
51 #include "ipa-utils.h"
52 #include "lto-streamer.h"
53 #include "ipa-inline.h"
54 #include "cfgloop.h"
55 #include "gimple-pretty-print.h"
57 /* FIXME: Only for PROP_loops, but cgraph shouldn't have to know about this. */
58 #include "tree-pass.h"
60 static void cgraph_node_remove_callers (struct cgraph_node *node);
61 static inline void cgraph_edge_remove_caller (struct cgraph_edge *e);
62 static inline void cgraph_edge_remove_callee (struct cgraph_edge *e);
64 /* Queue of cgraph nodes scheduled to be lowered. */
65 symtab_node x_cgraph_nodes_queue;
66 #define cgraph_nodes_queue ((struct cgraph_node *)x_cgraph_nodes_queue)
68 /* Number of nodes in existence. */
69 int cgraph_n_nodes;
71 /* Maximal uid used in cgraph nodes. */
72 int cgraph_max_uid;
74 /* Maximal uid used in cgraph edges. */
75 int cgraph_edge_max_uid;
77 /* Set when whole unit has been analyzed so we can access global info. */
78 bool cgraph_global_info_ready = false;
80 /* What state callgraph is in right now. */
81 enum cgraph_state cgraph_state = CGRAPH_STATE_PARSING;
83 /* Set when the cgraph is fully build and the basic flags are computed. */
84 bool cgraph_function_flags_ready = false;
86 /* List of hooks triggered on cgraph_edge events. */
87 struct cgraph_edge_hook_list {
88 cgraph_edge_hook hook;
89 void *data;
90 struct cgraph_edge_hook_list *next;
93 /* List of hooks triggered on cgraph_node events. */
94 struct cgraph_node_hook_list {
95 cgraph_node_hook hook;
96 void *data;
97 struct cgraph_node_hook_list *next;
100 /* List of hooks triggered on events involving two cgraph_edges. */
101 struct cgraph_2edge_hook_list {
102 cgraph_2edge_hook hook;
103 void *data;
104 struct cgraph_2edge_hook_list *next;
107 /* List of hooks triggered on events involving two cgraph_nodes. */
108 struct cgraph_2node_hook_list {
109 cgraph_2node_hook hook;
110 void *data;
111 struct cgraph_2node_hook_list *next;
114 /* List of hooks triggered when an edge is removed. */
115 struct cgraph_edge_hook_list *first_cgraph_edge_removal_hook;
116 /* List of hooks triggered when a node is removed. */
117 struct cgraph_node_hook_list *first_cgraph_node_removal_hook;
118 /* List of hooks triggered when an edge is duplicated. */
119 struct cgraph_2edge_hook_list *first_cgraph_edge_duplicated_hook;
120 /* List of hooks triggered when a node is duplicated. */
121 struct cgraph_2node_hook_list *first_cgraph_node_duplicated_hook;
122 /* List of hooks triggered when an function is inserted. */
123 struct cgraph_node_hook_list *first_cgraph_function_insertion_hook;
125 /* Head of a linked list of unused (freed) call graph nodes.
126 Do not GTY((delete)) this list so UIDs gets reliably recycled. */
127 static GTY(()) struct cgraph_node *free_nodes;
128 /* Head of a linked list of unused (freed) call graph edges.
129 Do not GTY((delete)) this list so UIDs gets reliably recycled. */
130 static GTY(()) struct cgraph_edge *free_edges;
132 /* Did procss_same_body_aliases run? */
133 bool same_body_aliases_done;
135 /* Map a cgraph_node to cgraph_function_version_info using this htab.
136 The cgraph_function_version_info has a THIS_NODE field that is the
137 corresponding cgraph_node.. */
139 static htab_t GTY((param_is (struct cgraph_function_version_info *)))
140 cgraph_fnver_htab = NULL;
142 /* Hash function for cgraph_fnver_htab. */
143 static hashval_t
144 cgraph_fnver_htab_hash (const void *ptr)
146 int uid = ((const struct cgraph_function_version_info *)ptr)->this_node->uid;
147 return (hashval_t)(uid);
150 /* eq function for cgraph_fnver_htab. */
151 static int
152 cgraph_fnver_htab_eq (const void *p1, const void *p2)
154 const struct cgraph_function_version_info *n1
155 = (const struct cgraph_function_version_info *)p1;
156 const struct cgraph_function_version_info *n2
157 = (const struct cgraph_function_version_info *)p2;
159 return n1->this_node->uid == n2->this_node->uid;
162 /* Mark as GC root all allocated nodes. */
163 static GTY(()) struct cgraph_function_version_info *
164 version_info_node = NULL;
166 /* Get the cgraph_function_version_info node corresponding to node. */
167 struct cgraph_function_version_info *
168 get_cgraph_node_version (struct cgraph_node *node)
170 struct cgraph_function_version_info *ret;
171 struct cgraph_function_version_info key;
172 key.this_node = node;
174 if (cgraph_fnver_htab == NULL)
175 return NULL;
177 ret = (struct cgraph_function_version_info *)
178 htab_find (cgraph_fnver_htab, &key);
180 return ret;
183 /* Insert a new cgraph_function_version_info node into cgraph_fnver_htab
184 corresponding to cgraph_node NODE. */
185 struct cgraph_function_version_info *
186 insert_new_cgraph_node_version (struct cgraph_node *node)
188 void **slot;
190 version_info_node = NULL;
191 version_info_node = ggc_alloc_cleared_cgraph_function_version_info ();
192 version_info_node->this_node = node;
194 if (cgraph_fnver_htab == NULL)
195 cgraph_fnver_htab = htab_create_ggc (2, cgraph_fnver_htab_hash,
196 cgraph_fnver_htab_eq, NULL);
198 slot = htab_find_slot (cgraph_fnver_htab, version_info_node, INSERT);
199 gcc_assert (slot != NULL);
200 *slot = version_info_node;
201 return version_info_node;
204 /* Remove the cgraph_function_version_info and cgraph_node for DECL. This
205 DECL is a duplicate declaration. */
206 void
207 delete_function_version (tree decl)
209 struct cgraph_node *decl_node = cgraph_get_node (decl);
210 struct cgraph_function_version_info *decl_v = NULL;
212 if (decl_node == NULL)
213 return;
215 decl_v = get_cgraph_node_version (decl_node);
217 if (decl_v == NULL)
218 return;
220 if (decl_v->prev != NULL)
221 decl_v->prev->next = decl_v->next;
223 if (decl_v->next != NULL)
224 decl_v->next->prev = decl_v->prev;
226 if (cgraph_fnver_htab != NULL)
227 htab_remove_elt (cgraph_fnver_htab, decl_v);
229 cgraph_remove_node (decl_node);
232 /* Record that DECL1 and DECL2 are semantically identical function
233 versions. */
234 void
235 record_function_versions (tree decl1, tree decl2)
237 struct cgraph_node *decl1_node = cgraph_get_create_node (decl1);
238 struct cgraph_node *decl2_node = cgraph_get_create_node (decl2);
239 struct cgraph_function_version_info *decl1_v = NULL;
240 struct cgraph_function_version_info *decl2_v = NULL;
241 struct cgraph_function_version_info *before;
242 struct cgraph_function_version_info *after;
244 gcc_assert (decl1_node != NULL && decl2_node != NULL);
245 decl1_v = get_cgraph_node_version (decl1_node);
246 decl2_v = get_cgraph_node_version (decl2_node);
248 if (decl1_v != NULL && decl2_v != NULL)
249 return;
251 if (decl1_v == NULL)
252 decl1_v = insert_new_cgraph_node_version (decl1_node);
254 if (decl2_v == NULL)
255 decl2_v = insert_new_cgraph_node_version (decl2_node);
257 /* Chain decl2_v and decl1_v. All semantically identical versions
258 will be chained together. */
260 before = decl1_v;
261 after = decl2_v;
263 while (before->next != NULL)
264 before = before->next;
266 while (after->prev != NULL)
267 after= after->prev;
269 before->next = after;
270 after->prev = before;
273 /* Macros to access the next item in the list of free cgraph nodes and
274 edges. */
275 #define NEXT_FREE_NODE(NODE) cgraph ((NODE)->symbol.next)
276 #define SET_NEXT_FREE_NODE(NODE,NODE2) ((NODE))->symbol.next = (symtab_node)NODE2
277 #define NEXT_FREE_EDGE(EDGE) (EDGE)->prev_caller
279 /* Register HOOK to be called with DATA on each removed edge. */
280 struct cgraph_edge_hook_list *
281 cgraph_add_edge_removal_hook (cgraph_edge_hook hook, void *data)
283 struct cgraph_edge_hook_list *entry;
284 struct cgraph_edge_hook_list **ptr = &first_cgraph_edge_removal_hook;
286 entry = (struct cgraph_edge_hook_list *) xmalloc (sizeof (*entry));
287 entry->hook = hook;
288 entry->data = data;
289 entry->next = NULL;
290 while (*ptr)
291 ptr = &(*ptr)->next;
292 *ptr = entry;
293 return entry;
296 /* Remove ENTRY from the list of hooks called on removing edges. */
297 void
298 cgraph_remove_edge_removal_hook (struct cgraph_edge_hook_list *entry)
300 struct cgraph_edge_hook_list **ptr = &first_cgraph_edge_removal_hook;
302 while (*ptr != entry)
303 ptr = &(*ptr)->next;
304 *ptr = entry->next;
305 free (entry);
308 /* Call all edge removal hooks. */
309 static void
310 cgraph_call_edge_removal_hooks (struct cgraph_edge *e)
312 struct cgraph_edge_hook_list *entry = first_cgraph_edge_removal_hook;
313 while (entry)
315 entry->hook (e, entry->data);
316 entry = entry->next;
320 /* Register HOOK to be called with DATA on each removed node. */
321 struct cgraph_node_hook_list *
322 cgraph_add_node_removal_hook (cgraph_node_hook hook, void *data)
324 struct cgraph_node_hook_list *entry;
325 struct cgraph_node_hook_list **ptr = &first_cgraph_node_removal_hook;
327 entry = (struct cgraph_node_hook_list *) xmalloc (sizeof (*entry));
328 entry->hook = hook;
329 entry->data = data;
330 entry->next = NULL;
331 while (*ptr)
332 ptr = &(*ptr)->next;
333 *ptr = entry;
334 return entry;
337 /* Remove ENTRY from the list of hooks called on removing nodes. */
338 void
339 cgraph_remove_node_removal_hook (struct cgraph_node_hook_list *entry)
341 struct cgraph_node_hook_list **ptr = &first_cgraph_node_removal_hook;
343 while (*ptr != entry)
344 ptr = &(*ptr)->next;
345 *ptr = entry->next;
346 free (entry);
349 /* Call all node removal hooks. */
350 static void
351 cgraph_call_node_removal_hooks (struct cgraph_node *node)
353 struct cgraph_node_hook_list *entry = first_cgraph_node_removal_hook;
354 while (entry)
356 entry->hook (node, entry->data);
357 entry = entry->next;
361 /* Register HOOK to be called with DATA on each inserted node. */
362 struct cgraph_node_hook_list *
363 cgraph_add_function_insertion_hook (cgraph_node_hook hook, void *data)
365 struct cgraph_node_hook_list *entry;
366 struct cgraph_node_hook_list **ptr = &first_cgraph_function_insertion_hook;
368 entry = (struct cgraph_node_hook_list *) xmalloc (sizeof (*entry));
369 entry->hook = hook;
370 entry->data = data;
371 entry->next = NULL;
372 while (*ptr)
373 ptr = &(*ptr)->next;
374 *ptr = entry;
375 return entry;
378 /* Remove ENTRY from the list of hooks called on inserted nodes. */
379 void
380 cgraph_remove_function_insertion_hook (struct cgraph_node_hook_list *entry)
382 struct cgraph_node_hook_list **ptr = &first_cgraph_function_insertion_hook;
384 while (*ptr != entry)
385 ptr = &(*ptr)->next;
386 *ptr = entry->next;
387 free (entry);
390 /* Call all node insertion hooks. */
391 void
392 cgraph_call_function_insertion_hooks (struct cgraph_node *node)
394 struct cgraph_node_hook_list *entry = first_cgraph_function_insertion_hook;
395 while (entry)
397 entry->hook (node, entry->data);
398 entry = entry->next;
402 /* Register HOOK to be called with DATA on each duplicated edge. */
403 struct cgraph_2edge_hook_list *
404 cgraph_add_edge_duplication_hook (cgraph_2edge_hook hook, void *data)
406 struct cgraph_2edge_hook_list *entry;
407 struct cgraph_2edge_hook_list **ptr = &first_cgraph_edge_duplicated_hook;
409 entry = (struct cgraph_2edge_hook_list *) xmalloc (sizeof (*entry));
410 entry->hook = hook;
411 entry->data = data;
412 entry->next = NULL;
413 while (*ptr)
414 ptr = &(*ptr)->next;
415 *ptr = entry;
416 return entry;
419 /* Remove ENTRY from the list of hooks called on duplicating edges. */
420 void
421 cgraph_remove_edge_duplication_hook (struct cgraph_2edge_hook_list *entry)
423 struct cgraph_2edge_hook_list **ptr = &first_cgraph_edge_duplicated_hook;
425 while (*ptr != entry)
426 ptr = &(*ptr)->next;
427 *ptr = entry->next;
428 free (entry);
431 /* Call all edge duplication hooks. */
432 void
433 cgraph_call_edge_duplication_hooks (struct cgraph_edge *cs1,
434 struct cgraph_edge *cs2)
436 struct cgraph_2edge_hook_list *entry = first_cgraph_edge_duplicated_hook;
437 while (entry)
439 entry->hook (cs1, cs2, entry->data);
440 entry = entry->next;
444 /* Register HOOK to be called with DATA on each duplicated node. */
445 struct cgraph_2node_hook_list *
446 cgraph_add_node_duplication_hook (cgraph_2node_hook hook, void *data)
448 struct cgraph_2node_hook_list *entry;
449 struct cgraph_2node_hook_list **ptr = &first_cgraph_node_duplicated_hook;
451 entry = (struct cgraph_2node_hook_list *) xmalloc (sizeof (*entry));
452 entry->hook = hook;
453 entry->data = data;
454 entry->next = NULL;
455 while (*ptr)
456 ptr = &(*ptr)->next;
457 *ptr = entry;
458 return entry;
461 /* Remove ENTRY from the list of hooks called on duplicating nodes. */
462 void
463 cgraph_remove_node_duplication_hook (struct cgraph_2node_hook_list *entry)
465 struct cgraph_2node_hook_list **ptr = &first_cgraph_node_duplicated_hook;
467 while (*ptr != entry)
468 ptr = &(*ptr)->next;
469 *ptr = entry->next;
470 free (entry);
473 /* Call all node duplication hooks. */
474 void
475 cgraph_call_node_duplication_hooks (struct cgraph_node *node1,
476 struct cgraph_node *node2)
478 struct cgraph_2node_hook_list *entry = first_cgraph_node_duplicated_hook;
479 while (entry)
481 entry->hook (node1, node2, entry->data);
482 entry = entry->next;
486 /* Allocate new callgraph node. */
488 static inline struct cgraph_node *
489 cgraph_allocate_node (void)
491 struct cgraph_node *node;
493 if (free_nodes)
495 node = free_nodes;
496 free_nodes = NEXT_FREE_NODE (node);
498 else
500 node = ggc_alloc_cleared_cgraph_node ();
501 node->uid = cgraph_max_uid++;
504 return node;
507 /* Allocate new callgraph node and insert it into basic data structures. */
509 struct cgraph_node *
510 cgraph_create_empty_node (void)
512 struct cgraph_node *node = cgraph_allocate_node ();
514 node->symbol.type = SYMTAB_FUNCTION;
515 node->frequency = NODE_FREQUENCY_NORMAL;
516 node->count_materialization_scale = REG_BR_PROB_BASE;
517 cgraph_n_nodes++;
518 return node;
521 /* Return cgraph node assigned to DECL. Create new one when needed. */
523 struct cgraph_node *
524 cgraph_create_node (tree decl)
526 struct cgraph_node *node = cgraph_create_empty_node ();
527 gcc_assert (TREE_CODE (decl) == FUNCTION_DECL);
529 node->symbol.decl = decl;
530 symtab_register_node ((symtab_node) node);
532 if (DECL_CONTEXT (decl) && TREE_CODE (DECL_CONTEXT (decl)) == FUNCTION_DECL)
534 node->origin = cgraph_get_create_node (DECL_CONTEXT (decl));
535 node->next_nested = node->origin->nested;
536 node->origin->nested = node;
538 return node;
541 /* Try to find a call graph node for declaration DECL and if it does not exist,
542 create it. */
544 struct cgraph_node *
545 cgraph_get_create_node (tree decl)
547 struct cgraph_node *node;
549 node = cgraph_get_node (decl);
550 if (node)
551 return node;
553 return cgraph_create_node (decl);
556 /* Mark ALIAS as an alias to DECL. DECL_NODE is cgraph node representing
557 the function body is associated with (not necessarily cgraph_node (DECL). */
559 struct cgraph_node *
560 cgraph_create_function_alias (tree alias, tree decl)
562 struct cgraph_node *alias_node;
564 gcc_assert (TREE_CODE (decl) == FUNCTION_DECL);
565 gcc_assert (TREE_CODE (alias) == FUNCTION_DECL);
566 alias_node = cgraph_get_create_node (alias);
567 gcc_assert (!alias_node->local.finalized);
568 alias_node->thunk.alias = decl;
569 alias_node->local.finalized = true;
570 alias_node->alias = 1;
571 return alias_node;
574 /* Attempt to mark ALIAS as an alias to DECL. Return alias node if successful
575 and NULL otherwise.
576 Same body aliases are output whenever the body of DECL is output,
577 and cgraph_get_node (ALIAS) transparently returns cgraph_get_node (DECL). */
579 struct cgraph_node *
580 cgraph_same_body_alias (struct cgraph_node *decl_node ATTRIBUTE_UNUSED, tree alias, tree decl)
582 struct cgraph_node *n;
583 #ifndef ASM_OUTPUT_DEF
584 /* If aliases aren't supported by the assembler, fail. */
585 return NULL;
586 #endif
587 /* Langhooks can create same body aliases of symbols not defined.
588 Those are useless. Drop them on the floor. */
589 if (cgraph_global_info_ready)
590 return NULL;
592 n = cgraph_create_function_alias (alias, decl);
593 n->same_body_alias = true;
594 if (same_body_aliases_done)
595 ipa_record_reference ((symtab_node)n, (symtab_node)cgraph_get_node (decl),
596 IPA_REF_ALIAS, NULL);
597 return n;
600 /* Add thunk alias into callgraph. The alias declaration is ALIAS and it
601 aliases DECL with an adjustments made into the first parameter.
602 See comments in thunk_adjust for detail on the parameters. */
604 struct cgraph_node *
605 cgraph_add_thunk (struct cgraph_node *decl_node ATTRIBUTE_UNUSED,
606 tree alias, tree decl ATTRIBUTE_UNUSED,
607 bool this_adjusting,
608 HOST_WIDE_INT fixed_offset, HOST_WIDE_INT virtual_value,
609 tree virtual_offset,
610 tree real_alias)
612 struct cgraph_node *node;
614 node = cgraph_get_node (alias);
615 if (node)
617 gcc_assert (node->local.finalized);
618 gcc_assert (!node->alias);
619 gcc_assert (!node->thunk.thunk_p);
620 cgraph_remove_node (node);
623 node = cgraph_create_node (alias);
624 gcc_checking_assert (!virtual_offset
625 || tree_to_double_int (virtual_offset) ==
626 double_int::from_shwi (virtual_value));
627 node->thunk.fixed_offset = fixed_offset;
628 node->thunk.this_adjusting = this_adjusting;
629 node->thunk.virtual_value = virtual_value;
630 node->thunk.virtual_offset_p = virtual_offset != NULL;
631 node->thunk.alias = real_alias;
632 node->thunk.thunk_p = true;
633 node->local.finalized = true;
635 return node;
638 /* Return the cgraph node that has ASMNAME for its DECL_ASSEMBLER_NAME.
639 Return NULL if there's no such node. */
641 struct cgraph_node *
642 cgraph_node_for_asm (tree asmname)
644 /* We do not want to look at inline clones. */
645 for (symtab_node node = symtab_node_for_asm (asmname);
646 node;
647 node = node->symbol.next_sharing_asm_name)
649 cgraph_node *cn = dyn_cast <cgraph_node> (node);
650 if (cn && !cn->global.inlined_to)
651 return cn;
653 return NULL;
656 /* Returns a hash value for X (which really is a cgraph_edge). */
658 static hashval_t
659 edge_hash (const void *x)
661 return htab_hash_pointer (((const struct cgraph_edge *) x)->call_stmt);
664 /* Return nonzero if the call_stmt of of cgraph_edge X is stmt *Y. */
666 static int
667 edge_eq (const void *x, const void *y)
669 return ((const struct cgraph_edge *) x)->call_stmt == y;
672 /* Add call graph edge E to call site hash of its caller. */
674 static inline void
675 cgraph_add_edge_to_call_site_hash (struct cgraph_edge *e)
677 void **slot;
678 slot = htab_find_slot_with_hash (e->caller->call_site_hash,
679 e->call_stmt,
680 htab_hash_pointer (e->call_stmt),
681 INSERT);
682 gcc_assert (!*slot);
683 *slot = e;
686 /* Return the callgraph edge representing the GIMPLE_CALL statement
687 CALL_STMT. */
689 struct cgraph_edge *
690 cgraph_edge (struct cgraph_node *node, gimple call_stmt)
692 struct cgraph_edge *e, *e2;
693 int n = 0;
695 if (node->call_site_hash)
696 return (struct cgraph_edge *)
697 htab_find_with_hash (node->call_site_hash, call_stmt,
698 htab_hash_pointer (call_stmt));
700 /* This loop may turn out to be performance problem. In such case adding
701 hashtables into call nodes with very many edges is probably best
702 solution. It is not good idea to add pointer into CALL_EXPR itself
703 because we want to make possible having multiple cgraph nodes representing
704 different clones of the same body before the body is actually cloned. */
705 for (e = node->callees; e; e = e->next_callee)
707 if (e->call_stmt == call_stmt)
708 break;
709 n++;
712 if (!e)
713 for (e = node->indirect_calls; e; e = e->next_callee)
715 if (e->call_stmt == call_stmt)
716 break;
717 n++;
720 if (n > 100)
722 node->call_site_hash = htab_create_ggc (120, edge_hash, edge_eq, NULL);
723 for (e2 = node->callees; e2; e2 = e2->next_callee)
724 cgraph_add_edge_to_call_site_hash (e2);
725 for (e2 = node->indirect_calls; e2; e2 = e2->next_callee)
726 cgraph_add_edge_to_call_site_hash (e2);
729 return e;
733 /* Change field call_stmt of edge E to NEW_STMT. */
735 void
736 cgraph_set_call_stmt (struct cgraph_edge *e, gimple new_stmt)
738 tree decl;
740 if (e->caller->call_site_hash)
742 htab_remove_elt_with_hash (e->caller->call_site_hash,
743 e->call_stmt,
744 htab_hash_pointer (e->call_stmt));
747 e->call_stmt = new_stmt;
748 if (e->indirect_unknown_callee
749 && (decl = gimple_call_fndecl (new_stmt)))
751 /* Constant propagation (and possibly also inlining?) can turn an
752 indirect call into a direct one. */
753 struct cgraph_node *new_callee = cgraph_get_node (decl);
755 gcc_checking_assert (new_callee);
756 cgraph_make_edge_direct (e, new_callee);
759 push_cfun (DECL_STRUCT_FUNCTION (e->caller->symbol.decl));
760 e->can_throw_external = stmt_can_throw_external (new_stmt);
761 pop_cfun ();
762 if (e->caller->call_site_hash)
763 cgraph_add_edge_to_call_site_hash (e);
766 /* Allocate a cgraph_edge structure and fill it with data according to the
767 parameters of which only CALLEE can be NULL (when creating an indirect call
768 edge). */
770 static struct cgraph_edge *
771 cgraph_create_edge_1 (struct cgraph_node *caller, struct cgraph_node *callee,
772 gimple call_stmt, gcov_type count, int freq)
774 struct cgraph_edge *edge;
776 /* LTO does not actually have access to the call_stmt since these
777 have not been loaded yet. */
778 if (call_stmt)
780 /* This is a rather expensive check possibly triggering
781 construction of call stmt hashtable. */
782 gcc_checking_assert (!cgraph_edge (caller, call_stmt));
784 gcc_assert (is_gimple_call (call_stmt));
787 if (free_edges)
789 edge = free_edges;
790 free_edges = NEXT_FREE_EDGE (edge);
792 else
794 edge = ggc_alloc_cgraph_edge ();
795 edge->uid = cgraph_edge_max_uid++;
798 edge->aux = NULL;
799 edge->caller = caller;
800 edge->callee = callee;
801 edge->prev_caller = NULL;
802 edge->next_caller = NULL;
803 edge->prev_callee = NULL;
804 edge->next_callee = NULL;
806 edge->count = count;
807 gcc_assert (count >= 0);
808 edge->frequency = freq;
809 gcc_assert (freq >= 0);
810 gcc_assert (freq <= CGRAPH_FREQ_MAX);
812 edge->call_stmt = call_stmt;
813 push_cfun (DECL_STRUCT_FUNCTION (caller->symbol.decl));
814 edge->can_throw_external
815 = call_stmt ? stmt_can_throw_external (call_stmt) : false;
816 pop_cfun ();
817 if (call_stmt
818 && callee && callee->symbol.decl
819 && !gimple_check_call_matching_types (call_stmt, callee->symbol.decl))
820 edge->call_stmt_cannot_inline_p = true;
821 else
822 edge->call_stmt_cannot_inline_p = false;
823 if (call_stmt && caller->call_site_hash)
824 cgraph_add_edge_to_call_site_hash (edge);
826 edge->indirect_info = NULL;
827 edge->indirect_inlining_edge = 0;
829 return edge;
832 /* Create edge from CALLER to CALLEE in the cgraph. */
834 struct cgraph_edge *
835 cgraph_create_edge (struct cgraph_node *caller, struct cgraph_node *callee,
836 gimple call_stmt, gcov_type count, int freq)
838 struct cgraph_edge *edge = cgraph_create_edge_1 (caller, callee, call_stmt,
839 count, freq);
841 edge->indirect_unknown_callee = 0;
842 initialize_inline_failed (edge);
844 edge->next_caller = callee->callers;
845 if (callee->callers)
846 callee->callers->prev_caller = edge;
847 edge->next_callee = caller->callees;
848 if (caller->callees)
849 caller->callees->prev_callee = edge;
850 caller->callees = edge;
851 callee->callers = edge;
853 return edge;
856 /* Allocate cgraph_indirect_call_info and set its fields to default values. */
858 struct cgraph_indirect_call_info *
859 cgraph_allocate_init_indirect_info (void)
861 struct cgraph_indirect_call_info *ii;
863 ii = ggc_alloc_cleared_cgraph_indirect_call_info ();
864 ii->param_index = -1;
865 return ii;
868 /* Create an indirect edge with a yet-undetermined callee where the call
869 statement destination is a formal parameter of the caller with index
870 PARAM_INDEX. */
872 struct cgraph_edge *
873 cgraph_create_indirect_edge (struct cgraph_node *caller, gimple call_stmt,
874 int ecf_flags,
875 gcov_type count, int freq)
877 struct cgraph_edge *edge = cgraph_create_edge_1 (caller, NULL, call_stmt,
878 count, freq);
880 edge->indirect_unknown_callee = 1;
881 initialize_inline_failed (edge);
883 edge->indirect_info = cgraph_allocate_init_indirect_info ();
884 edge->indirect_info->ecf_flags = ecf_flags;
886 edge->next_callee = caller->indirect_calls;
887 if (caller->indirect_calls)
888 caller->indirect_calls->prev_callee = edge;
889 caller->indirect_calls = edge;
891 return edge;
894 /* Remove the edge E from the list of the callers of the callee. */
896 static inline void
897 cgraph_edge_remove_callee (struct cgraph_edge *e)
899 gcc_assert (!e->indirect_unknown_callee);
900 if (e->prev_caller)
901 e->prev_caller->next_caller = e->next_caller;
902 if (e->next_caller)
903 e->next_caller->prev_caller = e->prev_caller;
904 if (!e->prev_caller)
905 e->callee->callers = e->next_caller;
908 /* Remove the edge E from the list of the callees of the caller. */
910 static inline void
911 cgraph_edge_remove_caller (struct cgraph_edge *e)
913 if (e->prev_callee)
914 e->prev_callee->next_callee = e->next_callee;
915 if (e->next_callee)
916 e->next_callee->prev_callee = e->prev_callee;
917 if (!e->prev_callee)
919 if (e->indirect_unknown_callee)
920 e->caller->indirect_calls = e->next_callee;
921 else
922 e->caller->callees = e->next_callee;
924 if (e->caller->call_site_hash)
925 htab_remove_elt_with_hash (e->caller->call_site_hash,
926 e->call_stmt,
927 htab_hash_pointer (e->call_stmt));
930 /* Put the edge onto the free list. */
932 static void
933 cgraph_free_edge (struct cgraph_edge *e)
935 int uid = e->uid;
937 /* Clear out the edge so we do not dangle pointers. */
938 memset (e, 0, sizeof (*e));
939 e->uid = uid;
940 NEXT_FREE_EDGE (e) = free_edges;
941 free_edges = e;
944 /* Remove the edge E in the cgraph. */
946 void
947 cgraph_remove_edge (struct cgraph_edge *e)
949 /* Call all edge removal hooks. */
950 cgraph_call_edge_removal_hooks (e);
952 if (!e->indirect_unknown_callee)
953 /* Remove from callers list of the callee. */
954 cgraph_edge_remove_callee (e);
956 /* Remove from callees list of the callers. */
957 cgraph_edge_remove_caller (e);
959 /* Put the edge onto the free list. */
960 cgraph_free_edge (e);
963 /* Set callee of call graph edge E and add it to the corresponding set of
964 callers. */
966 static void
967 cgraph_set_edge_callee (struct cgraph_edge *e, struct cgraph_node *n)
969 e->prev_caller = NULL;
970 if (n->callers)
971 n->callers->prev_caller = e;
972 e->next_caller = n->callers;
973 n->callers = e;
974 e->callee = n;
977 /* Redirect callee of E to N. The function does not update underlying
978 call expression. */
980 void
981 cgraph_redirect_edge_callee (struct cgraph_edge *e, struct cgraph_node *n)
983 /* Remove from callers list of the current callee. */
984 cgraph_edge_remove_callee (e);
986 /* Insert to callers list of the new callee. */
987 cgraph_set_edge_callee (e, n);
990 /* Make an indirect EDGE with an unknown callee an ordinary edge leading to
991 CALLEE. DELTA is an integer constant that is to be added to the this
992 pointer (first parameter) to compensate for skipping a thunk adjustment. */
994 void
995 cgraph_make_edge_direct (struct cgraph_edge *edge, struct cgraph_node *callee)
997 edge->indirect_unknown_callee = 0;
999 /* Get the edge out of the indirect edge list. */
1000 if (edge->prev_callee)
1001 edge->prev_callee->next_callee = edge->next_callee;
1002 if (edge->next_callee)
1003 edge->next_callee->prev_callee = edge->prev_callee;
1004 if (!edge->prev_callee)
1005 edge->caller->indirect_calls = edge->next_callee;
1007 /* Put it into the normal callee list */
1008 edge->prev_callee = NULL;
1009 edge->next_callee = edge->caller->callees;
1010 if (edge->caller->callees)
1011 edge->caller->callees->prev_callee = edge;
1012 edge->caller->callees = edge;
1014 /* Insert to callers list of the new callee. */
1015 cgraph_set_edge_callee (edge, callee);
1017 if (edge->call_stmt)
1018 edge->call_stmt_cannot_inline_p
1019 = !gimple_check_call_matching_types (edge->call_stmt, callee->symbol.decl);
1021 /* We need to re-determine the inlining status of the edge. */
1022 initialize_inline_failed (edge);
1025 /* If necessary, change the function declaration in the call statement
1026 associated with E so that it corresponds to the edge callee. */
1028 gimple
1029 cgraph_redirect_edge_call_stmt_to_callee (struct cgraph_edge *e)
1031 tree decl = gimple_call_fndecl (e->call_stmt);
1032 gimple new_stmt;
1033 gimple_stmt_iterator gsi;
1034 #ifdef ENABLE_CHECKING
1035 struct cgraph_node *node;
1036 #endif
1038 if (e->indirect_unknown_callee
1039 || decl == e->callee->symbol.decl)
1040 return e->call_stmt;
1042 #ifdef ENABLE_CHECKING
1043 if (decl)
1045 node = cgraph_get_node (decl);
1046 gcc_assert (!node || !node->clone.combined_args_to_skip);
1048 #endif
1050 if (cgraph_dump_file)
1052 fprintf (cgraph_dump_file, "updating call of %s/%i -> %s/%i: ",
1053 xstrdup (cgraph_node_name (e->caller)), e->caller->uid,
1054 xstrdup (cgraph_node_name (e->callee)), e->callee->uid);
1055 print_gimple_stmt (cgraph_dump_file, e->call_stmt, 0, dump_flags);
1056 if (e->callee->clone.combined_args_to_skip)
1058 fprintf (cgraph_dump_file, " combined args to skip: ");
1059 dump_bitmap (cgraph_dump_file,
1060 e->callee->clone.combined_args_to_skip);
1064 if (e->callee->clone.combined_args_to_skip)
1066 int lp_nr;
1068 new_stmt
1069 = gimple_call_copy_skip_args (e->call_stmt,
1070 e->callee->clone.combined_args_to_skip);
1071 gimple_call_set_fndecl (new_stmt, e->callee->symbol.decl);
1073 if (gimple_vdef (new_stmt)
1074 && TREE_CODE (gimple_vdef (new_stmt)) == SSA_NAME)
1075 SSA_NAME_DEF_STMT (gimple_vdef (new_stmt)) = new_stmt;
1077 gsi = gsi_for_stmt (e->call_stmt);
1078 gsi_replace (&gsi, new_stmt, false);
1079 /* We need to defer cleaning EH info on the new statement to
1080 fixup-cfg. We may not have dominator information at this point
1081 and thus would end up with unreachable blocks and have no way
1082 to communicate that we need to run CFG cleanup then. */
1083 lp_nr = lookup_stmt_eh_lp (e->call_stmt);
1084 if (lp_nr != 0)
1086 remove_stmt_from_eh_lp (e->call_stmt);
1087 add_stmt_to_eh_lp (new_stmt, lp_nr);
1090 else
1092 new_stmt = e->call_stmt;
1093 gimple_call_set_fndecl (new_stmt, e->callee->symbol.decl);
1094 update_stmt (new_stmt);
1097 cgraph_set_call_stmt_including_clones (e->caller, e->call_stmt, new_stmt);
1099 if (cgraph_dump_file)
1101 fprintf (cgraph_dump_file, " updated to:");
1102 print_gimple_stmt (cgraph_dump_file, e->call_stmt, 0, dump_flags);
1104 return new_stmt;
1107 /* Update or remove the corresponding cgraph edge if a GIMPLE_CALL
1108 OLD_STMT changed into NEW_STMT. OLD_CALL is gimple_call_fndecl
1109 of OLD_STMT if it was previously call statement.
1110 If NEW_STMT is NULL, the call has been dropped without any
1111 replacement. */
1113 static void
1114 cgraph_update_edges_for_call_stmt_node (struct cgraph_node *node,
1115 gimple old_stmt, tree old_call,
1116 gimple new_stmt)
1118 tree new_call = (new_stmt && is_gimple_call (new_stmt))
1119 ? gimple_call_fndecl (new_stmt) : 0;
1121 /* We are seeing indirect calls, then there is nothing to update. */
1122 if (!new_call && !old_call)
1123 return;
1124 /* See if we turned indirect call into direct call or folded call to one builtin
1125 into different builtin. */
1126 if (old_call != new_call)
1128 struct cgraph_edge *e = cgraph_edge (node, old_stmt);
1129 struct cgraph_edge *ne = NULL;
1130 gcov_type count;
1131 int frequency;
1133 if (e)
1135 /* See if the edge is already there and has the correct callee. It
1136 might be so because of indirect inlining has already updated
1137 it. We also might've cloned and redirected the edge. */
1138 if (new_call && e->callee)
1140 struct cgraph_node *callee = e->callee;
1141 while (callee)
1143 if (callee->symbol.decl == new_call
1144 || callee->former_clone_of == new_call)
1145 return;
1146 callee = callee->clone_of;
1150 /* Otherwise remove edge and create new one; we can't simply redirect
1151 since function has changed, so inline plan and other information
1152 attached to edge is invalid. */
1153 count = e->count;
1154 frequency = e->frequency;
1155 cgraph_remove_edge (e);
1157 else if (new_call)
1159 /* We are seeing new direct call; compute profile info based on BB. */
1160 basic_block bb = gimple_bb (new_stmt);
1161 count = bb->count;
1162 frequency = compute_call_stmt_bb_frequency (current_function_decl,
1163 bb);
1166 if (new_call)
1168 ne = cgraph_create_edge (node, cgraph_get_create_node (new_call),
1169 new_stmt, count, frequency);
1170 gcc_assert (ne->inline_failed);
1173 /* We only updated the call stmt; update pointer in cgraph edge.. */
1174 else if (old_stmt != new_stmt)
1175 cgraph_set_call_stmt (cgraph_edge (node, old_stmt), new_stmt);
1178 /* Update or remove the corresponding cgraph edge if a GIMPLE_CALL
1179 OLD_STMT changed into NEW_STMT. OLD_DECL is gimple_call_fndecl
1180 of OLD_STMT before it was updated (updating can happen inplace). */
1182 void
1183 cgraph_update_edges_for_call_stmt (gimple old_stmt, tree old_decl, gimple new_stmt)
1185 struct cgraph_node *orig = cgraph_get_node (cfun->decl);
1186 struct cgraph_node *node;
1188 gcc_checking_assert (orig);
1189 cgraph_update_edges_for_call_stmt_node (orig, old_stmt, old_decl, new_stmt);
1190 if (orig->clones)
1191 for (node = orig->clones; node != orig;)
1193 cgraph_update_edges_for_call_stmt_node (node, old_stmt, old_decl, new_stmt);
1194 if (node->clones)
1195 node = node->clones;
1196 else if (node->next_sibling_clone)
1197 node = node->next_sibling_clone;
1198 else
1200 while (node != orig && !node->next_sibling_clone)
1201 node = node->clone_of;
1202 if (node != orig)
1203 node = node->next_sibling_clone;
1209 /* Remove all callees from the node. */
1211 void
1212 cgraph_node_remove_callees (struct cgraph_node *node)
1214 struct cgraph_edge *e, *f;
1216 /* It is sufficient to remove the edges from the lists of callers of
1217 the callees. The callee list of the node can be zapped with one
1218 assignment. */
1219 for (e = node->callees; e; e = f)
1221 f = e->next_callee;
1222 cgraph_call_edge_removal_hooks (e);
1223 if (!e->indirect_unknown_callee)
1224 cgraph_edge_remove_callee (e);
1225 cgraph_free_edge (e);
1227 for (e = node->indirect_calls; e; e = f)
1229 f = e->next_callee;
1230 cgraph_call_edge_removal_hooks (e);
1231 if (!e->indirect_unknown_callee)
1232 cgraph_edge_remove_callee (e);
1233 cgraph_free_edge (e);
1235 node->indirect_calls = NULL;
1236 node->callees = NULL;
1237 if (node->call_site_hash)
1239 htab_delete (node->call_site_hash);
1240 node->call_site_hash = NULL;
1244 /* Remove all callers from the node. */
1246 static void
1247 cgraph_node_remove_callers (struct cgraph_node *node)
1249 struct cgraph_edge *e, *f;
1251 /* It is sufficient to remove the edges from the lists of callees of
1252 the callers. The caller list of the node can be zapped with one
1253 assignment. */
1254 for (e = node->callers; e; e = f)
1256 f = e->next_caller;
1257 cgraph_call_edge_removal_hooks (e);
1258 cgraph_edge_remove_caller (e);
1259 cgraph_free_edge (e);
1261 node->callers = NULL;
1264 /* Release memory used to represent body of function NODE. */
1266 void
1267 cgraph_release_function_body (struct cgraph_node *node)
1269 if (DECL_STRUCT_FUNCTION (node->symbol.decl))
1271 push_cfun (DECL_STRUCT_FUNCTION (node->symbol.decl));
1272 if (cfun->cfg
1273 && current_loops)
1275 cfun->curr_properties &= ~PROP_loops;
1276 loop_optimizer_finalize ();
1278 if (cfun->gimple_df)
1280 delete_tree_ssa ();
1281 delete_tree_cfg_annotations ();
1282 cfun->eh = NULL;
1284 if (cfun->cfg)
1286 gcc_assert (dom_computed[0] == DOM_NONE);
1287 gcc_assert (dom_computed[1] == DOM_NONE);
1288 clear_edges ();
1290 if (cfun->value_histograms)
1291 free_histograms ();
1292 pop_cfun();
1293 gimple_set_body (node->symbol.decl, NULL);
1294 node->ipa_transforms_to_apply.release ();
1295 /* Struct function hangs a lot of data that would leak if we didn't
1296 removed all pointers to it. */
1297 ggc_free (DECL_STRUCT_FUNCTION (node->symbol.decl));
1298 DECL_STRUCT_FUNCTION (node->symbol.decl) = NULL;
1300 DECL_SAVED_TREE (node->symbol.decl) = NULL;
1301 /* If the node is abstract and needed, then do not clear DECL_INITIAL
1302 of its associated function function declaration because it's
1303 needed to emit debug info later. */
1304 if (!node->abstract_and_needed && DECL_INITIAL (node->symbol.decl))
1305 DECL_INITIAL (node->symbol.decl) = error_mark_node;
1308 /* Remove the node from cgraph. */
1310 void
1311 cgraph_remove_node (struct cgraph_node *node)
1313 struct cgraph_node *n;
1314 int uid = node->uid;
1316 cgraph_call_node_removal_hooks (node);
1317 cgraph_node_remove_callers (node);
1318 cgraph_node_remove_callees (node);
1319 node->ipa_transforms_to_apply.release ();
1321 /* Incremental inlining access removed nodes stored in the postorder list.
1323 node->symbol.force_output = false;
1324 for (n = node->nested; n; n = n->next_nested)
1325 n->origin = NULL;
1326 node->nested = NULL;
1327 if (node->origin)
1329 struct cgraph_node **node2 = &node->origin->nested;
1331 while (*node2 != node)
1332 node2 = &(*node2)->next_nested;
1333 *node2 = node->next_nested;
1335 symtab_unregister_node ((symtab_node)node);
1336 if (node->prev_sibling_clone)
1337 node->prev_sibling_clone->next_sibling_clone = node->next_sibling_clone;
1338 else if (node->clone_of)
1339 node->clone_of->clones = node->next_sibling_clone;
1340 if (node->next_sibling_clone)
1341 node->next_sibling_clone->prev_sibling_clone = node->prev_sibling_clone;
1342 if (node->clones)
1344 struct cgraph_node *n, *next;
1346 if (node->clone_of)
1348 for (n = node->clones; n->next_sibling_clone; n = n->next_sibling_clone)
1349 n->clone_of = node->clone_of;
1350 n->clone_of = node->clone_of;
1351 n->next_sibling_clone = node->clone_of->clones;
1352 if (node->clone_of->clones)
1353 node->clone_of->clones->prev_sibling_clone = n;
1354 node->clone_of->clones = node->clones;
1356 else
1358 /* We are removing node with clones. This makes clones inconsistent,
1359 but assume they will be removed subsequently and just keep clone
1360 tree intact. This can happen in unreachable function removal since
1361 we remove unreachable functions in random order, not by bottom-up
1362 walk of clone trees. */
1363 for (n = node->clones; n; n = next)
1365 next = n->next_sibling_clone;
1366 n->next_sibling_clone = NULL;
1367 n->prev_sibling_clone = NULL;
1368 n->clone_of = NULL;
1373 /* While all the clones are removed after being proceeded, the function
1374 itself is kept in the cgraph even after it is compiled. Check whether
1375 we are done with this body and reclaim it proactively if this is the case.
1377 n = cgraph_get_node (node->symbol.decl);
1378 if (!n
1379 || (!n->clones && !n->clone_of && !n->global.inlined_to
1380 && (cgraph_global_info_ready
1381 && (TREE_ASM_WRITTEN (n->symbol.decl)
1382 || DECL_EXTERNAL (n->symbol.decl)
1383 || !n->analyzed
1384 || n->symbol.in_other_partition))))
1385 cgraph_release_function_body (node);
1387 node->symbol.decl = NULL;
1388 if (node->call_site_hash)
1390 htab_delete (node->call_site_hash);
1391 node->call_site_hash = NULL;
1393 cgraph_n_nodes--;
1395 /* Clear out the node to NULL all pointers and add the node to the free
1396 list. */
1397 memset (node, 0, sizeof(*node));
1398 node->symbol.type = SYMTAB_FUNCTION;
1399 node->uid = uid;
1400 SET_NEXT_FREE_NODE (node, free_nodes);
1401 free_nodes = node;
1404 /* Likewise indicate that a node is having address taken. */
1406 void
1407 cgraph_mark_address_taken_node (struct cgraph_node *node)
1409 gcc_assert (!node->global.inlined_to);
1410 /* FIXME: address_taken flag is used both as a shortcut for testing whether
1411 IPA_REF_ADDR reference exists (and thus it should be set on node
1412 representing alias we take address of) and as a test whether address
1413 of the object was taken (and thus it should be set on node alias is
1414 referring to). We should remove the first use and the remove the
1415 following set. */
1416 node->symbol.address_taken = 1;
1417 node = cgraph_function_or_thunk_node (node, NULL);
1418 node->symbol.address_taken = 1;
1421 /* Return local info for the compiled function. */
1423 struct cgraph_local_info *
1424 cgraph_local_info (tree decl)
1426 struct cgraph_node *node;
1428 gcc_assert (TREE_CODE (decl) == FUNCTION_DECL);
1429 node = cgraph_get_node (decl);
1430 if (!node)
1431 return NULL;
1432 return &node->local;
1435 /* Return local info for the compiled function. */
1437 struct cgraph_global_info *
1438 cgraph_global_info (tree decl)
1440 struct cgraph_node *node;
1442 gcc_assert (TREE_CODE (decl) == FUNCTION_DECL && cgraph_global_info_ready);
1443 node = cgraph_get_node (decl);
1444 if (!node)
1445 return NULL;
1446 return &node->global;
1449 /* Return local info for the compiled function. */
1451 struct cgraph_rtl_info *
1452 cgraph_rtl_info (tree decl)
1454 struct cgraph_node *node;
1456 gcc_assert (TREE_CODE (decl) == FUNCTION_DECL);
1457 node = cgraph_get_node (decl);
1458 if (!node
1459 || (decl != current_function_decl
1460 && !TREE_ASM_WRITTEN (node->symbol.decl)))
1461 return NULL;
1462 return &node->rtl;
1465 /* Return a string describing the failure REASON. */
1467 const char*
1468 cgraph_inline_failed_string (cgraph_inline_failed_t reason)
1470 #undef DEFCIFCODE
1471 #define DEFCIFCODE(code, string) string,
1473 static const char *cif_string_table[CIF_N_REASONS] = {
1474 #include "cif-code.def"
1477 /* Signedness of an enum type is implementation defined, so cast it
1478 to unsigned before testing. */
1479 gcc_assert ((unsigned) reason < CIF_N_REASONS);
1480 return cif_string_table[reason];
1483 /* Names used to print out the availability enum. */
1484 const char * const cgraph_availability_names[] =
1485 {"unset", "not_available", "overwritable", "available", "local"};
1488 /* Dump call graph node NODE to file F. */
1490 void
1491 dump_cgraph_node (FILE *f, struct cgraph_node *node)
1493 struct cgraph_edge *edge;
1494 int indirect_calls_count = 0;
1496 dump_symtab_base (f, (symtab_node) node);
1498 if (node->global.inlined_to)
1499 fprintf (f, " Function %s/%i is inline copy in %s/%i\n",
1500 xstrdup (cgraph_node_name (node)),
1501 node->symbol.order,
1502 xstrdup (cgraph_node_name (node->global.inlined_to)),
1503 node->global.inlined_to->symbol.order);
1504 if (node->clone_of)
1505 fprintf (f, " Clone of %s/%i\n",
1506 cgraph_node_asm_name (node->clone_of),
1507 node->clone_of->symbol.order);
1508 if (cgraph_function_flags_ready)
1509 fprintf (f, " Availability: %s\n",
1510 cgraph_availability_names [cgraph_function_body_availability (node)]);
1512 fprintf (f, " Function flags:");
1513 if (node->analyzed)
1514 fprintf (f, " analyzed");
1515 if (node->count)
1516 fprintf (f, " executed "HOST_WIDEST_INT_PRINT_DEC"x",
1517 (HOST_WIDEST_INT)node->count);
1518 if (node->origin)
1519 fprintf (f, " nested in: %s", cgraph_node_asm_name (node->origin));
1520 if (gimple_has_body_p (node->symbol.decl))
1521 fprintf (f, " body");
1522 if (node->process)
1523 fprintf (f, " process");
1524 if (node->local.local)
1525 fprintf (f, " local");
1526 if (node->local.finalized)
1527 fprintf (f, " finalized");
1528 if (node->local.redefined_extern_inline)
1529 fprintf (f, " redefined_extern_inline");
1530 if (node->only_called_at_startup)
1531 fprintf (f, " only_called_at_startup");
1532 if (node->only_called_at_exit)
1533 fprintf (f, " only_called_at_exit");
1534 else if (node->alias)
1535 fprintf (f, " alias");
1536 if (node->tm_clone)
1537 fprintf (f, " tm_clone");
1539 fprintf (f, "\n");
1541 if (node->thunk.thunk_p)
1543 fprintf (f, " Thunk of %s (asm: %s) fixed offset %i virtual value %i has "
1544 "virtual offset %i)\n",
1545 lang_hooks.decl_printable_name (node->thunk.alias, 2),
1546 IDENTIFIER_POINTER (DECL_ASSEMBLER_NAME (node->thunk.alias)),
1547 (int)node->thunk.fixed_offset,
1548 (int)node->thunk.virtual_value,
1549 (int)node->thunk.virtual_offset_p);
1551 if (node->alias && node->thunk.alias)
1553 fprintf (f, " Alias of %s",
1554 lang_hooks.decl_printable_name (node->thunk.alias, 2));
1555 if (DECL_ASSEMBLER_NAME_SET_P (node->thunk.alias))
1556 fprintf (f, " (asm: %s)",
1557 IDENTIFIER_POINTER (DECL_ASSEMBLER_NAME (node->thunk.alias)));
1558 fprintf (f, "\n");
1561 fprintf (f, " Called by: ");
1563 for (edge = node->callers; edge; edge = edge->next_caller)
1565 fprintf (f, "%s/%i ", cgraph_node_asm_name (edge->caller),
1566 edge->caller->symbol.order);
1567 if (edge->count)
1568 fprintf (f, "("HOST_WIDEST_INT_PRINT_DEC"x) ",
1569 (HOST_WIDEST_INT)edge->count);
1570 if (edge->frequency)
1571 fprintf (f, "(%.2f per call) ",
1572 edge->frequency / (double)CGRAPH_FREQ_BASE);
1573 if (!edge->inline_failed)
1574 fprintf(f, "(inlined) ");
1575 if (edge->indirect_inlining_edge)
1576 fprintf(f, "(indirect_inlining) ");
1577 if (edge->can_throw_external)
1578 fprintf(f, "(can throw external) ");
1581 fprintf (f, "\n Calls: ");
1582 for (edge = node->callees; edge; edge = edge->next_callee)
1584 fprintf (f, "%s/%i ", cgraph_node_asm_name (edge->callee),
1585 edge->callee->symbol.order);
1586 if (!edge->inline_failed)
1587 fprintf(f, "(inlined) ");
1588 if (edge->indirect_inlining_edge)
1589 fprintf(f, "(indirect_inlining) ");
1590 if (edge->count)
1591 fprintf (f, "("HOST_WIDEST_INT_PRINT_DEC"x) ",
1592 (HOST_WIDEST_INT)edge->count);
1593 if (edge->frequency)
1594 fprintf (f, "(%.2f per call) ",
1595 edge->frequency / (double)CGRAPH_FREQ_BASE);
1596 if (edge->can_throw_external)
1597 fprintf(f, "(can throw external) ");
1599 fprintf (f, "\n");
1601 for (edge = node->indirect_calls; edge; edge = edge->next_callee)
1602 indirect_calls_count++;
1603 if (indirect_calls_count)
1604 fprintf (f, " Has %i outgoing edges for indirect calls.\n",
1605 indirect_calls_count);
1609 /* Dump call graph node NODE to stderr. */
1611 DEBUG_FUNCTION void
1612 debug_cgraph_node (struct cgraph_node *node)
1614 dump_cgraph_node (stderr, node);
1618 /* Dump the callgraph to file F. */
1620 void
1621 dump_cgraph (FILE *f)
1623 struct cgraph_node *node;
1625 fprintf (f, "callgraph:\n\n");
1626 FOR_EACH_FUNCTION (node)
1627 dump_cgraph_node (f, node);
1631 /* Dump the call graph to stderr. */
1633 DEBUG_FUNCTION void
1634 debug_cgraph (void)
1636 dump_cgraph (stderr);
1639 /* Return true when the DECL can possibly be inlined. */
1640 bool
1641 cgraph_function_possibly_inlined_p (tree decl)
1643 if (!cgraph_global_info_ready)
1644 return !DECL_UNINLINABLE (decl);
1645 return DECL_POSSIBLY_INLINED (decl);
1648 /* NODE is no longer nested function; update cgraph accordingly. */
1649 void
1650 cgraph_unnest_node (struct cgraph_node *node)
1652 struct cgraph_node **node2 = &node->origin->nested;
1653 gcc_assert (node->origin);
1655 while (*node2 != node)
1656 node2 = &(*node2)->next_nested;
1657 *node2 = node->next_nested;
1658 node->origin = NULL;
1661 /* Return function availability. See cgraph.h for description of individual
1662 return values. */
1663 enum availability
1664 cgraph_function_body_availability (struct cgraph_node *node)
1666 enum availability avail;
1667 gcc_assert (cgraph_function_flags_ready);
1668 if (!node->analyzed)
1669 avail = AVAIL_NOT_AVAILABLE;
1670 else if (node->local.local)
1671 avail = AVAIL_LOCAL;
1672 else if (!node->symbol.externally_visible)
1673 avail = AVAIL_AVAILABLE;
1674 /* Inline functions are safe to be analyzed even if their symbol can
1675 be overwritten at runtime. It is not meaningful to enforce any sane
1676 behaviour on replacing inline function by different body. */
1677 else if (DECL_DECLARED_INLINE_P (node->symbol.decl))
1678 avail = AVAIL_AVAILABLE;
1680 /* If the function can be overwritten, return OVERWRITABLE. Take
1681 care at least of two notable extensions - the COMDAT functions
1682 used to share template instantiations in C++ (this is symmetric
1683 to code cp_cannot_inline_tree_fn and probably shall be shared and
1684 the inlinability hooks completely eliminated).
1686 ??? Does the C++ one definition rule allow us to always return
1687 AVAIL_AVAILABLE here? That would be good reason to preserve this
1688 bit. */
1690 else if (decl_replaceable_p (node->symbol.decl)
1691 && !DECL_EXTERNAL (node->symbol.decl))
1692 avail = AVAIL_OVERWRITABLE;
1693 else avail = AVAIL_AVAILABLE;
1695 return avail;
1698 /* Worker for cgraph_node_can_be_local_p. */
1699 static bool
1700 cgraph_node_cannot_be_local_p_1 (struct cgraph_node *node,
1701 void *data ATTRIBUTE_UNUSED)
1703 return !(!node->symbol.force_output
1704 && ((DECL_COMDAT (node->symbol.decl)
1705 && !node->symbol.same_comdat_group)
1706 || !node->symbol.externally_visible));
1709 /* Return true if NODE can be made local for API change.
1710 Extern inline functions and C++ COMDAT functions can be made local
1711 at the expense of possible code size growth if function is used in multiple
1712 compilation units. */
1713 bool
1714 cgraph_node_can_be_local_p (struct cgraph_node *node)
1716 return (!node->symbol.address_taken
1717 && !cgraph_for_node_and_aliases (node,
1718 cgraph_node_cannot_be_local_p_1,
1719 NULL, true));
1722 /* Call calback on NODE, thunks and aliases associated to NODE.
1723 When INCLUDE_OVERWRITABLE is false, overwritable aliases and thunks are
1724 skipped. */
1726 bool
1727 cgraph_for_node_thunks_and_aliases (struct cgraph_node *node,
1728 bool (*callback) (struct cgraph_node *, void *),
1729 void *data,
1730 bool include_overwritable)
1732 struct cgraph_edge *e;
1733 int i;
1734 struct ipa_ref *ref;
1736 if (callback (node, data))
1737 return true;
1738 for (e = node->callers; e; e = e->next_caller)
1739 if (e->caller->thunk.thunk_p
1740 && (include_overwritable
1741 || cgraph_function_body_availability (e->caller) > AVAIL_OVERWRITABLE))
1742 if (cgraph_for_node_thunks_and_aliases (e->caller, callback, data,
1743 include_overwritable))
1744 return true;
1745 for (i = 0; ipa_ref_list_referring_iterate (&node->symbol.ref_list, i, ref); i++)
1746 if (ref->use == IPA_REF_ALIAS)
1748 struct cgraph_node *alias = ipa_ref_referring_node (ref);
1749 if (include_overwritable
1750 || cgraph_function_body_availability (alias) > AVAIL_OVERWRITABLE)
1751 if (cgraph_for_node_thunks_and_aliases (alias, callback, data,
1752 include_overwritable))
1753 return true;
1755 return false;
1758 /* Call calback on NODE and aliases associated to NODE.
1759 When INCLUDE_OVERWRITABLE is false, overwritable aliases and thunks are
1760 skipped. */
1762 bool
1763 cgraph_for_node_and_aliases (struct cgraph_node *node,
1764 bool (*callback) (struct cgraph_node *, void *),
1765 void *data,
1766 bool include_overwritable)
1768 int i;
1769 struct ipa_ref *ref;
1771 if (callback (node, data))
1772 return true;
1773 for (i = 0; ipa_ref_list_referring_iterate (&node->symbol.ref_list, i, ref); i++)
1774 if (ref->use == IPA_REF_ALIAS)
1776 struct cgraph_node *alias = ipa_ref_referring_node (ref);
1777 if (include_overwritable
1778 || cgraph_function_body_availability (alias) > AVAIL_OVERWRITABLE)
1779 if (cgraph_for_node_and_aliases (alias, callback, data,
1780 include_overwritable))
1781 return true;
1783 return false;
1786 /* Worker to bring NODE local. */
1788 static bool
1789 cgraph_make_node_local_1 (struct cgraph_node *node, void *data ATTRIBUTE_UNUSED)
1791 gcc_checking_assert (cgraph_node_can_be_local_p (node));
1792 if (DECL_COMDAT (node->symbol.decl) || DECL_EXTERNAL (node->symbol.decl))
1794 symtab_make_decl_local (node->symbol.decl);
1796 node->symbol.externally_visible = false;
1797 node->local.local = true;
1798 node->symbol.resolution = LDPR_PREVAILING_DEF_IRONLY;
1799 gcc_assert (cgraph_function_body_availability (node) == AVAIL_LOCAL);
1801 return false;
1804 /* Bring NODE local. */
1806 void
1807 cgraph_make_node_local (struct cgraph_node *node)
1809 cgraph_for_node_thunks_and_aliases (node, cgraph_make_node_local_1,
1810 NULL, true);
1813 /* Worker to set nothrow flag. */
1815 static bool
1816 cgraph_set_nothrow_flag_1 (struct cgraph_node *node, void *data)
1818 struct cgraph_edge *e;
1820 TREE_NOTHROW (node->symbol.decl) = data != NULL;
1822 if (data != NULL)
1823 for (e = node->callers; e; e = e->next_caller)
1824 e->can_throw_external = false;
1825 return false;
1828 /* Set TREE_NOTHROW on NODE's decl and on aliases of NODE
1829 if any to NOTHROW. */
1831 void
1832 cgraph_set_nothrow_flag (struct cgraph_node *node, bool nothrow)
1834 cgraph_for_node_thunks_and_aliases (node, cgraph_set_nothrow_flag_1,
1835 (void *)(size_t)nothrow, false);
1838 /* Worker to set const flag. */
1840 static bool
1841 cgraph_set_const_flag_1 (struct cgraph_node *node, void *data)
1843 /* Static constructors and destructors without a side effect can be
1844 optimized out. */
1845 if (data && !((size_t)data & 2))
1847 if (DECL_STATIC_CONSTRUCTOR (node->symbol.decl))
1848 DECL_STATIC_CONSTRUCTOR (node->symbol.decl) = 0;
1849 if (DECL_STATIC_DESTRUCTOR (node->symbol.decl))
1850 DECL_STATIC_DESTRUCTOR (node->symbol.decl) = 0;
1852 TREE_READONLY (node->symbol.decl) = data != NULL;
1853 DECL_LOOPING_CONST_OR_PURE_P (node->symbol.decl) = ((size_t)data & 2) != 0;
1854 return false;
1857 /* Set TREE_READONLY on NODE's decl and on aliases of NODE
1858 if any to READONLY. */
1860 void
1861 cgraph_set_const_flag (struct cgraph_node *node, bool readonly, bool looping)
1863 cgraph_for_node_thunks_and_aliases (node, cgraph_set_const_flag_1,
1864 (void *)(size_t)(readonly + (int)looping * 2),
1865 false);
1868 /* Worker to set pure flag. */
1870 static bool
1871 cgraph_set_pure_flag_1 (struct cgraph_node *node, void *data)
1873 /* Static constructors and destructors without a side effect can be
1874 optimized out. */
1875 if (data && !((size_t)data & 2))
1877 if (DECL_STATIC_CONSTRUCTOR (node->symbol.decl))
1878 DECL_STATIC_CONSTRUCTOR (node->symbol.decl) = 0;
1879 if (DECL_STATIC_DESTRUCTOR (node->symbol.decl))
1880 DECL_STATIC_DESTRUCTOR (node->symbol.decl) = 0;
1882 DECL_PURE_P (node->symbol.decl) = data != NULL;
1883 DECL_LOOPING_CONST_OR_PURE_P (node->symbol.decl) = ((size_t)data & 2) != 0;
1884 return false;
1887 /* Set DECL_PURE_P on NODE's decl and on aliases of NODE
1888 if any to PURE. */
1890 void
1891 cgraph_set_pure_flag (struct cgraph_node *node, bool pure, bool looping)
1893 cgraph_for_node_thunks_and_aliases (node, cgraph_set_pure_flag_1,
1894 (void *)(size_t)(pure + (int)looping * 2),
1895 false);
1898 /* Data used by cgraph_propagate_frequency. */
1900 struct cgraph_propagate_frequency_data
1902 bool maybe_unlikely_executed;
1903 bool maybe_executed_once;
1904 bool only_called_at_startup;
1905 bool only_called_at_exit;
1908 /* Worker for cgraph_propagate_frequency_1. */
1910 static bool
1911 cgraph_propagate_frequency_1 (struct cgraph_node *node, void *data)
1913 struct cgraph_propagate_frequency_data *d;
1914 struct cgraph_edge *edge;
1916 d = (struct cgraph_propagate_frequency_data *)data;
1917 for (edge = node->callers;
1918 edge && (d->maybe_unlikely_executed || d->maybe_executed_once
1919 || d->only_called_at_startup || d->only_called_at_exit);
1920 edge = edge->next_caller)
1922 if (edge->caller != node)
1924 d->only_called_at_startup &= edge->caller->only_called_at_startup;
1925 /* It makes sense to put main() together with the static constructors.
1926 It will be executed for sure, but rest of functions called from
1927 main are definitely not at startup only. */
1928 if (MAIN_NAME_P (DECL_NAME (edge->caller->symbol.decl)))
1929 d->only_called_at_startup = 0;
1930 d->only_called_at_exit &= edge->caller->only_called_at_exit;
1932 if (!edge->frequency)
1933 continue;
1934 switch (edge->caller->frequency)
1936 case NODE_FREQUENCY_UNLIKELY_EXECUTED:
1937 break;
1938 case NODE_FREQUENCY_EXECUTED_ONCE:
1939 if (dump_file && (dump_flags & TDF_DETAILS))
1940 fprintf (dump_file, " Called by %s that is executed once\n",
1941 cgraph_node_name (edge->caller));
1942 d->maybe_unlikely_executed = false;
1943 if (inline_edge_summary (edge)->loop_depth)
1945 d->maybe_executed_once = false;
1946 if (dump_file && (dump_flags & TDF_DETAILS))
1947 fprintf (dump_file, " Called in loop\n");
1949 break;
1950 case NODE_FREQUENCY_HOT:
1951 case NODE_FREQUENCY_NORMAL:
1952 if (dump_file && (dump_flags & TDF_DETAILS))
1953 fprintf (dump_file, " Called by %s that is normal or hot\n",
1954 cgraph_node_name (edge->caller));
1955 d->maybe_unlikely_executed = false;
1956 d->maybe_executed_once = false;
1957 break;
1960 return edge != NULL;
1963 /* See if the frequency of NODE can be updated based on frequencies of its
1964 callers. */
1965 bool
1966 cgraph_propagate_frequency (struct cgraph_node *node)
1968 struct cgraph_propagate_frequency_data d = {true, true, true, true};
1969 bool changed = false;
1971 if (!node->local.local)
1972 return false;
1973 gcc_assert (node->analyzed);
1974 if (dump_file && (dump_flags & TDF_DETAILS))
1975 fprintf (dump_file, "Processing frequency %s\n", cgraph_node_name (node));
1977 cgraph_for_node_and_aliases (node, cgraph_propagate_frequency_1, &d, true);
1979 if ((d.only_called_at_startup && !d.only_called_at_exit)
1980 && !node->only_called_at_startup)
1982 node->only_called_at_startup = true;
1983 if (dump_file)
1984 fprintf (dump_file, "Node %s promoted to only called at startup.\n",
1985 cgraph_node_name (node));
1986 changed = true;
1988 if ((d.only_called_at_exit && !d.only_called_at_startup)
1989 && !node->only_called_at_exit)
1991 node->only_called_at_exit = true;
1992 if (dump_file)
1993 fprintf (dump_file, "Node %s promoted to only called at exit.\n",
1994 cgraph_node_name (node));
1995 changed = true;
1997 /* These come either from profile or user hints; never update them. */
1998 if (node->frequency == NODE_FREQUENCY_HOT
1999 || node->frequency == NODE_FREQUENCY_UNLIKELY_EXECUTED)
2000 return changed;
2001 if (d.maybe_unlikely_executed)
2003 node->frequency = NODE_FREQUENCY_UNLIKELY_EXECUTED;
2004 if (dump_file)
2005 fprintf (dump_file, "Node %s promoted to unlikely executed.\n",
2006 cgraph_node_name (node));
2007 changed = true;
2009 else if (d.maybe_executed_once && node->frequency != NODE_FREQUENCY_EXECUTED_ONCE)
2011 node->frequency = NODE_FREQUENCY_EXECUTED_ONCE;
2012 if (dump_file)
2013 fprintf (dump_file, "Node %s promoted to executed once.\n",
2014 cgraph_node_name (node));
2015 changed = true;
2017 return changed;
2020 /* Return true when NODE can not return or throw and thus
2021 it is safe to ignore its side effects for IPA analysis. */
2023 bool
2024 cgraph_node_cannot_return (struct cgraph_node *node)
2026 int flags = flags_from_decl_or_type (node->symbol.decl);
2027 if (!flag_exceptions)
2028 return (flags & ECF_NORETURN) != 0;
2029 else
2030 return ((flags & (ECF_NORETURN | ECF_NOTHROW))
2031 == (ECF_NORETURN | ECF_NOTHROW));
2034 /* Return true when call of E can not lead to return from caller
2035 and thus it is safe to ignore its side effects for IPA analysis
2036 when computing side effects of the caller.
2037 FIXME: We could actually mark all edges that have no reaching
2038 patch to EXIT_BLOCK_PTR or throw to get better results. */
2039 bool
2040 cgraph_edge_cannot_lead_to_return (struct cgraph_edge *e)
2042 if (cgraph_node_cannot_return (e->caller))
2043 return true;
2044 if (e->indirect_unknown_callee)
2046 int flags = e->indirect_info->ecf_flags;
2047 if (!flag_exceptions)
2048 return (flags & ECF_NORETURN) != 0;
2049 else
2050 return ((flags & (ECF_NORETURN | ECF_NOTHROW))
2051 == (ECF_NORETURN | ECF_NOTHROW));
2053 else
2054 return cgraph_node_cannot_return (e->callee);
2057 /* Return true when function NODE can be removed from callgraph
2058 if all direct calls are eliminated. */
2060 bool
2061 cgraph_can_remove_if_no_direct_calls_and_refs_p (struct cgraph_node *node)
2063 gcc_assert (!node->global.inlined_to);
2064 /* Extern inlines can always go, we will use the external definition. */
2065 if (DECL_EXTERNAL (node->symbol.decl))
2066 return true;
2067 /* When function is needed, we can not remove it. */
2068 if (node->symbol.force_output || node->symbol.used_from_other_partition)
2069 return false;
2070 if (DECL_STATIC_CONSTRUCTOR (node->symbol.decl)
2071 || DECL_STATIC_DESTRUCTOR (node->symbol.decl))
2072 return false;
2073 /* Only COMDAT functions can be removed if externally visible. */
2074 if (node->symbol.externally_visible
2075 && (!DECL_COMDAT (node->symbol.decl)
2076 || symtab_used_from_object_file_p ((symtab_node) node)))
2077 return false;
2078 return true;
2081 /* Worker for cgraph_can_remove_if_no_direct_calls_p. */
2083 static bool
2084 nonremovable_p (struct cgraph_node *node, void *data ATTRIBUTE_UNUSED)
2086 return !cgraph_can_remove_if_no_direct_calls_and_refs_p (node);
2089 /* Return true when function NODE and its aliases can be removed from callgraph
2090 if all direct calls are eliminated. */
2092 bool
2093 cgraph_can_remove_if_no_direct_calls_p (struct cgraph_node *node)
2095 /* Extern inlines can always go, we will use the external definition. */
2096 if (DECL_EXTERNAL (node->symbol.decl))
2097 return true;
2098 if (node->symbol.address_taken)
2099 return false;
2100 return !cgraph_for_node_and_aliases (node, nonremovable_p, NULL, true);
2103 /* Worker for cgraph_can_remove_if_no_direct_calls_p. */
2105 static bool
2106 used_from_object_file_p (struct cgraph_node *node, void *data ATTRIBUTE_UNUSED)
2108 return symtab_used_from_object_file_p ((symtab_node) node);
2111 /* Return true when function NODE can be expected to be removed
2112 from program when direct calls in this compilation unit are removed.
2114 As a special case COMDAT functions are
2115 cgraph_can_remove_if_no_direct_calls_p while the are not
2116 cgraph_only_called_directly_p (it is possible they are called from other
2117 unit)
2119 This function behaves as cgraph_only_called_directly_p because eliminating
2120 all uses of COMDAT function does not make it necessarily disappear from
2121 the program unless we are compiling whole program or we do LTO. In this
2122 case we know we win since dynamic linking will not really discard the
2123 linkonce section. */
2125 bool
2126 cgraph_will_be_removed_from_program_if_no_direct_calls (struct cgraph_node *node)
2128 gcc_assert (!node->global.inlined_to);
2129 if (cgraph_for_node_and_aliases (node, used_from_object_file_p, NULL, true))
2130 return false;
2131 if (!in_lto_p && !flag_whole_program)
2132 return cgraph_only_called_directly_p (node);
2133 else
2135 if (DECL_EXTERNAL (node->symbol.decl))
2136 return true;
2137 return cgraph_can_remove_if_no_direct_calls_p (node);
2142 /* Worker for cgraph_only_called_directly_p. */
2144 static bool
2145 cgraph_not_only_called_directly_p_1 (struct cgraph_node *node, void *data ATTRIBUTE_UNUSED)
2147 return !cgraph_only_called_directly_or_aliased_p (node);
2150 /* Return true when function NODE and all its aliases are only called
2151 directly.
2152 i.e. it is not externally visible, address was not taken and
2153 it is not used in any other non-standard way. */
2155 bool
2156 cgraph_only_called_directly_p (struct cgraph_node *node)
2158 gcc_assert (cgraph_function_or_thunk_node (node, NULL) == node);
2159 return !cgraph_for_node_and_aliases (node, cgraph_not_only_called_directly_p_1,
2160 NULL, true);
2164 /* Collect all callers of NODE. Worker for collect_callers_of_node. */
2166 static bool
2167 collect_callers_of_node_1 (struct cgraph_node *node, void *data)
2169 vec<cgraph_edge_p> *redirect_callers = (vec<cgraph_edge_p> *)data;
2170 struct cgraph_edge *cs;
2171 enum availability avail;
2172 cgraph_function_or_thunk_node (node, &avail);
2174 if (avail > AVAIL_OVERWRITABLE)
2175 for (cs = node->callers; cs != NULL; cs = cs->next_caller)
2176 if (!cs->indirect_inlining_edge)
2177 redirect_callers->safe_push (cs);
2178 return false;
2181 /* Collect all callers of NODE and its aliases that are known to lead to NODE
2182 (i.e. are not overwritable). */
2184 vec<cgraph_edge_p>
2185 collect_callers_of_node (struct cgraph_node *node)
2187 vec<cgraph_edge_p> redirect_callers = vNULL;
2188 cgraph_for_node_and_aliases (node, collect_callers_of_node_1,
2189 &redirect_callers, false);
2190 return redirect_callers;
2193 /* Return TRUE if NODE2 is equivalent to NODE or its clone. */
2194 static bool
2195 clone_of_p (struct cgraph_node *node, struct cgraph_node *node2)
2197 node = cgraph_function_or_thunk_node (node, NULL);
2198 node2 = cgraph_function_or_thunk_node (node2, NULL);
2199 while (node != node2 && node2)
2200 node2 = node2->clone_of;
2201 return node2 != NULL;
2204 /* Verify edge E count and frequency. */
2206 static bool
2207 verify_edge_count_and_frequency (struct cgraph_edge *e)
2209 bool error_found = false;
2210 if (e->count < 0)
2212 error ("caller edge count is negative");
2213 error_found = true;
2215 if (e->frequency < 0)
2217 error ("caller edge frequency is negative");
2218 error_found = true;
2220 if (e->frequency > CGRAPH_FREQ_MAX)
2222 error ("caller edge frequency is too large");
2223 error_found = true;
2225 if (gimple_has_body_p (e->caller->symbol.decl)
2226 && !e->caller->global.inlined_to
2227 /* FIXME: Inline-analysis sets frequency to 0 when edge is optimized out.
2228 Remove this once edges are actually removed from the function at that time. */
2229 && (e->frequency
2230 || (inline_edge_summary_vec.exists ()
2231 && ((inline_edge_summary_vec.length () <= (unsigned) e->uid)
2232 || !inline_edge_summary (e)->predicate)))
2233 && (e->frequency
2234 != compute_call_stmt_bb_frequency (e->caller->symbol.decl,
2235 gimple_bb (e->call_stmt))))
2237 error ("caller edge frequency %i does not match BB frequency %i",
2238 e->frequency,
2239 compute_call_stmt_bb_frequency (e->caller->symbol.decl,
2240 gimple_bb (e->call_stmt)));
2241 error_found = true;
2243 return error_found;
2246 /* Switch to THIS_CFUN if needed and print STMT to stderr. */
2247 static void
2248 cgraph_debug_gimple_stmt (struct function *this_cfun, gimple stmt)
2250 bool fndecl_was_null = false;
2251 /* debug_gimple_stmt needs correct cfun */
2252 if (cfun != this_cfun)
2253 set_cfun (this_cfun);
2254 /* ...and an actual current_function_decl */
2255 if (!current_function_decl)
2257 current_function_decl = this_cfun->decl;
2258 fndecl_was_null = true;
2260 debug_gimple_stmt (stmt);
2261 if (fndecl_was_null)
2262 current_function_decl = NULL;
2265 /* Verify that call graph edge E corresponds to DECL from the associated
2266 statement. Return true if the verification should fail. */
2268 static bool
2269 verify_edge_corresponds_to_fndecl (struct cgraph_edge *e, tree decl)
2271 struct cgraph_node *node;
2273 if (!decl || e->callee->global.inlined_to)
2274 return false;
2275 node = cgraph_get_node (decl);
2277 /* We do not know if a node from a different partition is an alias or what it
2278 aliases and therefore cannot do the former_clone_of check reliably. */
2279 if (!node || node->symbol.in_other_partition)
2280 return false;
2281 node = cgraph_function_or_thunk_node (node, NULL);
2283 if ((e->callee->former_clone_of != node->symbol.decl
2284 && (!node->same_body_alias
2285 || e->callee->former_clone_of != node->thunk.alias))
2286 /* IPA-CP sometimes redirect edge to clone and then back to the former
2287 function. This ping-pong has to go, eventually. */
2288 && (node != cgraph_function_or_thunk_node (e->callee, NULL))
2289 && !clone_of_p (node, e->callee)
2290 /* If decl is a same body alias of some other decl, allow e->callee to be
2291 a clone of a clone of that other decl too. */
2292 && (!node->same_body_alias
2293 || !clone_of_p (cgraph_get_node (node->thunk.alias), e->callee)))
2294 return true;
2295 else
2296 return false;
2299 /* Verify cgraph nodes of given cgraph node. */
2300 DEBUG_FUNCTION void
2301 verify_cgraph_node (struct cgraph_node *node)
2303 struct cgraph_edge *e;
2304 struct function *this_cfun = DECL_STRUCT_FUNCTION (node->symbol.decl);
2305 basic_block this_block;
2306 gimple_stmt_iterator gsi;
2307 bool error_found = false;
2309 if (seen_error ())
2310 return;
2312 timevar_push (TV_CGRAPH_VERIFY);
2313 error_found |= verify_symtab_base ((symtab_node) node);
2314 for (e = node->callees; e; e = e->next_callee)
2315 if (e->aux)
2317 error ("aux field set for edge %s->%s",
2318 identifier_to_locale (cgraph_node_name (e->caller)),
2319 identifier_to_locale (cgraph_node_name (e->callee)));
2320 error_found = true;
2322 if (node->count < 0)
2324 error ("execution count is negative");
2325 error_found = true;
2327 if (node->global.inlined_to && node->symbol.same_comdat_group)
2329 error ("inline clone in same comdat group list");
2330 error_found = true;
2332 if (node->global.inlined_to && node->symbol.externally_visible)
2334 error ("externally visible inline clone");
2335 error_found = true;
2337 if (node->global.inlined_to && node->symbol.address_taken)
2339 error ("inline clone with address taken");
2340 error_found = true;
2342 if (node->global.inlined_to && node->symbol.force_output)
2344 error ("inline clone is forced to output");
2345 error_found = true;
2347 for (e = node->indirect_calls; e; e = e->next_callee)
2349 if (e->aux)
2351 error ("aux field set for indirect edge from %s",
2352 identifier_to_locale (cgraph_node_name (e->caller)));
2353 error_found = true;
2355 if (!e->indirect_unknown_callee
2356 || !e->indirect_info)
2358 error ("An indirect edge from %s is not marked as indirect or has "
2359 "associated indirect_info, the corresponding statement is: ",
2360 identifier_to_locale (cgraph_node_name (e->caller)));
2361 cgraph_debug_gimple_stmt (this_cfun, e->call_stmt);
2362 error_found = true;
2365 for (e = node->callers; e; e = e->next_caller)
2367 if (verify_edge_count_and_frequency (e))
2368 error_found = true;
2369 if (!e->inline_failed)
2371 if (node->global.inlined_to
2372 != (e->caller->global.inlined_to
2373 ? e->caller->global.inlined_to : e->caller))
2375 error ("inlined_to pointer is wrong");
2376 error_found = true;
2378 if (node->callers->next_caller)
2380 error ("multiple inline callers");
2381 error_found = true;
2384 else
2385 if (node->global.inlined_to)
2387 error ("inlined_to pointer set for noninline callers");
2388 error_found = true;
2391 for (e = node->indirect_calls; e; e = e->next_callee)
2392 if (verify_edge_count_and_frequency (e))
2393 error_found = true;
2394 if (!node->callers && node->global.inlined_to)
2396 error ("inlined_to pointer is set but no predecessors found");
2397 error_found = true;
2399 if (node->global.inlined_to == node)
2401 error ("inlined_to pointer refers to itself");
2402 error_found = true;
2405 if (node->clone_of)
2407 struct cgraph_node *n;
2408 for (n = node->clone_of->clones; n; n = n->next_sibling_clone)
2409 if (n == node)
2410 break;
2411 if (!n)
2413 error ("node has wrong clone_of");
2414 error_found = true;
2417 if (node->clones)
2419 struct cgraph_node *n;
2420 for (n = node->clones; n; n = n->next_sibling_clone)
2421 if (n->clone_of != node)
2422 break;
2423 if (n)
2425 error ("node has wrong clone list");
2426 error_found = true;
2429 if ((node->prev_sibling_clone || node->next_sibling_clone) && !node->clone_of)
2431 error ("node is in clone list but it is not clone");
2432 error_found = true;
2434 if (!node->prev_sibling_clone && node->clone_of && node->clone_of->clones != node)
2436 error ("node has wrong prev_clone pointer");
2437 error_found = true;
2439 if (node->prev_sibling_clone && node->prev_sibling_clone->next_sibling_clone != node)
2441 error ("double linked list of clones corrupted");
2442 error_found = true;
2445 if (node->analyzed && node->alias)
2447 bool ref_found = false;
2448 int i;
2449 struct ipa_ref *ref;
2451 if (node->callees)
2453 error ("Alias has call edges");
2454 error_found = true;
2456 for (i = 0; ipa_ref_list_reference_iterate (&node->symbol.ref_list,
2457 i, ref); i++)
2458 if (ref->use != IPA_REF_ALIAS)
2460 error ("Alias has non-alias reference");
2461 error_found = true;
2463 else if (ref_found)
2465 error ("Alias has more than one alias reference");
2466 error_found = true;
2468 else
2469 ref_found = true;
2470 if (!ref_found)
2472 error ("Analyzed alias has no reference");
2473 error_found = true;
2476 if (node->analyzed && node->thunk.thunk_p)
2478 if (!node->callees)
2480 error ("No edge out of thunk node");
2481 error_found = true;
2483 else if (node->callees->next_callee)
2485 error ("More than one edge out of thunk node");
2486 error_found = true;
2488 if (gimple_has_body_p (node->symbol.decl))
2490 error ("Thunk is not supposed to have body");
2491 error_found = true;
2494 else if (node->analyzed && gimple_has_body_p (node->symbol.decl)
2495 && !TREE_ASM_WRITTEN (node->symbol.decl)
2496 && (!DECL_EXTERNAL (node->symbol.decl) || node->global.inlined_to)
2497 && !flag_wpa)
2499 if (this_cfun->cfg)
2501 /* Reach the trees by walking over the CFG, and note the
2502 enclosing basic-blocks in the call edges. */
2503 FOR_EACH_BB_FN (this_block, this_cfun)
2504 for (gsi = gsi_start_bb (this_block);
2505 !gsi_end_p (gsi);
2506 gsi_next (&gsi))
2508 gimple stmt = gsi_stmt (gsi);
2509 if (is_gimple_call (stmt))
2511 struct cgraph_edge *e = cgraph_edge (node, stmt);
2512 tree decl = gimple_call_fndecl (stmt);
2513 if (e)
2515 if (e->aux)
2517 error ("shared call_stmt:");
2518 cgraph_debug_gimple_stmt (this_cfun, stmt);
2519 error_found = true;
2521 if (!e->indirect_unknown_callee)
2523 if (verify_edge_corresponds_to_fndecl (e, decl))
2525 error ("edge points to wrong declaration:");
2526 debug_tree (e->callee->symbol.decl);
2527 fprintf (stderr," Instead of:");
2528 debug_tree (decl);
2529 error_found = true;
2532 else if (decl)
2534 error ("an indirect edge with unknown callee "
2535 "corresponding to a call_stmt with "
2536 "a known declaration:");
2537 error_found = true;
2538 cgraph_debug_gimple_stmt (this_cfun, e->call_stmt);
2540 e->aux = (void *)1;
2542 else if (decl)
2544 error ("missing callgraph edge for call stmt:");
2545 cgraph_debug_gimple_stmt (this_cfun, stmt);
2546 error_found = true;
2551 else
2552 /* No CFG available?! */
2553 gcc_unreachable ();
2555 for (e = node->callees; e; e = e->next_callee)
2557 if (!e->aux)
2559 error ("edge %s->%s has no corresponding call_stmt",
2560 identifier_to_locale (cgraph_node_name (e->caller)),
2561 identifier_to_locale (cgraph_node_name (e->callee)));
2562 cgraph_debug_gimple_stmt (this_cfun, e->call_stmt);
2563 error_found = true;
2565 e->aux = 0;
2567 for (e = node->indirect_calls; e; e = e->next_callee)
2569 if (!e->aux)
2571 error ("an indirect edge from %s has no corresponding call_stmt",
2572 identifier_to_locale (cgraph_node_name (e->caller)));
2573 cgraph_debug_gimple_stmt (this_cfun, e->call_stmt);
2574 error_found = true;
2576 e->aux = 0;
2579 if (error_found)
2581 dump_cgraph_node (stderr, node);
2582 internal_error ("verify_cgraph_node failed");
2584 timevar_pop (TV_CGRAPH_VERIFY);
2587 /* Verify whole cgraph structure. */
2588 DEBUG_FUNCTION void
2589 verify_cgraph (void)
2591 struct cgraph_node *node;
2593 if (seen_error ())
2594 return;
2596 FOR_EACH_FUNCTION (node)
2597 verify_cgraph_node (node);
2599 #include "gt-cgraph.h"