OSDN Git Service

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