OSDN Git Service

PR target/47101
[pf3gnuchains/gcc-fork.git] / gcc / cgraph.c
1 /* Callgraph handling code.
2    Copyright (C) 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010
3    Free Software Foundation, Inc.
4    Contributed by Jan Hubicka
5
6 This file is part of GCC.
7
8 GCC is free software; you can redistribute it and/or modify it under
9 the terms of the GNU General Public License as published by the Free
10 Software Foundation; either version 3, or (at your option) any later
11 version.
12
13 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
14 WARRANTY; without even the implied warranty of MERCHANTABILITY or
15 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
16 for more details.
17
18 You should have received a copy of the GNU General Public License
19 along with GCC; see the file COPYING3.  If not see
20 <http://www.gnu.org/licenses/>.  */
21
22 /*  This file contains basic routines manipulating call graph
23
24 The callgraph:
25
26     The call-graph is data structure designed for intra-procedural optimization
27     but it is also used in non-unit-at-a-time compilation to allow easier code
28     sharing.
29
30     The call-graph consist of nodes and edges represented via linked lists.
31     Each function (external or not) corresponds to the unique node.
32
33     The mapping from declarations to call-graph nodes is done using hash table
34     based on DECL_UID.  The call-graph nodes are created lazily using
35     cgraph_node function when called for unknown declaration.
36
37     The callgraph at the moment does not represent all indirect calls or calls
38     from other compilation units.  Flag NEEDED is set for each node that may be
39     accessed in such an invisible way and it shall be considered an entry point
40     to the callgraph.
41
42     On the other hand, the callgraph currently does contain some edges for
43     indirect calls with unknown callees which can be accessed through
44     indirect_calls field of a node.  It should be noted however that at the
45     moment only calls which are potential candidates for indirect inlining are
46     added there.
47
48     Interprocedural information:
49
50       Callgraph is place to store data needed for interprocedural optimization.
51       All data structures are divided into three components: local_info that
52       is produced while analyzing the function, global_info that is result
53       of global walking of the callgraph on the end of compilation and
54       rtl_info used by RTL backend to propagate data from already compiled
55       functions to their callers.
56
57       Moreover, each node has a uid which can be used to keep information in
58       on-the-side arrays.  UIDs are reused and therefore reasonably dense.
59
60     Inlining plans:
61
62       The function inlining information is decided in advance and maintained
63       in the callgraph as so called inline plan.
64       For each inlined call, the callee's node is cloned to represent the
65       new function copy produced by inliner.
66       Each inlined call gets a unique corresponding clone node of the callee
67       and the data structure is updated while inlining is performed, so
68       the clones are eliminated and their callee edges redirected to the
69       caller.
70
71       Each edge has "inline_failed" field.  When the field is set to NULL,
72       the call will be inlined.  When it is non-NULL it contains a reason
73       why inlining wasn't performed.  */
74
75 #include "config.h"
76 #include "system.h"
77 #include "coretypes.h"
78 #include "tm.h"
79 #include "tree.h"
80 #include "tree-inline.h"
81 #include "langhooks.h"
82 #include "hashtab.h"
83 #include "toplev.h"
84 #include "flags.h"
85 #include "ggc.h"
86 #include "debug.h"
87 #include "target.h"
88 #include "basic-block.h"
89 #include "cgraph.h"
90 #include "output.h"
91 #include "intl.h"
92 #include "gimple.h"
93 #include "tree-dump.h"
94 #include "tree-flow.h"
95 #include "value-prof.h"
96 #include "except.h"
97 #include "diagnostic-core.h"
98 #include "rtl.h"
99 #include "ipa-utils.h"
100 #include "lto-streamer.h"
101
102 const char * const ld_plugin_symbol_resolution_names[]=
103 {
104   "",
105   "undef",
106   "prevailing_def",
107   "prevailing_def_ironly",
108   "preempted_reg",
109   "preempted_ir",
110   "resolved_ir",
111   "resolved_exec",
112   "resolved_dyn"
113 };
114
115 static void cgraph_node_remove_callers (struct cgraph_node *node);
116 static inline void cgraph_edge_remove_caller (struct cgraph_edge *e);
117 static inline void cgraph_edge_remove_callee (struct cgraph_edge *e);
118
119 /* Hash table used to convert declarations into nodes.  */
120 static GTY((param_is (struct cgraph_node))) htab_t cgraph_hash;
121 /* Hash table used to convert assembler names into nodes.  */
122 static GTY((param_is (struct cgraph_node))) htab_t assembler_name_hash;
123
124 /* The linked list of cgraph nodes.  */
125 struct cgraph_node *cgraph_nodes;
126
127 /* Queue of cgraph nodes scheduled to be lowered.  */
128 struct cgraph_node *cgraph_nodes_queue;
129
130 /* Queue of cgraph nodes scheduled to be added into cgraph.  This is a
131    secondary queue used during optimization to accommodate passes that
132    may generate new functions that need to be optimized and expanded.  */
133 struct cgraph_node *cgraph_new_nodes;
134
135 /* Number of nodes in existence.  */
136 int cgraph_n_nodes;
137
138 /* Maximal uid used in cgraph nodes.  */
139 int cgraph_max_uid;
140
141 /* Maximal uid used in cgraph edges.  */
142 int cgraph_edge_max_uid;
143
144 /* Maximal pid used for profiling */
145 int cgraph_max_pid;
146
147 /* Set when whole unit has been analyzed so we can access global info.  */
148 bool cgraph_global_info_ready = false;
149
150 /* What state callgraph is in right now.  */
151 enum cgraph_state cgraph_state = CGRAPH_STATE_CONSTRUCTION;
152
153 /* Set when the cgraph is fully build and the basic flags are computed.  */
154 bool cgraph_function_flags_ready = false;
155
156 /* Linked list of cgraph asm nodes.  */
157 struct cgraph_asm_node *cgraph_asm_nodes;
158
159 /* Last node in cgraph_asm_nodes.  */
160 static GTY(()) struct cgraph_asm_node *cgraph_asm_last_node;
161
162 /* The order index of the next cgraph node to be created.  This is
163    used so that we can sort the cgraph nodes in order by when we saw
164    them, to support -fno-toplevel-reorder.  */
165 int cgraph_order;
166
167 /* List of hooks trigerred on cgraph_edge events.  */
168 struct cgraph_edge_hook_list {
169   cgraph_edge_hook hook;
170   void *data;
171   struct cgraph_edge_hook_list *next;
172 };
173
174 /* List of hooks trigerred on cgraph_node events.  */
175 struct cgraph_node_hook_list {
176   cgraph_node_hook hook;
177   void *data;
178   struct cgraph_node_hook_list *next;
179 };
180
181 /* List of hooks trigerred on events involving two cgraph_edges.  */
182 struct cgraph_2edge_hook_list {
183   cgraph_2edge_hook hook;
184   void *data;
185   struct cgraph_2edge_hook_list *next;
186 };
187
188 /* List of hooks trigerred on events involving two cgraph_nodes.  */
189 struct cgraph_2node_hook_list {
190   cgraph_2node_hook hook;
191   void *data;
192   struct cgraph_2node_hook_list *next;
193 };
194
195 /* List of hooks triggered when an edge is removed.  */
196 struct cgraph_edge_hook_list *first_cgraph_edge_removal_hook;
197 /* List of hooks triggered when a node is removed.  */
198 struct cgraph_node_hook_list *first_cgraph_node_removal_hook;
199 /* List of hooks triggered when an edge is duplicated.  */
200 struct cgraph_2edge_hook_list *first_cgraph_edge_duplicated_hook;
201 /* List of hooks triggered when a node is duplicated.  */
202 struct cgraph_2node_hook_list *first_cgraph_node_duplicated_hook;
203 /* List of hooks triggered when an function is inserted.  */
204 struct cgraph_node_hook_list *first_cgraph_function_insertion_hook;
205
206 /* Head of a linked list of unused (freed) call graph nodes.
207    Do not GTY((delete)) this list so UIDs gets reliably recycled.  */
208 static GTY(()) struct cgraph_node *free_nodes;
209 /* Head of a linked list of unused (freed) call graph edges.
210    Do not GTY((delete)) this list so UIDs gets reliably recycled.  */
211 static GTY(()) struct cgraph_edge *free_edges;
212
213 /* Macros to access the next item in the list of free cgraph nodes and
214    edges. */
215 #define NEXT_FREE_NODE(NODE) (NODE)->next
216 #define NEXT_FREE_EDGE(EDGE) (EDGE)->prev_caller
217
218 /* Register HOOK to be called with DATA on each removed edge.  */
219 struct cgraph_edge_hook_list *
220 cgraph_add_edge_removal_hook (cgraph_edge_hook hook, void *data)
221 {
222   struct cgraph_edge_hook_list *entry;
223   struct cgraph_edge_hook_list **ptr = &first_cgraph_edge_removal_hook;
224
225   entry = (struct cgraph_edge_hook_list *) xmalloc (sizeof (*entry));
226   entry->hook = hook;
227   entry->data = data;
228   entry->next = NULL;
229   while (*ptr)
230     ptr = &(*ptr)->next;
231   *ptr = entry;
232   return entry;
233 }
234
235 /* Remove ENTRY from the list of hooks called on removing edges.  */
236 void
237 cgraph_remove_edge_removal_hook (struct cgraph_edge_hook_list *entry)
238 {
239   struct cgraph_edge_hook_list **ptr = &first_cgraph_edge_removal_hook;
240
241   while (*ptr != entry)
242     ptr = &(*ptr)->next;
243   *ptr = entry->next;
244   free (entry);
245 }
246
247 /* Call all edge removal hooks.  */
248 static void
249 cgraph_call_edge_removal_hooks (struct cgraph_edge *e)
250 {
251   struct cgraph_edge_hook_list *entry = first_cgraph_edge_removal_hook;
252   while (entry)
253   {
254     entry->hook (e, entry->data);
255     entry = entry->next;
256   }
257 }
258
259 /* Register HOOK to be called with DATA on each removed node.  */
260 struct cgraph_node_hook_list *
261 cgraph_add_node_removal_hook (cgraph_node_hook hook, void *data)
262 {
263   struct cgraph_node_hook_list *entry;
264   struct cgraph_node_hook_list **ptr = &first_cgraph_node_removal_hook;
265
266   entry = (struct cgraph_node_hook_list *) xmalloc (sizeof (*entry));
267   entry->hook = hook;
268   entry->data = data;
269   entry->next = NULL;
270   while (*ptr)
271     ptr = &(*ptr)->next;
272   *ptr = entry;
273   return entry;
274 }
275
276 /* Remove ENTRY from the list of hooks called on removing nodes.  */
277 void
278 cgraph_remove_node_removal_hook (struct cgraph_node_hook_list *entry)
279 {
280   struct cgraph_node_hook_list **ptr = &first_cgraph_node_removal_hook;
281
282   while (*ptr != entry)
283     ptr = &(*ptr)->next;
284   *ptr = entry->next;
285   free (entry);
286 }
287
288 /* Call all node removal hooks.  */
289 static void
290 cgraph_call_node_removal_hooks (struct cgraph_node *node)
291 {
292   struct cgraph_node_hook_list *entry = first_cgraph_node_removal_hook;
293   while (entry)
294   {
295     entry->hook (node, entry->data);
296     entry = entry->next;
297   }
298 }
299
300 /* Register HOOK to be called with DATA on each inserted node.  */
301 struct cgraph_node_hook_list *
302 cgraph_add_function_insertion_hook (cgraph_node_hook hook, void *data)
303 {
304   struct cgraph_node_hook_list *entry;
305   struct cgraph_node_hook_list **ptr = &first_cgraph_function_insertion_hook;
306
307   entry = (struct cgraph_node_hook_list *) xmalloc (sizeof (*entry));
308   entry->hook = hook;
309   entry->data = data;
310   entry->next = NULL;
311   while (*ptr)
312     ptr = &(*ptr)->next;
313   *ptr = entry;
314   return entry;
315 }
316
317 /* Remove ENTRY from the list of hooks called on inserted nodes.  */
318 void
319 cgraph_remove_function_insertion_hook (struct cgraph_node_hook_list *entry)
320 {
321   struct cgraph_node_hook_list **ptr = &first_cgraph_function_insertion_hook;
322
323   while (*ptr != entry)
324     ptr = &(*ptr)->next;
325   *ptr = entry->next;
326   free (entry);
327 }
328
329 /* Call all node insertion hooks.  */
330 void
331 cgraph_call_function_insertion_hooks (struct cgraph_node *node)
332 {
333   struct cgraph_node_hook_list *entry = first_cgraph_function_insertion_hook;
334   while (entry)
335   {
336     entry->hook (node, entry->data);
337     entry = entry->next;
338   }
339 }
340
341 /* Register HOOK to be called with DATA on each duplicated edge.  */
342 struct cgraph_2edge_hook_list *
343 cgraph_add_edge_duplication_hook (cgraph_2edge_hook hook, void *data)
344 {
345   struct cgraph_2edge_hook_list *entry;
346   struct cgraph_2edge_hook_list **ptr = &first_cgraph_edge_duplicated_hook;
347
348   entry = (struct cgraph_2edge_hook_list *) xmalloc (sizeof (*entry));
349   entry->hook = hook;
350   entry->data = data;
351   entry->next = NULL;
352   while (*ptr)
353     ptr = &(*ptr)->next;
354   *ptr = entry;
355   return entry;
356 }
357
358 /* Remove ENTRY from the list of hooks called on duplicating edges.  */
359 void
360 cgraph_remove_edge_duplication_hook (struct cgraph_2edge_hook_list *entry)
361 {
362   struct cgraph_2edge_hook_list **ptr = &first_cgraph_edge_duplicated_hook;
363
364   while (*ptr != entry)
365     ptr = &(*ptr)->next;
366   *ptr = entry->next;
367   free (entry);
368 }
369
370 /* Call all edge duplication hooks.  */
371 static void
372 cgraph_call_edge_duplication_hooks (struct cgraph_edge *cs1,
373                                     struct cgraph_edge *cs2)
374 {
375   struct cgraph_2edge_hook_list *entry = first_cgraph_edge_duplicated_hook;
376   while (entry)
377   {
378     entry->hook (cs1, cs2, entry->data);
379     entry = entry->next;
380   }
381 }
382
383 /* Register HOOK to be called with DATA on each duplicated node.  */
384 struct cgraph_2node_hook_list *
385 cgraph_add_node_duplication_hook (cgraph_2node_hook hook, void *data)
386 {
387   struct cgraph_2node_hook_list *entry;
388   struct cgraph_2node_hook_list **ptr = &first_cgraph_node_duplicated_hook;
389
390   entry = (struct cgraph_2node_hook_list *) xmalloc (sizeof (*entry));
391   entry->hook = hook;
392   entry->data = data;
393   entry->next = NULL;
394   while (*ptr)
395     ptr = &(*ptr)->next;
396   *ptr = entry;
397   return entry;
398 }
399
400 /* Remove ENTRY from the list of hooks called on duplicating nodes.  */
401 void
402 cgraph_remove_node_duplication_hook (struct cgraph_2node_hook_list *entry)
403 {
404   struct cgraph_2node_hook_list **ptr = &first_cgraph_node_duplicated_hook;
405
406   while (*ptr != entry)
407     ptr = &(*ptr)->next;
408   *ptr = entry->next;
409   free (entry);
410 }
411
412 /* Call all node duplication hooks.  */
413 static void
414 cgraph_call_node_duplication_hooks (struct cgraph_node *node1,
415                                     struct cgraph_node *node2)
416 {
417   struct cgraph_2node_hook_list *entry = first_cgraph_node_duplicated_hook;
418   while (entry)
419   {
420     entry->hook (node1, node2, entry->data);
421     entry = entry->next;
422   }
423 }
424
425 /* Returns a hash code for P.  */
426
427 static hashval_t
428 hash_node (const void *p)
429 {
430   const struct cgraph_node *n = (const struct cgraph_node *) p;
431   return (hashval_t) DECL_UID (n->decl);
432 }
433
434
435 /* Returns nonzero if P1 and P2 are equal.  */
436
437 static int
438 eq_node (const void *p1, const void *p2)
439 {
440   const struct cgraph_node *n1 = (const struct cgraph_node *) p1;
441   const struct cgraph_node *n2 = (const struct cgraph_node *) p2;
442   return DECL_UID (n1->decl) == DECL_UID (n2->decl);
443 }
444
445 /* Allocate new callgraph node.  */
446
447 static inline struct cgraph_node *
448 cgraph_allocate_node (void)
449 {
450   struct cgraph_node *node;
451
452   if (free_nodes)
453     {
454       node = free_nodes;
455       free_nodes = NEXT_FREE_NODE (node);
456     }
457   else
458     {
459       node = ggc_alloc_cleared_cgraph_node ();
460       node->uid = cgraph_max_uid++;
461     }
462
463   return node;
464 }
465
466 /* Allocate new callgraph node and insert it into basic data structures.  */
467
468 static struct cgraph_node *
469 cgraph_create_node (void)
470 {
471   struct cgraph_node *node = cgraph_allocate_node ();
472
473   node->next = cgraph_nodes;
474   node->pid = -1;
475   node->order = cgraph_order++;
476   if (cgraph_nodes)
477     cgraph_nodes->previous = node;
478   node->previous = NULL;
479   node->global.estimated_growth = INT_MIN;
480   node->frequency = NODE_FREQUENCY_NORMAL;
481   node->count_materialization_scale = REG_BR_PROB_BASE;
482   ipa_empty_ref_list (&node->ref_list);
483   cgraph_nodes = node;
484   cgraph_n_nodes++;
485   return node;
486 }
487
488 /* Return cgraph node assigned to DECL.  Create new one when needed.  */
489
490 struct cgraph_node *
491 cgraph_node (tree decl)
492 {
493   struct cgraph_node key, *node, **slot;
494
495   gcc_assert (TREE_CODE (decl) == FUNCTION_DECL);
496
497   if (!cgraph_hash)
498     cgraph_hash = htab_create_ggc (10, hash_node, eq_node, NULL);
499
500   key.decl = decl;
501
502   slot = (struct cgraph_node **) htab_find_slot (cgraph_hash, &key, INSERT);
503
504   if (*slot)
505     {
506       node = *slot;
507       if (node->same_body_alias)
508         node = node->same_body;
509       return node;
510     }
511
512   node = cgraph_create_node ();
513   node->decl = decl;
514   *slot = node;
515   if (DECL_CONTEXT (decl) && TREE_CODE (DECL_CONTEXT (decl)) == FUNCTION_DECL)
516     {
517       node->origin = cgraph_node (DECL_CONTEXT (decl));
518       node->next_nested = node->origin->nested;
519       node->origin->nested = node;
520     }
521   if (assembler_name_hash)
522     {
523       void **aslot;
524       tree name = DECL_ASSEMBLER_NAME (decl);
525
526       aslot = htab_find_slot_with_hash (assembler_name_hash, name,
527                                         decl_assembler_name_hash (name),
528                                         INSERT);
529       /* We can have multiple declarations with same assembler name. For C++
530          it is __builtin_strlen and strlen, for instance.  Do we need to
531          record them all?  Original implementation marked just first one
532          so lets hope for the best.  */
533       if (*aslot == NULL)
534         *aslot = node;
535     }
536   return node;
537 }
538
539 /* Mark ALIAS as an alias to DECL.  */
540
541 static struct cgraph_node *
542 cgraph_same_body_alias_1 (tree alias, tree decl)
543 {
544   struct cgraph_node key, *alias_node, *decl_node, **slot;
545
546   gcc_assert (TREE_CODE (decl) == FUNCTION_DECL);
547   gcc_assert (TREE_CODE (alias) == FUNCTION_DECL);
548   decl_node = cgraph_node (decl);
549
550   key.decl = alias;
551
552   slot = (struct cgraph_node **) htab_find_slot (cgraph_hash, &key, INSERT);
553
554   /* If the cgraph_node has been already created, fail.  */
555   if (*slot)
556     return NULL;
557
558   alias_node = cgraph_allocate_node ();
559   alias_node->decl = alias;
560   alias_node->same_body_alias = 1;
561   alias_node->same_body = decl_node;
562   alias_node->previous = NULL;
563   if (decl_node->same_body)
564     decl_node->same_body->previous = alias_node;
565   alias_node->next = decl_node->same_body;
566   alias_node->thunk.alias = decl;
567   decl_node->same_body = alias_node;
568   *slot = alias_node;
569   return alias_node;
570 }
571
572 /* Attempt to mark ALIAS as an alias to DECL.  Return alias node if successful
573    and NULL otherwise. 
574    Same body aliases are output whenever the body of DECL is output,
575    and cgraph_node (ALIAS) transparently returns cgraph_node (DECL).   */
576
577 struct cgraph_node *
578 cgraph_same_body_alias (tree alias, tree decl)
579 {
580 #ifndef ASM_OUTPUT_DEF
581   /* If aliases aren't supported by the assembler, fail.  */
582   return NULL;
583 #endif
584
585   /*gcc_assert (!assembler_name_hash);*/
586
587   return cgraph_same_body_alias_1 (alias, decl);
588 }
589
590 /* Add thunk alias into callgraph.  The alias declaration is ALIAS and it
591    alises DECL with an adjustments made into the first parameter.
592    See comments in thunk_adjust for detail on the parameters.  */
593
594 struct cgraph_node *
595 cgraph_add_thunk (tree alias, tree decl, bool this_adjusting,
596                   HOST_WIDE_INT fixed_offset, HOST_WIDE_INT virtual_value,
597                   tree virtual_offset,
598                   tree real_alias)
599 {
600   struct cgraph_node *node = cgraph_get_node (alias);
601
602   if (node)
603     {
604       gcc_assert (node->local.finalized);
605       gcc_assert (!node->same_body);
606       cgraph_remove_node (node);
607     }
608   
609   node = cgraph_same_body_alias_1 (alias, decl);
610   gcc_assert (node);
611   gcc_checking_assert (!virtual_offset
612                        || tree_int_cst_equal (virtual_offset,
613                                               size_int (virtual_value)));
614   node->thunk.fixed_offset = fixed_offset;
615   node->thunk.this_adjusting = this_adjusting;
616   node->thunk.virtual_value = virtual_value;
617   node->thunk.virtual_offset_p = virtual_offset != NULL;
618   node->thunk.alias = real_alias;
619   node->thunk.thunk_p = true;
620   return node;
621 }
622
623 /* Returns the cgraph node assigned to DECL or NULL if no cgraph node
624    is assigned.  */
625
626 struct cgraph_node *
627 cgraph_get_node_or_alias (const_tree decl)
628 {
629   struct cgraph_node key, *node = NULL, **slot;
630
631   gcc_assert (TREE_CODE (decl) == FUNCTION_DECL);
632
633   if (!cgraph_hash)
634     return NULL;
635
636   key.decl = CONST_CAST2 (tree, const_tree, decl);
637
638   slot = (struct cgraph_node **) htab_find_slot (cgraph_hash, &key,
639                                                  NO_INSERT);
640
641   if (slot && *slot)
642     node = *slot;
643   return node;
644 }
645
646 /* Returns the cgraph node assigned to DECL or NULL if no cgraph node
647    is assigned.  */
648
649 struct cgraph_node *
650 cgraph_get_node (const_tree decl)
651 {
652   struct cgraph_node key, *node = NULL, **slot;
653
654   gcc_assert (TREE_CODE (decl) == FUNCTION_DECL);
655
656   if (!cgraph_hash)
657     return NULL;
658
659   key.decl = CONST_CAST2 (tree, const_tree, decl);
660
661   slot = (struct cgraph_node **) htab_find_slot (cgraph_hash, &key,
662                                                  NO_INSERT);
663
664   if (slot && *slot)
665     {
666       node = *slot;
667       if (node->same_body_alias)
668         node = node->same_body;
669     }
670   return node;
671 }
672
673 /* Insert already constructed node into hashtable.  */
674
675 void
676 cgraph_insert_node_to_hashtable (struct cgraph_node *node)
677 {
678   struct cgraph_node **slot;
679
680   slot = (struct cgraph_node **) htab_find_slot (cgraph_hash, node, INSERT);
681
682   gcc_assert (!*slot);
683   *slot = node;
684 }
685
686 /* Returns a hash code for P.  */
687
688 static hashval_t
689 hash_node_by_assembler_name (const void *p)
690 {
691   const struct cgraph_node *n = (const struct cgraph_node *) p;
692   return (hashval_t) decl_assembler_name_hash (DECL_ASSEMBLER_NAME (n->decl));
693 }
694
695 /* Returns nonzero if P1 and P2 are equal.  */
696
697 static int
698 eq_assembler_name (const void *p1, const void *p2)
699 {
700   const struct cgraph_node *n1 = (const struct cgraph_node *) p1;
701   const_tree name = (const_tree)p2;
702   return (decl_assembler_name_equal (n1->decl, name));
703 }
704
705 /* Return the cgraph node that has ASMNAME for its DECL_ASSEMBLER_NAME.
706    Return NULL if there's no such node.  */
707
708 struct cgraph_node *
709 cgraph_node_for_asm (tree asmname)
710 {
711   struct cgraph_node *node;
712   void **slot;
713
714   if (!assembler_name_hash)
715     {
716       assembler_name_hash =
717         htab_create_ggc (10, hash_node_by_assembler_name, eq_assembler_name,
718                          NULL);
719       for (node = cgraph_nodes; node; node = node->next)
720         if (!node->global.inlined_to)
721           {
722             tree name = DECL_ASSEMBLER_NAME (node->decl);
723             slot = htab_find_slot_with_hash (assembler_name_hash, name,
724                                              decl_assembler_name_hash (name),
725                                              INSERT);
726             /* We can have multiple declarations with same assembler name. For C++
727                it is __builtin_strlen and strlen, for instance.  Do we need to
728                record them all?  Original implementation marked just first one
729                so lets hope for the best.  */
730             if (!*slot)
731               *slot = node;
732             if (node->same_body)
733               {
734                 struct cgraph_node *alias;
735
736                 for (alias = node->same_body; alias; alias = alias->next)
737                   {
738                     hashval_t hash;
739                     name = DECL_ASSEMBLER_NAME (alias->decl);
740                     hash = decl_assembler_name_hash (name);
741                     slot = htab_find_slot_with_hash (assembler_name_hash, name,
742                                                      hash,  INSERT);
743                     if (!*slot)
744                       *slot = alias;
745                   }
746               }
747           }
748     }
749
750   slot = htab_find_slot_with_hash (assembler_name_hash, asmname,
751                                    decl_assembler_name_hash (asmname),
752                                    NO_INSERT);
753
754   if (slot)
755     {
756       node = (struct cgraph_node *) *slot;
757       if (node->same_body_alias)
758         node = node->same_body;
759       return node;
760     }
761   return NULL;
762 }
763
764 /* Returns a hash value for X (which really is a die_struct).  */
765
766 static hashval_t
767 edge_hash (const void *x)
768 {
769   return htab_hash_pointer (((const struct cgraph_edge *) x)->call_stmt);
770 }
771
772 /* Return nonzero if decl_id of die_struct X is the same as UID of decl *Y.  */
773
774 static int
775 edge_eq (const void *x, const void *y)
776 {
777   return ((const struct cgraph_edge *) x)->call_stmt == y;
778 }
779
780 /* Add call graph edge E to call site hash of its caller.  */
781
782 static inline void
783 cgraph_add_edge_to_call_site_hash (struct cgraph_edge *e)
784 {
785   void **slot;
786   slot = htab_find_slot_with_hash (e->caller->call_site_hash,
787                                    e->call_stmt,
788                                    htab_hash_pointer (e->call_stmt),
789                                    INSERT);
790   gcc_assert (!*slot);
791   *slot = e;
792 }
793
794 /* Return the callgraph edge representing the GIMPLE_CALL statement
795    CALL_STMT.  */
796
797 struct cgraph_edge *
798 cgraph_edge (struct cgraph_node *node, gimple call_stmt)
799 {
800   struct cgraph_edge *e, *e2;
801   int n = 0;
802
803   if (node->call_site_hash)
804     return (struct cgraph_edge *)
805       htab_find_with_hash (node->call_site_hash, call_stmt,
806                            htab_hash_pointer (call_stmt));
807
808   /* This loop may turn out to be performance problem.  In such case adding
809      hashtables into call nodes with very many edges is probably best
810      solution.  It is not good idea to add pointer into CALL_EXPR itself
811      because we want to make possible having multiple cgraph nodes representing
812      different clones of the same body before the body is actually cloned.  */
813   for (e = node->callees; e; e = e->next_callee)
814     {
815       if (e->call_stmt == call_stmt)
816         break;
817       n++;
818     }
819
820   if (!e)
821     for (e = node->indirect_calls; e; e = e->next_callee)
822       {
823         if (e->call_stmt == call_stmt)
824           break;
825         n++;
826       }
827
828   if (n > 100)
829     {
830       node->call_site_hash = htab_create_ggc (120, edge_hash, edge_eq, NULL);
831       for (e2 = node->callees; e2; e2 = e2->next_callee)
832         cgraph_add_edge_to_call_site_hash (e2);
833       for (e2 = node->indirect_calls; e2; e2 = e2->next_callee)
834         cgraph_add_edge_to_call_site_hash (e2);
835     }
836
837   return e;
838 }
839
840
841 /* Change field call_stmt of edge E to NEW_STMT.  */
842
843 void
844 cgraph_set_call_stmt (struct cgraph_edge *e, gimple new_stmt)
845 {
846   tree decl;
847
848   if (e->caller->call_site_hash)
849     {
850       htab_remove_elt_with_hash (e->caller->call_site_hash,
851                                  e->call_stmt,
852                                  htab_hash_pointer (e->call_stmt));
853     }
854
855   e->call_stmt = new_stmt;
856   if (e->indirect_unknown_callee
857       && (decl = gimple_call_fndecl (new_stmt)))
858     {
859       /* Constant propagation (and possibly also inlining?) can turn an
860          indirect call into a direct one.  */
861       struct cgraph_node *new_callee = cgraph_node (decl);
862
863       cgraph_make_edge_direct (e, new_callee, NULL);
864     }
865
866   push_cfun (DECL_STRUCT_FUNCTION (e->caller->decl));
867   e->can_throw_external = stmt_can_throw_external (new_stmt);
868   pop_cfun ();
869   if (e->caller->call_site_hash)
870     cgraph_add_edge_to_call_site_hash (e);
871 }
872
873 /* Like cgraph_set_call_stmt but walk the clone tree and update all
874    clones sharing the same function body.  */
875
876 void
877 cgraph_set_call_stmt_including_clones (struct cgraph_node *orig,
878                                        gimple old_stmt, gimple new_stmt)
879 {
880   struct cgraph_node *node;
881   struct cgraph_edge *edge = cgraph_edge (orig, old_stmt);
882
883   if (edge)
884     cgraph_set_call_stmt (edge, new_stmt);
885
886   node = orig->clones;
887   if (node)
888     while (node != orig)
889       {
890         struct cgraph_edge *edge = cgraph_edge (node, old_stmt);
891         if (edge)
892           cgraph_set_call_stmt (edge, new_stmt);
893         if (node->clones)
894           node = node->clones;
895         else if (node->next_sibling_clone)
896           node = node->next_sibling_clone;
897         else
898           {
899             while (node != orig && !node->next_sibling_clone)
900               node = node->clone_of;
901             if (node != orig)
902               node = node->next_sibling_clone;
903           }
904       }
905 }
906
907 /* Like cgraph_create_edge walk the clone tree and update all clones sharing
908    same function body.  If clones already have edge for OLD_STMT; only
909    update the edge same way as cgraph_set_call_stmt_including_clones does.
910
911    TODO: COUNT and LOOP_DEPTH should be properly distributed based on relative
912    frequencies of the clones.  */
913
914 void
915 cgraph_create_edge_including_clones (struct cgraph_node *orig,
916                                      struct cgraph_node *callee,
917                                      gimple old_stmt,
918                                      gimple stmt, gcov_type count,
919                                      int freq, int loop_depth,
920                                      cgraph_inline_failed_t reason)
921 {
922   struct cgraph_node *node;
923   struct cgraph_edge *edge;
924
925   if (!cgraph_edge (orig, stmt))
926     {
927       edge = cgraph_create_edge (orig, callee, stmt, count, freq, loop_depth);
928       edge->inline_failed = reason;
929     }
930
931   node = orig->clones;
932   if (node)
933     while (node != orig)
934       {
935         struct cgraph_edge *edge = cgraph_edge (node, old_stmt);
936
937         /* It is possible that clones already contain the edge while
938            master didn't.  Either we promoted indirect call into direct
939            call in the clone or we are processing clones of unreachable
940            master where edges has been rmeoved.  */
941         if (edge)
942           cgraph_set_call_stmt (edge, stmt);
943         else if (!cgraph_edge (node, stmt))
944           {
945             edge = cgraph_create_edge (node, callee, stmt, count,
946                                        freq, loop_depth);
947             edge->inline_failed = reason;
948           }
949
950         if (node->clones)
951           node = node->clones;
952         else if (node->next_sibling_clone)
953           node = node->next_sibling_clone;
954         else
955           {
956             while (node != orig && !node->next_sibling_clone)
957               node = node->clone_of;
958             if (node != orig)
959               node = node->next_sibling_clone;
960           }
961       }
962 }
963
964 /* Give initial reasons why inlining would fail on EDGE.  This gets either
965    nullified or usually overwritten by more precise reasons later.  */
966
967 static void
968 initialize_inline_failed (struct cgraph_edge *e)
969 {
970   struct cgraph_node *callee = e->callee;
971
972   if (e->indirect_unknown_callee)
973     e->inline_failed = CIF_INDIRECT_UNKNOWN_CALL;
974   else if (!callee->analyzed)
975     e->inline_failed = CIF_BODY_NOT_AVAILABLE;
976   else if (callee->local.redefined_extern_inline)
977     e->inline_failed = CIF_REDEFINED_EXTERN_INLINE;
978   else if (!callee->local.inlinable)
979     e->inline_failed = CIF_FUNCTION_NOT_INLINABLE;
980   else if (e->call_stmt && gimple_call_cannot_inline_p (e->call_stmt))
981     e->inline_failed = CIF_MISMATCHED_ARGUMENTS;
982   else
983     e->inline_failed = CIF_FUNCTION_NOT_CONSIDERED;
984 }
985
986 /* Allocate a cgraph_edge structure and fill it with data according to the
987    parameters of which only CALLEE can be NULL (when creating an indirect call
988    edge).  */
989
990 static struct cgraph_edge *
991 cgraph_create_edge_1 (struct cgraph_node *caller, struct cgraph_node *callee,
992                        gimple call_stmt, gcov_type count, int freq, int nest)
993 {
994   struct cgraph_edge *edge;
995
996   /* LTO does not actually have access to the call_stmt since these
997      have not been loaded yet.  */
998   if (call_stmt)
999     {
1000       /* This is a rather expensive check possibly trigerring
1001          construction of call stmt hashtable.  */
1002       gcc_checking_assert (!cgraph_edge (caller, call_stmt));
1003
1004       gcc_assert (is_gimple_call (call_stmt));
1005     }
1006
1007   if (free_edges)
1008     {
1009       edge = free_edges;
1010       free_edges = NEXT_FREE_EDGE (edge);
1011     }
1012   else
1013     {
1014       edge = ggc_alloc_cgraph_edge ();
1015       edge->uid = cgraph_edge_max_uid++;
1016     }
1017
1018   edge->aux = NULL;
1019   edge->caller = caller;
1020   edge->callee = callee;
1021   edge->prev_caller = NULL;
1022   edge->next_caller = NULL;
1023   edge->prev_callee = NULL;
1024   edge->next_callee = NULL;
1025
1026   edge->count = count;
1027   gcc_assert (count >= 0);
1028   edge->frequency = freq;
1029   gcc_assert (freq >= 0);
1030   gcc_assert (freq <= CGRAPH_FREQ_MAX);
1031   edge->loop_nest = nest;
1032
1033   edge->call_stmt = call_stmt;
1034   push_cfun (DECL_STRUCT_FUNCTION (caller->decl));
1035   edge->can_throw_external
1036     = call_stmt ? stmt_can_throw_external (call_stmt) : false;
1037   pop_cfun ();
1038   edge->call_stmt_cannot_inline_p =
1039     (call_stmt ? gimple_call_cannot_inline_p (call_stmt) : false);
1040   if (call_stmt && caller->call_site_hash)
1041     cgraph_add_edge_to_call_site_hash (edge);
1042
1043   edge->indirect_info = NULL;
1044   edge->indirect_inlining_edge = 0;
1045
1046   return edge;
1047 }
1048
1049 /* Create edge from CALLER to CALLEE in the cgraph.  */
1050
1051 struct cgraph_edge *
1052 cgraph_create_edge (struct cgraph_node *caller, struct cgraph_node *callee,
1053                     gimple call_stmt, gcov_type count, int freq, int nest)
1054 {
1055   struct cgraph_edge *edge = cgraph_create_edge_1 (caller, callee, call_stmt,
1056                                                    count, freq, nest);
1057
1058   edge->indirect_unknown_callee = 0;
1059   initialize_inline_failed (edge);
1060
1061   edge->next_caller = callee->callers;
1062   if (callee->callers)
1063     callee->callers->prev_caller = edge;
1064   edge->next_callee = caller->callees;
1065   if (caller->callees)
1066     caller->callees->prev_callee = edge;
1067   caller->callees = edge;
1068   callee->callers = edge;
1069
1070   return edge;
1071 }
1072
1073
1074 /* Create an indirect edge with a yet-undetermined callee where the call
1075    statement destination is a formal parameter of the caller with index
1076    PARAM_INDEX. */
1077
1078 struct cgraph_edge *
1079 cgraph_create_indirect_edge (struct cgraph_node *caller, gimple call_stmt,
1080                              int ecf_flags,
1081                              gcov_type count, int freq, int nest)
1082 {
1083   struct cgraph_edge *edge = cgraph_create_edge_1 (caller, NULL, call_stmt,
1084                                                    count, freq, nest);
1085
1086   edge->indirect_unknown_callee = 1;
1087   initialize_inline_failed (edge);
1088
1089   edge->indirect_info = ggc_alloc_cleared_cgraph_indirect_call_info ();
1090   edge->indirect_info->param_index = -1;
1091   edge->indirect_info->ecf_flags = ecf_flags;
1092
1093   edge->next_callee = caller->indirect_calls;
1094   if (caller->indirect_calls)
1095     caller->indirect_calls->prev_callee = edge;
1096   caller->indirect_calls = edge;
1097
1098   return edge;
1099 }
1100
1101 /* Remove the edge E from the list of the callers of the callee.  */
1102
1103 static inline void
1104 cgraph_edge_remove_callee (struct cgraph_edge *e)
1105 {
1106   gcc_assert (!e->indirect_unknown_callee);
1107   if (e->prev_caller)
1108     e->prev_caller->next_caller = e->next_caller;
1109   if (e->next_caller)
1110     e->next_caller->prev_caller = e->prev_caller;
1111   if (!e->prev_caller)
1112     e->callee->callers = e->next_caller;
1113 }
1114
1115 /* Remove the edge E from the list of the callees of the caller.  */
1116
1117 static inline void
1118 cgraph_edge_remove_caller (struct cgraph_edge *e)
1119 {
1120   if (e->prev_callee)
1121     e->prev_callee->next_callee = e->next_callee;
1122   if (e->next_callee)
1123     e->next_callee->prev_callee = e->prev_callee;
1124   if (!e->prev_callee)
1125     {
1126       if (e->indirect_unknown_callee)
1127         e->caller->indirect_calls = e->next_callee;
1128       else
1129         e->caller->callees = e->next_callee;
1130     }
1131   if (e->caller->call_site_hash)
1132     htab_remove_elt_with_hash (e->caller->call_site_hash,
1133                                e->call_stmt,
1134                                htab_hash_pointer (e->call_stmt));
1135 }
1136
1137 /* Put the edge onto the free list.  */
1138
1139 static void
1140 cgraph_free_edge (struct cgraph_edge *e)
1141 {
1142   int uid = e->uid;
1143
1144   /* Clear out the edge so we do not dangle pointers.  */
1145   memset (e, 0, sizeof (*e));
1146   e->uid = uid;
1147   NEXT_FREE_EDGE (e) = free_edges;
1148   free_edges = e;
1149 }
1150
1151 /* Remove the edge E in the cgraph.  */
1152
1153 void
1154 cgraph_remove_edge (struct cgraph_edge *e)
1155 {
1156   /* Call all edge removal hooks.  */
1157   cgraph_call_edge_removal_hooks (e);
1158
1159   if (!e->indirect_unknown_callee)
1160     /* Remove from callers list of the callee.  */
1161     cgraph_edge_remove_callee (e);
1162
1163   /* Remove from callees list of the callers.  */
1164   cgraph_edge_remove_caller (e);
1165
1166   /* Put the edge onto the free list.  */
1167   cgraph_free_edge (e);
1168 }
1169
1170 /* Set callee of call graph edge E and add it to the corresponding set of
1171    callers. */
1172
1173 static void
1174 cgraph_set_edge_callee (struct cgraph_edge *e, struct cgraph_node *n)
1175 {
1176   e->prev_caller = NULL;
1177   if (n->callers)
1178     n->callers->prev_caller = e;
1179   e->next_caller = n->callers;
1180   n->callers = e;
1181   e->callee = n;
1182 }
1183
1184 /* Redirect callee of E to N.  The function does not update underlying
1185    call expression.  */
1186
1187 void
1188 cgraph_redirect_edge_callee (struct cgraph_edge *e, struct cgraph_node *n)
1189 {
1190   /* Remove from callers list of the current callee.  */
1191   cgraph_edge_remove_callee (e);
1192
1193   /* Insert to callers list of the new callee.  */
1194   cgraph_set_edge_callee (e, n);
1195 }
1196
1197 /* Make an indirect EDGE with an unknown callee an ordinary edge leading to
1198    CALLEE.  DELTA, if non-NULL, is an integer constant that is to be added to
1199    the this pointer (first parameter).  */
1200
1201 void
1202 cgraph_make_edge_direct (struct cgraph_edge *edge, struct cgraph_node *callee,
1203                          tree delta)
1204 {
1205   edge->indirect_unknown_callee = 0;
1206   edge->indirect_info->thunk_delta = delta;
1207
1208   /* Get the edge out of the indirect edge list. */
1209   if (edge->prev_callee)
1210     edge->prev_callee->next_callee = edge->next_callee;
1211   if (edge->next_callee)
1212     edge->next_callee->prev_callee = edge->prev_callee;
1213   if (!edge->prev_callee)
1214     edge->caller->indirect_calls = edge->next_callee;
1215
1216   /* Put it into the normal callee list */
1217   edge->prev_callee = NULL;
1218   edge->next_callee = edge->caller->callees;
1219   if (edge->caller->callees)
1220     edge->caller->callees->prev_callee = edge;
1221   edge->caller->callees = edge;
1222
1223   /* Insert to callers list of the new callee.  */
1224   cgraph_set_edge_callee (edge, callee);
1225
1226   /* We need to re-determine the inlining status of the edge.  */
1227   initialize_inline_failed (edge);
1228 }
1229
1230
1231 /* Update or remove the corresponding cgraph edge if a GIMPLE_CALL
1232    OLD_STMT changed into NEW_STMT.  OLD_CALL is gimple_call_fndecl
1233    of OLD_STMT if it was previously call statement.  */
1234
1235 static void
1236 cgraph_update_edges_for_call_stmt_node (struct cgraph_node *node,
1237                                         gimple old_stmt, tree old_call, gimple new_stmt)
1238 {
1239   tree new_call = (is_gimple_call (new_stmt)) ? gimple_call_fndecl (new_stmt) : 0;
1240
1241   /* We are seeing indirect calls, then there is nothing to update.  */
1242   if (!new_call && !old_call)
1243     return;
1244   /* See if we turned indirect call into direct call or folded call to one builtin
1245      into different bultin.  */
1246   if (old_call != new_call)
1247     {
1248       struct cgraph_edge *e = cgraph_edge (node, old_stmt);
1249       struct cgraph_edge *ne = NULL;
1250       gcov_type count;
1251       int frequency;
1252       int loop_nest;
1253
1254       if (e)
1255         {
1256           /* See if the edge is already there and has the correct callee.  It
1257              might be so because of indirect inlining has already updated
1258              it.  We also might've cloned and redirected the edge.  */
1259           if (new_call && e->callee)
1260             {
1261               struct cgraph_node *callee = e->callee;
1262               while (callee)
1263                 {
1264                   if (callee->decl == new_call
1265                       || callee->former_clone_of == new_call)
1266                     return;
1267                   callee = callee->clone_of;
1268                 }
1269             }
1270
1271           /* Otherwise remove edge and create new one; we can't simply redirect
1272              since function has changed, so inline plan and other information
1273              attached to edge is invalid.  */
1274           count = e->count;
1275           frequency = e->frequency;
1276           loop_nest = e->loop_nest;
1277           cgraph_remove_edge (e);
1278         }
1279       else
1280         {
1281           /* We are seeing new direct call; compute profile info based on BB.  */
1282           basic_block bb = gimple_bb (new_stmt);
1283           count = bb->count;
1284           frequency = compute_call_stmt_bb_frequency (current_function_decl,
1285                                                       bb);
1286           loop_nest = bb->loop_depth;
1287         }
1288
1289       if (new_call)
1290         {
1291           ne = cgraph_create_edge (node, cgraph_node (new_call),
1292                                    new_stmt, count, frequency,
1293                                    loop_nest);
1294           gcc_assert (ne->inline_failed);
1295         }
1296     }
1297   /* We only updated the call stmt; update pointer in cgraph edge..  */
1298   else if (old_stmt != new_stmt)
1299     cgraph_set_call_stmt (cgraph_edge (node, old_stmt), new_stmt);
1300 }
1301
1302 /* Update or remove the corresponding cgraph edge if a GIMPLE_CALL
1303    OLD_STMT changed into NEW_STMT.  OLD_DECL is gimple_call_fndecl
1304    of OLD_STMT before it was updated (updating can happen inplace).  */
1305
1306 void
1307 cgraph_update_edges_for_call_stmt (gimple old_stmt, tree old_decl, gimple new_stmt)
1308 {
1309   struct cgraph_node *orig = cgraph_node (cfun->decl);
1310   struct cgraph_node *node;
1311
1312   cgraph_update_edges_for_call_stmt_node (orig, old_stmt, old_decl, new_stmt);
1313   if (orig->clones)
1314     for (node = orig->clones; node != orig;)
1315       {
1316         cgraph_update_edges_for_call_stmt_node (node, old_stmt, old_decl, new_stmt);
1317         if (node->clones)
1318           node = node->clones;
1319         else if (node->next_sibling_clone)
1320           node = node->next_sibling_clone;
1321         else
1322           {
1323             while (node != orig && !node->next_sibling_clone)
1324               node = node->clone_of;
1325             if (node != orig)
1326               node = node->next_sibling_clone;
1327           }
1328       }
1329 }
1330
1331
1332 /* Remove all callees from the node.  */
1333
1334 void
1335 cgraph_node_remove_callees (struct cgraph_node *node)
1336 {
1337   struct cgraph_edge *e, *f;
1338
1339   /* It is sufficient to remove the edges from the lists of callers of
1340      the callees.  The callee list of the node can be zapped with one
1341      assignment.  */
1342   for (e = node->callees; e; e = f)
1343     {
1344       f = e->next_callee;
1345       cgraph_call_edge_removal_hooks (e);
1346       if (!e->indirect_unknown_callee)
1347         cgraph_edge_remove_callee (e);
1348       cgraph_free_edge (e);
1349     }
1350   for (e = node->indirect_calls; e; e = f)
1351     {
1352       f = e->next_callee;
1353       cgraph_call_edge_removal_hooks (e);
1354       if (!e->indirect_unknown_callee)
1355         cgraph_edge_remove_callee (e);
1356       cgraph_free_edge (e);
1357     }
1358   node->indirect_calls = NULL;
1359   node->callees = NULL;
1360   if (node->call_site_hash)
1361     {
1362       htab_delete (node->call_site_hash);
1363       node->call_site_hash = NULL;
1364     }
1365 }
1366
1367 /* Remove all callers from the node.  */
1368
1369 static void
1370 cgraph_node_remove_callers (struct cgraph_node *node)
1371 {
1372   struct cgraph_edge *e, *f;
1373
1374   /* It is sufficient to remove the edges from the lists of callees of
1375      the callers.  The caller list of the node can be zapped with one
1376      assignment.  */
1377   for (e = node->callers; e; e = f)
1378     {
1379       f = e->next_caller;
1380       cgraph_call_edge_removal_hooks (e);
1381       cgraph_edge_remove_caller (e);
1382       cgraph_free_edge (e);
1383     }
1384   node->callers = NULL;
1385 }
1386
1387 /* Release memory used to represent body of function NODE.  */
1388
1389 void
1390 cgraph_release_function_body (struct cgraph_node *node)
1391 {
1392   if (DECL_STRUCT_FUNCTION (node->decl))
1393     {
1394       tree old_decl = current_function_decl;
1395       push_cfun (DECL_STRUCT_FUNCTION (node->decl));
1396       if (cfun->gimple_df)
1397         {
1398           current_function_decl = node->decl;
1399           delete_tree_ssa ();
1400           delete_tree_cfg_annotations ();
1401           cfun->eh = NULL;
1402           current_function_decl = old_decl;
1403         }
1404       if (cfun->cfg)
1405         {
1406           gcc_assert (dom_computed[0] == DOM_NONE);
1407           gcc_assert (dom_computed[1] == DOM_NONE);
1408           clear_edges ();
1409         }
1410       if (cfun->value_histograms)
1411         free_histograms ();
1412       gcc_assert (!current_loops);
1413       pop_cfun();
1414       gimple_set_body (node->decl, NULL);
1415       VEC_free (ipa_opt_pass, heap,
1416                 node->ipa_transforms_to_apply);
1417       /* Struct function hangs a lot of data that would leak if we didn't
1418          removed all pointers to it.   */
1419       ggc_free (DECL_STRUCT_FUNCTION (node->decl));
1420       DECL_STRUCT_FUNCTION (node->decl) = NULL;
1421     }
1422   DECL_SAVED_TREE (node->decl) = NULL;
1423   /* If the node is abstract and needed, then do not clear DECL_INITIAL
1424      of its associated function function declaration because it's
1425      needed to emit debug info later.  */
1426   if (!node->abstract_and_needed)
1427     DECL_INITIAL (node->decl) = error_mark_node;
1428 }
1429
1430 /* Remove same body alias node.  */
1431
1432 void
1433 cgraph_remove_same_body_alias (struct cgraph_node *node)
1434 {
1435   void **slot;
1436   int uid = node->uid;
1437
1438   gcc_assert (node->same_body_alias);
1439   if (node->previous)
1440     node->previous->next = node->next;
1441   else
1442     node->same_body->same_body = node->next;
1443   if (node->next)
1444     node->next->previous = node->previous;
1445   node->next = NULL;
1446   node->previous = NULL;
1447   slot = htab_find_slot (cgraph_hash, node, NO_INSERT);
1448   if (*slot == node)
1449     htab_clear_slot (cgraph_hash, slot);
1450   if (assembler_name_hash)
1451     {
1452       tree name = DECL_ASSEMBLER_NAME (node->decl);
1453       slot = htab_find_slot_with_hash (assembler_name_hash, name,
1454                                        decl_assembler_name_hash (name),
1455                                        NO_INSERT);
1456       if (slot && *slot == node)
1457         htab_clear_slot (assembler_name_hash, slot);
1458     }
1459
1460   /* Clear out the node to NULL all pointers and add the node to the free
1461      list.  */
1462   memset (node, 0, sizeof(*node));
1463   node->uid = uid;
1464   NEXT_FREE_NODE (node) = free_nodes;
1465   free_nodes = node;
1466 }
1467
1468 /* Remove the node from cgraph.  */
1469
1470 void
1471 cgraph_remove_node (struct cgraph_node *node)
1472 {
1473   void **slot;
1474   bool kill_body = false;
1475   struct cgraph_node *n;
1476   int uid = node->uid;
1477
1478   cgraph_call_node_removal_hooks (node);
1479   cgraph_node_remove_callers (node);
1480   cgraph_node_remove_callees (node);
1481   ipa_remove_all_references (&node->ref_list);
1482   ipa_remove_all_refering (&node->ref_list);
1483   VEC_free (ipa_opt_pass, heap,
1484             node->ipa_transforms_to_apply);
1485
1486   /* Incremental inlining access removed nodes stored in the postorder list.
1487      */
1488   node->needed = node->reachable = false;
1489   for (n = node->nested; n; n = n->next_nested)
1490     n->origin = NULL;
1491   node->nested = NULL;
1492   if (node->origin)
1493     {
1494       struct cgraph_node **node2 = &node->origin->nested;
1495
1496       while (*node2 != node)
1497         node2 = &(*node2)->next_nested;
1498       *node2 = node->next_nested;
1499     }
1500   if (node->previous)
1501     node->previous->next = node->next;
1502   else
1503     cgraph_nodes = node->next;
1504   if (node->next)
1505     node->next->previous = node->previous;
1506   node->next = NULL;
1507   node->previous = NULL;
1508   slot = htab_find_slot (cgraph_hash, node, NO_INSERT);
1509   if (*slot == node)
1510     {
1511       struct cgraph_node *next_inline_clone;
1512
1513       for (next_inline_clone = node->clones;
1514            next_inline_clone && next_inline_clone->decl != node->decl;
1515            next_inline_clone = next_inline_clone->next_sibling_clone)
1516         ;
1517
1518       /* If there is inline clone of the node being removed, we need
1519          to put it into the position of removed node and reorganize all
1520          other clones to be based on it.  */
1521       if (next_inline_clone)
1522         {
1523           struct cgraph_node *n;
1524           struct cgraph_node *new_clones;
1525
1526           *slot = next_inline_clone;
1527
1528           /* Unlink inline clone from the list of clones of removed node.  */
1529           if (next_inline_clone->next_sibling_clone)
1530             next_inline_clone->next_sibling_clone->prev_sibling_clone
1531               = next_inline_clone->prev_sibling_clone;
1532           if (next_inline_clone->prev_sibling_clone)
1533             {
1534               gcc_assert (node->clones != next_inline_clone);
1535               next_inline_clone->prev_sibling_clone->next_sibling_clone
1536                 = next_inline_clone->next_sibling_clone;
1537             }
1538           else
1539             {
1540               gcc_assert (node->clones == next_inline_clone);
1541               node->clones = next_inline_clone->next_sibling_clone;
1542             }
1543
1544           new_clones = node->clones;
1545           node->clones = NULL;
1546
1547           /* Copy clone info.  */
1548           next_inline_clone->clone = node->clone;
1549
1550           /* Now place it into clone tree at same level at NODE.  */
1551           next_inline_clone->clone_of = node->clone_of;
1552           next_inline_clone->prev_sibling_clone = NULL;
1553           next_inline_clone->next_sibling_clone = NULL;
1554           if (node->clone_of)
1555             {
1556               if (node->clone_of->clones)
1557                 node->clone_of->clones->prev_sibling_clone = next_inline_clone;
1558               next_inline_clone->next_sibling_clone = node->clone_of->clones;
1559               node->clone_of->clones = next_inline_clone;
1560             }
1561
1562           /* Merge the clone list.  */
1563           if (new_clones)
1564             {
1565               if (!next_inline_clone->clones)
1566                 next_inline_clone->clones = new_clones;
1567               else
1568                 {
1569                   n = next_inline_clone->clones;
1570                   while (n->next_sibling_clone)
1571                     n =  n->next_sibling_clone;
1572                   n->next_sibling_clone = new_clones;
1573                   new_clones->prev_sibling_clone = n;
1574                 }
1575             }
1576
1577           /* Update clone_of pointers.  */
1578           n = new_clones;
1579           while (n)
1580             {
1581               n->clone_of = next_inline_clone;
1582               n = n->next_sibling_clone;
1583             }
1584         }
1585       else
1586         {
1587           htab_clear_slot (cgraph_hash, slot);
1588           kill_body = true;
1589         }
1590
1591     }
1592   if (node->prev_sibling_clone)
1593     node->prev_sibling_clone->next_sibling_clone = node->next_sibling_clone;
1594   else if (node->clone_of)
1595     node->clone_of->clones = node->next_sibling_clone;
1596   if (node->next_sibling_clone)
1597     node->next_sibling_clone->prev_sibling_clone = node->prev_sibling_clone;
1598   if (node->clones)
1599     {
1600       struct cgraph_node *n, *next;
1601
1602       if (node->clone_of)
1603         {
1604           for (n = node->clones; n->next_sibling_clone; n = n->next_sibling_clone)
1605             n->clone_of = node->clone_of;
1606           n->clone_of = node->clone_of;
1607           n->next_sibling_clone = node->clone_of->clones;
1608           if (node->clone_of->clones)
1609             node->clone_of->clones->prev_sibling_clone = n;
1610           node->clone_of->clones = node->clones;
1611         }
1612       else
1613         {
1614           /* We are removing node with clones.  this makes clones inconsistent,
1615              but assume they will be removed subsequently and just keep clone
1616              tree intact.  This can happen in unreachable function removal since
1617              we remove unreachable functions in random order, not by bottom-up
1618              walk of clone trees.  */
1619           for (n = node->clones; n; n = next)
1620             {
1621                next = n->next_sibling_clone;
1622                n->next_sibling_clone = NULL;
1623                n->prev_sibling_clone = NULL;
1624                n->clone_of = NULL;
1625             }
1626         }
1627     }
1628
1629   while (node->same_body)
1630     cgraph_remove_same_body_alias (node->same_body);
1631
1632   if (node->same_comdat_group)
1633     {
1634       struct cgraph_node *prev;
1635       for (prev = node->same_comdat_group;
1636            prev->same_comdat_group != node;
1637            prev = prev->same_comdat_group)
1638         ;
1639       if (node->same_comdat_group == prev)
1640         prev->same_comdat_group = NULL;
1641       else
1642         prev->same_comdat_group = node->same_comdat_group;
1643       node->same_comdat_group = NULL;
1644     }
1645
1646   /* While all the clones are removed after being proceeded, the function
1647      itself is kept in the cgraph even after it is compiled.  Check whether
1648      we are done with this body and reclaim it proactively if this is the case.
1649      */
1650   if (!kill_body && *slot)
1651     {
1652       struct cgraph_node *n = (struct cgraph_node *) *slot;
1653       if (!n->clones && !n->clone_of && !n->global.inlined_to
1654           && (cgraph_global_info_ready
1655               && (TREE_ASM_WRITTEN (n->decl) || DECL_EXTERNAL (n->decl)
1656                   || n->in_other_partition)))
1657         kill_body = true;
1658     }
1659   if (assembler_name_hash)
1660     {
1661       tree name = DECL_ASSEMBLER_NAME (node->decl);
1662       slot = htab_find_slot_with_hash (assembler_name_hash, name,
1663                                        decl_assembler_name_hash (name),
1664                                        NO_INSERT);
1665       /* Inline clones are not hashed.  */
1666       if (slot && *slot == node)
1667         htab_clear_slot (assembler_name_hash, slot);
1668     }
1669
1670   if (kill_body)
1671     cgraph_release_function_body (node);
1672   node->decl = NULL;
1673   if (node->call_site_hash)
1674     {
1675       htab_delete (node->call_site_hash);
1676       node->call_site_hash = NULL;
1677     }
1678   cgraph_n_nodes--;
1679
1680   /* Clear out the node to NULL all pointers and add the node to the free
1681      list.  */
1682   memset (node, 0, sizeof(*node));
1683   node->uid = uid;
1684   NEXT_FREE_NODE (node) = free_nodes;
1685   free_nodes = node;
1686 }
1687
1688 /* Remove the node from cgraph.  */
1689
1690 void
1691 cgraph_remove_node_and_inline_clones (struct cgraph_node *node)
1692 {
1693   struct cgraph_edge *e, *next;
1694   for (e = node->callees; e; e = next)
1695     {
1696       next = e->next_callee;
1697       if (!e->inline_failed)
1698         cgraph_remove_node_and_inline_clones (e->callee);
1699     }
1700   cgraph_remove_node (node);
1701 }
1702
1703 /* Notify finalize_compilation_unit that given node is reachable.  */
1704
1705 void
1706 cgraph_mark_reachable_node (struct cgraph_node *node)
1707 {
1708   if (!node->reachable && node->local.finalized)
1709     {
1710       if (cgraph_global_info_ready)
1711         {
1712           /* Verify that function does not appear to be needed out of blue
1713              during the optimization process.  This can happen for extern
1714              inlines when bodies was removed after inlining.  */
1715           gcc_assert ((node->analyzed || node->in_other_partition
1716                        || DECL_EXTERNAL (node->decl)));
1717         }
1718       else
1719         notice_global_symbol (node->decl);
1720       node->reachable = 1;
1721
1722       node->next_needed = cgraph_nodes_queue;
1723       cgraph_nodes_queue = node;
1724     }
1725 }
1726
1727 /* Likewise indicate that a node is needed, i.e. reachable via some
1728    external means.  */
1729
1730 void
1731 cgraph_mark_needed_node (struct cgraph_node *node)
1732 {
1733   node->needed = 1;
1734   gcc_assert (!node->global.inlined_to);
1735   cgraph_mark_reachable_node (node);
1736 }
1737
1738 /* Likewise indicate that a node is having address taken.  */
1739
1740 void
1741 cgraph_mark_address_taken_node (struct cgraph_node *node)
1742 {
1743   gcc_assert (!node->global.inlined_to);
1744   cgraph_mark_reachable_node (node);
1745   node->address_taken = 1;
1746 }
1747
1748 /* Return local info for the compiled function.  */
1749
1750 struct cgraph_local_info *
1751 cgraph_local_info (tree decl)
1752 {
1753   struct cgraph_node *node;
1754
1755   gcc_assert (TREE_CODE (decl) == FUNCTION_DECL);
1756   node = cgraph_node (decl);
1757   return &node->local;
1758 }
1759
1760 /* Return local info for the compiled function.  */
1761
1762 struct cgraph_global_info *
1763 cgraph_global_info (tree decl)
1764 {
1765   struct cgraph_node *node;
1766
1767   gcc_assert (TREE_CODE (decl) == FUNCTION_DECL && cgraph_global_info_ready);
1768   node = cgraph_node (decl);
1769   return &node->global;
1770 }
1771
1772 /* Return local info for the compiled function.  */
1773
1774 struct cgraph_rtl_info *
1775 cgraph_rtl_info (tree decl)
1776 {
1777   struct cgraph_node *node;
1778
1779   gcc_assert (TREE_CODE (decl) == FUNCTION_DECL);
1780   node = cgraph_node (decl);
1781   if (decl != current_function_decl
1782       && !TREE_ASM_WRITTEN (node->decl))
1783     return NULL;
1784   return &node->rtl;
1785 }
1786
1787 /* Return a string describing the failure REASON.  */
1788
1789 const char*
1790 cgraph_inline_failed_string (cgraph_inline_failed_t reason)
1791 {
1792 #undef DEFCIFCODE
1793 #define DEFCIFCODE(code, string)        string,
1794
1795   static const char *cif_string_table[CIF_N_REASONS] = {
1796 #include "cif-code.def"
1797   };
1798
1799   /* Signedness of an enum type is implementation defined, so cast it
1800      to unsigned before testing. */
1801   gcc_assert ((unsigned) reason < CIF_N_REASONS);
1802   return cif_string_table[reason];
1803 }
1804
1805 /* Return name of the node used in debug output.  */
1806 const char *
1807 cgraph_node_name (struct cgraph_node *node)
1808 {
1809   return lang_hooks.decl_printable_name (node->decl, 2);
1810 }
1811
1812 /* Names used to print out the availability enum.  */
1813 const char * const cgraph_availability_names[] =
1814   {"unset", "not_available", "overwritable", "available", "local"};
1815
1816
1817 /* Dump call graph node NODE to file F.  */
1818
1819 void
1820 dump_cgraph_node (FILE *f, struct cgraph_node *node)
1821 {
1822   struct cgraph_edge *edge;
1823   int indirect_calls_count = 0;
1824
1825   fprintf (f, "%s/%i(%i)", cgraph_node_name (node), node->uid,
1826            node->pid);
1827   dump_addr (f, " @", (void *)node);
1828   if (DECL_ASSEMBLER_NAME_SET_P (node->decl))
1829     fprintf (f, " (asm: %s)", IDENTIFIER_POINTER (DECL_ASSEMBLER_NAME (node->decl)));
1830   if (node->global.inlined_to)
1831     fprintf (f, " (inline copy in %s/%i)",
1832              cgraph_node_name (node->global.inlined_to),
1833              node->global.inlined_to->uid);
1834   if (node->same_comdat_group)
1835     fprintf (f, " (same comdat group as %s/%i)",
1836              cgraph_node_name (node->same_comdat_group),
1837              node->same_comdat_group->uid);
1838   if (node->clone_of)
1839     fprintf (f, " (clone of %s/%i)",
1840              cgraph_node_name (node->clone_of),
1841              node->clone_of->uid);
1842   if (cgraph_function_flags_ready)
1843     fprintf (f, " availability:%s",
1844              cgraph_availability_names [cgraph_function_body_availability (node)]);
1845   if (node->analyzed)
1846     fprintf (f, " analyzed");
1847   if (node->in_other_partition)
1848     fprintf (f, " in_other_partition");
1849   if (node->count)
1850     fprintf (f, " executed "HOST_WIDEST_INT_PRINT_DEC"x",
1851              (HOST_WIDEST_INT)node->count);
1852   if (node->local.inline_summary.self_time)
1853     fprintf (f, " %i time, %i benefit", node->local.inline_summary.self_time,
1854                                         node->local.inline_summary.time_inlining_benefit);
1855   if (node->global.time && node->global.time
1856       != node->local.inline_summary.self_time)
1857     fprintf (f, " (%i after inlining)", node->global.time);
1858   if (node->local.inline_summary.self_size)
1859     fprintf (f, " %i size, %i benefit", node->local.inline_summary.self_size,
1860                                         node->local.inline_summary.size_inlining_benefit);
1861   if (node->global.size && node->global.size
1862       != node->local.inline_summary.self_size)
1863     fprintf (f, " (%i after inlining)", node->global.size);
1864   if (node->local.inline_summary.estimated_self_stack_size)
1865     fprintf (f, " %i bytes stack usage", (int)node->local.inline_summary.estimated_self_stack_size);
1866   if (node->global.estimated_stack_size != node->local.inline_summary.estimated_self_stack_size)
1867     fprintf (f, " %i bytes after inlining", (int)node->global.estimated_stack_size);
1868   if (node->origin)
1869     fprintf (f, " nested in: %s", cgraph_node_name (node->origin));
1870   if (node->needed)
1871     fprintf (f, " needed");
1872   if (node->address_taken)
1873     fprintf (f, " address_taken");
1874   else if (node->reachable)
1875     fprintf (f, " reachable");
1876   else if (node->reachable_from_other_partition)
1877     fprintf (f, " reachable_from_other_partition");
1878   if (gimple_has_body_p (node->decl))
1879     fprintf (f, " body");
1880   if (node->process)
1881     fprintf (f, " process");
1882   if (node->local.local)
1883     fprintf (f, " local");
1884   if (node->local.externally_visible)
1885     fprintf (f, " externally_visible");
1886   if (node->resolution != LDPR_UNKNOWN)
1887     fprintf (f, " %s",
1888              ld_plugin_symbol_resolution_names[(int)node->resolution]);
1889   if (node->local.finalized)
1890     fprintf (f, " finalized");
1891   if (node->local.disregard_inline_limits)
1892     fprintf (f, " always_inline");
1893   else if (node->local.inlinable)
1894     fprintf (f, " inlinable");
1895   else if (node->local.versionable)
1896     fprintf (f, " versionable");
1897   if (node->local.redefined_extern_inline)
1898     fprintf (f, " redefined_extern_inline");
1899   if (TREE_ASM_WRITTEN (node->decl))
1900     fprintf (f, " asm_written");
1901   if (node->only_called_at_startup)
1902     fprintf (f, " only_called_at_startup");
1903   if (node->only_called_at_exit)
1904     fprintf (f, " only_called_at_exit");
1905
1906   fprintf (f, "\n  called by: ");
1907   for (edge = node->callers; edge; edge = edge->next_caller)
1908     {
1909       fprintf (f, "%s/%i ", cgraph_node_name (edge->caller),
1910                edge->caller->uid);
1911       if (edge->count)
1912         fprintf (f, "("HOST_WIDEST_INT_PRINT_DEC"x) ",
1913                  (HOST_WIDEST_INT)edge->count);
1914       if (edge->frequency)
1915         fprintf (f, "(%.2f per call) ",
1916                  edge->frequency / (double)CGRAPH_FREQ_BASE);
1917       if (!edge->inline_failed)
1918         fprintf(f, "(inlined) ");
1919       if (edge->indirect_inlining_edge)
1920         fprintf(f, "(indirect_inlining) ");
1921       if (edge->can_throw_external)
1922         fprintf(f, "(can throw external) ");
1923     }
1924
1925   fprintf (f, "\n  calls: ");
1926   for (edge = node->callees; edge; edge = edge->next_callee)
1927     {
1928       fprintf (f, "%s/%i ", cgraph_node_name (edge->callee),
1929                edge->callee->uid);
1930       if (!edge->inline_failed)
1931         fprintf(f, "(inlined) ");
1932       if (edge->indirect_inlining_edge)
1933         fprintf(f, "(indirect_inlining) ");
1934       if (edge->count)
1935         fprintf (f, "("HOST_WIDEST_INT_PRINT_DEC"x) ",
1936                  (HOST_WIDEST_INT)edge->count);
1937       if (edge->frequency)
1938         fprintf (f, "(%.2f per call) ",
1939                  edge->frequency / (double)CGRAPH_FREQ_BASE);
1940       if (edge->loop_nest)
1941         fprintf (f, "(nested in %i loops) ", edge->loop_nest);
1942       if (edge->can_throw_external)
1943         fprintf(f, "(can throw external) ");
1944     }
1945   fprintf (f, "\n");
1946   fprintf (f, "  References: ");
1947   ipa_dump_references (f, &node->ref_list);
1948   fprintf (f, "  Refering this function: ");
1949   ipa_dump_refering (f, &node->ref_list);
1950
1951   for (edge = node->indirect_calls; edge; edge = edge->next_callee)
1952     indirect_calls_count++;
1953   if (indirect_calls_count)
1954     fprintf (f, "  has %i outgoing edges for indirect calls.\n",
1955              indirect_calls_count);
1956
1957   if (node->same_body)
1958     {
1959       struct cgraph_node *n;
1960       fprintf (f, "  aliases & thunks:");
1961       for (n = node->same_body; n; n = n->next)
1962         {
1963           fprintf (f, " %s/%i", cgraph_node_name (n), n->uid);
1964           if (n->thunk.thunk_p)
1965             {
1966               fprintf (f, " (thunk of %s fixed ofset %i virtual value %i has "
1967                        "virtual offset %i",
1968                        lang_hooks.decl_printable_name (n->thunk.alias, 2),
1969                        (int)n->thunk.fixed_offset,
1970                        (int)n->thunk.virtual_value,
1971                        (int)n->thunk.virtual_offset_p);
1972               fprintf (f, ")");
1973             }
1974           if (DECL_ASSEMBLER_NAME_SET_P (n->decl))
1975             fprintf (f, " (asm: %s)", IDENTIFIER_POINTER (DECL_ASSEMBLER_NAME (n->decl)));
1976         }
1977       fprintf (f, "\n");
1978     }
1979 }
1980
1981
1982 /* Dump call graph node NODE to stderr.  */
1983
1984 DEBUG_FUNCTION void
1985 debug_cgraph_node (struct cgraph_node *node)
1986 {
1987   dump_cgraph_node (stderr, node);
1988 }
1989
1990
1991 /* Dump the callgraph to file F.  */
1992
1993 void
1994 dump_cgraph (FILE *f)
1995 {
1996   struct cgraph_node *node;
1997
1998   fprintf (f, "callgraph:\n\n");
1999   for (node = cgraph_nodes; node; node = node->next)
2000     dump_cgraph_node (f, node);
2001 }
2002
2003
2004 /* Dump the call graph to stderr.  */
2005
2006 DEBUG_FUNCTION void
2007 debug_cgraph (void)
2008 {
2009   dump_cgraph (stderr);
2010 }
2011
2012
2013 /* Set the DECL_ASSEMBLER_NAME and update cgraph hashtables.  */
2014
2015 void
2016 change_decl_assembler_name (tree decl, tree name)
2017 {
2018   struct cgraph_node *node;
2019   void **slot;
2020   if (!DECL_ASSEMBLER_NAME_SET_P (decl))
2021     SET_DECL_ASSEMBLER_NAME (decl, name);
2022   else
2023     {
2024       if (name == DECL_ASSEMBLER_NAME (decl))
2025         return;
2026
2027       if (assembler_name_hash
2028           && TREE_CODE (decl) == FUNCTION_DECL
2029           && (node = cgraph_get_node_or_alias (decl)) != NULL)
2030         {
2031           tree old_name = DECL_ASSEMBLER_NAME (decl);
2032           slot = htab_find_slot_with_hash (assembler_name_hash, old_name,
2033                                            decl_assembler_name_hash (old_name),
2034                                            NO_INSERT);
2035           /* Inline clones are not hashed.  */
2036           if (slot && *slot == node)
2037             htab_clear_slot (assembler_name_hash, slot);
2038         }
2039       if (TREE_SYMBOL_REFERENCED (DECL_ASSEMBLER_NAME (decl))
2040           && DECL_RTL_SET_P (decl))
2041         warning (0, "%D renamed after being referenced in assembly", decl);
2042
2043       SET_DECL_ASSEMBLER_NAME (decl, name);
2044     }
2045   if (assembler_name_hash
2046       && TREE_CODE (decl) == FUNCTION_DECL
2047       && (node = cgraph_get_node_or_alias (decl)) != NULL)
2048     {
2049       slot = htab_find_slot_with_hash (assembler_name_hash, name,
2050                                        decl_assembler_name_hash (name),
2051                                        INSERT);
2052       gcc_assert (!*slot);
2053       *slot = node;
2054     }
2055 }
2056
2057 /* Add a top-level asm statement to the list.  */
2058
2059 struct cgraph_asm_node *
2060 cgraph_add_asm_node (tree asm_str)
2061 {
2062   struct cgraph_asm_node *node;
2063
2064   node = ggc_alloc_cleared_cgraph_asm_node ();
2065   node->asm_str = asm_str;
2066   node->order = cgraph_order++;
2067   node->next = NULL;
2068   if (cgraph_asm_nodes == NULL)
2069     cgraph_asm_nodes = node;
2070   else
2071     cgraph_asm_last_node->next = node;
2072   cgraph_asm_last_node = node;
2073   return node;
2074 }
2075
2076 /* Return true when the DECL can possibly be inlined.  */
2077 bool
2078 cgraph_function_possibly_inlined_p (tree decl)
2079 {
2080   if (!cgraph_global_info_ready)
2081     return !DECL_UNINLINABLE (decl);
2082   return DECL_POSSIBLY_INLINED (decl);
2083 }
2084
2085 /* Create clone of E in the node N represented by CALL_EXPR the callgraph.  */
2086 struct cgraph_edge *
2087 cgraph_clone_edge (struct cgraph_edge *e, struct cgraph_node *n,
2088                    gimple call_stmt, unsigned stmt_uid, gcov_type count_scale,
2089                    int freq_scale, int loop_nest, bool update_original)
2090 {
2091   struct cgraph_edge *new_edge;
2092   gcov_type count = e->count * count_scale / REG_BR_PROB_BASE;
2093   gcov_type freq;
2094
2095   /* We do not want to ignore loop nest after frequency drops to 0.  */
2096   if (!freq_scale)
2097     freq_scale = 1;
2098   freq = e->frequency * (gcov_type) freq_scale / CGRAPH_FREQ_BASE;
2099   if (freq > CGRAPH_FREQ_MAX)
2100     freq = CGRAPH_FREQ_MAX;
2101
2102   if (e->indirect_unknown_callee)
2103     {
2104       tree decl;
2105
2106       if (call_stmt && (decl = gimple_call_fndecl (call_stmt)))
2107         {
2108           struct cgraph_node *callee = cgraph_node (decl);
2109           new_edge = cgraph_create_edge (n, callee, call_stmt, count, freq,
2110                                          e->loop_nest + loop_nest);
2111         }
2112       else
2113         {
2114           new_edge = cgraph_create_indirect_edge (n, call_stmt,
2115                                                   e->indirect_info->ecf_flags,
2116                                                   count, freq,
2117                                                   e->loop_nest + loop_nest);
2118           *new_edge->indirect_info = *e->indirect_info;
2119         }
2120     }
2121   else
2122     {
2123       new_edge = cgraph_create_edge (n, e->callee, call_stmt, count, freq,
2124                                      e->loop_nest + loop_nest);
2125       if (e->indirect_info)
2126         {
2127           new_edge->indirect_info
2128             = ggc_alloc_cleared_cgraph_indirect_call_info ();
2129           *new_edge->indirect_info = *e->indirect_info;
2130         }
2131     }
2132
2133   new_edge->inline_failed = e->inline_failed;
2134   new_edge->indirect_inlining_edge = e->indirect_inlining_edge;
2135   new_edge->lto_stmt_uid = stmt_uid;
2136   /* Clone flags that depend on call_stmt availability manually.  */
2137   new_edge->can_throw_external = e->can_throw_external;
2138   new_edge->call_stmt_cannot_inline_p = e->call_stmt_cannot_inline_p;
2139   if (update_original)
2140     {
2141       e->count -= new_edge->count;
2142       if (e->count < 0)
2143         e->count = 0;
2144     }
2145   cgraph_call_edge_duplication_hooks (e, new_edge);
2146   return new_edge;
2147 }
2148
2149 /* Create node representing clone of N executed COUNT times.  Decrease
2150    the execution counts from original node too.
2151    The new clone will have decl set to DECL that may or may not be the same
2152    as decl of N.
2153
2154    When UPDATE_ORIGINAL is true, the counts are subtracted from the original
2155    function's profile to reflect the fact that part of execution is handled
2156    by node.  */
2157 struct cgraph_node *
2158 cgraph_clone_node (struct cgraph_node *n, tree decl, gcov_type count, int freq,
2159                    int loop_nest, bool update_original,
2160                    VEC(cgraph_edge_p,heap) *redirect_callers)
2161 {
2162   struct cgraph_node *new_node = cgraph_create_node ();
2163   struct cgraph_edge *e;
2164   gcov_type count_scale;
2165   unsigned i;
2166
2167   new_node->decl = decl;
2168   new_node->origin = n->origin;
2169   if (new_node->origin)
2170     {
2171       new_node->next_nested = new_node->origin->nested;
2172       new_node->origin->nested = new_node;
2173     }
2174   new_node->analyzed = n->analyzed;
2175   new_node->local = n->local;
2176   new_node->local.externally_visible = false;
2177   new_node->local.local = true;
2178   new_node->local.vtable_method = false;
2179   new_node->global = n->global;
2180   new_node->rtl = n->rtl;
2181   new_node->count = count;
2182   new_node->frequency = n->frequency;
2183   new_node->clone = n->clone;
2184   new_node->clone.tree_map = 0;
2185   if (n->count)
2186     {
2187       if (new_node->count > n->count)
2188         count_scale = REG_BR_PROB_BASE;
2189       else
2190         count_scale = new_node->count * REG_BR_PROB_BASE / n->count;
2191     }
2192   else
2193     count_scale = 0;
2194   if (update_original)
2195     {
2196       n->count -= count;
2197       if (n->count < 0)
2198         n->count = 0;
2199     }
2200
2201   FOR_EACH_VEC_ELT (cgraph_edge_p, redirect_callers, i, e)
2202     {
2203       /* Redirect calls to the old version node to point to its new
2204          version.  */
2205       cgraph_redirect_edge_callee (e, new_node);
2206     }
2207
2208
2209   for (e = n->callees;e; e=e->next_callee)
2210     cgraph_clone_edge (e, new_node, e->call_stmt, e->lto_stmt_uid,
2211                        count_scale, freq, loop_nest, update_original);
2212
2213   for (e = n->indirect_calls; e; e = e->next_callee)
2214     cgraph_clone_edge (e, new_node, e->call_stmt, e->lto_stmt_uid,
2215                        count_scale, freq, loop_nest, update_original);
2216   ipa_clone_references (new_node, NULL, &n->ref_list);
2217
2218   new_node->next_sibling_clone = n->clones;
2219   if (n->clones)
2220     n->clones->prev_sibling_clone = new_node;
2221   n->clones = new_node;
2222   new_node->clone_of = n;
2223
2224   cgraph_call_node_duplication_hooks (n, new_node);
2225   if (n->decl != decl)
2226     {
2227       struct cgraph_node **slot;
2228       slot = (struct cgraph_node **) htab_find_slot (cgraph_hash, new_node, INSERT);
2229       gcc_assert (!*slot);
2230       *slot = new_node;
2231       if (assembler_name_hash)
2232         {
2233           void **aslot;
2234           tree name = DECL_ASSEMBLER_NAME (decl);
2235
2236           aslot = htab_find_slot_with_hash (assembler_name_hash, name,
2237                                             decl_assembler_name_hash (name),
2238                                             INSERT);
2239           gcc_assert (!*aslot);
2240           *aslot = new_node;
2241         }
2242     }
2243   return new_node;
2244 }
2245
2246 /* Create a new name for clone of DECL, add SUFFIX.  Returns an identifier.  */
2247
2248 static GTY(()) unsigned int clone_fn_id_num;
2249
2250 tree
2251 clone_function_name (tree decl, const char *suffix)
2252 {
2253   tree name = DECL_ASSEMBLER_NAME (decl);
2254   size_t len = IDENTIFIER_LENGTH (name);
2255   char *tmp_name, *prefix;
2256
2257   prefix = XALLOCAVEC (char, len + strlen (suffix) + 2);
2258   memcpy (prefix, IDENTIFIER_POINTER (name), len);
2259   strcpy (prefix + len + 1, suffix);
2260 #ifndef NO_DOT_IN_LABEL
2261   prefix[len] = '.';
2262 #elif !defined NO_DOLLAR_IN_LABEL
2263   prefix[len] = '$';
2264 #else
2265   prefix[len] = '_';
2266 #endif
2267   ASM_FORMAT_PRIVATE_NAME (tmp_name, prefix, clone_fn_id_num++);
2268   return get_identifier (tmp_name);
2269 }
2270
2271 /* Create callgraph node clone with new declaration.  The actual body will
2272    be copied later at compilation stage.
2273
2274    TODO: after merging in ipa-sra use function call notes instead of args_to_skip
2275    bitmap interface.
2276    */
2277 struct cgraph_node *
2278 cgraph_create_virtual_clone (struct cgraph_node *old_node,
2279                              VEC(cgraph_edge_p,heap) *redirect_callers,
2280                              VEC(ipa_replace_map_p,gc) *tree_map,
2281                              bitmap args_to_skip,
2282                              const char * suffix)
2283 {
2284   tree old_decl = old_node->decl;
2285   struct cgraph_node *new_node = NULL;
2286   tree new_decl;
2287   size_t i;
2288   struct ipa_replace_map *map;
2289
2290   if (!flag_wpa)
2291     gcc_checking_assert  (tree_versionable_function_p (old_decl));
2292
2293   /* Make a new FUNCTION_DECL tree node */
2294   if (!args_to_skip)
2295     new_decl = copy_node (old_decl);
2296   else
2297     new_decl = build_function_decl_skip_args (old_decl, args_to_skip);
2298   DECL_STRUCT_FUNCTION (new_decl) = NULL;
2299
2300   /* Generate a new name for the new version. */
2301   DECL_NAME (new_decl) = clone_function_name (old_decl, suffix);
2302   SET_DECL_ASSEMBLER_NAME (new_decl, DECL_NAME (new_decl));
2303   SET_DECL_RTL (new_decl, NULL);
2304
2305   new_node = cgraph_clone_node (old_node, new_decl, old_node->count,
2306                                 CGRAPH_FREQ_BASE, 0, false,
2307                                 redirect_callers);
2308   /* Update the properties.
2309      Make clone visible only within this translation unit.  Make sure
2310      that is not weak also.
2311      ??? We cannot use COMDAT linkage because there is no
2312      ABI support for this.  */
2313   DECL_EXTERNAL (new_node->decl) = 0;
2314   if (DECL_ONE_ONLY (old_decl))
2315     DECL_SECTION_NAME (new_node->decl) = NULL;
2316   DECL_COMDAT_GROUP (new_node->decl) = 0;
2317   TREE_PUBLIC (new_node->decl) = 0;
2318   DECL_COMDAT (new_node->decl) = 0;
2319   DECL_WEAK (new_node->decl) = 0;
2320   new_node->clone.tree_map = tree_map;
2321   new_node->clone.args_to_skip = args_to_skip;
2322   FOR_EACH_VEC_ELT (ipa_replace_map_p, tree_map, i, map)
2323     {
2324       tree var = map->new_tree;
2325
2326       STRIP_NOPS (var);
2327       if (TREE_CODE (var) != ADDR_EXPR)
2328         continue;
2329       var = get_base_var (var);
2330       if (!var)
2331         continue;
2332
2333       /* Record references of the future statement initializing the constant
2334          argument.  */
2335       if (TREE_CODE (var) == FUNCTION_DECL)
2336         ipa_record_reference (new_node, NULL, cgraph_node (var),
2337                               NULL, IPA_REF_ADDR, NULL);
2338       else if (TREE_CODE (var) == VAR_DECL)
2339         ipa_record_reference (new_node, NULL, NULL, varpool_node (var),
2340                               IPA_REF_ADDR, NULL);
2341     }
2342   if (!args_to_skip)
2343     new_node->clone.combined_args_to_skip = old_node->clone.combined_args_to_skip;
2344   else if (old_node->clone.combined_args_to_skip)
2345     {
2346       int newi = 0, oldi = 0;
2347       tree arg;
2348       bitmap new_args_to_skip = BITMAP_GGC_ALLOC ();
2349       struct cgraph_node *orig_node;
2350       for (orig_node = old_node; orig_node->clone_of; orig_node = orig_node->clone_of)
2351         ;
2352       for (arg = DECL_ARGUMENTS (orig_node->decl); arg; arg = DECL_CHAIN (arg), oldi++)
2353         {
2354           if (bitmap_bit_p (old_node->clone.combined_args_to_skip, oldi))
2355             {
2356               bitmap_set_bit (new_args_to_skip, oldi);
2357               continue;
2358             }
2359           if (bitmap_bit_p (args_to_skip, newi))
2360             bitmap_set_bit (new_args_to_skip, oldi);
2361           newi++;
2362         }
2363       new_node->clone.combined_args_to_skip = new_args_to_skip;
2364     }
2365   else
2366     new_node->clone.combined_args_to_skip = args_to_skip;
2367   new_node->local.externally_visible = 0;
2368   new_node->local.local = 1;
2369   new_node->lowered = true;
2370   new_node->reachable = true;
2371
2372
2373   return new_node;
2374 }
2375
2376 /* NODE is no longer nested function; update cgraph accordingly.  */
2377 void
2378 cgraph_unnest_node (struct cgraph_node *node)
2379 {
2380   struct cgraph_node **node2 = &node->origin->nested;
2381   gcc_assert (node->origin);
2382
2383   while (*node2 != node)
2384     node2 = &(*node2)->next_nested;
2385   *node2 = node->next_nested;
2386   node->origin = NULL;
2387 }
2388
2389 /* Return function availability.  See cgraph.h for description of individual
2390    return values.  */
2391 enum availability
2392 cgraph_function_body_availability (struct cgraph_node *node)
2393 {
2394   enum availability avail;
2395   gcc_assert (cgraph_function_flags_ready);
2396   if (!node->analyzed)
2397     avail = AVAIL_NOT_AVAILABLE;
2398   else if (node->local.local)
2399     avail = AVAIL_LOCAL;
2400   else if (!node->local.externally_visible)
2401     avail = AVAIL_AVAILABLE;
2402   /* Inline functions are safe to be analyzed even if their sybol can
2403      be overwritten at runtime.  It is not meaningful to enfore any sane
2404      behaviour on replacing inline function by different body.  */
2405   else if (DECL_DECLARED_INLINE_P (node->decl))
2406     avail = AVAIL_AVAILABLE;
2407
2408   /* If the function can be overwritten, return OVERWRITABLE.  Take
2409      care at least of two notable extensions - the COMDAT functions
2410      used to share template instantiations in C++ (this is symmetric
2411      to code cp_cannot_inline_tree_fn and probably shall be shared and
2412      the inlinability hooks completely eliminated).
2413
2414      ??? Does the C++ one definition rule allow us to always return
2415      AVAIL_AVAILABLE here?  That would be good reason to preserve this
2416      bit.  */
2417
2418   else if (decl_replaceable_p (node->decl) && !DECL_EXTERNAL (node->decl))
2419     avail = AVAIL_OVERWRITABLE;
2420   else avail = AVAIL_AVAILABLE;
2421
2422   return avail;
2423 }
2424
2425 /* Add the function FNDECL to the call graph.
2426    Unlike cgraph_finalize_function, this function is intended to be used
2427    by middle end and allows insertion of new function at arbitrary point
2428    of compilation.  The function can be either in high, low or SSA form
2429    GIMPLE.
2430
2431    The function is assumed to be reachable and have address taken (so no
2432    API breaking optimizations are performed on it).
2433
2434    Main work done by this function is to enqueue the function for later
2435    processing to avoid need the passes to be re-entrant.  */
2436
2437 void
2438 cgraph_add_new_function (tree fndecl, bool lowered)
2439 {
2440   struct cgraph_node *node;
2441   switch (cgraph_state)
2442     {
2443       case CGRAPH_STATE_CONSTRUCTION:
2444         /* Just enqueue function to be processed at nearest occurrence.  */
2445         node = cgraph_node (fndecl);
2446         node->next_needed = cgraph_new_nodes;
2447         if (lowered)
2448           node->lowered = true;
2449         cgraph_new_nodes = node;
2450         break;
2451
2452       case CGRAPH_STATE_IPA:
2453       case CGRAPH_STATE_IPA_SSA:
2454       case CGRAPH_STATE_EXPANSION:
2455         /* Bring the function into finalized state and enqueue for later
2456            analyzing and compilation.  */
2457         node = cgraph_node (fndecl);
2458         node->local.local = false;
2459         node->local.finalized = true;
2460         node->reachable = node->needed = true;
2461         if (!lowered && cgraph_state == CGRAPH_STATE_EXPANSION)
2462           {
2463             push_cfun (DECL_STRUCT_FUNCTION (fndecl));
2464             current_function_decl = fndecl;
2465             gimple_register_cfg_hooks ();
2466             tree_lowering_passes (fndecl);
2467             bitmap_obstack_initialize (NULL);
2468             if (!gimple_in_ssa_p (DECL_STRUCT_FUNCTION (fndecl)))
2469               execute_pass_list (pass_early_local_passes.pass.sub);
2470             bitmap_obstack_release (NULL);
2471             pop_cfun ();
2472             current_function_decl = NULL;
2473
2474             lowered = true;
2475           }
2476         if (lowered)
2477           node->lowered = true;
2478         node->next_needed = cgraph_new_nodes;
2479         cgraph_new_nodes = node;
2480         break;
2481
2482       case CGRAPH_STATE_FINISHED:
2483         /* At the very end of compilation we have to do all the work up
2484            to expansion.  */
2485         push_cfun (DECL_STRUCT_FUNCTION (fndecl));
2486         current_function_decl = fndecl;
2487         gimple_register_cfg_hooks ();
2488         if (!lowered)
2489           tree_lowering_passes (fndecl);
2490         bitmap_obstack_initialize (NULL);
2491         if (!gimple_in_ssa_p (DECL_STRUCT_FUNCTION (fndecl)))
2492           execute_pass_list (pass_early_local_passes.pass.sub);
2493         bitmap_obstack_release (NULL);
2494         tree_rest_of_compilation (fndecl);
2495         pop_cfun ();
2496         current_function_decl = NULL;
2497         break;
2498     }
2499
2500   /* Set a personality if required and we already passed EH lowering.  */
2501   if (lowered
2502       && (function_needs_eh_personality (DECL_STRUCT_FUNCTION (fndecl))
2503           == eh_personality_lang))
2504     DECL_FUNCTION_PERSONALITY (fndecl) = lang_hooks.eh_personality ();
2505 }
2506
2507 /* Return true if NODE can be made local for API change.
2508    Extern inline functions and C++ COMDAT functions can be made local
2509    at the expense of possible code size growth if function is used in multiple
2510    compilation units.  */
2511 bool
2512 cgraph_node_can_be_local_p (struct cgraph_node *node)
2513 {
2514   return (!node->needed && !node->address_taken
2515           && ((DECL_COMDAT (node->decl) && !node->same_comdat_group)
2516               || !node->local.externally_visible));
2517 }
2518
2519 /* Make DECL local.  FIXME: We shouldn't need to mess with rtl this early,
2520    but other code such as notice_global_symbol generates rtl.  */
2521 void
2522 cgraph_make_decl_local (tree decl)
2523 {
2524   rtx rtl, symbol;
2525
2526   if (TREE_CODE (decl) == VAR_DECL)
2527     DECL_COMMON (decl) = 0;
2528   else gcc_assert (TREE_CODE (decl) == FUNCTION_DECL);
2529
2530   if (DECL_COMDAT (decl))
2531     {
2532       /* It is possible that we are linking against library defining same COMDAT
2533          function.  To avoid conflict we need to rename our local name of the
2534          function just in the case WHOPR partitioning decide to make it hidden
2535          to avoid cross partition references.  */
2536       if (flag_wpa)
2537         {
2538           const char *old_name;
2539
2540           old_name  = IDENTIFIER_POINTER (DECL_ASSEMBLER_NAME (decl));
2541           if (TREE_CODE (decl) == FUNCTION_DECL)
2542             {
2543               struct cgraph_node *node = cgraph_get_node_or_alias (decl);
2544               change_decl_assembler_name (decl,
2545                                           clone_function_name (decl, "local"));
2546               if (node->local.lto_file_data)
2547                 lto_record_renamed_decl (node->local.lto_file_data,
2548                                          old_name,
2549                                          IDENTIFIER_POINTER
2550                                            (DECL_ASSEMBLER_NAME (decl)));
2551             }
2552           else if (TREE_CODE (decl) == VAR_DECL)
2553             {
2554               struct varpool_node *vnode = varpool_get_node (decl);
2555               /* change_decl_assembler_name will warn here on vtables because
2556                  C++ frontend still sets TREE_SYMBOL_REFERENCED on them.  */
2557               SET_DECL_ASSEMBLER_NAME (decl,
2558                                        clone_function_name (decl, "local"));
2559               if (vnode->lto_file_data)
2560                 lto_record_renamed_decl (vnode->lto_file_data,
2561                                          old_name,
2562                                          IDENTIFIER_POINTER
2563                                            (DECL_ASSEMBLER_NAME (decl)));
2564             }
2565         }
2566       DECL_SECTION_NAME (decl) = 0;
2567       DECL_COMDAT (decl) = 0;
2568     }
2569   DECL_COMDAT_GROUP (decl) = 0;
2570   DECL_WEAK (decl) = 0;
2571   DECL_EXTERNAL (decl) = 0;
2572   TREE_PUBLIC (decl) = 0;
2573   if (!DECL_RTL_SET_P (decl))
2574     return;
2575
2576   /* Update rtl flags.  */
2577   make_decl_rtl (decl);
2578
2579   rtl = DECL_RTL (decl);
2580   if (!MEM_P (rtl))
2581     return;
2582
2583   symbol = XEXP (rtl, 0);
2584   if (GET_CODE (symbol) != SYMBOL_REF)
2585     return;
2586
2587   SYMBOL_REF_WEAK (symbol) = DECL_WEAK (decl);
2588 }
2589
2590 /* Bring NODE local.  */
2591 void
2592 cgraph_make_node_local (struct cgraph_node *node)
2593 {
2594   gcc_assert (cgraph_node_can_be_local_p (node));
2595   if (DECL_COMDAT (node->decl) || DECL_EXTERNAL (node->decl))
2596     {
2597       struct cgraph_node *alias;
2598       cgraph_make_decl_local (node->decl);
2599
2600       for (alias = node->same_body; alias; alias = alias->next)
2601         cgraph_make_decl_local (alias->decl);
2602
2603       node->local.externally_visible = false;
2604       node->local.local = true;
2605       node->resolution = LDPR_PREVAILING_DEF_IRONLY;
2606       gcc_assert (cgraph_function_body_availability (node) == AVAIL_LOCAL);
2607     }
2608 }
2609
2610 /* Set TREE_NOTHROW on NODE's decl and on same_body aliases of NODE
2611    if any to NOTHROW.  */
2612
2613 void
2614 cgraph_set_nothrow_flag (struct cgraph_node *node, bool nothrow)
2615 {
2616   struct cgraph_node *alias;
2617   TREE_NOTHROW (node->decl) = nothrow;
2618   for (alias = node->same_body; alias; alias = alias->next)
2619     TREE_NOTHROW (alias->decl) = nothrow;
2620 }
2621
2622 /* Set TREE_READONLY on NODE's decl and on same_body aliases of NODE
2623    if any to READONLY.  */
2624
2625 void
2626 cgraph_set_const_flag (struct cgraph_node *node, bool readonly, bool looping)
2627 {
2628   struct cgraph_node *alias;
2629   /* Static constructors and destructors without a side effect can be
2630      optimized out.  */
2631   if (!looping && readonly)
2632     {
2633       if (DECL_STATIC_CONSTRUCTOR (node->decl))
2634         DECL_STATIC_CONSTRUCTOR (node->decl) = 0;
2635       if (DECL_STATIC_DESTRUCTOR (node->decl))
2636         DECL_STATIC_DESTRUCTOR (node->decl) = 0;
2637     }
2638   TREE_READONLY (node->decl) = readonly;
2639   DECL_LOOPING_CONST_OR_PURE_P (node->decl) = looping;
2640   for (alias = node->same_body; alias; alias = alias->next)
2641     {
2642       TREE_READONLY (alias->decl) = readonly;
2643       DECL_LOOPING_CONST_OR_PURE_P (alias->decl) = looping;
2644     }
2645 }
2646
2647 /* Set DECL_PURE_P on NODE's decl and on same_body aliases of NODE
2648    if any to PURE.  */
2649
2650 void
2651 cgraph_set_pure_flag (struct cgraph_node *node, bool pure, bool looping)
2652 {
2653   struct cgraph_node *alias;
2654   /* Static constructors and destructors without a side effect can be
2655      optimized out.  */
2656   if (!looping && pure)
2657     {
2658       if (DECL_STATIC_CONSTRUCTOR (node->decl))
2659         DECL_STATIC_CONSTRUCTOR (node->decl) = 0;
2660       if (DECL_STATIC_DESTRUCTOR (node->decl))
2661         DECL_STATIC_DESTRUCTOR (node->decl) = 0;
2662     }
2663   DECL_PURE_P (node->decl) = pure;
2664   DECL_LOOPING_CONST_OR_PURE_P (node->decl) = looping;
2665   for (alias = node->same_body; alias; alias = alias->next)
2666     {
2667       DECL_PURE_P (alias->decl) = pure;
2668       DECL_LOOPING_CONST_OR_PURE_P (alias->decl) = looping;
2669     }
2670 }
2671
2672 /* See if the frequency of NODE can be updated based on frequencies of its
2673    callers.  */
2674 bool
2675 cgraph_propagate_frequency (struct cgraph_node *node)
2676 {
2677   bool maybe_unlikely_executed = true, maybe_executed_once = true;
2678   bool only_called_at_startup = true;
2679   bool only_called_at_exit = true;
2680   bool changed = false;
2681   struct cgraph_edge *edge;
2682
2683   if (!node->local.local)
2684     return false;
2685   gcc_assert (node->analyzed);
2686   if (dump_file && (dump_flags & TDF_DETAILS))
2687     fprintf (dump_file, "Processing frequency %s\n", cgraph_node_name (node));
2688
2689   for (edge = node->callers;
2690        edge && (maybe_unlikely_executed || maybe_executed_once
2691                 || only_called_at_startup || only_called_at_exit);
2692        edge = edge->next_caller)
2693     {
2694       if (edge->caller != node)
2695         {
2696           only_called_at_startup &= edge->caller->only_called_at_startup;
2697           /* It makes snese to put main() together with the static constructors.
2698              It will be executed for sure, but rest of functions called from
2699              main are definitly not at startup only.  */
2700           if (MAIN_NAME_P (DECL_NAME (edge->caller->decl)))
2701             only_called_at_startup = 0;
2702           only_called_at_exit &= edge->caller->only_called_at_exit;
2703         }
2704       if (!edge->frequency)
2705         continue;
2706       switch (edge->caller->frequency)
2707         {
2708         case NODE_FREQUENCY_UNLIKELY_EXECUTED:
2709           break;
2710         case NODE_FREQUENCY_EXECUTED_ONCE:
2711           if (dump_file && (dump_flags & TDF_DETAILS))
2712             fprintf (dump_file, "  Called by %s that is executed once\n",
2713                      cgraph_node_name (node));
2714           maybe_unlikely_executed = false;
2715           if (edge->loop_nest)
2716             {
2717               maybe_executed_once = false;
2718               if (dump_file && (dump_flags & TDF_DETAILS))
2719                 fprintf (dump_file, "  Called in loop\n");
2720             }
2721           break;
2722         case NODE_FREQUENCY_HOT:
2723         case NODE_FREQUENCY_NORMAL:
2724           if (dump_file && (dump_flags & TDF_DETAILS))
2725             fprintf (dump_file, "  Called by %s that is normal or hot\n",
2726                      cgraph_node_name (node));
2727           maybe_unlikely_executed = false;
2728           maybe_executed_once = false;
2729           break;
2730         }
2731     }
2732   if ((only_called_at_startup && !only_called_at_exit)
2733       && !node->only_called_at_startup)
2734     {
2735        node->only_called_at_startup = true;
2736        if (dump_file)
2737          fprintf (dump_file, "Node %s promoted to only called at startup.\n",
2738                   cgraph_node_name (node));
2739        changed = true;
2740     }
2741   if ((only_called_at_exit && !only_called_at_startup)
2742       && !node->only_called_at_exit)
2743     {
2744        node->only_called_at_exit = true;
2745        if (dump_file)
2746          fprintf (dump_file, "Node %s promoted to only called at exit.\n",
2747                   cgraph_node_name (node));
2748        changed = true;
2749     }
2750   /* These come either from profile or user hints; never update them.  */
2751   if (node->frequency == NODE_FREQUENCY_HOT
2752       || node->frequency == NODE_FREQUENCY_UNLIKELY_EXECUTED)
2753     return changed;
2754   if (maybe_unlikely_executed)
2755     {
2756       node->frequency = NODE_FREQUENCY_UNLIKELY_EXECUTED;
2757       if (dump_file)
2758         fprintf (dump_file, "Node %s promoted to unlikely executed.\n",
2759                  cgraph_node_name (node));
2760       changed = true;
2761     }
2762   else if (maybe_executed_once && node->frequency != NODE_FREQUENCY_EXECUTED_ONCE)
2763     {
2764       node->frequency = NODE_FREQUENCY_EXECUTED_ONCE;
2765       if (dump_file)
2766         fprintf (dump_file, "Node %s promoted to executed once.\n",
2767                  cgraph_node_name (node));
2768       changed = true;
2769     }
2770   return changed;
2771 }
2772
2773 /* Return true when NODE can not return or throw and thus
2774    it is safe to ignore its side effects for IPA analysis.  */
2775
2776 bool
2777 cgraph_node_cannot_return (struct cgraph_node *node)
2778 {
2779   int flags = flags_from_decl_or_type (node->decl);
2780   if (!flag_exceptions)
2781     return (flags & ECF_NORETURN) != 0;
2782   else
2783     return ((flags & (ECF_NORETURN | ECF_NOTHROW))
2784              == (ECF_NORETURN | ECF_NOTHROW));
2785 }
2786
2787 /* Return true when call of E can not lead to return from caller
2788    and thus it is safe to ignore its side effects for IPA analysis
2789    when computing side effects of the caller.
2790    FIXME: We could actually mark all edges that have no reaching
2791    patch to EXIT_BLOCK_PTR or throw to get better results.  */
2792 bool
2793 cgraph_edge_cannot_lead_to_return (struct cgraph_edge *e)
2794 {
2795   if (cgraph_node_cannot_return (e->caller))
2796     return true;
2797   if (e->indirect_unknown_callee)
2798     {
2799       int flags = e->indirect_info->ecf_flags;
2800       if (!flag_exceptions)
2801         return (flags & ECF_NORETURN) != 0;
2802       else
2803         return ((flags & (ECF_NORETURN | ECF_NOTHROW))
2804                  == (ECF_NORETURN | ECF_NOTHROW));
2805     }
2806   else
2807     return cgraph_node_cannot_return (e->callee);
2808 }
2809
2810 /* Return true when function NODE can be removed from callgraph
2811    if all direct calls are eliminated.  */
2812
2813 bool
2814 cgraph_can_remove_if_no_direct_calls_and_refs_p (struct cgraph_node *node)
2815 {
2816   gcc_assert (!node->global.inlined_to);
2817   /* Extern inlines can always go, we will use the external definition.  */
2818   if (DECL_EXTERNAL (node->decl))
2819     return true;
2820   /* When function is needed, we can not remove it.  */
2821   if (node->needed || node->reachable_from_other_partition)
2822     return false;
2823   if (DECL_STATIC_CONSTRUCTOR (node->decl)
2824       || DECL_STATIC_DESTRUCTOR (node->decl))
2825     return false;
2826   /* Only COMDAT functions can be removed if externally visible.  */
2827   if (node->local.externally_visible
2828       && (!DECL_COMDAT (node->decl)
2829           || cgraph_used_from_object_file_p (node)))
2830     return false;
2831   return true;
2832 }
2833
2834 /* Return true when function NODE can be excpected to be removed
2835    from program when direct calls in this compilation unit are removed.
2836
2837    As a special case COMDAT functions are
2838    cgraph_can_remove_if_no_direct_calls_p while the are not
2839    cgraph_only_called_directly_p (it is possible they are called from other
2840    unit)
2841
2842    This function behaves as cgraph_only_called_directly_p because eliminating
2843    all uses of COMDAT function does not make it neccesarily disappear from
2844    the program unless we are compiling whole program or we do LTO.  In this
2845    case we know we win since dynamic linking will not really discard the
2846    linkonce section.  */
2847
2848 bool
2849 cgraph_will_be_removed_from_program_if_no_direct_calls (struct cgraph_node *node)
2850 {
2851   gcc_assert (!node->global.inlined_to);
2852   if (cgraph_used_from_object_file_p (node))
2853     return false;
2854   if (!in_lto_p && !flag_whole_program)
2855     return cgraph_only_called_directly_p (node);
2856   else
2857     {
2858        if (DECL_EXTERNAL (node->decl))
2859          return true;
2860       return cgraph_can_remove_if_no_direct_calls_p (node);
2861     }
2862 }
2863
2864 /* Return true when RESOLUTION indicate that linker will use
2865    the symbol from non-LTo object files.  */
2866
2867 bool
2868 resolution_used_from_other_file_p (enum ld_plugin_symbol_resolution resolution)
2869 {
2870   return (resolution == LDPR_PREVAILING_DEF
2871           || resolution == LDPR_PREEMPTED_REG
2872           || resolution == LDPR_RESOLVED_EXEC
2873           || resolution == LDPR_RESOLVED_DYN);
2874 }
2875
2876 /* Return true when NODE is known to be used from other (non-LTO) object file.
2877    Known only when doing LTO via linker plugin.  */
2878
2879 bool
2880 cgraph_used_from_object_file_p (struct cgraph_node *node)
2881 {
2882   struct cgraph_node *alias;
2883
2884   gcc_assert (!node->global.inlined_to);
2885   if (!TREE_PUBLIC (node->decl) || DECL_EXTERNAL (node->decl))
2886     return false;
2887   if (resolution_used_from_other_file_p (node->resolution))
2888     return true;
2889   for (alias = node->same_body; alias; alias = alias->next)
2890     if (TREE_PUBLIC (alias->decl)
2891         && resolution_used_from_other_file_p (alias->resolution))
2892       return true;
2893   return false;
2894 }
2895
2896 #include "gt-cgraph.h"