OSDN Git Service

* cgraph.h (struct varpool_node): Add aux.
[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                              gcov_type count, int freq, int nest)
1040 {
1041   struct cgraph_edge *edge = cgraph_create_edge_1 (caller, NULL, call_stmt,
1042                                                    count, freq, nest);
1043
1044   edge->indirect_unknown_callee = 1;
1045   initialize_inline_failed (edge);
1046
1047   edge->indirect_info = GGC_NEW (struct cgraph_indirect_call_info);
1048   edge->indirect_info->param_index = -1;
1049
1050   edge->next_callee = caller->indirect_calls;
1051   if (caller->indirect_calls)
1052     caller->indirect_calls->prev_callee = edge;
1053   caller->indirect_calls = edge;
1054
1055   return edge;
1056 }
1057
1058 /* Remove the edge E from the list of the callers of the callee.  */
1059
1060 static inline void
1061 cgraph_edge_remove_callee (struct cgraph_edge *e)
1062 {
1063   gcc_assert (!e->indirect_unknown_callee);
1064   if (e->prev_caller)
1065     e->prev_caller->next_caller = e->next_caller;
1066   if (e->next_caller)
1067     e->next_caller->prev_caller = e->prev_caller;
1068   if (!e->prev_caller)
1069     e->callee->callers = e->next_caller;
1070 }
1071
1072 /* Remove the edge E from the list of the callees of the caller.  */
1073
1074 static inline void
1075 cgraph_edge_remove_caller (struct cgraph_edge *e)
1076 {
1077   if (e->prev_callee)
1078     e->prev_callee->next_callee = e->next_callee;
1079   if (e->next_callee)
1080     e->next_callee->prev_callee = e->prev_callee;
1081   if (!e->prev_callee)
1082     {
1083       if (e->indirect_unknown_callee)
1084         e->caller->indirect_calls = e->next_callee;
1085       else
1086         e->caller->callees = e->next_callee;
1087     }
1088   if (e->caller->call_site_hash)
1089     htab_remove_elt_with_hash (e->caller->call_site_hash,
1090                                e->call_stmt,
1091                                htab_hash_pointer (e->call_stmt));
1092 }
1093
1094 /* Put the edge onto the free list.  */
1095
1096 static void
1097 cgraph_free_edge (struct cgraph_edge *e)
1098 {
1099   int uid = e->uid;
1100
1101   /* Clear out the edge so we do not dangle pointers.  */
1102   memset (e, 0, sizeof (*e));
1103   e->uid = uid;
1104   NEXT_FREE_EDGE (e) = free_edges;
1105   free_edges = e;
1106 }
1107
1108 /* Remove the edge E in the cgraph.  */
1109
1110 void
1111 cgraph_remove_edge (struct cgraph_edge *e)
1112 {
1113   /* Call all edge removal hooks.  */
1114   cgraph_call_edge_removal_hooks (e);
1115
1116   if (!e->indirect_unknown_callee)
1117     /* Remove from callers list of the callee.  */
1118     cgraph_edge_remove_callee (e);
1119
1120   /* Remove from callees list of the callers.  */
1121   cgraph_edge_remove_caller (e);
1122
1123   /* Put the edge onto the free list.  */
1124   cgraph_free_edge (e);
1125 }
1126
1127 /* Set callee of call graph edge E and add it to the corresponding set of
1128    callers. */
1129
1130 static void
1131 cgraph_set_edge_callee (struct cgraph_edge *e, struct cgraph_node *n)
1132 {
1133   e->prev_caller = NULL;
1134   if (n->callers)
1135     n->callers->prev_caller = e;
1136   e->next_caller = n->callers;
1137   n->callers = e;
1138   e->callee = n;
1139 }
1140
1141 /* Redirect callee of E to N.  The function does not update underlying
1142    call expression.  */
1143
1144 void
1145 cgraph_redirect_edge_callee (struct cgraph_edge *e, struct cgraph_node *n)
1146 {
1147   /* Remove from callers list of the current callee.  */
1148   cgraph_edge_remove_callee (e);
1149
1150   /* Insert to callers list of the new callee.  */
1151   cgraph_set_edge_callee (e, n);
1152 }
1153
1154 /* Make an indirect EDGE with an unknown callee an ordinary edge leading to
1155    CALLEE.  */
1156
1157 void
1158 cgraph_make_edge_direct (struct cgraph_edge *edge, struct cgraph_node *callee)
1159 {
1160   edge->indirect_unknown_callee = 0;
1161
1162   /* Get the edge out of the indirect edge list. */
1163   if (edge->prev_callee)
1164     edge->prev_callee->next_callee = edge->next_callee;
1165   if (edge->next_callee)
1166     edge->next_callee->prev_callee = edge->prev_callee;
1167   if (!edge->prev_callee)
1168     edge->caller->indirect_calls = edge->next_callee;
1169
1170   /* Put it into the normal callee list */
1171   edge->prev_callee = NULL;
1172   edge->next_callee = edge->caller->callees;
1173   if (edge->caller->callees)
1174     edge->caller->callees->prev_callee = edge;
1175   edge->caller->callees = edge;
1176
1177   /* Insert to callers list of the new callee.  */
1178   cgraph_set_edge_callee (edge, callee);
1179
1180   /* We need to re-determine the inlining status of the edge.  */
1181   initialize_inline_failed (edge);
1182 }
1183
1184
1185 /* Update or remove the corresponding cgraph edge if a GIMPLE_CALL
1186    OLD_STMT changed into NEW_STMT.  OLD_CALL is gimple_call_fndecl
1187    of OLD_STMT if it was previously call statement.  */
1188
1189 static void
1190 cgraph_update_edges_for_call_stmt_node (struct cgraph_node *node,
1191                                         gimple old_stmt, tree old_call, gimple new_stmt)
1192 {
1193   tree new_call = (is_gimple_call (new_stmt)) ? gimple_call_fndecl (new_stmt) : 0;
1194
1195   /* We are seeing indirect calls, then there is nothing to update.  */
1196   if (!new_call && !old_call)
1197     return;
1198   /* See if we turned indirect call into direct call or folded call to one builtin
1199      into different bultin.  */
1200   if (old_call != new_call)
1201     {
1202       struct cgraph_edge *e = cgraph_edge (node, old_stmt);
1203       struct cgraph_edge *ne = NULL;
1204       gcov_type count;
1205       int frequency;
1206       int loop_nest;
1207
1208       if (e)
1209         {
1210           /* See if the edge is already there and has the correct callee.  It
1211              might be so because of indirect inlining has already updated
1212              it.  */
1213           if (new_call && e->callee && e->callee->decl == new_call)
1214             return;
1215
1216           /* Otherwise remove edge and create new one; we can't simply redirect
1217              since function has changed, so inline plan and other information
1218              attached to edge is invalid.  */
1219           count = e->count;
1220           frequency = e->frequency;
1221           loop_nest = e->loop_nest;
1222           cgraph_remove_edge (e);
1223         }
1224       else
1225         {
1226           /* We are seeing new direct call; compute profile info based on BB.  */
1227           basic_block bb = gimple_bb (new_stmt);
1228           count = bb->count;
1229           frequency = compute_call_stmt_bb_frequency (current_function_decl,
1230                                                       bb);
1231           loop_nest = bb->loop_depth;
1232         }
1233
1234       if (new_call)
1235         {
1236           ne = cgraph_create_edge (node, cgraph_node (new_call),
1237                                    new_stmt, count, frequency,
1238                                    loop_nest);
1239           gcc_assert (ne->inline_failed);
1240         }
1241     }
1242   /* We only updated the call stmt; update pointer in cgraph edge..  */
1243   else if (old_stmt != new_stmt)
1244     cgraph_set_call_stmt (cgraph_edge (node, old_stmt), new_stmt);
1245 }
1246
1247 /* Update or remove the corresponding cgraph edge if a GIMPLE_CALL
1248    OLD_STMT changed into NEW_STMT.  OLD_DECL is gimple_call_fndecl
1249    of OLD_STMT before it was updated (updating can happen inplace).  */
1250
1251 void
1252 cgraph_update_edges_for_call_stmt (gimple old_stmt, tree old_decl, gimple new_stmt)
1253 {
1254   struct cgraph_node *orig = cgraph_node (cfun->decl);
1255   struct cgraph_node *node;
1256
1257   cgraph_update_edges_for_call_stmt_node (orig, old_stmt, old_decl, new_stmt);
1258   if (orig->clones)
1259     for (node = orig->clones; node != orig;)
1260       {
1261         cgraph_update_edges_for_call_stmt_node (node, old_stmt, old_decl, new_stmt);
1262         if (node->clones)
1263           node = node->clones;
1264         else if (node->next_sibling_clone)
1265           node = node->next_sibling_clone;
1266         else
1267           {
1268             while (node != orig && !node->next_sibling_clone)
1269               node = node->clone_of;
1270             if (node != orig)
1271               node = node->next_sibling_clone;
1272           }
1273       }
1274 }
1275
1276
1277 /* Remove all callees from the node.  */
1278
1279 void
1280 cgraph_node_remove_callees (struct cgraph_node *node)
1281 {
1282   struct cgraph_edge *e, *f;
1283
1284   /* It is sufficient to remove the edges from the lists of callers of
1285      the callees.  The callee list of the node can be zapped with one
1286      assignment.  */
1287   for (e = node->callees; e; e = f)
1288     {
1289       f = e->next_callee;
1290       cgraph_call_edge_removal_hooks (e);
1291       if (!e->indirect_unknown_callee)
1292         cgraph_edge_remove_callee (e);
1293       cgraph_free_edge (e);
1294     }
1295   node->callees = NULL;
1296   if (node->call_site_hash)
1297     {
1298       htab_delete (node->call_site_hash);
1299       node->call_site_hash = NULL;
1300     }
1301 }
1302
1303 /* Remove all callers from the node.  */
1304
1305 static void
1306 cgraph_node_remove_callers (struct cgraph_node *node)
1307 {
1308   struct cgraph_edge *e, *f;
1309
1310   /* It is sufficient to remove the edges from the lists of callees of
1311      the callers.  The caller list of the node can be zapped with one
1312      assignment.  */
1313   for (e = node->callers; e; e = f)
1314     {
1315       f = e->next_caller;
1316       cgraph_call_edge_removal_hooks (e);
1317       cgraph_edge_remove_caller (e);
1318       cgraph_free_edge (e);
1319     }
1320   node->callers = NULL;
1321 }
1322
1323 /* Release memory used to represent body of function NODE.  */
1324
1325 void
1326 cgraph_release_function_body (struct cgraph_node *node)
1327 {
1328   if (DECL_STRUCT_FUNCTION (node->decl))
1329     {
1330       tree old_decl = current_function_decl;
1331       push_cfun (DECL_STRUCT_FUNCTION (node->decl));
1332       if (cfun->gimple_df)
1333         {
1334           current_function_decl = node->decl;
1335           delete_tree_ssa ();
1336           delete_tree_cfg_annotations ();
1337           cfun->eh = NULL;
1338           current_function_decl = old_decl;
1339         }
1340       if (cfun->cfg)
1341         {
1342           gcc_assert (dom_computed[0] == DOM_NONE);
1343           gcc_assert (dom_computed[1] == DOM_NONE);
1344           clear_edges ();
1345         }
1346       if (cfun->value_histograms)
1347         free_histograms ();
1348       gcc_assert (!current_loops);
1349       pop_cfun();
1350       gimple_set_body (node->decl, NULL);
1351       VEC_free (ipa_opt_pass, heap,
1352                 node->ipa_transforms_to_apply);
1353       /* Struct function hangs a lot of data that would leak if we didn't
1354          removed all pointers to it.   */
1355       ggc_free (DECL_STRUCT_FUNCTION (node->decl));
1356       DECL_STRUCT_FUNCTION (node->decl) = NULL;
1357     }
1358   DECL_SAVED_TREE (node->decl) = NULL;
1359   /* If the node is abstract and needed, then do not clear DECL_INITIAL
1360      of its associated function function declaration because it's
1361      needed to emit debug info later.  */
1362   if (!node->abstract_and_needed)
1363     DECL_INITIAL (node->decl) = error_mark_node;
1364 }
1365
1366 /* Remove same body alias node.  */
1367
1368 void
1369 cgraph_remove_same_body_alias (struct cgraph_node *node)
1370 {
1371   void **slot;
1372   int uid = node->uid;
1373
1374   gcc_assert (node->same_body_alias);
1375   if (node->previous)
1376     node->previous->next = node->next;
1377   else
1378     node->same_body->same_body = node->next;
1379   if (node->next)
1380     node->next->previous = node->previous;
1381   node->next = NULL;
1382   node->previous = NULL;
1383   slot = htab_find_slot (cgraph_hash, node, NO_INSERT);
1384   if (*slot == node)
1385     htab_clear_slot (cgraph_hash, slot);
1386   if (assembler_name_hash)
1387     {
1388       tree name = DECL_ASSEMBLER_NAME (node->decl);
1389       slot = htab_find_slot_with_hash (assembler_name_hash, name,
1390                                        decl_assembler_name_hash (name),
1391                                        NO_INSERT);
1392       if (slot && *slot == node)
1393         htab_clear_slot (assembler_name_hash, slot);
1394     }
1395
1396   /* Clear out the node to NULL all pointers and add the node to the free
1397      list.  */
1398   memset (node, 0, sizeof(*node));
1399   node->uid = uid;
1400   NEXT_FREE_NODE (node) = free_nodes;
1401   free_nodes = node;
1402 }
1403
1404 /* Remove the node from cgraph.  */
1405
1406 void
1407 cgraph_remove_node (struct cgraph_node *node)
1408 {
1409   void **slot;
1410   bool kill_body = false;
1411   struct cgraph_node *n;
1412   int uid = node->uid;
1413
1414   cgraph_call_node_removal_hooks (node);
1415   cgraph_node_remove_callers (node);
1416   cgraph_node_remove_callees (node);
1417   ipa_remove_all_references (&node->ref_list);
1418   ipa_remove_all_refering (&node->ref_list);
1419   VEC_free (ipa_opt_pass, heap,
1420             node->ipa_transforms_to_apply);
1421
1422   /* Incremental inlining access removed nodes stored in the postorder list.
1423      */
1424   node->needed = node->reachable = false;
1425   for (n = node->nested; n; n = n->next_nested)
1426     n->origin = NULL;
1427   node->nested = NULL;
1428   if (node->origin)
1429     {
1430       struct cgraph_node **node2 = &node->origin->nested;
1431
1432       while (*node2 != node)
1433         node2 = &(*node2)->next_nested;
1434       *node2 = node->next_nested;
1435     }
1436   if (node->previous)
1437     node->previous->next = node->next;
1438   else
1439     cgraph_nodes = node->next;
1440   if (node->next)
1441     node->next->previous = node->previous;
1442   node->next = NULL;
1443   node->previous = NULL;
1444   slot = htab_find_slot (cgraph_hash, node, NO_INSERT);
1445   if (*slot == node)
1446     {
1447       struct cgraph_node *next_inline_clone;
1448
1449       for (next_inline_clone = node->clones;
1450            next_inline_clone && next_inline_clone->decl != node->decl;
1451            next_inline_clone = next_inline_clone->next_sibling_clone)
1452         ;
1453
1454       /* If there is inline clone of the node being removed, we need
1455          to put it into the position of removed node and reorganize all
1456          other clones to be based on it.  */
1457       if (next_inline_clone)
1458         {
1459           struct cgraph_node *n;
1460           struct cgraph_node *new_clones;
1461
1462           *slot = next_inline_clone;
1463
1464           /* Unlink inline clone from the list of clones of removed node.  */
1465           if (next_inline_clone->next_sibling_clone)
1466             next_inline_clone->next_sibling_clone->prev_sibling_clone
1467               = next_inline_clone->prev_sibling_clone;
1468           if (next_inline_clone->prev_sibling_clone)
1469             {
1470               gcc_assert (node->clones != next_inline_clone);
1471               next_inline_clone->prev_sibling_clone->next_sibling_clone
1472                 = next_inline_clone->next_sibling_clone;
1473             }
1474           else
1475             {
1476               gcc_assert (node->clones == next_inline_clone);
1477               node->clones = next_inline_clone->next_sibling_clone;
1478             }
1479
1480           new_clones = node->clones;
1481           node->clones = NULL;
1482
1483           /* Copy clone info.  */
1484           next_inline_clone->clone = node->clone;
1485
1486           /* Now place it into clone tree at same level at NODE.  */
1487           next_inline_clone->clone_of = node->clone_of;
1488           next_inline_clone->prev_sibling_clone = NULL;
1489           next_inline_clone->next_sibling_clone = NULL;
1490           if (node->clone_of)
1491             {
1492               if (node->clone_of->clones)
1493                 node->clone_of->clones->prev_sibling_clone = next_inline_clone;
1494               next_inline_clone->next_sibling_clone = node->clone_of->clones;
1495               node->clone_of->clones = next_inline_clone;
1496             }
1497
1498           /* Merge the clone list.  */
1499           if (new_clones)
1500             {
1501               if (!next_inline_clone->clones)
1502                 next_inline_clone->clones = new_clones;
1503               else
1504                 {
1505                   n = next_inline_clone->clones;
1506                   while (n->next_sibling_clone)
1507                     n =  n->next_sibling_clone;
1508                   n->next_sibling_clone = new_clones;
1509                   new_clones->prev_sibling_clone = n;
1510                 }
1511             }
1512
1513           /* Update clone_of pointers.  */
1514           n = new_clones;
1515           while (n)
1516             {
1517               n->clone_of = next_inline_clone;
1518               n = n->next_sibling_clone;
1519             }
1520         }
1521       else
1522         {
1523           htab_clear_slot (cgraph_hash, slot);
1524           kill_body = true;
1525         }
1526
1527     }
1528   if (node->prev_sibling_clone)
1529     node->prev_sibling_clone->next_sibling_clone = node->next_sibling_clone;
1530   else if (node->clone_of)
1531     node->clone_of->clones = node->next_sibling_clone;
1532   if (node->next_sibling_clone)
1533     node->next_sibling_clone->prev_sibling_clone = node->prev_sibling_clone;
1534   if (node->clones)
1535     {
1536       struct cgraph_node *n, *next;
1537
1538       if (node->clone_of)
1539         {
1540           for (n = node->clones; n->next_sibling_clone; n = n->next_sibling_clone)
1541             n->clone_of = node->clone_of;
1542           n->clone_of = node->clone_of;
1543           n->next_sibling_clone = node->clone_of->clones;
1544           if (node->clone_of->clones)
1545             node->clone_of->clones->prev_sibling_clone = n;
1546           node->clone_of->clones = node->clones;
1547         }
1548       else
1549         {
1550           /* We are removing node with clones.  this makes clones inconsistent,
1551              but assume they will be removed subsequently and just keep clone
1552              tree intact.  This can happen in unreachable function removal since
1553              we remove unreachable functions in random order, not by bottom-up
1554              walk of clone trees.  */
1555           for (n = node->clones; n; n = next)
1556             {
1557                next = n->next_sibling_clone;
1558                n->next_sibling_clone = NULL;
1559                n->prev_sibling_clone = NULL;
1560                n->clone_of = NULL;
1561             }
1562         }
1563     }
1564
1565   while (node->same_body)
1566     cgraph_remove_same_body_alias (node->same_body);
1567
1568   if (node->same_comdat_group)
1569     {
1570       struct cgraph_node *prev;
1571       for (prev = node->same_comdat_group;
1572            prev->same_comdat_group != node;
1573            prev = prev->same_comdat_group)
1574         ;
1575       if (node->same_comdat_group == prev)
1576         prev->same_comdat_group = NULL;
1577       else
1578         prev->same_comdat_group = node->same_comdat_group;
1579       node->same_comdat_group = NULL;
1580     }
1581
1582   /* While all the clones are removed after being proceeded, the function
1583      itself is kept in the cgraph even after it is compiled.  Check whether
1584      we are done with this body and reclaim it proactively if this is the case.
1585      */
1586   if (!kill_body && *slot)
1587     {
1588       struct cgraph_node *n = (struct cgraph_node *) *slot;
1589       if (!n->clones && !n->clone_of && !n->global.inlined_to
1590           && (cgraph_global_info_ready
1591               && (TREE_ASM_WRITTEN (n->decl) || DECL_EXTERNAL (n->decl)
1592                   || n->in_other_partition)))
1593         kill_body = true;
1594     }
1595   if (assembler_name_hash)
1596     {
1597       tree name = DECL_ASSEMBLER_NAME (node->decl);
1598       slot = htab_find_slot_with_hash (assembler_name_hash, name,
1599                                        decl_assembler_name_hash (name),
1600                                        NO_INSERT);
1601       /* Inline clones are not hashed.  */
1602       if (slot && *slot == node)
1603         htab_clear_slot (assembler_name_hash, slot);
1604     }
1605
1606   if (kill_body)
1607     cgraph_release_function_body (node);
1608   node->decl = NULL;
1609   if (node->call_site_hash)
1610     {
1611       htab_delete (node->call_site_hash);
1612       node->call_site_hash = NULL;
1613     }
1614   cgraph_n_nodes--;
1615
1616   /* Clear out the node to NULL all pointers and add the node to the free
1617      list.  */
1618   memset (node, 0, sizeof(*node));
1619   node->uid = uid;
1620   NEXT_FREE_NODE (node) = free_nodes;
1621   free_nodes = node;
1622 }
1623
1624 /* Remove the node from cgraph.  */
1625
1626 void
1627 cgraph_remove_node_and_inline_clones (struct cgraph_node *node)
1628 {
1629   struct cgraph_edge *e, *next;
1630   for (e = node->callees; e; e = next)
1631     {
1632       next = e->next_callee;
1633       if (!e->inline_failed)
1634         cgraph_remove_node_and_inline_clones (e->callee);
1635     }
1636   cgraph_remove_node (node);
1637 }
1638
1639 /* Notify finalize_compilation_unit that given node is reachable.  */
1640
1641 void
1642 cgraph_mark_reachable_node (struct cgraph_node *node)
1643 {
1644   if (!node->reachable && node->local.finalized)
1645     {
1646       if (cgraph_global_info_ready)
1647         {
1648           /* Verify that function does not appear to be needed out of blue
1649              during the optimization process.  This can happen for extern
1650              inlines when bodies was removed after inlining.  */
1651           gcc_assert ((node->analyzed || DECL_EXTERNAL (node->decl)));
1652         }
1653       else
1654         notice_global_symbol (node->decl);
1655       node->reachable = 1;
1656
1657       node->next_needed = cgraph_nodes_queue;
1658       cgraph_nodes_queue = node;
1659     }
1660 }
1661
1662 /* Likewise indicate that a node is needed, i.e. reachable via some
1663    external means.  */
1664
1665 void
1666 cgraph_mark_needed_node (struct cgraph_node *node)
1667 {
1668   node->needed = 1;
1669   gcc_assert (!node->global.inlined_to);
1670   cgraph_mark_reachable_node (node);
1671 }
1672
1673 /* Likewise indicate that a node is having address taken.  */
1674
1675 void
1676 cgraph_mark_address_taken_node (struct cgraph_node *node)
1677 {
1678   node->address_taken = 1;
1679   cgraph_mark_needed_node (node);
1680 }
1681
1682 /* Return local info for the compiled function.  */
1683
1684 struct cgraph_local_info *
1685 cgraph_local_info (tree decl)
1686 {
1687   struct cgraph_node *node;
1688
1689   gcc_assert (TREE_CODE (decl) == FUNCTION_DECL);
1690   node = cgraph_node (decl);
1691   return &node->local;
1692 }
1693
1694 /* Return local info for the compiled function.  */
1695
1696 struct cgraph_global_info *
1697 cgraph_global_info (tree decl)
1698 {
1699   struct cgraph_node *node;
1700
1701   gcc_assert (TREE_CODE (decl) == FUNCTION_DECL && cgraph_global_info_ready);
1702   node = cgraph_node (decl);
1703   return &node->global;
1704 }
1705
1706 /* Return local info for the compiled function.  */
1707
1708 struct cgraph_rtl_info *
1709 cgraph_rtl_info (tree decl)
1710 {
1711   struct cgraph_node *node;
1712
1713   gcc_assert (TREE_CODE (decl) == FUNCTION_DECL);
1714   node = cgraph_node (decl);
1715   if (decl != current_function_decl
1716       && !TREE_ASM_WRITTEN (node->decl))
1717     return NULL;
1718   return &node->rtl;
1719 }
1720
1721 /* Return a string describing the failure REASON.  */
1722
1723 const char*
1724 cgraph_inline_failed_string (cgraph_inline_failed_t reason)
1725 {
1726 #undef DEFCIFCODE
1727 #define DEFCIFCODE(code, string)        string,
1728
1729   static const char *cif_string_table[CIF_N_REASONS] = {
1730 #include "cif-code.def"
1731   };
1732
1733   /* Signedness of an enum type is implementation defined, so cast it
1734      to unsigned before testing. */
1735   gcc_assert ((unsigned) reason < CIF_N_REASONS);
1736   return cif_string_table[reason];
1737 }
1738
1739 /* Return name of the node used in debug output.  */
1740 const char *
1741 cgraph_node_name (struct cgraph_node *node)
1742 {
1743   return lang_hooks.decl_printable_name (node->decl, 2);
1744 }
1745
1746 /* Names used to print out the availability enum.  */
1747 const char * const cgraph_availability_names[] =
1748   {"unset", "not_available", "overwritable", "available", "local"};
1749
1750
1751 /* Dump call graph node NODE to file F.  */
1752
1753 void
1754 dump_cgraph_node (FILE *f, struct cgraph_node *node)
1755 {
1756   struct cgraph_edge *edge;
1757   int indirect_calls_count = 0;
1758
1759   fprintf (f, "%s/%i(%i)", cgraph_node_name (node), node->uid,
1760            node->pid);
1761   dump_addr (f, " @", (void *)node);
1762   if (DECL_ASSEMBLER_NAME_SET_P (node->decl))
1763     fprintf (f, " (asm: %s)", IDENTIFIER_POINTER (DECL_ASSEMBLER_NAME (node->decl)));
1764   if (node->global.inlined_to)
1765     fprintf (f, " (inline copy in %s/%i)",
1766              cgraph_node_name (node->global.inlined_to),
1767              node->global.inlined_to->uid);
1768   if (node->clone_of)
1769     fprintf (f, " (clone of %s/%i)",
1770              cgraph_node_name (node->clone_of),
1771              node->clone_of->uid);
1772   if (cgraph_function_flags_ready)
1773     fprintf (f, " availability:%s",
1774              cgraph_availability_names [cgraph_function_body_availability (node)]);
1775   if (node->analyzed)
1776     fprintf (f, " analyzed");
1777   if (node->in_other_partition)
1778     fprintf (f, " in_other_partition");
1779   if (node->count)
1780     fprintf (f, " executed "HOST_WIDEST_INT_PRINT_DEC"x",
1781              (HOST_WIDEST_INT)node->count);
1782   if (node->local.inline_summary.self_time)
1783     fprintf (f, " %i time, %i benefit", node->local.inline_summary.self_time,
1784                                         node->local.inline_summary.time_inlining_benefit);
1785   if (node->global.time && node->global.time
1786       != node->local.inline_summary.self_time)
1787     fprintf (f, " (%i after inlining)", node->global.time);
1788   if (node->local.inline_summary.self_size)
1789     fprintf (f, " %i size, %i benefit", node->local.inline_summary.self_size,
1790                                         node->local.inline_summary.size_inlining_benefit);
1791   if (node->global.size && node->global.size
1792       != node->local.inline_summary.self_size)
1793     fprintf (f, " (%i after inlining)", node->global.size);
1794   if (node->local.inline_summary.estimated_self_stack_size)
1795     fprintf (f, " %i bytes stack usage", (int)node->local.inline_summary.estimated_self_stack_size);
1796   if (node->global.estimated_stack_size != node->local.inline_summary.estimated_self_stack_size)
1797     fprintf (f, " %i bytes after inlining", (int)node->global.estimated_stack_size);
1798   if (node->origin)
1799     fprintf (f, " nested in: %s", cgraph_node_name (node->origin));
1800   if (node->needed)
1801     fprintf (f, " needed");
1802   if (node->address_taken)
1803     fprintf (f, " address_taken");
1804   else if (node->reachable)
1805     fprintf (f, " reachable");
1806   else if (node->reachable_from_other_partition)
1807     fprintf (f, " reachable_from_other_partition");
1808   if (gimple_has_body_p (node->decl))
1809     fprintf (f, " body");
1810   if (node->process)
1811     fprintf (f, " process");
1812   if (node->local.local)
1813     fprintf (f, " local");
1814   if (node->local.externally_visible)
1815     fprintf (f, " externally_visible");
1816   if (node->local.finalized)
1817     fprintf (f, " finalized");
1818   if (node->local.disregard_inline_limits)
1819     fprintf (f, " always_inline");
1820   else if (node->local.inlinable)
1821     fprintf (f, " inlinable");
1822   if (node->local.redefined_extern_inline)
1823     fprintf (f, " redefined_extern_inline");
1824   if (TREE_ASM_WRITTEN (node->decl))
1825     fprintf (f, " asm_written");
1826
1827   fprintf (f, "\n  called by: ");
1828   for (edge = node->callers; edge; edge = edge->next_caller)
1829     {
1830       fprintf (f, "%s/%i ", cgraph_node_name (edge->caller),
1831                edge->caller->uid);
1832       if (edge->count)
1833         fprintf (f, "("HOST_WIDEST_INT_PRINT_DEC"x) ",
1834                  (HOST_WIDEST_INT)edge->count);
1835       if (edge->frequency)
1836         fprintf (f, "(%.2f per call) ",
1837                  edge->frequency / (double)CGRAPH_FREQ_BASE);
1838       if (!edge->inline_failed)
1839         fprintf(f, "(inlined) ");
1840       if (edge->indirect_inlining_edge)
1841         fprintf(f, "(indirect_inlining) ");
1842       if (edge->can_throw_external)
1843         fprintf(f, "(can throw external) ");
1844     }
1845
1846   fprintf (f, "\n  calls: ");
1847   for (edge = node->callees; edge; edge = edge->next_callee)
1848     {
1849       fprintf (f, "%s/%i ", cgraph_node_name (edge->callee),
1850                edge->callee->uid);
1851       if (!edge->inline_failed)
1852         fprintf(f, "(inlined) ");
1853       if (edge->indirect_inlining_edge)
1854         fprintf(f, "(indirect_inlining) ");
1855       if (edge->count)
1856         fprintf (f, "("HOST_WIDEST_INT_PRINT_DEC"x) ",
1857                  (HOST_WIDEST_INT)edge->count);
1858       if (edge->frequency)
1859         fprintf (f, "(%.2f per call) ",
1860                  edge->frequency / (double)CGRAPH_FREQ_BASE);
1861       if (edge->loop_nest)
1862         fprintf (f, "(nested in %i loops) ", edge->loop_nest);
1863       if (edge->can_throw_external)
1864         fprintf(f, "(can throw external) ");
1865     }
1866   fprintf (f, "\n");
1867   fprintf (f, "  References: ");
1868   ipa_dump_references (f, &node->ref_list);
1869   fprintf (f, "  Refering this function: ");
1870   ipa_dump_refering (f, &node->ref_list);
1871
1872   for (edge = node->indirect_calls; edge; edge = edge->next_callee)
1873     indirect_calls_count++;
1874   if (indirect_calls_count)
1875     fprintf (f, "  has %i outgoing edges for indirect calls.\n",
1876              indirect_calls_count);
1877
1878   if (node->same_body)
1879     {
1880       struct cgraph_node *n;
1881       fprintf (f, "  aliases & thunks:");
1882       for (n = node->same_body; n; n = n->next)
1883         {
1884           fprintf (f, " %s/%i", cgraph_node_name (n), n->uid);
1885           if (n->thunk.thunk_p)
1886             {
1887               fprintf (f, " (thunk of %s fixed ofset %i virtual value %i has "
1888                        "virtual offset %i",
1889                        lang_hooks.decl_printable_name (n->thunk.alias, 2),
1890                        (int)n->thunk.fixed_offset,
1891                        (int)n->thunk.virtual_value,
1892                        (int)n->thunk.virtual_offset_p);
1893               fprintf (f, ")");
1894             }
1895           if (DECL_ASSEMBLER_NAME_SET_P (n->decl))
1896             fprintf (f, " (asm: %s)", IDENTIFIER_POINTER (DECL_ASSEMBLER_NAME (n->decl)));
1897         }
1898       fprintf (f, "\n");
1899     }
1900 }
1901
1902
1903 /* Dump call graph node NODE to stderr.  */
1904
1905 void
1906 debug_cgraph_node (struct cgraph_node *node)
1907 {
1908   dump_cgraph_node (stderr, node);
1909 }
1910
1911
1912 /* Dump the callgraph to file F.  */
1913
1914 void
1915 dump_cgraph (FILE *f)
1916 {
1917   struct cgraph_node *node;
1918
1919   fprintf (f, "callgraph:\n\n");
1920   for (node = cgraph_nodes; node; node = node->next)
1921     dump_cgraph_node (f, node);
1922 }
1923
1924
1925 /* Dump the call graph to stderr.  */
1926
1927 void
1928 debug_cgraph (void)
1929 {
1930   dump_cgraph (stderr);
1931 }
1932
1933
1934 /* Set the DECL_ASSEMBLER_NAME and update cgraph hashtables.  */
1935
1936 void
1937 change_decl_assembler_name (tree decl, tree name)
1938 {
1939   gcc_assert (!assembler_name_hash);
1940   if (!DECL_ASSEMBLER_NAME_SET_P (decl))
1941     {
1942       SET_DECL_ASSEMBLER_NAME (decl, name);
1943       return;
1944     }
1945   if (name == DECL_ASSEMBLER_NAME (decl))
1946     return;
1947
1948   if (TREE_SYMBOL_REFERENCED (DECL_ASSEMBLER_NAME (decl))
1949       && DECL_RTL_SET_P (decl))
1950     warning (0, "%D renamed after being referenced in assembly", decl);
1951
1952   SET_DECL_ASSEMBLER_NAME (decl, name);
1953 }
1954
1955 /* Add a top-level asm statement to the list.  */
1956
1957 struct cgraph_asm_node *
1958 cgraph_add_asm_node (tree asm_str)
1959 {
1960   struct cgraph_asm_node *node;
1961
1962   node = GGC_CNEW (struct cgraph_asm_node);
1963   node->asm_str = asm_str;
1964   node->order = cgraph_order++;
1965   node->next = NULL;
1966   if (cgraph_asm_nodes == NULL)
1967     cgraph_asm_nodes = node;
1968   else
1969     cgraph_asm_last_node->next = node;
1970   cgraph_asm_last_node = node;
1971   return node;
1972 }
1973
1974 /* Return true when the DECL can possibly be inlined.  */
1975 bool
1976 cgraph_function_possibly_inlined_p (tree decl)
1977 {
1978   if (!cgraph_global_info_ready)
1979     return !DECL_UNINLINABLE (decl);
1980   return DECL_POSSIBLY_INLINED (decl);
1981 }
1982
1983 /* Create clone of E in the node N represented by CALL_EXPR the callgraph.  */
1984 struct cgraph_edge *
1985 cgraph_clone_edge (struct cgraph_edge *e, struct cgraph_node *n,
1986                    gimple call_stmt, unsigned stmt_uid, gcov_type count_scale,
1987                    int freq_scale, int loop_nest, bool update_original)
1988 {
1989   struct cgraph_edge *new_edge;
1990   gcov_type count = e->count * count_scale / REG_BR_PROB_BASE;
1991   gcov_type freq;
1992
1993   /* We do not want to ignore loop nest after frequency drops to 0.  */
1994   if (!freq_scale)
1995     freq_scale = 1;
1996   freq = e->frequency * (gcov_type) freq_scale / CGRAPH_FREQ_BASE;
1997   if (freq > CGRAPH_FREQ_MAX)
1998     freq = CGRAPH_FREQ_MAX;
1999
2000   if (e->indirect_unknown_callee)
2001     {
2002       tree decl;
2003
2004       if (call_stmt && (decl = gimple_call_fndecl (call_stmt)))
2005         {
2006           struct cgraph_node *callee = cgraph_node (decl);
2007           new_edge = cgraph_create_edge (n, callee, call_stmt, count, freq,
2008                                          e->loop_nest + loop_nest);
2009         }
2010       else
2011         {
2012           new_edge = cgraph_create_indirect_edge (n, call_stmt, count, freq,
2013                                                   e->loop_nest + loop_nest);
2014           new_edge->indirect_info->param_index = e->indirect_info->param_index;
2015         }
2016     }
2017   else
2018     new_edge = cgraph_create_edge (n, e->callee, call_stmt, count, freq,
2019                                    e->loop_nest + loop_nest);
2020
2021   new_edge->inline_failed = e->inline_failed;
2022   new_edge->indirect_inlining_edge = e->indirect_inlining_edge;
2023   new_edge->lto_stmt_uid = stmt_uid;
2024   if (update_original)
2025     {
2026       e->count -= new_edge->count;
2027       if (e->count < 0)
2028         e->count = 0;
2029     }
2030   cgraph_call_edge_duplication_hooks (e, new_edge);
2031   return new_edge;
2032 }
2033
2034 /* Create node representing clone of N executed COUNT times.  Decrease
2035    the execution counts from original node too.
2036
2037    When UPDATE_ORIGINAL is true, the counts are subtracted from the original
2038    function's profile to reflect the fact that part of execution is handled
2039    by node.  */
2040 struct cgraph_node *
2041 cgraph_clone_node (struct cgraph_node *n, gcov_type count, int freq,
2042                    int loop_nest, bool update_original,
2043                    VEC(cgraph_edge_p,heap) *redirect_callers)
2044 {
2045   struct cgraph_node *new_node = cgraph_create_node ();
2046   struct cgraph_edge *e;
2047   gcov_type count_scale;
2048   unsigned i;
2049
2050   new_node->decl = n->decl;
2051   new_node->origin = n->origin;
2052   if (new_node->origin)
2053     {
2054       new_node->next_nested = new_node->origin->nested;
2055       new_node->origin->nested = new_node;
2056     }
2057   new_node->analyzed = n->analyzed;
2058   new_node->local = n->local;
2059   new_node->local.externally_visible = false;
2060   new_node->local.local = true;
2061   new_node->local.vtable_method = false;
2062   new_node->global = n->global;
2063   new_node->rtl = n->rtl;
2064   new_node->count = count;
2065   new_node->frequency = n->frequency;
2066   new_node->clone = n->clone;
2067   new_node->clone.tree_map = 0;
2068   if (n->count)
2069     {
2070       if (new_node->count > n->count)
2071         count_scale = REG_BR_PROB_BASE;
2072       else
2073         count_scale = new_node->count * REG_BR_PROB_BASE / n->count;
2074     }
2075   else
2076     count_scale = 0;
2077   if (update_original)
2078     {
2079       n->count -= count;
2080       if (n->count < 0)
2081         n->count = 0;
2082     }
2083
2084   for (i = 0; VEC_iterate (cgraph_edge_p, redirect_callers, i, e); i++)
2085     {
2086       /* Redirect calls to the old version node to point to its new
2087          version.  */
2088       cgraph_redirect_edge_callee (e, new_node);
2089     }
2090
2091
2092   for (e = n->callees;e; e=e->next_callee)
2093     cgraph_clone_edge (e, new_node, e->call_stmt, e->lto_stmt_uid,
2094                        count_scale, freq, loop_nest, update_original);
2095
2096   for (e = n->indirect_calls; e; e = e->next_callee)
2097     cgraph_clone_edge (e, new_node, e->call_stmt, e->lto_stmt_uid,
2098                        count_scale, freq, loop_nest, update_original);
2099   ipa_clone_references (new_node, NULL, &n->ref_list);
2100
2101   new_node->next_sibling_clone = n->clones;
2102   if (n->clones)
2103     n->clones->prev_sibling_clone = new_node;
2104   n->clones = new_node;
2105   new_node->clone_of = n;
2106
2107   cgraph_call_node_duplication_hooks (n, new_node);
2108   return new_node;
2109 }
2110
2111 /* Create a new name for omp child function.  Returns an identifier.  */
2112
2113 static GTY(()) unsigned int clone_fn_id_num;
2114
2115 static tree
2116 clone_function_name (tree decl)
2117 {
2118   tree name = DECL_ASSEMBLER_NAME (decl);
2119   size_t len = IDENTIFIER_LENGTH (name);
2120   char *tmp_name, *prefix;
2121
2122   prefix = XALLOCAVEC (char, len + strlen ("_clone") + 1);
2123   memcpy (prefix, IDENTIFIER_POINTER (name), len);
2124   strcpy (prefix + len, "_clone");
2125 #ifndef NO_DOT_IN_LABEL
2126   prefix[len] = '.';
2127 #elif !defined NO_DOLLAR_IN_LABEL
2128   prefix[len] = '$';
2129 #endif
2130   ASM_FORMAT_PRIVATE_NAME (tmp_name, prefix, clone_fn_id_num++);
2131   return get_identifier (tmp_name);
2132 }
2133
2134 /* Create callgraph node clone with new declaration.  The actual body will
2135    be copied later at compilation stage.
2136
2137    TODO: after merging in ipa-sra use function call notes instead of args_to_skip
2138    bitmap interface.
2139    */
2140 struct cgraph_node *
2141 cgraph_create_virtual_clone (struct cgraph_node *old_node,
2142                              VEC(cgraph_edge_p,heap) *redirect_callers,
2143                              VEC(ipa_replace_map_p,gc) *tree_map,
2144                              bitmap args_to_skip)
2145 {
2146   tree old_decl = old_node->decl;
2147   struct cgraph_node *new_node = NULL;
2148   tree new_decl;
2149   struct cgraph_node key, **slot;
2150   size_t i;
2151   struct ipa_replace_map *map;
2152
2153   gcc_assert  (tree_versionable_function_p (old_decl));
2154
2155   /* Make a new FUNCTION_DECL tree node */
2156   if (!args_to_skip)
2157     new_decl = copy_node (old_decl);
2158   else
2159     new_decl = build_function_decl_skip_args (old_decl, args_to_skip);
2160   DECL_STRUCT_FUNCTION (new_decl) = NULL;
2161
2162   /* Generate a new name for the new version. */
2163   DECL_NAME (new_decl) = clone_function_name (old_decl);
2164   SET_DECL_ASSEMBLER_NAME (new_decl, DECL_NAME (new_decl));
2165   SET_DECL_RTL (new_decl, NULL);
2166
2167   new_node = cgraph_clone_node (old_node, old_node->count,
2168                                 CGRAPH_FREQ_BASE, 0, false,
2169                                 redirect_callers);
2170   new_node->decl = new_decl;
2171   /* Update the properties.
2172      Make clone visible only within this translation unit.  Make sure
2173      that is not weak also.
2174      ??? We cannot use COMDAT linkage because there is no
2175      ABI support for this.  */
2176   DECL_EXTERNAL (new_node->decl) = 0;
2177   DECL_COMDAT_GROUP (new_node->decl) = 0;
2178   TREE_PUBLIC (new_node->decl) = 0;
2179   DECL_COMDAT (new_node->decl) = 0;
2180   DECL_WEAK (new_node->decl) = 0;
2181   new_node->clone.tree_map = tree_map;
2182   new_node->clone.args_to_skip = args_to_skip;
2183   for (i = 0; VEC_iterate (ipa_replace_map_p, tree_map, i, map); i++)
2184     {
2185       tree var = map->new_tree;
2186
2187       STRIP_NOPS (var);
2188       if (TREE_CODE (var) != ADDR_EXPR)
2189         continue;
2190       var = get_base_var (var);
2191       if (!var)
2192         continue;
2193
2194       /* Record references of the future statement initializing the constant
2195          argument.  */
2196       if (TREE_CODE (var) == FUNCTION_DECL)
2197         ipa_record_reference (new_node, NULL, cgraph_node (var),
2198                               NULL, IPA_REF_ADDR, NULL);
2199       else if (TREE_CODE (var) == VAR_DECL)
2200         ipa_record_reference (new_node, NULL, NULL, varpool_node (var),
2201                               IPA_REF_ADDR, NULL);
2202     }
2203   if (!args_to_skip)
2204     new_node->clone.combined_args_to_skip = old_node->clone.combined_args_to_skip;
2205   else if (old_node->clone.combined_args_to_skip)
2206     {
2207       int newi = 0, oldi = 0;
2208       tree arg;
2209       bitmap new_args_to_skip = BITMAP_GGC_ALLOC ();
2210       struct cgraph_node *orig_node;
2211       for (orig_node = old_node; orig_node->clone_of; orig_node = orig_node->clone_of)
2212         ;
2213       for (arg = DECL_ARGUMENTS (orig_node->decl); arg; arg = TREE_CHAIN (arg), oldi++)
2214         {
2215           if (bitmap_bit_p (old_node->clone.combined_args_to_skip, oldi))
2216             {
2217               bitmap_set_bit (new_args_to_skip, oldi);
2218               continue;
2219             }
2220           if (bitmap_bit_p (args_to_skip, newi))
2221             bitmap_set_bit (new_args_to_skip, oldi);
2222           newi++;
2223         }
2224       new_node->clone.combined_args_to_skip = new_args_to_skip;
2225     }
2226   else
2227     new_node->clone.combined_args_to_skip = args_to_skip;
2228   new_node->local.externally_visible = 0;
2229   new_node->local.local = 1;
2230   new_node->lowered = true;
2231   new_node->reachable = true;
2232
2233   key.decl = new_decl;
2234   slot = (struct cgraph_node **) htab_find_slot (cgraph_hash, &key, INSERT);
2235   gcc_assert (!*slot);
2236   *slot = new_node;
2237   if (assembler_name_hash)
2238     {
2239       void **aslot;
2240       tree name = DECL_ASSEMBLER_NAME (new_decl);
2241
2242       aslot = htab_find_slot_with_hash (assembler_name_hash, name,
2243                                         decl_assembler_name_hash (name),
2244                                         INSERT);
2245       gcc_assert (!*aslot);
2246       *aslot = new_node;
2247     }
2248
2249   return new_node;
2250 }
2251
2252 /* NODE is no longer nested function; update cgraph accordingly.  */
2253 void
2254 cgraph_unnest_node (struct cgraph_node *node)
2255 {
2256   struct cgraph_node **node2 = &node->origin->nested;
2257   gcc_assert (node->origin);
2258
2259   while (*node2 != node)
2260     node2 = &(*node2)->next_nested;
2261   *node2 = node->next_nested;
2262   node->origin = NULL;
2263 }
2264
2265 /* Return function availability.  See cgraph.h for description of individual
2266    return values.  */
2267 enum availability
2268 cgraph_function_body_availability (struct cgraph_node *node)
2269 {
2270   enum availability avail;
2271   gcc_assert (cgraph_function_flags_ready);
2272   if (!node->analyzed)
2273     avail = AVAIL_NOT_AVAILABLE;
2274   else if (node->local.local)
2275     avail = AVAIL_LOCAL;
2276   else if (!node->local.externally_visible)
2277     avail = AVAIL_AVAILABLE;
2278   /* Inline functions are safe to be analyzed even if their sybol can
2279      be overwritten at runtime.  It is not meaningful to enfore any sane
2280      behaviour on replacing inline function by different body.  */
2281   else if (DECL_DECLARED_INLINE_P (node->decl))
2282     avail = AVAIL_AVAILABLE;
2283
2284   /* If the function can be overwritten, return OVERWRITABLE.  Take
2285      care at least of two notable extensions - the COMDAT functions
2286      used to share template instantiations in C++ (this is symmetric
2287      to code cp_cannot_inline_tree_fn and probably shall be shared and
2288      the inlinability hooks completely eliminated).
2289
2290      ??? Does the C++ one definition rule allow us to always return
2291      AVAIL_AVAILABLE here?  That would be good reason to preserve this
2292      bit.  */
2293
2294   else if (DECL_REPLACEABLE_P (node->decl) && !DECL_EXTERNAL (node->decl))
2295     avail = AVAIL_OVERWRITABLE;
2296   else avail = AVAIL_AVAILABLE;
2297
2298   return avail;
2299 }
2300
2301 /* Add the function FNDECL to the call graph.
2302    Unlike cgraph_finalize_function, this function is intended to be used
2303    by middle end and allows insertion of new function at arbitrary point
2304    of compilation.  The function can be either in high, low or SSA form
2305    GIMPLE.
2306
2307    The function is assumed to be reachable and have address taken (so no
2308    API breaking optimizations are performed on it).
2309
2310    Main work done by this function is to enqueue the function for later
2311    processing to avoid need the passes to be re-entrant.  */
2312
2313 void
2314 cgraph_add_new_function (tree fndecl, bool lowered)
2315 {
2316   struct cgraph_node *node;
2317   switch (cgraph_state)
2318     {
2319       case CGRAPH_STATE_CONSTRUCTION:
2320         /* Just enqueue function to be processed at nearest occurrence.  */
2321         node = cgraph_node (fndecl);
2322         node->next_needed = cgraph_new_nodes;
2323         if (lowered)
2324           node->lowered = true;
2325         cgraph_new_nodes = node;
2326         break;
2327
2328       case CGRAPH_STATE_IPA:
2329       case CGRAPH_STATE_IPA_SSA:
2330       case CGRAPH_STATE_EXPANSION:
2331         /* Bring the function into finalized state and enqueue for later
2332            analyzing and compilation.  */
2333         node = cgraph_node (fndecl);
2334         node->local.local = false;
2335         node->local.finalized = true;
2336         node->reachable = node->needed = true;
2337         if (!lowered && cgraph_state == CGRAPH_STATE_EXPANSION)
2338           {
2339             push_cfun (DECL_STRUCT_FUNCTION (fndecl));
2340             current_function_decl = fndecl;
2341             gimple_register_cfg_hooks ();
2342             tree_lowering_passes (fndecl);
2343             bitmap_obstack_initialize (NULL);
2344             if (!gimple_in_ssa_p (DECL_STRUCT_FUNCTION (fndecl)))
2345               execute_pass_list (pass_early_local_passes.pass.sub);
2346             bitmap_obstack_release (NULL);
2347             pop_cfun ();
2348             current_function_decl = NULL;
2349
2350             lowered = true;
2351           }
2352         if (lowered)
2353           node->lowered = true;
2354         node->next_needed = cgraph_new_nodes;
2355         cgraph_new_nodes = node;
2356         break;
2357
2358       case CGRAPH_STATE_FINISHED:
2359         /* At the very end of compilation we have to do all the work up
2360            to expansion.  */
2361         push_cfun (DECL_STRUCT_FUNCTION (fndecl));
2362         current_function_decl = fndecl;
2363         gimple_register_cfg_hooks ();
2364         if (!lowered)
2365           tree_lowering_passes (fndecl);
2366         bitmap_obstack_initialize (NULL);
2367         if (!gimple_in_ssa_p (DECL_STRUCT_FUNCTION (fndecl)))
2368           execute_pass_list (pass_early_local_passes.pass.sub);
2369         bitmap_obstack_release (NULL);
2370         tree_rest_of_compilation (fndecl);
2371         pop_cfun ();
2372         current_function_decl = NULL;
2373         break;
2374     }
2375
2376   /* Set a personality if required and we already passed EH lowering.  */
2377   if (lowered
2378       && (function_needs_eh_personality (DECL_STRUCT_FUNCTION (fndecl))
2379           == eh_personality_lang))
2380     DECL_FUNCTION_PERSONALITY (fndecl) = lang_hooks.eh_personality ();
2381 }
2382
2383 /* Return true if NODE can be made local for API change.
2384    Extern inline functions and C++ COMDAT functions can be made local
2385    at the expense of possible code size growth if function is used in multiple
2386    compilation units.  */
2387 bool
2388 cgraph_node_can_be_local_p (struct cgraph_node *node)
2389 {
2390   return (!node->needed && !node->address_taken
2391           && ((DECL_COMDAT (node->decl) && !node->same_comdat_group)
2392               || !node->local.externally_visible));
2393 }
2394
2395 /* Make DECL local.  FIXME: We shouldn't need to mess with rtl this early,
2396    but other code such as notice_global_symbol generates rtl.  */
2397 void
2398 cgraph_make_decl_local (tree decl)
2399 {
2400   rtx rtl, symbol;
2401
2402   if (TREE_CODE (decl) == VAR_DECL)
2403     DECL_COMMON (decl) = 0;
2404   else if (TREE_CODE (decl) == FUNCTION_DECL)
2405     {
2406       DECL_COMDAT (decl) = 0;
2407       DECL_COMDAT_GROUP (decl) = 0;
2408       DECL_WEAK (decl) = 0;
2409       DECL_EXTERNAL (decl) = 0;
2410     }
2411   else
2412     gcc_unreachable ();
2413   TREE_PUBLIC (decl) = 0;
2414   if (!DECL_RTL_SET_P (decl))
2415     return;
2416
2417   /* Update rtl flags.  */
2418   make_decl_rtl (decl);
2419
2420   rtl = DECL_RTL (decl);
2421   if (!MEM_P (rtl))
2422     return;
2423
2424   symbol = XEXP (rtl, 0);
2425   if (GET_CODE (symbol) != SYMBOL_REF)
2426     return;
2427
2428   SYMBOL_REF_WEAK (symbol) = DECL_WEAK (decl);
2429 }
2430
2431 /* Bring NODE local.  */
2432 void
2433 cgraph_make_node_local (struct cgraph_node *node)
2434 {
2435   gcc_assert (cgraph_node_can_be_local_p (node));
2436   if (DECL_COMDAT (node->decl) || DECL_EXTERNAL (node->decl))
2437     {
2438       struct cgraph_node *alias;
2439       cgraph_make_decl_local (node->decl);
2440
2441       for (alias = node->same_body; alias; alias = alias->next)
2442         cgraph_make_decl_local (alias->decl);
2443
2444       node->local.externally_visible = false;
2445       node->local.local = true;
2446       gcc_assert (cgraph_function_body_availability (node) == AVAIL_LOCAL);
2447     }
2448 }
2449
2450 /* Set TREE_NOTHROW on NODE's decl and on same_body aliases of NODE
2451    if any to NOTHROW.  */
2452
2453 void
2454 cgraph_set_nothrow_flag (struct cgraph_node *node, bool nothrow)
2455 {
2456   struct cgraph_node *alias;
2457   TREE_NOTHROW (node->decl) = nothrow;
2458   for (alias = node->same_body; alias; alias = alias->next)
2459     TREE_NOTHROW (alias->decl) = nothrow;
2460 }
2461
2462 /* Set TREE_READONLY on NODE's decl and on same_body aliases of NODE
2463    if any to READONLY.  */
2464
2465 void
2466 cgraph_set_readonly_flag (struct cgraph_node *node, bool readonly)
2467 {
2468   struct cgraph_node *alias;
2469   TREE_READONLY (node->decl) = readonly;
2470   for (alias = node->same_body; alias; alias = alias->next)
2471     TREE_READONLY (alias->decl) = readonly;
2472 }
2473
2474 /* Set DECL_PURE_P on NODE's decl and on same_body aliases of NODE
2475    if any to PURE.  */
2476
2477 void
2478 cgraph_set_pure_flag (struct cgraph_node *node, bool pure)
2479 {
2480   struct cgraph_node *alias;
2481   DECL_PURE_P (node->decl) = pure;
2482   for (alias = node->same_body; alias; alias = alias->next)
2483     DECL_PURE_P (alias->decl) = pure;
2484 }
2485
2486 /* Set DECL_LOOPING_CONST_OR_PURE_P on NODE's decl and on
2487    same_body aliases of NODE if any to LOOPING_CONST_OR_PURE.  */
2488
2489 void
2490 cgraph_set_looping_const_or_pure_flag (struct cgraph_node *node,
2491                                        bool looping_const_or_pure)
2492 {
2493   struct cgraph_node *alias;
2494   DECL_LOOPING_CONST_OR_PURE_P (node->decl) = looping_const_or_pure;
2495   for (alias = node->same_body; alias; alias = alias->next)
2496     DECL_LOOPING_CONST_OR_PURE_P (alias->decl) = looping_const_or_pure;
2497 }
2498
2499 /* See if the frequency of NODE can be updated based on frequencies of its
2500    callers.  */
2501 bool
2502 cgraph_propagate_frequency (struct cgraph_node *node)
2503 {
2504   bool maybe_unlikely_executed = true, maybe_executed_once = true;
2505   struct cgraph_edge *edge;
2506   if (!node->local.local)
2507     return false;
2508   gcc_assert (node->analyzed);
2509   if (node->frequency == NODE_FREQUENCY_HOT)
2510     return false;
2511   if (node->frequency == NODE_FREQUENCY_UNLIKELY_EXECUTED)
2512     return false;
2513   if (dump_file && (dump_flags & TDF_DETAILS))
2514     fprintf (dump_file, "Processing frequency %s\n", cgraph_node_name (node));
2515   for (edge = node->callers;
2516        edge && (maybe_unlikely_executed || maybe_executed_once);
2517        edge = edge->next_caller)
2518     {
2519       if (!edge->frequency)
2520         continue;
2521       switch (edge->caller->frequency)
2522         {
2523         case NODE_FREQUENCY_UNLIKELY_EXECUTED:
2524           break;
2525         case NODE_FREQUENCY_EXECUTED_ONCE:
2526           if (dump_file && (dump_flags & TDF_DETAILS))
2527             fprintf (dump_file, "  Called by %s that is executed once\n", cgraph_node_name (node));
2528           maybe_unlikely_executed = false;
2529           if (edge->loop_nest)
2530             {
2531               maybe_executed_once = false;
2532               if (dump_file && (dump_flags & TDF_DETAILS))
2533                 fprintf (dump_file, "  Called in loop\n");
2534             }
2535           break;
2536         case NODE_FREQUENCY_HOT:
2537         case NODE_FREQUENCY_NORMAL:
2538           if (dump_file && (dump_flags & TDF_DETAILS))
2539             fprintf (dump_file, "  Called by %s that is normal or hot\n", cgraph_node_name (node));
2540           maybe_unlikely_executed = false;
2541           maybe_executed_once = false;
2542           break;
2543         }
2544     }
2545    if (maybe_unlikely_executed)
2546      {
2547        node->frequency = NODE_FREQUENCY_UNLIKELY_EXECUTED;
2548        if (dump_file)
2549          fprintf (dump_file, "Node %s promoted to unlikely executed.\n", cgraph_node_name (node));
2550        return true;
2551      }
2552    if (maybe_executed_once && node->frequency != NODE_FREQUENCY_EXECUTED_ONCE)
2553      {
2554        node->frequency = NODE_FREQUENCY_EXECUTED_ONCE;
2555        if (dump_file)
2556          fprintf (dump_file, "Node %s promoted to executed once.\n", cgraph_node_name (node));
2557        return true;
2558      }
2559    return false;
2560 }
2561
2562 #include "gt-cgraph.h"