OSDN Git Service

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