remove unused files
[platform/upstream/gcc48.git] / gcc / cgraph.c
1 /* Callgraph handling code.
2    Copyright (C) 2003-2013 Free Software Foundation, Inc.
3    Contributed by Jan Hubicka
4
5 This file is part of GCC.
6
7 GCC is free software; you can redistribute it and/or modify it under
8 the terms of the GNU General Public License as published by the Free
9 Software Foundation; either version 3, or (at your option) any later
10 version.
11
12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13 WARRANTY; without even the implied warranty of MERCHANTABILITY or
14 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
15 for more details.
16
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING3.  If not see
19 <http://www.gnu.org/licenses/>.  */
20
21 /*  This file contains basic routines manipulating call graph
22
23     The call-graph is a data structure designed for intra-procedural optimization.
24     It represents a multi-graph where nodes are functions and edges are call sites. */
25
26 #include "config.h"
27 #include "system.h"
28 #include "coretypes.h"
29 #include "tm.h"
30 #include "tree.h"
31 #include "tree-inline.h"
32 #include "langhooks.h"
33 #include "hashtab.h"
34 #include "toplev.h"
35 #include "flags.h"
36 #include "ggc.h"
37 #include "debug.h"
38 #include "target.h"
39 #include "basic-block.h"
40 #include "cgraph.h"
41 #include "intl.h"
42 #include "gimple.h"
43 #include "timevar.h"
44 #include "dumpfile.h"
45 #include "tree-flow.h"
46 #include "value-prof.h"
47 #include "except.h"
48 #include "diagnostic-core.h"
49 #include "rtl.h"
50 #include "ipa-utils.h"
51 #include "lto-streamer.h"
52 #include "ipa-inline.h"
53 #include "cfgloop.h"
54 #include "gimple-pretty-print.h"
55
56 /* FIXME: Only for PROP_loops, but cgraph shouldn't have to know about this.  */
57 #include "tree-pass.h"
58
59 static void cgraph_node_remove_callers (struct cgraph_node *node);
60 static inline void cgraph_edge_remove_caller (struct cgraph_edge *e);
61 static inline void cgraph_edge_remove_callee (struct cgraph_edge *e);
62
63 /* Queue of cgraph nodes scheduled to be lowered.  */
64 symtab_node x_cgraph_nodes_queue;
65 #define cgraph_nodes_queue ((struct cgraph_node *)x_cgraph_nodes_queue)
66
67 /* Number of nodes in existence.  */
68 int cgraph_n_nodes;
69
70 /* Maximal uid used in cgraph nodes.  */
71 int cgraph_max_uid;
72
73 /* Maximal uid used in cgraph edges.  */
74 int cgraph_edge_max_uid;
75
76 /* Set when whole unit has been analyzed so we can access global info.  */
77 bool cgraph_global_info_ready = false;
78
79 /* What state callgraph is in right now.  */
80 enum cgraph_state cgraph_state = CGRAPH_STATE_PARSING;
81
82 /* Set when the cgraph is fully build and the basic flags are computed.  */
83 bool cgraph_function_flags_ready = false;
84
85 /* List of hooks triggered on cgraph_edge events.  */
86 struct cgraph_edge_hook_list {
87   cgraph_edge_hook hook;
88   void *data;
89   struct cgraph_edge_hook_list *next;
90 };
91
92 /* List of hooks triggered on cgraph_node events.  */
93 struct cgraph_node_hook_list {
94   cgraph_node_hook hook;
95   void *data;
96   struct cgraph_node_hook_list *next;
97 };
98
99 /* List of hooks triggered on events involving two cgraph_edges.  */
100 struct cgraph_2edge_hook_list {
101   cgraph_2edge_hook hook;
102   void *data;
103   struct cgraph_2edge_hook_list *next;
104 };
105
106 /* List of hooks triggered on events involving two cgraph_nodes.  */
107 struct cgraph_2node_hook_list {
108   cgraph_2node_hook hook;
109   void *data;
110   struct cgraph_2node_hook_list *next;
111 };
112
113 /* List of hooks triggered when an edge is removed.  */
114 struct cgraph_edge_hook_list *first_cgraph_edge_removal_hook;
115 /* List of hooks triggered when a node is removed.  */
116 struct cgraph_node_hook_list *first_cgraph_node_removal_hook;
117 /* List of hooks triggered when an edge is duplicated.  */
118 struct cgraph_2edge_hook_list *first_cgraph_edge_duplicated_hook;
119 /* List of hooks triggered when a node is duplicated.  */
120 struct cgraph_2node_hook_list *first_cgraph_node_duplicated_hook;
121 /* List of hooks triggered when an function is inserted.  */
122 struct cgraph_node_hook_list *first_cgraph_function_insertion_hook;
123
124 /* Head of a linked list of unused (freed) call graph nodes.
125    Do not GTY((delete)) this list so UIDs gets reliably recycled.  */
126 static GTY(()) struct cgraph_node *free_nodes;
127 /* Head of a linked list of unused (freed) call graph edges.
128    Do not GTY((delete)) this list so UIDs gets reliably recycled.  */
129 static GTY(()) struct cgraph_edge *free_edges;
130
131 /* Did procss_same_body_aliases run?  */
132 bool same_body_aliases_done;
133
134 /* Map a cgraph_node to cgraph_function_version_info using this htab.
135    The cgraph_function_version_info has a THIS_NODE field that is the
136    corresponding cgraph_node..  */
137
138 static htab_t GTY((param_is (struct cgraph_function_version_info *)))
139   cgraph_fnver_htab = NULL;
140
141 /* Hash function for cgraph_fnver_htab.  */
142 static hashval_t
143 cgraph_fnver_htab_hash (const void *ptr)
144 {
145   int uid = ((const struct cgraph_function_version_info *)ptr)->this_node->uid;
146   return (hashval_t)(uid);
147 }
148
149 /* eq function for cgraph_fnver_htab.  */
150 static int
151 cgraph_fnver_htab_eq (const void *p1, const void *p2)
152 {
153   const struct cgraph_function_version_info *n1
154     = (const struct cgraph_function_version_info *)p1;
155   const struct cgraph_function_version_info *n2
156     = (const struct cgraph_function_version_info *)p2;
157
158   return n1->this_node->uid == n2->this_node->uid;
159 }
160
161 /* Mark as GC root all allocated nodes.  */
162 static GTY(()) struct cgraph_function_version_info *
163   version_info_node = NULL;
164
165 /* Get the cgraph_function_version_info node corresponding to node.  */
166 struct cgraph_function_version_info *
167 get_cgraph_node_version (struct cgraph_node *node)
168 {
169   struct cgraph_function_version_info *ret;
170   struct cgraph_function_version_info key;
171   key.this_node = node;
172
173   if (cgraph_fnver_htab == NULL)
174     return NULL;
175
176   ret = (struct cgraph_function_version_info *)
177     htab_find (cgraph_fnver_htab, &key);
178
179   return ret;
180 }
181
182 /* Insert a new cgraph_function_version_info node into cgraph_fnver_htab
183    corresponding to cgraph_node NODE.  */
184 struct cgraph_function_version_info *
185 insert_new_cgraph_node_version (struct cgraph_node *node)
186 {
187   void **slot;
188   
189   version_info_node = NULL;
190   version_info_node = ggc_alloc_cleared_cgraph_function_version_info ();
191   version_info_node->this_node = node;
192
193   if (cgraph_fnver_htab == NULL)
194     cgraph_fnver_htab = htab_create_ggc (2, cgraph_fnver_htab_hash,
195                                          cgraph_fnver_htab_eq, NULL);
196
197   slot = htab_find_slot (cgraph_fnver_htab, version_info_node, INSERT);
198   gcc_assert (slot != NULL);
199   *slot = version_info_node;
200   return version_info_node;
201 }
202
203 /* Remove the cgraph_function_version_info and cgraph_node for DECL.  This
204    DECL is a duplicate declaration.  */
205 void
206 delete_function_version (tree decl)
207 {
208   struct cgraph_node *decl_node = cgraph_get_node (decl);
209   struct cgraph_function_version_info *decl_v = NULL;
210
211   if (decl_node == NULL)
212     return;
213
214   decl_v = get_cgraph_node_version (decl_node);
215
216   if (decl_v == NULL)
217     return;
218
219   if (decl_v->prev != NULL)
220    decl_v->prev->next = decl_v->next;
221
222   if (decl_v->next != NULL)
223     decl_v->next->prev = decl_v->prev;
224
225   if (cgraph_fnver_htab != NULL)
226     htab_remove_elt (cgraph_fnver_htab, decl_v);
227
228   cgraph_remove_node (decl_node);
229 }
230
231 /* Record that DECL1 and DECL2 are semantically identical function
232    versions.  */
233 void
234 record_function_versions (tree decl1, tree decl2)
235 {
236   struct cgraph_node *decl1_node = cgraph_get_create_node (decl1);
237   struct cgraph_node *decl2_node = cgraph_get_create_node (decl2);
238   struct cgraph_function_version_info *decl1_v = NULL;
239   struct cgraph_function_version_info *decl2_v = NULL;
240   struct cgraph_function_version_info *before;
241   struct cgraph_function_version_info *after;
242
243   gcc_assert (decl1_node != NULL && decl2_node != NULL);
244   decl1_v = get_cgraph_node_version (decl1_node);
245   decl2_v = get_cgraph_node_version (decl2_node);
246
247   if (decl1_v != NULL && decl2_v != NULL)
248     return;
249
250   if (decl1_v == NULL)
251     decl1_v = insert_new_cgraph_node_version (decl1_node);
252
253   if (decl2_v == NULL)
254     decl2_v = insert_new_cgraph_node_version (decl2_node);
255
256   /* Chain decl2_v and decl1_v.  All semantically identical versions
257      will be chained together.  */
258
259   before = decl1_v;
260   after = decl2_v;
261
262   while (before->next != NULL)
263     before = before->next;
264
265   while (after->prev != NULL)
266     after= after->prev;
267
268   before->next = after;
269   after->prev = before;
270 }
271
272 /* Macros to access the next item in the list of free cgraph nodes and
273    edges. */
274 #define NEXT_FREE_NODE(NODE) cgraph ((NODE)->symbol.next)
275 #define SET_NEXT_FREE_NODE(NODE,NODE2) ((NODE))->symbol.next = (symtab_node)NODE2
276 #define NEXT_FREE_EDGE(EDGE) (EDGE)->prev_caller
277
278 /* Register HOOK to be called with DATA on each removed edge.  */
279 struct cgraph_edge_hook_list *
280 cgraph_add_edge_removal_hook (cgraph_edge_hook hook, void *data)
281 {
282   struct cgraph_edge_hook_list *entry;
283   struct cgraph_edge_hook_list **ptr = &first_cgraph_edge_removal_hook;
284
285   entry = (struct cgraph_edge_hook_list *) xmalloc (sizeof (*entry));
286   entry->hook = hook;
287   entry->data = data;
288   entry->next = NULL;
289   while (*ptr)
290     ptr = &(*ptr)->next;
291   *ptr = entry;
292   return entry;
293 }
294
295 /* Remove ENTRY from the list of hooks called on removing edges.  */
296 void
297 cgraph_remove_edge_removal_hook (struct cgraph_edge_hook_list *entry)
298 {
299   struct cgraph_edge_hook_list **ptr = &first_cgraph_edge_removal_hook;
300
301   while (*ptr != entry)
302     ptr = &(*ptr)->next;
303   *ptr = entry->next;
304   free (entry);
305 }
306
307 /* Call all edge removal hooks.  */
308 static void
309 cgraph_call_edge_removal_hooks (struct cgraph_edge *e)
310 {
311   struct cgraph_edge_hook_list *entry = first_cgraph_edge_removal_hook;
312   while (entry)
313   {
314     entry->hook (e, entry->data);
315     entry = entry->next;
316   }
317 }
318
319 /* Register HOOK to be called with DATA on each removed node.  */
320 struct cgraph_node_hook_list *
321 cgraph_add_node_removal_hook (cgraph_node_hook hook, void *data)
322 {
323   struct cgraph_node_hook_list *entry;
324   struct cgraph_node_hook_list **ptr = &first_cgraph_node_removal_hook;
325
326   entry = (struct cgraph_node_hook_list *) xmalloc (sizeof (*entry));
327   entry->hook = hook;
328   entry->data = data;
329   entry->next = NULL;
330   while (*ptr)
331     ptr = &(*ptr)->next;
332   *ptr = entry;
333   return entry;
334 }
335
336 /* Remove ENTRY from the list of hooks called on removing nodes.  */
337 void
338 cgraph_remove_node_removal_hook (struct cgraph_node_hook_list *entry)
339 {
340   struct cgraph_node_hook_list **ptr = &first_cgraph_node_removal_hook;
341
342   while (*ptr != entry)
343     ptr = &(*ptr)->next;
344   *ptr = entry->next;
345   free (entry);
346 }
347
348 /* Call all node removal hooks.  */
349 static void
350 cgraph_call_node_removal_hooks (struct cgraph_node *node)
351 {
352   struct cgraph_node_hook_list *entry = first_cgraph_node_removal_hook;
353   while (entry)
354   {
355     entry->hook (node, entry->data);
356     entry = entry->next;
357   }
358 }
359
360 /* Register HOOK to be called with DATA on each inserted node.  */
361 struct cgraph_node_hook_list *
362 cgraph_add_function_insertion_hook (cgraph_node_hook hook, void *data)
363 {
364   struct cgraph_node_hook_list *entry;
365   struct cgraph_node_hook_list **ptr = &first_cgraph_function_insertion_hook;
366
367   entry = (struct cgraph_node_hook_list *) xmalloc (sizeof (*entry));
368   entry->hook = hook;
369   entry->data = data;
370   entry->next = NULL;
371   while (*ptr)
372     ptr = &(*ptr)->next;
373   *ptr = entry;
374   return entry;
375 }
376
377 /* Remove ENTRY from the list of hooks called on inserted nodes.  */
378 void
379 cgraph_remove_function_insertion_hook (struct cgraph_node_hook_list *entry)
380 {
381   struct cgraph_node_hook_list **ptr = &first_cgraph_function_insertion_hook;
382
383   while (*ptr != entry)
384     ptr = &(*ptr)->next;
385   *ptr = entry->next;
386   free (entry);
387 }
388
389 /* Call all node insertion hooks.  */
390 void
391 cgraph_call_function_insertion_hooks (struct cgraph_node *node)
392 {
393   struct cgraph_node_hook_list *entry = first_cgraph_function_insertion_hook;
394   while (entry)
395   {
396     entry->hook (node, entry->data);
397     entry = entry->next;
398   }
399 }
400
401 /* Register HOOK to be called with DATA on each duplicated edge.  */
402 struct cgraph_2edge_hook_list *
403 cgraph_add_edge_duplication_hook (cgraph_2edge_hook hook, void *data)
404 {
405   struct cgraph_2edge_hook_list *entry;
406   struct cgraph_2edge_hook_list **ptr = &first_cgraph_edge_duplicated_hook;
407
408   entry = (struct cgraph_2edge_hook_list *) xmalloc (sizeof (*entry));
409   entry->hook = hook;
410   entry->data = data;
411   entry->next = NULL;
412   while (*ptr)
413     ptr = &(*ptr)->next;
414   *ptr = entry;
415   return entry;
416 }
417
418 /* Remove ENTRY from the list of hooks called on duplicating edges.  */
419 void
420 cgraph_remove_edge_duplication_hook (struct cgraph_2edge_hook_list *entry)
421 {
422   struct cgraph_2edge_hook_list **ptr = &first_cgraph_edge_duplicated_hook;
423
424   while (*ptr != entry)
425     ptr = &(*ptr)->next;
426   *ptr = entry->next;
427   free (entry);
428 }
429
430 /* Call all edge duplication hooks.  */
431 void
432 cgraph_call_edge_duplication_hooks (struct cgraph_edge *cs1,
433                                     struct cgraph_edge *cs2)
434 {
435   struct cgraph_2edge_hook_list *entry = first_cgraph_edge_duplicated_hook;
436   while (entry)
437   {
438     entry->hook (cs1, cs2, entry->data);
439     entry = entry->next;
440   }
441 }
442
443 /* Register HOOK to be called with DATA on each duplicated node.  */
444 struct cgraph_2node_hook_list *
445 cgraph_add_node_duplication_hook (cgraph_2node_hook hook, void *data)
446 {
447   struct cgraph_2node_hook_list *entry;
448   struct cgraph_2node_hook_list **ptr = &first_cgraph_node_duplicated_hook;
449
450   entry = (struct cgraph_2node_hook_list *) xmalloc (sizeof (*entry));
451   entry->hook = hook;
452   entry->data = data;
453   entry->next = NULL;
454   while (*ptr)
455     ptr = &(*ptr)->next;
456   *ptr = entry;
457   return entry;
458 }
459
460 /* Remove ENTRY from the list of hooks called on duplicating nodes.  */
461 void
462 cgraph_remove_node_duplication_hook (struct cgraph_2node_hook_list *entry)
463 {
464   struct cgraph_2node_hook_list **ptr = &first_cgraph_node_duplicated_hook;
465
466   while (*ptr != entry)
467     ptr = &(*ptr)->next;
468   *ptr = entry->next;
469   free (entry);
470 }
471
472 /* Call all node duplication hooks.  */
473 void
474 cgraph_call_node_duplication_hooks (struct cgraph_node *node1,
475                                     struct cgraph_node *node2)
476 {
477   struct cgraph_2node_hook_list *entry = first_cgraph_node_duplicated_hook;
478   while (entry)
479   {
480     entry->hook (node1, node2, entry->data);
481     entry = entry->next;
482   }
483 }
484
485 /* Allocate new callgraph node.  */
486
487 static inline struct cgraph_node *
488 cgraph_allocate_node (void)
489 {
490   struct cgraph_node *node;
491
492   if (free_nodes)
493     {
494       node = free_nodes;
495       free_nodes = NEXT_FREE_NODE (node);
496     }
497   else
498     {
499       node = ggc_alloc_cleared_cgraph_node ();
500       node->uid = cgraph_max_uid++;
501     }
502
503   return node;
504 }
505
506 /* Allocate new callgraph node and insert it into basic data structures.  */
507
508 struct cgraph_node *
509 cgraph_create_empty_node (void)
510 {
511   struct cgraph_node *node = cgraph_allocate_node ();
512
513   node->symbol.type = SYMTAB_FUNCTION;
514   node->frequency = NODE_FREQUENCY_NORMAL;
515   node->count_materialization_scale = REG_BR_PROB_BASE;
516   cgraph_n_nodes++;
517   return node;
518 }
519
520 /* Return cgraph node assigned to DECL.  Create new one when needed.  */
521
522 struct cgraph_node *
523 cgraph_create_node (tree decl)
524 {
525   struct cgraph_node *node = cgraph_create_empty_node ();
526   gcc_assert (TREE_CODE (decl) == FUNCTION_DECL);
527
528   node->symbol.decl = decl;
529   symtab_register_node ((symtab_node) node);
530
531   if (DECL_CONTEXT (decl) && TREE_CODE (DECL_CONTEXT (decl)) == FUNCTION_DECL)
532     {
533       node->origin = cgraph_get_create_node (DECL_CONTEXT (decl));
534       node->next_nested = node->origin->nested;
535       node->origin->nested = node;
536     }
537   return node;
538 }
539
540 /* Try to find a call graph node for declaration DECL and if it does not exist,
541    create it.  */
542
543 struct cgraph_node *
544 cgraph_get_create_node (tree decl)
545 {
546   struct cgraph_node *node;
547
548   node = cgraph_get_node (decl);
549   if (node)
550     return node;
551
552   return cgraph_create_node (decl);
553 }
554
555 /* Mark ALIAS as an alias to DECL.  DECL_NODE is cgraph node representing
556    the function body is associated with (not necessarily cgraph_node (DECL).  */
557
558 struct cgraph_node *
559 cgraph_create_function_alias (tree alias, tree decl)
560 {
561   struct cgraph_node *alias_node;
562
563   gcc_assert (TREE_CODE (decl) == FUNCTION_DECL);
564   gcc_assert (TREE_CODE (alias) == FUNCTION_DECL);
565   alias_node = cgraph_get_create_node (alias);
566   gcc_assert (!alias_node->local.finalized);
567   alias_node->thunk.alias = decl;
568   alias_node->local.finalized = true;
569   alias_node->alias = 1;
570   return alias_node;
571 }
572
573 /* Attempt to mark ALIAS as an alias to DECL.  Return alias node if successful
574    and NULL otherwise.
575    Same body aliases are output whenever the body of DECL is output,
576    and cgraph_get_node (ALIAS) transparently returns cgraph_get_node (DECL).  */
577
578 struct cgraph_node *
579 cgraph_same_body_alias (struct cgraph_node *decl_node ATTRIBUTE_UNUSED, tree alias, tree decl)
580 {
581   struct cgraph_node *n;
582 #ifndef ASM_OUTPUT_DEF
583   /* If aliases aren't supported by the assembler, fail.  */
584   return NULL;
585 #endif
586   /* Langhooks can create same body aliases of symbols not defined.
587      Those are useless. Drop them on the floor.  */
588   if (cgraph_global_info_ready)
589     return NULL;
590
591   n = cgraph_create_function_alias (alias, decl);
592   n->same_body_alias = true;
593   if (same_body_aliases_done)
594     ipa_record_reference ((symtab_node)n, (symtab_node)cgraph_get_node (decl),
595                           IPA_REF_ALIAS, NULL);
596   return n;
597 }
598
599 /* Add thunk alias into callgraph.  The alias declaration is ALIAS and it
600    aliases DECL with an adjustments made into the first parameter.
601    See comments in thunk_adjust for detail on the parameters.  */
602
603 struct cgraph_node *
604 cgraph_add_thunk (struct cgraph_node *decl_node ATTRIBUTE_UNUSED,
605                   tree alias, tree decl ATTRIBUTE_UNUSED,
606                   bool this_adjusting,
607                   HOST_WIDE_INT fixed_offset, HOST_WIDE_INT virtual_value,
608                   tree virtual_offset,
609                   tree real_alias)
610 {
611   struct cgraph_node *node;
612
613   node = cgraph_get_node (alias);
614   if (node)
615     {
616       gcc_assert (node->local.finalized);
617       gcc_assert (!node->alias);
618       gcc_assert (!node->thunk.thunk_p);
619       cgraph_remove_node (node);
620     }
621   
622   node = cgraph_create_node (alias);
623   gcc_checking_assert (!virtual_offset
624                        || tree_to_double_int (virtual_offset) ==
625                              double_int::from_shwi (virtual_value));
626   node->thunk.fixed_offset = fixed_offset;
627   node->thunk.this_adjusting = this_adjusting;
628   node->thunk.virtual_value = virtual_value;
629   node->thunk.virtual_offset_p = virtual_offset != NULL;
630   node->thunk.alias = real_alias;
631   node->thunk.thunk_p = true;
632   node->local.finalized = true;
633
634   return node;
635 }
636
637 /* Return the cgraph node that has ASMNAME for its DECL_ASSEMBLER_NAME.
638    Return NULL if there's no such node.  */
639
640 struct cgraph_node *
641 cgraph_node_for_asm (tree asmname)
642 {
643   /* We do not want to look at inline clones.  */
644   for (symtab_node node = symtab_node_for_asm (asmname);
645        node;
646        node = node->symbol.next_sharing_asm_name)
647     {
648       cgraph_node *cn = dyn_cast <cgraph_node> (node);
649       if (cn && !cn->global.inlined_to)
650         return cn;
651     }
652   return NULL;
653 }
654
655 /* Returns a hash value for X (which really is a cgraph_edge).  */
656
657 static hashval_t
658 edge_hash (const void *x)
659 {
660   return htab_hash_pointer (((const struct cgraph_edge *) x)->call_stmt);
661 }
662
663 /* Return nonzero if the call_stmt of of cgraph_edge X is stmt *Y.  */
664
665 static int
666 edge_eq (const void *x, const void *y)
667 {
668   return ((const struct cgraph_edge *) x)->call_stmt == y;
669 }
670
671 /* Add call graph edge E to call site hash of its caller.  */
672
673 static inline void
674 cgraph_add_edge_to_call_site_hash (struct cgraph_edge *e)
675 {
676   void **slot;
677   slot = htab_find_slot_with_hash (e->caller->call_site_hash,
678                                    e->call_stmt,
679                                    htab_hash_pointer (e->call_stmt),
680                                    INSERT);
681   gcc_assert (!*slot);
682   *slot = e;
683 }
684
685 /* Return the callgraph edge representing the GIMPLE_CALL statement
686    CALL_STMT.  */
687
688 struct cgraph_edge *
689 cgraph_edge (struct cgraph_node *node, gimple call_stmt)
690 {
691   struct cgraph_edge *e, *e2;
692   int n = 0;
693
694   if (node->call_site_hash)
695     return (struct cgraph_edge *)
696       htab_find_with_hash (node->call_site_hash, call_stmt,
697                            htab_hash_pointer (call_stmt));
698
699   /* This loop may turn out to be performance problem.  In such case adding
700      hashtables into call nodes with very many edges is probably best
701      solution.  It is not good idea to add pointer into CALL_EXPR itself
702      because we want to make possible having multiple cgraph nodes representing
703      different clones of the same body before the body is actually cloned.  */
704   for (e = node->callees; e; e = e->next_callee)
705     {
706       if (e->call_stmt == call_stmt)
707         break;
708       n++;
709     }
710
711   if (!e)
712     for (e = node->indirect_calls; e; e = e->next_callee)
713       {
714         if (e->call_stmt == call_stmt)
715           break;
716         n++;
717       }
718
719   if (n > 100)
720     {
721       node->call_site_hash = htab_create_ggc (120, edge_hash, edge_eq, NULL);
722       for (e2 = node->callees; e2; e2 = e2->next_callee)
723         cgraph_add_edge_to_call_site_hash (e2);
724       for (e2 = node->indirect_calls; e2; e2 = e2->next_callee)
725         cgraph_add_edge_to_call_site_hash (e2);
726     }
727
728   return e;
729 }
730
731
732 /* Change field call_stmt of edge E to NEW_STMT.  */
733
734 void
735 cgraph_set_call_stmt (struct cgraph_edge *e, gimple new_stmt)
736 {
737   tree decl;
738
739   if (e->caller->call_site_hash)
740     {
741       htab_remove_elt_with_hash (e->caller->call_site_hash,
742                                  e->call_stmt,
743                                  htab_hash_pointer (e->call_stmt));
744     }
745
746   e->call_stmt = new_stmt;
747   if (e->indirect_unknown_callee
748       && (decl = gimple_call_fndecl (new_stmt)))
749     {
750       /* Constant propagation (and possibly also inlining?) can turn an
751          indirect call into a direct one.  */
752       struct cgraph_node *new_callee = cgraph_get_node (decl);
753
754       gcc_checking_assert (new_callee);
755       cgraph_make_edge_direct (e, new_callee);
756     }
757
758   push_cfun (DECL_STRUCT_FUNCTION (e->caller->symbol.decl));
759   e->can_throw_external = stmt_can_throw_external (new_stmt);
760   pop_cfun ();
761   if (e->caller->call_site_hash)
762     cgraph_add_edge_to_call_site_hash (e);
763 }
764
765 /* Allocate a cgraph_edge structure and fill it with data according to the
766    parameters of which only CALLEE can be NULL (when creating an indirect call
767    edge).  */
768
769 static struct cgraph_edge *
770 cgraph_create_edge_1 (struct cgraph_node *caller, struct cgraph_node *callee,
771                        gimple call_stmt, gcov_type count, int freq)
772 {
773   struct cgraph_edge *edge;
774
775   /* LTO does not actually have access to the call_stmt since these
776      have not been loaded yet.  */
777   if (call_stmt)
778     {
779       /* This is a rather expensive check possibly triggering
780          construction of call stmt hashtable.  */
781       gcc_checking_assert (!cgraph_edge (caller, call_stmt));
782
783       gcc_assert (is_gimple_call (call_stmt));
784     }
785
786   if (free_edges)
787     {
788       edge = free_edges;
789       free_edges = NEXT_FREE_EDGE (edge);
790     }
791   else
792     {
793       edge = ggc_alloc_cgraph_edge ();
794       edge->uid = cgraph_edge_max_uid++;
795     }
796
797   edge->aux = NULL;
798   edge->caller = caller;
799   edge->callee = callee;
800   edge->prev_caller = NULL;
801   edge->next_caller = NULL;
802   edge->prev_callee = NULL;
803   edge->next_callee = NULL;
804
805   edge->count = count;
806   gcc_assert (count >= 0);
807   edge->frequency = freq;
808   gcc_assert (freq >= 0);
809   gcc_assert (freq <= CGRAPH_FREQ_MAX);
810
811   edge->call_stmt = call_stmt;
812   push_cfun (DECL_STRUCT_FUNCTION (caller->symbol.decl));
813   edge->can_throw_external
814     = call_stmt ? stmt_can_throw_external (call_stmt) : false;
815   pop_cfun ();
816   if (call_stmt
817       && callee && callee->symbol.decl
818       && !gimple_check_call_matching_types (call_stmt, callee->symbol.decl))
819     edge->call_stmt_cannot_inline_p = true;
820   else
821     edge->call_stmt_cannot_inline_p = false;
822   if (call_stmt && caller->call_site_hash)
823     cgraph_add_edge_to_call_site_hash (edge);
824
825   edge->indirect_info = NULL;
826   edge->indirect_inlining_edge = 0;
827
828   return edge;
829 }
830
831 /* Create edge from CALLER to CALLEE in the cgraph.  */
832
833 struct cgraph_edge *
834 cgraph_create_edge (struct cgraph_node *caller, struct cgraph_node *callee,
835                     gimple call_stmt, gcov_type count, int freq)
836 {
837   struct cgraph_edge *edge = cgraph_create_edge_1 (caller, callee, call_stmt,
838                                                    count, freq);
839
840   edge->indirect_unknown_callee = 0;
841   initialize_inline_failed (edge);
842
843   edge->next_caller = callee->callers;
844   if (callee->callers)
845     callee->callers->prev_caller = edge;
846   edge->next_callee = caller->callees;
847   if (caller->callees)
848     caller->callees->prev_callee = edge;
849   caller->callees = edge;
850   callee->callers = edge;
851
852   return edge;
853 }
854
855 /* Allocate cgraph_indirect_call_info and set its fields to default values. */
856
857 struct cgraph_indirect_call_info *
858 cgraph_allocate_init_indirect_info (void)
859 {
860   struct cgraph_indirect_call_info *ii;
861
862   ii = ggc_alloc_cleared_cgraph_indirect_call_info ();
863   ii->param_index = -1;
864   return ii;
865 }
866
867 /* Create an indirect edge with a yet-undetermined callee where the call
868    statement destination is a formal parameter of the caller with index
869    PARAM_INDEX. */
870
871 struct cgraph_edge *
872 cgraph_create_indirect_edge (struct cgraph_node *caller, gimple call_stmt,
873                              int ecf_flags,
874                              gcov_type count, int freq)
875 {
876   struct cgraph_edge *edge = cgraph_create_edge_1 (caller, NULL, call_stmt,
877                                                    count, freq);
878
879   edge->indirect_unknown_callee = 1;
880   initialize_inline_failed (edge);
881
882   edge->indirect_info = cgraph_allocate_init_indirect_info ();
883   edge->indirect_info->ecf_flags = ecf_flags;
884
885   edge->next_callee = caller->indirect_calls;
886   if (caller->indirect_calls)
887     caller->indirect_calls->prev_callee = edge;
888   caller->indirect_calls = edge;
889
890   return edge;
891 }
892
893 /* Remove the edge E from the list of the callers of the callee.  */
894
895 static inline void
896 cgraph_edge_remove_callee (struct cgraph_edge *e)
897 {
898   gcc_assert (!e->indirect_unknown_callee);
899   if (e->prev_caller)
900     e->prev_caller->next_caller = e->next_caller;
901   if (e->next_caller)
902     e->next_caller->prev_caller = e->prev_caller;
903   if (!e->prev_caller)
904     e->callee->callers = e->next_caller;
905 }
906
907 /* Remove the edge E from the list of the callees of the caller.  */
908
909 static inline void
910 cgraph_edge_remove_caller (struct cgraph_edge *e)
911 {
912   if (e->prev_callee)
913     e->prev_callee->next_callee = e->next_callee;
914   if (e->next_callee)
915     e->next_callee->prev_callee = e->prev_callee;
916   if (!e->prev_callee)
917     {
918       if (e->indirect_unknown_callee)
919         e->caller->indirect_calls = e->next_callee;
920       else
921         e->caller->callees = e->next_callee;
922     }
923   if (e->caller->call_site_hash)
924     htab_remove_elt_with_hash (e->caller->call_site_hash,
925                                e->call_stmt,
926                                htab_hash_pointer (e->call_stmt));
927 }
928
929 /* Put the edge onto the free list.  */
930
931 static void
932 cgraph_free_edge (struct cgraph_edge *e)
933 {
934   int uid = e->uid;
935
936   /* Clear out the edge so we do not dangle pointers.  */
937   memset (e, 0, sizeof (*e));
938   e->uid = uid;
939   NEXT_FREE_EDGE (e) = free_edges;
940   free_edges = e;
941 }
942
943 /* Remove the edge E in the cgraph.  */
944
945 void
946 cgraph_remove_edge (struct cgraph_edge *e)
947 {
948   /* Call all edge removal hooks.  */
949   cgraph_call_edge_removal_hooks (e);
950
951   if (!e->indirect_unknown_callee)
952     /* Remove from callers list of the callee.  */
953     cgraph_edge_remove_callee (e);
954
955   /* Remove from callees list of the callers.  */
956   cgraph_edge_remove_caller (e);
957
958   /* Put the edge onto the free list.  */
959   cgraph_free_edge (e);
960 }
961
962 /* Set callee of call graph edge E and add it to the corresponding set of
963    callers. */
964
965 static void
966 cgraph_set_edge_callee (struct cgraph_edge *e, struct cgraph_node *n)
967 {
968   e->prev_caller = NULL;
969   if (n->callers)
970     n->callers->prev_caller = e;
971   e->next_caller = n->callers;
972   n->callers = e;
973   e->callee = n;
974 }
975
976 /* Redirect callee of E to N.  The function does not update underlying
977    call expression.  */
978
979 void
980 cgraph_redirect_edge_callee (struct cgraph_edge *e, struct cgraph_node *n)
981 {
982   /* Remove from callers list of the current callee.  */
983   cgraph_edge_remove_callee (e);
984
985   /* Insert to callers list of the new callee.  */
986   cgraph_set_edge_callee (e, n);
987 }
988
989 /* Make an indirect EDGE with an unknown callee an ordinary edge leading to
990    CALLEE.  DELTA is an integer constant that is to be added to the this
991    pointer (first parameter) to compensate for skipping a thunk adjustment.  */
992
993 void
994 cgraph_make_edge_direct (struct cgraph_edge *edge, struct cgraph_node *callee)
995 {
996   edge->indirect_unknown_callee = 0;
997
998   /* Get the edge out of the indirect edge list. */
999   if (edge->prev_callee)
1000     edge->prev_callee->next_callee = edge->next_callee;
1001   if (edge->next_callee)
1002     edge->next_callee->prev_callee = edge->prev_callee;
1003   if (!edge->prev_callee)
1004     edge->caller->indirect_calls = edge->next_callee;
1005
1006   /* Put it into the normal callee list */
1007   edge->prev_callee = NULL;
1008   edge->next_callee = edge->caller->callees;
1009   if (edge->caller->callees)
1010     edge->caller->callees->prev_callee = edge;
1011   edge->caller->callees = edge;
1012
1013   /* Insert to callers list of the new callee.  */
1014   cgraph_set_edge_callee (edge, callee);
1015
1016   if (edge->call_stmt)
1017     edge->call_stmt_cannot_inline_p
1018       = !gimple_check_call_matching_types (edge->call_stmt, callee->symbol.decl);
1019
1020   /* We need to re-determine the inlining status of the edge.  */
1021   initialize_inline_failed (edge);
1022 }
1023
1024 /* If necessary, change the function declaration in the call statement
1025    associated with E so that it corresponds to the edge callee.  */
1026
1027 gimple
1028 cgraph_redirect_edge_call_stmt_to_callee (struct cgraph_edge *e)
1029 {
1030   tree decl = gimple_call_fndecl (e->call_stmt);
1031   gimple new_stmt;
1032   gimple_stmt_iterator gsi;
1033 #ifdef ENABLE_CHECKING
1034   struct cgraph_node *node;
1035 #endif
1036
1037   if (e->indirect_unknown_callee
1038       || decl == e->callee->symbol.decl)
1039     return e->call_stmt;
1040
1041 #ifdef ENABLE_CHECKING
1042   if (decl)
1043     {
1044       node = cgraph_get_node (decl);
1045       gcc_assert (!node || !node->clone.combined_args_to_skip);
1046     }
1047 #endif
1048
1049   if (cgraph_dump_file)
1050     {
1051       fprintf (cgraph_dump_file, "updating call of %s/%i -> %s/%i: ",
1052                xstrdup (cgraph_node_name (e->caller)), e->caller->uid,
1053                xstrdup (cgraph_node_name (e->callee)), e->callee->uid);
1054       print_gimple_stmt (cgraph_dump_file, e->call_stmt, 0, dump_flags);
1055       if (e->callee->clone.combined_args_to_skip)
1056         {
1057           fprintf (cgraph_dump_file, " combined args to skip: ");
1058           dump_bitmap (cgraph_dump_file,
1059                        e->callee->clone.combined_args_to_skip);
1060         }
1061     }
1062
1063   if (e->callee->clone.combined_args_to_skip)
1064     {
1065       int lp_nr;
1066
1067       new_stmt
1068         = gimple_call_copy_skip_args (e->call_stmt,
1069                                       e->callee->clone.combined_args_to_skip);
1070       gimple_call_set_fndecl (new_stmt, e->callee->symbol.decl);
1071       gimple_call_set_fntype (new_stmt, gimple_call_fntype (e->call_stmt));
1072
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;
1076
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)
1085         {
1086           remove_stmt_from_eh_lp (e->call_stmt);
1087           add_stmt_to_eh_lp (new_stmt, lp_nr);
1088         }
1089     }
1090   else
1091     {
1092       new_stmt = e->call_stmt;
1093       gimple_call_set_fndecl (new_stmt, e->callee->symbol.decl);
1094       update_stmt (new_stmt);
1095     }
1096
1097   cgraph_set_call_stmt_including_clones (e->caller, e->call_stmt, new_stmt);
1098
1099   if (cgraph_dump_file)
1100     {
1101       fprintf (cgraph_dump_file, "  updated to:");
1102       print_gimple_stmt (cgraph_dump_file, e->call_stmt, 0, dump_flags);
1103     }
1104   return new_stmt;
1105 }
1106
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.  */
1112
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)
1117 {
1118   tree new_call = (new_stmt && is_gimple_call (new_stmt))
1119                   ? gimple_call_fndecl (new_stmt) : 0;
1120
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)
1127     {
1128       struct cgraph_edge *e = cgraph_edge (node, old_stmt);
1129       struct cgraph_edge *ne = NULL;
1130       gcov_type count;
1131       int frequency;
1132
1133       if (e)
1134         {
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)
1139             {
1140               struct cgraph_node *callee = e->callee;
1141               while (callee)
1142                 {
1143                   if (callee->symbol.decl == new_call
1144                       || callee->former_clone_of == new_call)
1145                     return;
1146                   callee = callee->clone_of;
1147                 }
1148             }
1149
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);
1156         }
1157       else if (new_call)
1158         {
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);
1164         }
1165
1166       if (new_call)
1167         {
1168           ne = cgraph_create_edge (node, cgraph_get_create_node (new_call),
1169                                    new_stmt, count, frequency);
1170           gcc_assert (ne->inline_failed);
1171         }
1172     }
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);
1176 }
1177
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).  */
1181
1182 void
1183 cgraph_update_edges_for_call_stmt (gimple old_stmt, tree old_decl, gimple new_stmt)
1184 {
1185   struct cgraph_node *orig = cgraph_get_node (cfun->decl);
1186   struct cgraph_node *node;
1187
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;)
1192       {
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
1199           {
1200             while (node != orig && !node->next_sibling_clone)
1201               node = node->clone_of;
1202             if (node != orig)
1203               node = node->next_sibling_clone;
1204           }
1205       }
1206 }
1207
1208
1209 /* Remove all callees from the node.  */
1210
1211 void
1212 cgraph_node_remove_callees (struct cgraph_node *node)
1213 {
1214   struct cgraph_edge *e, *f;
1215
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)
1220     {
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);
1226     }
1227   for (e = node->indirect_calls; e; e = f)
1228     {
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);
1234     }
1235   node->indirect_calls = NULL;
1236   node->callees = NULL;
1237   if (node->call_site_hash)
1238     {
1239       htab_delete (node->call_site_hash);
1240       node->call_site_hash = NULL;
1241     }
1242 }
1243
1244 /* Remove all callers from the node.  */
1245
1246 static void
1247 cgraph_node_remove_callers (struct cgraph_node *node)
1248 {
1249   struct cgraph_edge *e, *f;
1250
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)
1255     {
1256       f = e->next_caller;
1257       cgraph_call_edge_removal_hooks (e);
1258       cgraph_edge_remove_caller (e);
1259       cgraph_free_edge (e);
1260     }
1261   node->callers = NULL;
1262 }
1263
1264 /* Release memory used to represent body of function NODE.  */
1265
1266 void
1267 cgraph_release_function_body (struct cgraph_node *node)
1268 {
1269   if (DECL_STRUCT_FUNCTION (node->symbol.decl))
1270     {
1271       push_cfun (DECL_STRUCT_FUNCTION (node->symbol.decl));
1272       if (cfun->cfg
1273           && current_loops)
1274         {
1275           cfun->curr_properties &= ~PROP_loops;
1276           loop_optimizer_finalize ();
1277         }
1278       if (cfun->gimple_df)
1279         {
1280           delete_tree_ssa ();
1281           delete_tree_cfg_annotations ();
1282           cfun->eh = NULL;
1283         }
1284       if (cfun->cfg)
1285         {
1286           gcc_assert (dom_computed[0] == DOM_NONE);
1287           gcc_assert (dom_computed[1] == DOM_NONE);
1288           clear_edges ();
1289         }
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;
1299     }
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;
1306 }
1307
1308 /* Remove the node from cgraph.  */
1309
1310 void
1311 cgraph_remove_node (struct cgraph_node *node)
1312 {
1313   struct cgraph_node *n;
1314   int uid = node->uid;
1315
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 ();
1320
1321   /* Incremental inlining access removed nodes stored in the postorder list.
1322      */
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)
1328     {
1329       struct cgraph_node **node2 = &node->origin->nested;
1330
1331       while (*node2 != node)
1332         node2 = &(*node2)->next_nested;
1333       *node2 = node->next_nested;
1334     }
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)
1343     {
1344       struct cgraph_node *n, *next;
1345
1346       if (node->clone_of)
1347         {
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;
1355         }
1356       else
1357         {
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)
1364             {
1365                next = n->next_sibling_clone;
1366                n->next_sibling_clone = NULL;
1367                n->prev_sibling_clone = NULL;
1368                n->clone_of = NULL;
1369             }
1370         }
1371     }
1372
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.
1376      */
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);
1386
1387   node->symbol.decl = NULL;
1388   if (node->call_site_hash)
1389     {
1390       htab_delete (node->call_site_hash);
1391       node->call_site_hash = NULL;
1392     }
1393   cgraph_n_nodes--;
1394
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;
1402 }
1403
1404 /* Likewise indicate that a node is having address taken.  */
1405
1406 void
1407 cgraph_mark_address_taken_node (struct cgraph_node *node)
1408 {
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;
1419 }
1420
1421 /* Return local info for the compiled function.  */
1422
1423 struct cgraph_local_info *
1424 cgraph_local_info (tree decl)
1425 {
1426   struct cgraph_node *node;
1427
1428   gcc_assert (TREE_CODE (decl) == FUNCTION_DECL);
1429   node = cgraph_get_node (decl);
1430   if (!node)
1431     return NULL;
1432   return &node->local;
1433 }
1434
1435 /* Return local info for the compiled function.  */
1436
1437 struct cgraph_global_info *
1438 cgraph_global_info (tree decl)
1439 {
1440   struct cgraph_node *node;
1441
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;
1447 }
1448
1449 /* Return local info for the compiled function.  */
1450
1451 struct cgraph_rtl_info *
1452 cgraph_rtl_info (tree decl)
1453 {
1454   struct cgraph_node *node;
1455
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;
1463 }
1464
1465 /* Return a string describing the failure REASON.  */
1466
1467 const char*
1468 cgraph_inline_failed_string (cgraph_inline_failed_t reason)
1469 {
1470 #undef DEFCIFCODE
1471 #define DEFCIFCODE(code, string)        string,
1472
1473   static const char *cif_string_table[CIF_N_REASONS] = {
1474 #include "cif-code.def"
1475   };
1476
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];
1481 }
1482
1483 /* Names used to print out the availability enum.  */
1484 const char * const cgraph_availability_names[] =
1485   {"unset", "not_available", "overwritable", "available", "local"};
1486
1487
1488 /* Dump call graph node NODE to file F.  */
1489
1490 void
1491 dump_cgraph_node (FILE *f, struct cgraph_node *node)
1492 {
1493   struct cgraph_edge *edge;
1494   int indirect_calls_count = 0;
1495
1496   dump_symtab_base (f, (symtab_node) node);
1497
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)]);
1511
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");
1538
1539   fprintf (f, "\n");
1540
1541   if (node->thunk.thunk_p)
1542     {
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);
1550     }
1551   if (node->alias && node->thunk.alias)
1552     {
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");
1559     }
1560   
1561   fprintf (f, "  Called by: ");
1562
1563   for (edge = node->callers; edge; edge = edge->next_caller)
1564     {
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) ");
1579     }
1580
1581   fprintf (f, "\n  Calls: ");
1582   for (edge = node->callees; edge; edge = edge->next_callee)
1583     {
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) ");
1598     }
1599   fprintf (f, "\n");
1600
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);
1606 }
1607
1608
1609 /* Dump call graph node NODE to stderr.  */
1610
1611 DEBUG_FUNCTION void
1612 debug_cgraph_node (struct cgraph_node *node)
1613 {
1614   dump_cgraph_node (stderr, node);
1615 }
1616
1617
1618 /* Dump the callgraph to file F.  */
1619
1620 void
1621 dump_cgraph (FILE *f)
1622 {
1623   struct cgraph_node *node;
1624
1625   fprintf (f, "callgraph:\n\n");
1626   FOR_EACH_FUNCTION (node)
1627     dump_cgraph_node (f, node);
1628 }
1629
1630
1631 /* Dump the call graph to stderr.  */
1632
1633 DEBUG_FUNCTION void
1634 debug_cgraph (void)
1635 {
1636   dump_cgraph (stderr);
1637 }
1638
1639 /* Return true when the DECL can possibly be inlined.  */
1640 bool
1641 cgraph_function_possibly_inlined_p (tree decl)
1642 {
1643   if (!cgraph_global_info_ready)
1644     return !DECL_UNINLINABLE (decl);
1645   return DECL_POSSIBLY_INLINED (decl);
1646 }
1647
1648 /* NODE is no longer nested function; update cgraph accordingly.  */
1649 void
1650 cgraph_unnest_node (struct cgraph_node *node)
1651 {
1652   struct cgraph_node **node2 = &node->origin->nested;
1653   gcc_assert (node->origin);
1654
1655   while (*node2 != node)
1656     node2 = &(*node2)->next_nested;
1657   *node2 = node->next_nested;
1658   node->origin = NULL;
1659 }
1660
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)
1665 {
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;
1679
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).
1685
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.  */
1689
1690   else if (decl_replaceable_p (node->symbol.decl)
1691            && !DECL_EXTERNAL (node->symbol.decl))
1692     avail = AVAIL_OVERWRITABLE;
1693   else avail = AVAIL_AVAILABLE;
1694
1695   return avail;
1696 }
1697
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)
1702 {
1703   return !(!node->symbol.force_output
1704            && ((DECL_COMDAT (node->symbol.decl)
1705                 && !node->symbol.same_comdat_group)
1706                || !node->symbol.externally_visible));
1707 }
1708
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)
1715 {
1716   return (!node->symbol.address_taken
1717           && !cgraph_for_node_and_aliases (node,
1718                                            cgraph_node_cannot_be_local_p_1,
1719                                            NULL, true));
1720 }
1721
1722 /* Call calback on NODE, thunks and aliases associated to NODE. 
1723    When INCLUDE_OVERWRITABLE is false, overwritable aliases and thunks are
1724    skipped. */
1725
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)
1731 {
1732   struct cgraph_edge *e;
1733   int i;
1734   struct ipa_ref *ref;
1735
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)
1747       {
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;
1754       }
1755   return false;
1756 }
1757
1758 /* Call calback on NODE and aliases associated to NODE. 
1759    When INCLUDE_OVERWRITABLE is false, overwritable aliases and thunks are
1760    skipped. */
1761
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)
1767 {
1768   int i;
1769   struct ipa_ref *ref;
1770
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)
1775       {
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;
1782       }
1783   return false;
1784 }
1785
1786 /* Worker to bring NODE local.  */
1787
1788 static bool
1789 cgraph_make_node_local_1 (struct cgraph_node *node, void *data ATTRIBUTE_UNUSED)
1790 {
1791   gcc_checking_assert (cgraph_node_can_be_local_p (node));
1792   if (DECL_COMDAT (node->symbol.decl) || DECL_EXTERNAL (node->symbol.decl))
1793     {
1794       symtab_make_decl_local (node->symbol.decl);
1795
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);
1800     }
1801   return false;
1802 }
1803
1804 /* Bring NODE local.  */
1805
1806 void
1807 cgraph_make_node_local (struct cgraph_node *node)
1808 {
1809   cgraph_for_node_thunks_and_aliases (node, cgraph_make_node_local_1,
1810                                       NULL, true);
1811 }
1812
1813 /* Worker to set nothrow flag.  */
1814
1815 static bool
1816 cgraph_set_nothrow_flag_1 (struct cgraph_node *node, void *data)
1817 {
1818   struct cgraph_edge *e;
1819
1820   TREE_NOTHROW (node->symbol.decl) = data != NULL;
1821
1822   if (data != NULL)
1823     for (e = node->callers; e; e = e->next_caller)
1824       e->can_throw_external = false;
1825   return false;
1826 }
1827
1828 /* Set TREE_NOTHROW on NODE's decl and on aliases of NODE
1829    if any to NOTHROW.  */
1830
1831 void
1832 cgraph_set_nothrow_flag (struct cgraph_node *node, bool nothrow)
1833 {
1834   cgraph_for_node_thunks_and_aliases (node, cgraph_set_nothrow_flag_1,
1835                                       (void *)(size_t)nothrow, false);
1836 }
1837
1838 /* Worker to set const flag.  */
1839
1840 static bool
1841 cgraph_set_const_flag_1 (struct cgraph_node *node, void *data)
1842 {
1843   /* Static constructors and destructors without a side effect can be
1844      optimized out.  */
1845   if (data && !((size_t)data & 2))
1846     {
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;
1851     }
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;
1855 }
1856
1857 /* Set TREE_READONLY on NODE's decl and on aliases of NODE
1858    if any to READONLY.  */
1859
1860 void
1861 cgraph_set_const_flag (struct cgraph_node *node, bool readonly, bool looping)
1862 {
1863   cgraph_for_node_thunks_and_aliases (node, cgraph_set_const_flag_1,
1864                                       (void *)(size_t)(readonly + (int)looping * 2),
1865                                       false);
1866 }
1867
1868 /* Worker to set pure flag.  */
1869
1870 static bool
1871 cgraph_set_pure_flag_1 (struct cgraph_node *node, void *data)
1872 {
1873   /* Static constructors and destructors without a side effect can be
1874      optimized out.  */
1875   if (data && !((size_t)data & 2))
1876     {
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;
1881     }
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;
1885 }
1886
1887 /* Set DECL_PURE_P on NODE's decl and on aliases of NODE
1888    if any to PURE.  */
1889
1890 void
1891 cgraph_set_pure_flag (struct cgraph_node *node, bool pure, bool looping)
1892 {
1893   cgraph_for_node_thunks_and_aliases (node, cgraph_set_pure_flag_1,
1894                                       (void *)(size_t)(pure + (int)looping * 2),
1895                                       false);
1896 }
1897
1898 /* Data used by cgraph_propagate_frequency.  */
1899
1900 struct cgraph_propagate_frequency_data
1901 {
1902   bool maybe_unlikely_executed;
1903   bool maybe_executed_once;
1904   bool only_called_at_startup;
1905   bool only_called_at_exit;
1906 };
1907
1908 /* Worker for cgraph_propagate_frequency_1.  */
1909
1910 static bool
1911 cgraph_propagate_frequency_1 (struct cgraph_node *node, void *data)
1912 {
1913   struct cgraph_propagate_frequency_data *d;
1914   struct cgraph_edge *edge;
1915
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)
1921     {
1922       if (edge->caller != node)
1923         {
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;
1931         }
1932       if (!edge->frequency)
1933         continue;
1934       switch (edge->caller->frequency)
1935         {
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)
1944             {
1945               d->maybe_executed_once = false;
1946               if (dump_file && (dump_flags & TDF_DETAILS))
1947                 fprintf (dump_file, "  Called in loop\n");
1948             }
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;
1958         }
1959     }
1960   return edge != NULL;
1961 }
1962
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)
1967 {
1968   struct cgraph_propagate_frequency_data d = {true, true, true, true};
1969   bool changed = false;
1970
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));
1976
1977   cgraph_for_node_and_aliases (node, cgraph_propagate_frequency_1, &d, true);
1978
1979   if ((d.only_called_at_startup && !d.only_called_at_exit)
1980       && !node->only_called_at_startup)
1981     {
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;
1987     }
1988   if ((d.only_called_at_exit && !d.only_called_at_startup)
1989       && !node->only_called_at_exit)
1990     {
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;
1996     }
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)
2002     {
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;
2008     }
2009   else if (d.maybe_executed_once && node->frequency != NODE_FREQUENCY_EXECUTED_ONCE)
2010     {
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;
2016     }
2017   return changed;
2018 }
2019
2020 /* Return true when NODE can not return or throw and thus
2021    it is safe to ignore its side effects for IPA analysis.  */
2022
2023 bool
2024 cgraph_node_cannot_return (struct cgraph_node *node)
2025 {
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));
2032 }
2033
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)
2041 {
2042   if (cgraph_node_cannot_return (e->caller))
2043     return true;
2044   if (e->indirect_unknown_callee)
2045     {
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));
2052     }
2053   else
2054     return cgraph_node_cannot_return (e->callee);
2055 }
2056
2057 /* Return true when function NODE can be removed from callgraph
2058    if all direct calls are eliminated.  */
2059
2060 bool
2061 cgraph_can_remove_if_no_direct_calls_and_refs_p (struct cgraph_node *node)
2062 {
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;
2079 }
2080
2081 /* Worker for cgraph_can_remove_if_no_direct_calls_p.  */
2082
2083 static bool
2084 nonremovable_p (struct cgraph_node *node, void *data ATTRIBUTE_UNUSED)
2085 {
2086   return !cgraph_can_remove_if_no_direct_calls_and_refs_p (node);
2087 }
2088
2089 /* Return true when function NODE and its aliases can be removed from callgraph
2090    if all direct calls are eliminated.  */
2091
2092 bool
2093 cgraph_can_remove_if_no_direct_calls_p (struct cgraph_node *node)
2094 {
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);
2101 }
2102
2103 /* Worker for cgraph_can_remove_if_no_direct_calls_p.  */
2104
2105 static bool
2106 used_from_object_file_p (struct cgraph_node *node, void *data ATTRIBUTE_UNUSED)
2107 {
2108   return symtab_used_from_object_file_p ((symtab_node) node);
2109 }
2110
2111 /* Return true when function NODE can be expected to be removed
2112    from program when direct calls in this compilation unit are removed.
2113
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)
2118
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.  */
2124
2125 bool
2126 cgraph_will_be_removed_from_program_if_no_direct_calls (struct cgraph_node *node)
2127 {
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
2134     {
2135        if (DECL_EXTERNAL (node->symbol.decl))
2136          return true;
2137       return cgraph_can_remove_if_no_direct_calls_p (node);
2138     }
2139 }
2140
2141
2142 /* Worker for cgraph_only_called_directly_p.  */
2143
2144 static bool
2145 cgraph_not_only_called_directly_p_1 (struct cgraph_node *node, void *data ATTRIBUTE_UNUSED)
2146 {
2147   return !cgraph_only_called_directly_or_aliased_p (node);
2148 }
2149
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.  */
2154
2155 bool
2156 cgraph_only_called_directly_p (struct cgraph_node *node)
2157 {
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);
2161 }
2162
2163
2164 /* Collect all callers of NODE.  Worker for collect_callers_of_node.  */
2165
2166 static bool
2167 collect_callers_of_node_1 (struct cgraph_node *node, void *data)
2168 {
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);
2173
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;
2179 }
2180
2181 /* Collect all callers of NODE and its aliases that are known to lead to NODE
2182    (i.e. are not overwritable).  */
2183
2184 vec<cgraph_edge_p> 
2185 collect_callers_of_node (struct cgraph_node *node)
2186 {
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;
2191 }
2192
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)
2196 {
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;
2202 }
2203
2204 /* Verify edge E count and frequency.  */
2205
2206 static bool
2207 verify_edge_count_and_frequency (struct cgraph_edge *e)
2208 {
2209   bool error_found = false;
2210   if (e->count < 0)
2211     {
2212       error ("caller edge count is negative");
2213       error_found = true;
2214     }
2215   if (e->frequency < 0)
2216     {
2217       error ("caller edge frequency is negative");
2218       error_found = true;
2219     }
2220   if (e->frequency > CGRAPH_FREQ_MAX)
2221     {
2222       error ("caller edge frequency is too large");
2223       error_found = true;
2224     }
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))))
2236     {
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;
2242     }
2243   return error_found;
2244 }
2245
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)
2249 {
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)
2256     {
2257       current_function_decl = this_cfun->decl;
2258       fndecl_was_null = true;
2259     }
2260   debug_gimple_stmt (stmt);
2261   if (fndecl_was_null)
2262     current_function_decl = NULL;
2263 }
2264
2265 /* Verify that call graph edge E corresponds to DECL from the associated
2266    statement.  Return true if the verification should fail.  */
2267
2268 static bool
2269 verify_edge_corresponds_to_fndecl (struct cgraph_edge *e, tree decl)
2270 {
2271   struct cgraph_node *node;
2272
2273   if (!decl || e->callee->global.inlined_to)
2274     return false;
2275   node = cgraph_get_node (decl);
2276
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);
2282
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;
2297 }
2298
2299 /* Verify cgraph nodes of given cgraph node.  */
2300 DEBUG_FUNCTION void
2301 verify_cgraph_node (struct cgraph_node *node)
2302 {
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;
2308
2309   if (seen_error ())
2310     return;
2311
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)
2316       {
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;
2321       }
2322   if (node->count < 0)
2323     {
2324       error ("execution count is negative");
2325       error_found = true;
2326     }
2327   if (node->global.inlined_to && node->symbol.same_comdat_group)
2328     {
2329       error ("inline clone in same comdat group list");
2330       error_found = true;
2331     }
2332   if (node->global.inlined_to && node->symbol.externally_visible)
2333     {
2334       error ("externally visible inline clone");
2335       error_found = true;
2336     }
2337   if (node->global.inlined_to && node->symbol.address_taken)
2338     {
2339       error ("inline clone with address taken");
2340       error_found = true;
2341     }
2342   if (node->global.inlined_to && node->symbol.force_output)
2343     {
2344       error ("inline clone is forced to output");
2345       error_found = true;
2346     }
2347   for (e = node->indirect_calls; e; e = e->next_callee)
2348     {
2349       if (e->aux)
2350         {
2351           error ("aux field set for indirect edge from %s",
2352                  identifier_to_locale (cgraph_node_name (e->caller)));
2353           error_found = true;
2354         }
2355       if (!e->indirect_unknown_callee
2356           || !e->indirect_info)
2357         {
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;
2363         }
2364     }
2365   for (e = node->callers; e; e = e->next_caller)
2366     {
2367       if (verify_edge_count_and_frequency (e))
2368         error_found = true;
2369       if (!e->inline_failed)
2370         {
2371           if (node->global.inlined_to
2372               != (e->caller->global.inlined_to
2373                   ? e->caller->global.inlined_to : e->caller))
2374             {
2375               error ("inlined_to pointer is wrong");
2376               error_found = true;
2377             }
2378           if (node->callers->next_caller)
2379             {
2380               error ("multiple inline callers");
2381               error_found = true;
2382             }
2383         }
2384       else
2385         if (node->global.inlined_to)
2386           {
2387             error ("inlined_to pointer set for noninline callers");
2388             error_found = true;
2389           }
2390     }
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)
2395     {
2396       error ("inlined_to pointer is set but no predecessors found");
2397       error_found = true;
2398     }
2399   if (node->global.inlined_to == node)
2400     {
2401       error ("inlined_to pointer refers to itself");
2402       error_found = true;
2403     }
2404
2405   if (node->clone_of)
2406     {
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)
2412         {
2413           error ("node has wrong clone_of");
2414           error_found = true;
2415         }
2416     }
2417   if (node->clones)
2418     {
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)
2424         {
2425           error ("node has wrong clone list");
2426           error_found = true;
2427         }
2428     }
2429   if ((node->prev_sibling_clone || node->next_sibling_clone) && !node->clone_of)
2430     {
2431        error ("node is in clone list but it is not clone");
2432        error_found = true;
2433     }
2434   if (!node->prev_sibling_clone && node->clone_of && node->clone_of->clones != node)
2435     {
2436       error ("node has wrong prev_clone pointer");
2437       error_found = true;
2438     }
2439   if (node->prev_sibling_clone && node->prev_sibling_clone->next_sibling_clone != node)
2440     {
2441       error ("double linked list of clones corrupted");
2442       error_found = true;
2443     }
2444
2445   if (node->analyzed && node->alias)
2446     {
2447       bool ref_found = false;
2448       int i;
2449       struct ipa_ref *ref;
2450
2451       if (node->callees)
2452         {
2453           error ("Alias has call edges");
2454           error_found = true;
2455         }
2456       for (i = 0; ipa_ref_list_reference_iterate (&node->symbol.ref_list,
2457                                                   i, ref); i++)
2458         if (ref->use != IPA_REF_ALIAS)
2459           {
2460             error ("Alias has non-alias reference");
2461             error_found = true;
2462           }
2463         else if (ref_found)
2464           {
2465             error ("Alias has more than one alias reference");
2466             error_found = true;
2467           }
2468         else
2469           ref_found = true;
2470         if (!ref_found)
2471           {
2472             error ("Analyzed alias has no reference");
2473             error_found = true;
2474           }
2475     }
2476   if (node->analyzed && node->thunk.thunk_p)
2477     {
2478       if (!node->callees)
2479         {
2480           error ("No edge out of thunk node");
2481           error_found = true;
2482         }
2483       else if (node->callees->next_callee)
2484         {
2485           error ("More than one edge out of thunk node");
2486           error_found = true;
2487         }
2488       if (gimple_has_body_p (node->symbol.decl))
2489         {
2490           error ("Thunk is not supposed to have body");
2491           error_found = true;
2492         }
2493     }
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)
2498     {
2499       if (this_cfun->cfg)
2500         {
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))
2507               {
2508                 gimple stmt = gsi_stmt (gsi);
2509                 if (is_gimple_call (stmt))
2510                   {
2511                     struct cgraph_edge *e = cgraph_edge (node, stmt);
2512                     tree decl = gimple_call_fndecl (stmt);
2513                     if (e)
2514                       {
2515                         if (e->aux)
2516                           {
2517                             error ("shared call_stmt:");
2518                             cgraph_debug_gimple_stmt (this_cfun, stmt);
2519                             error_found = true;
2520                           }
2521                         if (!e->indirect_unknown_callee)
2522                           {
2523                             if (verify_edge_corresponds_to_fndecl (e, decl))
2524                               {
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;
2530                               }
2531                           }
2532                         else if (decl)
2533                           {
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);
2539                           }
2540                         e->aux = (void *)1;
2541                       }
2542                     else if (decl)
2543                       {
2544                         error ("missing callgraph edge for call stmt:");
2545                         cgraph_debug_gimple_stmt (this_cfun, stmt);
2546                         error_found = true;
2547                       }
2548                   }
2549               }
2550         }
2551       else
2552         /* No CFG available?!  */
2553         gcc_unreachable ();
2554
2555       for (e = node->callees; e; e = e->next_callee)
2556         {
2557           if (!e->aux)
2558             {
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;
2564             }
2565           e->aux = 0;
2566         }
2567       for (e = node->indirect_calls; e; e = e->next_callee)
2568         {
2569           if (!e->aux)
2570             {
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;
2575             }
2576           e->aux = 0;
2577         }
2578     }
2579   if (error_found)
2580     {
2581       dump_cgraph_node (stderr, node);
2582       internal_error ("verify_cgraph_node failed");
2583     }
2584   timevar_pop (TV_CGRAPH_VERIFY);
2585 }
2586
2587 /* Verify whole cgraph structure.  */
2588 DEBUG_FUNCTION void
2589 verify_cgraph (void)
2590 {
2591   struct cgraph_node *node;
2592
2593   if (seen_error ())
2594     return;
2595
2596   FOR_EACH_FUNCTION (node)
2597     verify_cgraph_node (node);
2598 }
2599 #include "gt-cgraph.h"