OSDN Git Service

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