OSDN Git Service

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