OSDN Git Service

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