OSDN Git Service

89e431a7a5371a0c7d7ed9cb47fbe6e92a5202a5
[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_CNEW (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   else if (node->local.versionable)
1834     fprintf (f, " versionable");
1835   if (node->local.redefined_extern_inline)
1836     fprintf (f, " redefined_extern_inline");
1837   if (TREE_ASM_WRITTEN (node->decl))
1838     fprintf (f, " asm_written");
1839
1840   fprintf (f, "\n  called by: ");
1841   for (edge = node->callers; edge; edge = edge->next_caller)
1842     {
1843       fprintf (f, "%s/%i ", cgraph_node_name (edge->caller),
1844                edge->caller->uid);
1845       if (edge->count)
1846         fprintf (f, "("HOST_WIDEST_INT_PRINT_DEC"x) ",
1847                  (HOST_WIDEST_INT)edge->count);
1848       if (edge->frequency)
1849         fprintf (f, "(%.2f per call) ",
1850                  edge->frequency / (double)CGRAPH_FREQ_BASE);
1851       if (!edge->inline_failed)
1852         fprintf(f, "(inlined) ");
1853       if (edge->indirect_inlining_edge)
1854         fprintf(f, "(indirect_inlining) ");
1855       if (edge->can_throw_external)
1856         fprintf(f, "(can throw external) ");
1857     }
1858
1859   fprintf (f, "\n  calls: ");
1860   for (edge = node->callees; edge; edge = edge->next_callee)
1861     {
1862       fprintf (f, "%s/%i ", cgraph_node_name (edge->callee),
1863                edge->callee->uid);
1864       if (!edge->inline_failed)
1865         fprintf(f, "(inlined) ");
1866       if (edge->indirect_inlining_edge)
1867         fprintf(f, "(indirect_inlining) ");
1868       if (edge->count)
1869         fprintf (f, "("HOST_WIDEST_INT_PRINT_DEC"x) ",
1870                  (HOST_WIDEST_INT)edge->count);
1871       if (edge->frequency)
1872         fprintf (f, "(%.2f per call) ",
1873                  edge->frequency / (double)CGRAPH_FREQ_BASE);
1874       if (edge->loop_nest)
1875         fprintf (f, "(nested in %i loops) ", edge->loop_nest);
1876       if (edge->can_throw_external)
1877         fprintf(f, "(can throw external) ");
1878     }
1879   fprintf (f, "\n");
1880   fprintf (f, "  References: ");
1881   ipa_dump_references (f, &node->ref_list);
1882   fprintf (f, "  Refering this function: ");
1883   ipa_dump_refering (f, &node->ref_list);
1884
1885   for (edge = node->indirect_calls; edge; edge = edge->next_callee)
1886     indirect_calls_count++;
1887   if (indirect_calls_count)
1888     fprintf (f, "  has %i outgoing edges for indirect calls.\n",
1889              indirect_calls_count);
1890
1891   if (node->same_body)
1892     {
1893       struct cgraph_node *n;
1894       fprintf (f, "  aliases & thunks:");
1895       for (n = node->same_body; n; n = n->next)
1896         {
1897           fprintf (f, " %s/%i", cgraph_node_name (n), n->uid);
1898           if (n->thunk.thunk_p)
1899             {
1900               fprintf (f, " (thunk of %s fixed ofset %i virtual value %i has "
1901                        "virtual offset %i",
1902                        lang_hooks.decl_printable_name (n->thunk.alias, 2),
1903                        (int)n->thunk.fixed_offset,
1904                        (int)n->thunk.virtual_value,
1905                        (int)n->thunk.virtual_offset_p);
1906               fprintf (f, ")");
1907             }
1908           if (DECL_ASSEMBLER_NAME_SET_P (n->decl))
1909             fprintf (f, " (asm: %s)", IDENTIFIER_POINTER (DECL_ASSEMBLER_NAME (n->decl)));
1910         }
1911       fprintf (f, "\n");
1912     }
1913 }
1914
1915
1916 /* Dump call graph node NODE to stderr.  */
1917
1918 void
1919 debug_cgraph_node (struct cgraph_node *node)
1920 {
1921   dump_cgraph_node (stderr, node);
1922 }
1923
1924
1925 /* Dump the callgraph to file F.  */
1926
1927 void
1928 dump_cgraph (FILE *f)
1929 {
1930   struct cgraph_node *node;
1931
1932   fprintf (f, "callgraph:\n\n");
1933   for (node = cgraph_nodes; node; node = node->next)
1934     dump_cgraph_node (f, node);
1935 }
1936
1937
1938 /* Dump the call graph to stderr.  */
1939
1940 void
1941 debug_cgraph (void)
1942 {
1943   dump_cgraph (stderr);
1944 }
1945
1946
1947 /* Set the DECL_ASSEMBLER_NAME and update cgraph hashtables.  */
1948
1949 void
1950 change_decl_assembler_name (tree decl, tree name)
1951 {
1952   gcc_assert (!assembler_name_hash);
1953   if (!DECL_ASSEMBLER_NAME_SET_P (decl))
1954     {
1955       SET_DECL_ASSEMBLER_NAME (decl, name);
1956       return;
1957     }
1958   if (name == DECL_ASSEMBLER_NAME (decl))
1959     return;
1960
1961   if (TREE_SYMBOL_REFERENCED (DECL_ASSEMBLER_NAME (decl))
1962       && DECL_RTL_SET_P (decl))
1963     warning (0, "%D renamed after being referenced in assembly", decl);
1964
1965   SET_DECL_ASSEMBLER_NAME (decl, name);
1966 }
1967
1968 /* Add a top-level asm statement to the list.  */
1969
1970 struct cgraph_asm_node *
1971 cgraph_add_asm_node (tree asm_str)
1972 {
1973   struct cgraph_asm_node *node;
1974
1975   node = GGC_CNEW (struct cgraph_asm_node);
1976   node->asm_str = asm_str;
1977   node->order = cgraph_order++;
1978   node->next = NULL;
1979   if (cgraph_asm_nodes == NULL)
1980     cgraph_asm_nodes = node;
1981   else
1982     cgraph_asm_last_node->next = node;
1983   cgraph_asm_last_node = node;
1984   return node;
1985 }
1986
1987 /* Return true when the DECL can possibly be inlined.  */
1988 bool
1989 cgraph_function_possibly_inlined_p (tree decl)
1990 {
1991   if (!cgraph_global_info_ready)
1992     return !DECL_UNINLINABLE (decl);
1993   return DECL_POSSIBLY_INLINED (decl);
1994 }
1995
1996 /* Create clone of E in the node N represented by CALL_EXPR the callgraph.  */
1997 struct cgraph_edge *
1998 cgraph_clone_edge (struct cgraph_edge *e, struct cgraph_node *n,
1999                    gimple call_stmt, unsigned stmt_uid, gcov_type count_scale,
2000                    int freq_scale, int loop_nest, bool update_original)
2001 {
2002   struct cgraph_edge *new_edge;
2003   gcov_type count = e->count * count_scale / REG_BR_PROB_BASE;
2004   gcov_type freq;
2005
2006   /* We do not want to ignore loop nest after frequency drops to 0.  */
2007   if (!freq_scale)
2008     freq_scale = 1;
2009   freq = e->frequency * (gcov_type) freq_scale / CGRAPH_FREQ_BASE;
2010   if (freq > CGRAPH_FREQ_MAX)
2011     freq = CGRAPH_FREQ_MAX;
2012
2013   if (e->indirect_unknown_callee)
2014     {
2015       tree decl;
2016
2017       if (call_stmt && (decl = gimple_call_fndecl (call_stmt)))
2018         {
2019           struct cgraph_node *callee = cgraph_node (decl);
2020           new_edge = cgraph_create_edge (n, callee, call_stmt, count, freq,
2021                                          e->loop_nest + loop_nest);
2022         }
2023       else
2024         {
2025           new_edge = cgraph_create_indirect_edge (n, call_stmt,
2026                                                   e->indirect_info->ecf_flags,
2027                                                   count, freq,
2028                                                   e->loop_nest + loop_nest);
2029           *new_edge->indirect_info = *e->indirect_info;
2030         }
2031     }
2032   else
2033     new_edge = cgraph_create_edge (n, e->callee, call_stmt, count, freq,
2034                                    e->loop_nest + loop_nest);
2035
2036   new_edge->inline_failed = e->inline_failed;
2037   new_edge->indirect_inlining_edge = e->indirect_inlining_edge;
2038   new_edge->lto_stmt_uid = stmt_uid;
2039   if (update_original)
2040     {
2041       e->count -= new_edge->count;
2042       if (e->count < 0)
2043         e->count = 0;
2044     }
2045   cgraph_call_edge_duplication_hooks (e, new_edge);
2046   return new_edge;
2047 }
2048
2049 /* Create node representing clone of N executed COUNT times.  Decrease
2050    the execution counts from original node too.
2051    The new clone will have decl set to DECL that may or may not be the same
2052    as decl of N.
2053
2054    When UPDATE_ORIGINAL is true, the counts are subtracted from the original
2055    function's profile to reflect the fact that part of execution is handled
2056    by node.  */
2057 struct cgraph_node *
2058 cgraph_clone_node (struct cgraph_node *n, tree decl, gcov_type count, int freq,
2059                    int loop_nest, bool update_original,
2060                    VEC(cgraph_edge_p,heap) *redirect_callers)
2061 {
2062   struct cgraph_node *new_node = cgraph_create_node ();
2063   struct cgraph_edge *e;
2064   gcov_type count_scale;
2065   unsigned i;
2066
2067   new_node->decl = decl;
2068   new_node->origin = n->origin;
2069   if (new_node->origin)
2070     {
2071       new_node->next_nested = new_node->origin->nested;
2072       new_node->origin->nested = new_node;
2073     }
2074   new_node->analyzed = n->analyzed;
2075   new_node->local = n->local;
2076   new_node->local.externally_visible = false;
2077   new_node->local.local = true;
2078   new_node->local.vtable_method = false;
2079   new_node->global = n->global;
2080   new_node->rtl = n->rtl;
2081   new_node->count = count;
2082   new_node->frequency = n->frequency;
2083   new_node->clone = n->clone;
2084   new_node->clone.tree_map = 0;
2085   if (n->count)
2086     {
2087       if (new_node->count > n->count)
2088         count_scale = REG_BR_PROB_BASE;
2089       else
2090         count_scale = new_node->count * REG_BR_PROB_BASE / n->count;
2091     }
2092   else
2093     count_scale = 0;
2094   if (update_original)
2095     {
2096       n->count -= count;
2097       if (n->count < 0)
2098         n->count = 0;
2099     }
2100
2101   for (i = 0; VEC_iterate (cgraph_edge_p, redirect_callers, i, e); i++)
2102     {
2103       /* Redirect calls to the old version node to point to its new
2104          version.  */
2105       cgraph_redirect_edge_callee (e, new_node);
2106     }
2107
2108
2109   for (e = n->callees;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
2113   for (e = n->indirect_calls; e; e = e->next_callee)
2114     cgraph_clone_edge (e, new_node, e->call_stmt, e->lto_stmt_uid,
2115                        count_scale, freq, loop_nest, update_original);
2116   ipa_clone_references (new_node, NULL, &n->ref_list);
2117
2118   new_node->next_sibling_clone = n->clones;
2119   if (n->clones)
2120     n->clones->prev_sibling_clone = new_node;
2121   n->clones = new_node;
2122   new_node->clone_of = n;
2123
2124   cgraph_call_node_duplication_hooks (n, new_node);
2125   if (n->decl != decl)
2126     {
2127       struct cgraph_node **slot;
2128       slot = (struct cgraph_node **) htab_find_slot (cgraph_hash, new_node, INSERT);
2129       gcc_assert (!*slot);
2130       *slot = new_node;
2131       if (assembler_name_hash)
2132         {
2133           void **aslot;
2134           tree name = DECL_ASSEMBLER_NAME (decl);
2135
2136           aslot = htab_find_slot_with_hash (assembler_name_hash, name,
2137                                             decl_assembler_name_hash (name),
2138                                             INSERT);
2139           gcc_assert (!*aslot);
2140           *aslot = new_node;
2141         }
2142     }
2143   return new_node;
2144 }
2145
2146 /* Create a new name for omp child function.  Returns an identifier.  */
2147
2148 static GTY(()) unsigned int clone_fn_id_num;
2149
2150 static tree
2151 clone_function_name (tree decl)
2152 {
2153   tree name = DECL_ASSEMBLER_NAME (decl);
2154   size_t len = IDENTIFIER_LENGTH (name);
2155   char *tmp_name, *prefix;
2156
2157   prefix = XALLOCAVEC (char, len + strlen ("_clone") + 1);
2158   memcpy (prefix, IDENTIFIER_POINTER (name), len);
2159   strcpy (prefix + len, "_clone");
2160 #ifndef NO_DOT_IN_LABEL
2161   prefix[len] = '.';
2162 #elif !defined NO_DOLLAR_IN_LABEL
2163   prefix[len] = '$';
2164 #endif
2165   ASM_FORMAT_PRIVATE_NAME (tmp_name, prefix, clone_fn_id_num++);
2166   return get_identifier (tmp_name);
2167 }
2168
2169 /* Create callgraph node clone with new declaration.  The actual body will
2170    be copied later at compilation stage.
2171
2172    TODO: after merging in ipa-sra use function call notes instead of args_to_skip
2173    bitmap interface.
2174    */
2175 struct cgraph_node *
2176 cgraph_create_virtual_clone (struct cgraph_node *old_node,
2177                              VEC(cgraph_edge_p,heap) *redirect_callers,
2178                              VEC(ipa_replace_map_p,gc) *tree_map,
2179                              bitmap args_to_skip)
2180 {
2181   tree old_decl = old_node->decl;
2182   struct cgraph_node *new_node = NULL;
2183   tree new_decl;
2184   size_t i;
2185   struct ipa_replace_map *map;
2186
2187   gcc_assert  (tree_versionable_function_p (old_decl));
2188
2189   /* Make a new FUNCTION_DECL tree node */
2190   if (!args_to_skip)
2191     new_decl = copy_node (old_decl);
2192   else
2193     new_decl = build_function_decl_skip_args (old_decl, args_to_skip);
2194   DECL_STRUCT_FUNCTION (new_decl) = NULL;
2195
2196   /* Generate a new name for the new version. */
2197   DECL_NAME (new_decl) = clone_function_name (old_decl);
2198   SET_DECL_ASSEMBLER_NAME (new_decl, DECL_NAME (new_decl));
2199   SET_DECL_RTL (new_decl, NULL);
2200
2201   new_node = cgraph_clone_node (old_node, new_decl, old_node->count,
2202                                 CGRAPH_FREQ_BASE, 0, false,
2203                                 redirect_callers);
2204   /* Update the properties.
2205      Make clone visible only within this translation unit.  Make sure
2206      that is not weak also.
2207      ??? We cannot use COMDAT linkage because there is no
2208      ABI support for this.  */
2209   DECL_EXTERNAL (new_node->decl) = 0;
2210   DECL_COMDAT_GROUP (new_node->decl) = 0;
2211   TREE_PUBLIC (new_node->decl) = 0;
2212   DECL_COMDAT (new_node->decl) = 0;
2213   DECL_WEAK (new_node->decl) = 0;
2214   new_node->clone.tree_map = tree_map;
2215   new_node->clone.args_to_skip = args_to_skip;
2216   for (i = 0; VEC_iterate (ipa_replace_map_p, tree_map, i, map); i++)
2217     {
2218       tree var = map->new_tree;
2219
2220       STRIP_NOPS (var);
2221       if (TREE_CODE (var) != ADDR_EXPR)
2222         continue;
2223       var = get_base_var (var);
2224       if (!var)
2225         continue;
2226
2227       /* Record references of the future statement initializing the constant
2228          argument.  */
2229       if (TREE_CODE (var) == FUNCTION_DECL)
2230         ipa_record_reference (new_node, NULL, cgraph_node (var),
2231                               NULL, IPA_REF_ADDR, NULL);
2232       else if (TREE_CODE (var) == VAR_DECL)
2233         ipa_record_reference (new_node, NULL, NULL, varpool_node (var),
2234                               IPA_REF_ADDR, NULL);
2235     }
2236   if (!args_to_skip)
2237     new_node->clone.combined_args_to_skip = old_node->clone.combined_args_to_skip;
2238   else if (old_node->clone.combined_args_to_skip)
2239     {
2240       int newi = 0, oldi = 0;
2241       tree arg;
2242       bitmap new_args_to_skip = BITMAP_GGC_ALLOC ();
2243       struct cgraph_node *orig_node;
2244       for (orig_node = old_node; orig_node->clone_of; orig_node = orig_node->clone_of)
2245         ;
2246       for (arg = DECL_ARGUMENTS (orig_node->decl); arg; arg = TREE_CHAIN (arg), oldi++)
2247         {
2248           if (bitmap_bit_p (old_node->clone.combined_args_to_skip, oldi))
2249             {
2250               bitmap_set_bit (new_args_to_skip, oldi);
2251               continue;
2252             }
2253           if (bitmap_bit_p (args_to_skip, newi))
2254             bitmap_set_bit (new_args_to_skip, oldi);
2255           newi++;
2256         }
2257       new_node->clone.combined_args_to_skip = new_args_to_skip;
2258     }
2259   else
2260     new_node->clone.combined_args_to_skip = args_to_skip;
2261   new_node->local.externally_visible = 0;
2262   new_node->local.local = 1;
2263   new_node->lowered = true;
2264   new_node->reachable = true;
2265
2266
2267   return new_node;
2268 }
2269
2270 /* NODE is no longer nested function; update cgraph accordingly.  */
2271 void
2272 cgraph_unnest_node (struct cgraph_node *node)
2273 {
2274   struct cgraph_node **node2 = &node->origin->nested;
2275   gcc_assert (node->origin);
2276
2277   while (*node2 != node)
2278     node2 = &(*node2)->next_nested;
2279   *node2 = node->next_nested;
2280   node->origin = NULL;
2281 }
2282
2283 /* Return function availability.  See cgraph.h for description of individual
2284    return values.  */
2285 enum availability
2286 cgraph_function_body_availability (struct cgraph_node *node)
2287 {
2288   enum availability avail;
2289   gcc_assert (cgraph_function_flags_ready);
2290   if (!node->analyzed)
2291     avail = AVAIL_NOT_AVAILABLE;
2292   else if (node->local.local)
2293     avail = AVAIL_LOCAL;
2294   else if (!node->local.externally_visible)
2295     avail = AVAIL_AVAILABLE;
2296   /* Inline functions are safe to be analyzed even if their sybol can
2297      be overwritten at runtime.  It is not meaningful to enfore any sane
2298      behaviour on replacing inline function by different body.  */
2299   else if (DECL_DECLARED_INLINE_P (node->decl))
2300     avail = AVAIL_AVAILABLE;
2301
2302   /* If the function can be overwritten, return OVERWRITABLE.  Take
2303      care at least of two notable extensions - the COMDAT functions
2304      used to share template instantiations in C++ (this is symmetric
2305      to code cp_cannot_inline_tree_fn and probably shall be shared and
2306      the inlinability hooks completely eliminated).
2307
2308      ??? Does the C++ one definition rule allow us to always return
2309      AVAIL_AVAILABLE here?  That would be good reason to preserve this
2310      bit.  */
2311
2312   else if (DECL_REPLACEABLE_P (node->decl) && !DECL_EXTERNAL (node->decl))
2313     avail = AVAIL_OVERWRITABLE;
2314   else avail = AVAIL_AVAILABLE;
2315
2316   return avail;
2317 }
2318
2319 /* Add the function FNDECL to the call graph.
2320    Unlike cgraph_finalize_function, this function is intended to be used
2321    by middle end and allows insertion of new function at arbitrary point
2322    of compilation.  The function can be either in high, low or SSA form
2323    GIMPLE.
2324
2325    The function is assumed to be reachable and have address taken (so no
2326    API breaking optimizations are performed on it).
2327
2328    Main work done by this function is to enqueue the function for later
2329    processing to avoid need the passes to be re-entrant.  */
2330
2331 void
2332 cgraph_add_new_function (tree fndecl, bool lowered)
2333 {
2334   struct cgraph_node *node;
2335   switch (cgraph_state)
2336     {
2337       case CGRAPH_STATE_CONSTRUCTION:
2338         /* Just enqueue function to be processed at nearest occurrence.  */
2339         node = cgraph_node (fndecl);
2340         node->next_needed = cgraph_new_nodes;
2341         if (lowered)
2342           node->lowered = true;
2343         cgraph_new_nodes = node;
2344         break;
2345
2346       case CGRAPH_STATE_IPA:
2347       case CGRAPH_STATE_IPA_SSA:
2348       case CGRAPH_STATE_EXPANSION:
2349         /* Bring the function into finalized state and enqueue for later
2350            analyzing and compilation.  */
2351         node = cgraph_node (fndecl);
2352         node->local.local = false;
2353         node->local.finalized = true;
2354         node->reachable = node->needed = true;
2355         if (!lowered && cgraph_state == CGRAPH_STATE_EXPANSION)
2356           {
2357             push_cfun (DECL_STRUCT_FUNCTION (fndecl));
2358             current_function_decl = fndecl;
2359             gimple_register_cfg_hooks ();
2360             tree_lowering_passes (fndecl);
2361             bitmap_obstack_initialize (NULL);
2362             if (!gimple_in_ssa_p (DECL_STRUCT_FUNCTION (fndecl)))
2363               execute_pass_list (pass_early_local_passes.pass.sub);
2364             bitmap_obstack_release (NULL);
2365             pop_cfun ();
2366             current_function_decl = NULL;
2367
2368             lowered = true;
2369           }
2370         if (lowered)
2371           node->lowered = true;
2372         node->next_needed = cgraph_new_nodes;
2373         cgraph_new_nodes = node;
2374         break;
2375
2376       case CGRAPH_STATE_FINISHED:
2377         /* At the very end of compilation we have to do all the work up
2378            to expansion.  */
2379         push_cfun (DECL_STRUCT_FUNCTION (fndecl));
2380         current_function_decl = fndecl;
2381         gimple_register_cfg_hooks ();
2382         if (!lowered)
2383           tree_lowering_passes (fndecl);
2384         bitmap_obstack_initialize (NULL);
2385         if (!gimple_in_ssa_p (DECL_STRUCT_FUNCTION (fndecl)))
2386           execute_pass_list (pass_early_local_passes.pass.sub);
2387         bitmap_obstack_release (NULL);
2388         tree_rest_of_compilation (fndecl);
2389         pop_cfun ();
2390         current_function_decl = NULL;
2391         break;
2392     }
2393
2394   /* Set a personality if required and we already passed EH lowering.  */
2395   if (lowered
2396       && (function_needs_eh_personality (DECL_STRUCT_FUNCTION (fndecl))
2397           == eh_personality_lang))
2398     DECL_FUNCTION_PERSONALITY (fndecl) = lang_hooks.eh_personality ();
2399 }
2400
2401 /* Return true if NODE can be made local for API change.
2402    Extern inline functions and C++ COMDAT functions can be made local
2403    at the expense of possible code size growth if function is used in multiple
2404    compilation units.  */
2405 bool
2406 cgraph_node_can_be_local_p (struct cgraph_node *node)
2407 {
2408   return (!node->needed && !node->address_taken
2409           && ((DECL_COMDAT (node->decl) && !node->same_comdat_group)
2410               || !node->local.externally_visible));
2411 }
2412
2413 /* Make DECL local.  FIXME: We shouldn't need to mess with rtl this early,
2414    but other code such as notice_global_symbol generates rtl.  */
2415 void
2416 cgraph_make_decl_local (tree decl)
2417 {
2418   rtx rtl, symbol;
2419
2420   if (TREE_CODE (decl) == VAR_DECL)
2421     DECL_COMMON (decl) = 0;
2422   else if (TREE_CODE (decl) == FUNCTION_DECL)
2423     {
2424       DECL_COMDAT (decl) = 0;
2425       DECL_COMDAT_GROUP (decl) = 0;
2426       DECL_WEAK (decl) = 0;
2427       DECL_EXTERNAL (decl) = 0;
2428     }
2429   else
2430     gcc_unreachable ();
2431   TREE_PUBLIC (decl) = 0;
2432   if (!DECL_RTL_SET_P (decl))
2433     return;
2434
2435   /* Update rtl flags.  */
2436   make_decl_rtl (decl);
2437
2438   rtl = DECL_RTL (decl);
2439   if (!MEM_P (rtl))
2440     return;
2441
2442   symbol = XEXP (rtl, 0);
2443   if (GET_CODE (symbol) != SYMBOL_REF)
2444     return;
2445
2446   SYMBOL_REF_WEAK (symbol) = DECL_WEAK (decl);
2447 }
2448
2449 /* Bring NODE local.  */
2450 void
2451 cgraph_make_node_local (struct cgraph_node *node)
2452 {
2453   gcc_assert (cgraph_node_can_be_local_p (node));
2454   if (DECL_COMDAT (node->decl) || DECL_EXTERNAL (node->decl))
2455     {
2456       struct cgraph_node *alias;
2457       cgraph_make_decl_local (node->decl);
2458
2459       for (alias = node->same_body; alias; alias = alias->next)
2460         cgraph_make_decl_local (alias->decl);
2461
2462       node->local.externally_visible = false;
2463       node->local.local = true;
2464       gcc_assert (cgraph_function_body_availability (node) == AVAIL_LOCAL);
2465     }
2466 }
2467
2468 /* Set TREE_NOTHROW on NODE's decl and on same_body aliases of NODE
2469    if any to NOTHROW.  */
2470
2471 void
2472 cgraph_set_nothrow_flag (struct cgraph_node *node, bool nothrow)
2473 {
2474   struct cgraph_node *alias;
2475   TREE_NOTHROW (node->decl) = nothrow;
2476   for (alias = node->same_body; alias; alias = alias->next)
2477     TREE_NOTHROW (alias->decl) = nothrow;
2478 }
2479
2480 /* Set TREE_READONLY on NODE's decl and on same_body aliases of NODE
2481    if any to READONLY.  */
2482
2483 void
2484 cgraph_set_readonly_flag (struct cgraph_node *node, bool readonly)
2485 {
2486   struct cgraph_node *alias;
2487   TREE_READONLY (node->decl) = readonly;
2488   for (alias = node->same_body; alias; alias = alias->next)
2489     TREE_READONLY (alias->decl) = readonly;
2490 }
2491
2492 /* Set DECL_PURE_P on NODE's decl and on same_body aliases of NODE
2493    if any to PURE.  */
2494
2495 void
2496 cgraph_set_pure_flag (struct cgraph_node *node, bool pure)
2497 {
2498   struct cgraph_node *alias;
2499   DECL_PURE_P (node->decl) = pure;
2500   for (alias = node->same_body; alias; alias = alias->next)
2501     DECL_PURE_P (alias->decl) = pure;
2502 }
2503
2504 /* Set DECL_LOOPING_CONST_OR_PURE_P on NODE's decl and on
2505    same_body aliases of NODE if any to LOOPING_CONST_OR_PURE.  */
2506
2507 void
2508 cgraph_set_looping_const_or_pure_flag (struct cgraph_node *node,
2509                                        bool looping_const_or_pure)
2510 {
2511   struct cgraph_node *alias;
2512   DECL_LOOPING_CONST_OR_PURE_P (node->decl) = looping_const_or_pure;
2513   for (alias = node->same_body; alias; alias = alias->next)
2514     DECL_LOOPING_CONST_OR_PURE_P (alias->decl) = looping_const_or_pure;
2515 }
2516
2517 /* See if the frequency of NODE can be updated based on frequencies of its
2518    callers.  */
2519 bool
2520 cgraph_propagate_frequency (struct cgraph_node *node)
2521 {
2522   bool maybe_unlikely_executed = true, maybe_executed_once = true;
2523   struct cgraph_edge *edge;
2524   if (!node->local.local)
2525     return false;
2526   gcc_assert (node->analyzed);
2527   if (node->frequency == NODE_FREQUENCY_HOT)
2528     return false;
2529   if (node->frequency == NODE_FREQUENCY_UNLIKELY_EXECUTED)
2530     return false;
2531   if (dump_file && (dump_flags & TDF_DETAILS))
2532     fprintf (dump_file, "Processing frequency %s\n", cgraph_node_name (node));
2533   for (edge = node->callers;
2534        edge && (maybe_unlikely_executed || maybe_executed_once);
2535        edge = edge->next_caller)
2536     {
2537       if (!edge->frequency)
2538         continue;
2539       switch (edge->caller->frequency)
2540         {
2541         case NODE_FREQUENCY_UNLIKELY_EXECUTED:
2542           break;
2543         case NODE_FREQUENCY_EXECUTED_ONCE:
2544           if (dump_file && (dump_flags & TDF_DETAILS))
2545             fprintf (dump_file, "  Called by %s that is executed once\n", cgraph_node_name (node));
2546           maybe_unlikely_executed = false;
2547           if (edge->loop_nest)
2548             {
2549               maybe_executed_once = false;
2550               if (dump_file && (dump_flags & TDF_DETAILS))
2551                 fprintf (dump_file, "  Called in loop\n");
2552             }
2553           break;
2554         case NODE_FREQUENCY_HOT:
2555         case NODE_FREQUENCY_NORMAL:
2556           if (dump_file && (dump_flags & TDF_DETAILS))
2557             fprintf (dump_file, "  Called by %s that is normal or hot\n", cgraph_node_name (node));
2558           maybe_unlikely_executed = false;
2559           maybe_executed_once = false;
2560           break;
2561         }
2562     }
2563    if (maybe_unlikely_executed)
2564      {
2565        node->frequency = NODE_FREQUENCY_UNLIKELY_EXECUTED;
2566        if (dump_file)
2567          fprintf (dump_file, "Node %s promoted to unlikely executed.\n", cgraph_node_name (node));
2568        return true;
2569      }
2570    if (maybe_executed_once && node->frequency != NODE_FREQUENCY_EXECUTED_ONCE)
2571      {
2572        node->frequency = NODE_FREQUENCY_EXECUTED_ONCE;
2573        if (dump_file)
2574          fprintf (dump_file, "Node %s promoted to executed once.\n", cgraph_node_name (node));
2575        return true;
2576      }
2577    return false;
2578 }
2579
2580 #include "gt-cgraph.h"