1 /* Callgraph handling code.
2 Copyright (C) 2003, 2004, 2005, 2006, 2007, 2008
3 Free Software Foundation, Inc.
4 Contributed by Jan Hubicka
6 This file is part of GCC.
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
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
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/>. */
22 /* This file contains basic routines manipulating call graph
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
30 The call-graph consist of nodes and edges represented via linked lists.
31 Each function (external or not) corresponds to the unique node.
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.
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.
42 Interprocedural information:
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.
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
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. */
68 #include "coretypes.h"
71 #include "tree-inline.h"
72 #include "langhooks.h"
79 #include "basic-block.h"
85 #include "tree-dump.h"
86 #include "tree-flow.h"
87 #include "value-prof.h"
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
);
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
;
98 /* The linked list of cgraph nodes. */
99 struct cgraph_node
*cgraph_nodes
;
101 /* Queue of cgraph nodes scheduled to be lowered. */
102 struct cgraph_node
*cgraph_nodes_queue
;
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
;
109 /* Number of nodes in existence. */
112 /* Maximal uid used in cgraph nodes. */
115 /* Maximal uid used in cgraph edges. */
116 int cgraph_edge_max_uid
;
118 /* Maximal pid used for profiling */
121 /* Set when whole unit has been analyzed so we can access global info. */
122 bool cgraph_global_info_ready
= false;
124 /* What state callgraph is in right now. */
125 enum cgraph_state cgraph_state
= CGRAPH_STATE_CONSTRUCTION
;
127 /* Set when the cgraph is fully build and the basic flags are computed. */
128 bool cgraph_function_flags_ready
= false;
130 /* Linked list of cgraph asm nodes. */
131 struct cgraph_asm_node
*cgraph_asm_nodes
;
133 /* Last node in cgraph_asm_nodes. */
134 static GTY(()) struct cgraph_asm_node
*cgraph_asm_last_node
;
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. */
141 /* List of hooks trigerred on cgraph_edge events. */
142 struct cgraph_edge_hook_list
{
143 cgraph_edge_hook hook
;
145 struct cgraph_edge_hook_list
*next
;
148 /* List of hooks trigerred on cgraph_node events. */
149 struct cgraph_node_hook_list
{
150 cgraph_node_hook hook
;
152 struct cgraph_node_hook_list
*next
;
155 /* List of hooks trigerred on events involving two cgraph_edges. */
156 struct cgraph_2edge_hook_list
{
157 cgraph_2edge_hook hook
;
159 struct cgraph_2edge_hook_list
*next
;
162 /* List of hooks trigerred on events involving two cgraph_nodes. */
163 struct cgraph_2node_hook_list
{
164 cgraph_2node_hook hook
;
166 struct cgraph_2node_hook_list
*next
;
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
;
180 /* Head of a linked list of unused (freed) call graph edges.
181 Do not GTY((delete)) this list so UIDs gets reliably recycled. */
182 static GTY(()) struct cgraph_edge
*free_edges
;
184 /* Macro to access the next item in the list of free cgraph edges. */
185 #define NEXT_FREE_EDGE(EDGE) (EDGE)->prev_caller
187 /* Register HOOK to be called with DATA on each removed edge. */
188 struct cgraph_edge_hook_list
*
189 cgraph_add_edge_removal_hook (cgraph_edge_hook hook
, void *data
)
191 struct cgraph_edge_hook_list
*entry
;
192 struct cgraph_edge_hook_list
**ptr
= &first_cgraph_edge_removal_hook
;
194 entry
= (struct cgraph_edge_hook_list
*) xmalloc (sizeof (*entry
));
204 /* Remove ENTRY from the list of hooks called on removing edges. */
206 cgraph_remove_edge_removal_hook (struct cgraph_edge_hook_list
*entry
)
208 struct cgraph_edge_hook_list
**ptr
= &first_cgraph_edge_removal_hook
;
210 while (*ptr
!= entry
)
216 /* Call all edge removal hooks. */
218 cgraph_call_edge_removal_hooks (struct cgraph_edge
*e
)
220 struct cgraph_edge_hook_list
*entry
= first_cgraph_edge_removal_hook
;
223 entry
->hook (e
, entry
->data
);
228 /* Register HOOK to be called with DATA on each removed node. */
229 struct cgraph_node_hook_list
*
230 cgraph_add_node_removal_hook (cgraph_node_hook hook
, void *data
)
232 struct cgraph_node_hook_list
*entry
;
233 struct cgraph_node_hook_list
**ptr
= &first_cgraph_node_removal_hook
;
235 entry
= (struct cgraph_node_hook_list
*) xmalloc (sizeof (*entry
));
245 /* Remove ENTRY from the list of hooks called on removing nodes. */
247 cgraph_remove_node_removal_hook (struct cgraph_node_hook_list
*entry
)
249 struct cgraph_node_hook_list
**ptr
= &first_cgraph_node_removal_hook
;
251 while (*ptr
!= entry
)
257 /* Call all node removal hooks. */
259 cgraph_call_node_removal_hooks (struct cgraph_node
*node
)
261 struct cgraph_node_hook_list
*entry
= first_cgraph_node_removal_hook
;
264 entry
->hook (node
, entry
->data
);
269 /* Register HOOK to be called with DATA on each removed node. */
270 struct cgraph_node_hook_list
*
271 cgraph_add_function_insertion_hook (cgraph_node_hook hook
, void *data
)
273 struct cgraph_node_hook_list
*entry
;
274 struct cgraph_node_hook_list
**ptr
= &first_cgraph_function_insertion_hook
;
276 entry
= (struct cgraph_node_hook_list
*) xmalloc (sizeof (*entry
));
286 /* Remove ENTRY from the list of hooks called on removing nodes. */
288 cgraph_remove_function_insertion_hook (struct cgraph_node_hook_list
*entry
)
290 struct cgraph_node_hook_list
**ptr
= &first_cgraph_function_insertion_hook
;
292 while (*ptr
!= entry
)
298 /* Call all node removal hooks. */
300 cgraph_call_function_insertion_hooks (struct cgraph_node
*node
)
302 struct cgraph_node_hook_list
*entry
= first_cgraph_function_insertion_hook
;
305 entry
->hook (node
, entry
->data
);
310 /* Register HOOK to be called with DATA on each duplicated edge. */
311 struct cgraph_2edge_hook_list
*
312 cgraph_add_edge_duplication_hook (cgraph_2edge_hook hook
, void *data
)
314 struct cgraph_2edge_hook_list
*entry
;
315 struct cgraph_2edge_hook_list
**ptr
= &first_cgraph_edge_duplicated_hook
;
317 entry
= (struct cgraph_2edge_hook_list
*) xmalloc (sizeof (*entry
));
327 /* Remove ENTRY from the list of hooks called on duplicating edges. */
329 cgraph_remove_edge_duplication_hook (struct cgraph_2edge_hook_list
*entry
)
331 struct cgraph_2edge_hook_list
**ptr
= &first_cgraph_edge_duplicated_hook
;
333 while (*ptr
!= entry
)
339 /* Call all edge duplication hooks. */
341 cgraph_call_edge_duplication_hooks (struct cgraph_edge
*cs1
,
342 struct cgraph_edge
*cs2
)
344 struct cgraph_2edge_hook_list
*entry
= first_cgraph_edge_duplicated_hook
;
347 entry
->hook (cs1
, cs2
, entry
->data
);
352 /* Register HOOK to be called with DATA on each duplicated node. */
353 struct cgraph_2node_hook_list
*
354 cgraph_add_node_duplication_hook (cgraph_2node_hook hook
, void *data
)
356 struct cgraph_2node_hook_list
*entry
;
357 struct cgraph_2node_hook_list
**ptr
= &first_cgraph_node_duplicated_hook
;
359 entry
= (struct cgraph_2node_hook_list
*) xmalloc (sizeof (*entry
));
369 /* Remove ENTRY from the list of hooks called on duplicating nodes. */
371 cgraph_remove_node_duplication_hook (struct cgraph_2node_hook_list
*entry
)
373 struct cgraph_2node_hook_list
**ptr
= &first_cgraph_node_duplicated_hook
;
375 while (*ptr
!= entry
)
381 /* Call all node duplication hooks. */
383 cgraph_call_node_duplication_hooks (struct cgraph_node
*node1
,
384 struct cgraph_node
*node2
)
386 struct cgraph_2node_hook_list
*entry
= first_cgraph_node_duplicated_hook
;
389 entry
->hook (node1
, node2
, entry
->data
);
394 /* Returns a hash code for P. */
397 hash_node (const void *p
)
399 const struct cgraph_node
*n
= (const struct cgraph_node
*) p
;
400 return (hashval_t
) DECL_UID (n
->decl
);
403 /* Returns nonzero if P1 and P2 are equal. */
406 eq_node (const void *p1
, const void *p2
)
408 const struct cgraph_node
*n1
= (const struct cgraph_node
*) p1
;
409 const struct cgraph_node
*n2
= (const struct cgraph_node
*) p2
;
410 return DECL_UID (n1
->decl
) == DECL_UID (n2
->decl
);
413 /* Allocate new callgraph node and insert it into basic data structures. */
415 static struct cgraph_node
*
416 cgraph_create_node (void)
418 struct cgraph_node
*node
;
420 node
= GGC_CNEW (struct cgraph_node
);
421 node
->next
= cgraph_nodes
;
422 node
->uid
= cgraph_max_uid
++;
424 node
->order
= cgraph_order
++;
426 cgraph_nodes
->previous
= node
;
427 node
->previous
= NULL
;
428 node
->global
.estimated_growth
= INT_MIN
;
434 /* Return cgraph node assigned to DECL. Create new one when needed. */
437 cgraph_node (tree decl
)
439 struct cgraph_node key
, *node
, **slot
;
441 gcc_assert (TREE_CODE (decl
) == FUNCTION_DECL
);
444 cgraph_hash
= htab_create_ggc (10, hash_node
, eq_node
, NULL
);
448 slot
= (struct cgraph_node
**) htab_find_slot (cgraph_hash
, &key
, INSERT
);
453 if (!node
->master_clone
)
454 node
->master_clone
= node
;
458 node
= cgraph_create_node ();
461 if (DECL_CONTEXT (decl
) && TREE_CODE (DECL_CONTEXT (decl
)) == FUNCTION_DECL
)
463 node
->origin
= cgraph_node (DECL_CONTEXT (decl
));
464 node
->next_nested
= node
->origin
->nested
;
465 node
->origin
->nested
= node
;
466 node
->master_clone
= node
;
468 if (assembler_name_hash
)
471 tree name
= DECL_ASSEMBLER_NAME (decl
);
473 aslot
= htab_find_slot_with_hash (assembler_name_hash
, name
,
474 decl_assembler_name_hash (name
),
476 /* We can have multiple declarations with same assembler name. For C++
477 it is __builtin_strlen and strlen, for instance. Do we need to
478 record them all? Original implementation marked just first one
479 so lets hope for the best. */
486 /* Insert already constructed node into hashtable. */
489 cgraph_insert_node_to_hashtable (struct cgraph_node
*node
)
491 struct cgraph_node
**slot
;
493 slot
= (struct cgraph_node
**) htab_find_slot (cgraph_hash
, node
, INSERT
);
499 /* Returns a hash code for P. */
502 hash_node_by_assembler_name (const void *p
)
504 const struct cgraph_node
*n
= (const struct cgraph_node
*) p
;
505 return (hashval_t
) decl_assembler_name_hash (DECL_ASSEMBLER_NAME (n
->decl
));
508 /* Returns nonzero if P1 and P2 are equal. */
511 eq_assembler_name (const void *p1
, const void *p2
)
513 const struct cgraph_node
*n1
= (const struct cgraph_node
*) p1
;
514 const_tree name
= (const_tree
)p2
;
515 return (decl_assembler_name_equal (n1
->decl
, name
));
518 /* Return the cgraph node that has ASMNAME for its DECL_ASSEMBLER_NAME.
519 Return NULL if there's no such node. */
522 cgraph_node_for_asm (tree asmname
)
524 struct cgraph_node
*node
;
527 if (!assembler_name_hash
)
529 assembler_name_hash
=
530 htab_create_ggc (10, hash_node_by_assembler_name
, eq_assembler_name
,
532 for (node
= cgraph_nodes
; node
; node
= node
->next
)
533 if (!node
->global
.inlined_to
)
535 tree name
= DECL_ASSEMBLER_NAME (node
->decl
);
536 slot
= htab_find_slot_with_hash (assembler_name_hash
, name
,
537 decl_assembler_name_hash (name
),
539 /* We can have multiple declarations with same assembler name. For C++
540 it is __builtin_strlen and strlen, for instance. Do we need to
541 record them all? Original implementation marked just first one
542 so lets hope for the best. */
549 slot
= htab_find_slot_with_hash (assembler_name_hash
, asmname
,
550 decl_assembler_name_hash (asmname
),
554 return (struct cgraph_node
*) *slot
;
558 /* Returns a hash value for X (which really is a die_struct). */
561 edge_hash (const void *x
)
563 return htab_hash_pointer (((const struct cgraph_edge
*) x
)->call_stmt
);
566 /* Return nonzero if decl_id of die_struct X is the same as UID of decl *Y. */
569 edge_eq (const void *x
, const void *y
)
571 return ((const struct cgraph_edge
*) x
)->call_stmt
== y
;
575 /* Return the callgraph edge representing the GIMPLE_CALL statement
579 cgraph_edge (struct cgraph_node
*node
, gimple call_stmt
)
581 struct cgraph_edge
*e
, *e2
;
584 if (node
->call_site_hash
)
585 return (struct cgraph_edge
*)
586 htab_find_with_hash (node
->call_site_hash
, call_stmt
,
587 htab_hash_pointer (call_stmt
));
589 /* This loop may turn out to be performance problem. In such case adding
590 hashtables into call nodes with very many edges is probably best
591 solution. It is not good idea to add pointer into CALL_EXPR itself
592 because we want to make possible having multiple cgraph nodes representing
593 different clones of the same body before the body is actually cloned. */
594 for (e
= node
->callees
; e
; e
= e
->next_callee
)
596 if (e
->call_stmt
== call_stmt
)
603 node
->call_site_hash
= htab_create_ggc (120, edge_hash
, edge_eq
, NULL
);
604 for (e2
= node
->callees
; e2
; e2
= e2
->next_callee
)
607 slot
= htab_find_slot_with_hash (node
->call_site_hash
,
609 htab_hash_pointer (e2
->call_stmt
),
620 /* Change field call_smt of edge E to NEW_STMT. */
623 cgraph_set_call_stmt (struct cgraph_edge
*e
, gimple new_stmt
)
625 if (e
->caller
->call_site_hash
)
627 htab_remove_elt_with_hash (e
->caller
->call_site_hash
,
629 htab_hash_pointer (e
->call_stmt
));
631 e
->call_stmt
= new_stmt
;
632 if (e
->caller
->call_site_hash
)
635 slot
= htab_find_slot_with_hash (e
->caller
->call_site_hash
,
638 (e
->call_stmt
), INSERT
);
644 /* Create edge from CALLER to CALLEE in the cgraph. */
647 cgraph_create_edge (struct cgraph_node
*caller
, struct cgraph_node
*callee
,
648 gimple call_stmt
, gcov_type count
, int freq
, int nest
)
650 struct cgraph_edge
*edge
;
652 #ifdef ENABLE_CHECKING
653 /* This is rather pricely check possibly trigerring construction of call stmt
655 gcc_assert (!cgraph_edge (caller
, call_stmt
));
658 gcc_assert (is_gimple_call (call_stmt
));
663 free_edges
= NEXT_FREE_EDGE (edge
);
667 edge
= GGC_NEW (struct cgraph_edge
);
668 edge
->uid
= cgraph_edge_max_uid
++;
671 if (!callee
->analyzed
)
672 edge
->inline_failed
= N_("function body not available");
673 else if (callee
->local
.redefined_extern_inline
)
674 edge
->inline_failed
= N_("redefined extern inline functions are not "
675 "considered for inlining");
676 else if (callee
->local
.inlinable
)
677 edge
->inline_failed
= N_("function not considered for inlining");
679 edge
->inline_failed
= N_("function not inlinable");
683 edge
->caller
= caller
;
684 edge
->callee
= callee
;
685 edge
->call_stmt
= call_stmt
;
686 edge
->prev_caller
= NULL
;
687 edge
->next_caller
= callee
->callers
;
689 callee
->callers
->prev_caller
= edge
;
690 edge
->prev_callee
= NULL
;
691 edge
->next_callee
= caller
->callees
;
693 caller
->callees
->prev_callee
= edge
;
694 caller
->callees
= edge
;
695 callee
->callers
= edge
;
697 gcc_assert (count
>= 0);
698 edge
->frequency
= freq
;
699 gcc_assert (freq
>= 0);
700 gcc_assert (freq
<= CGRAPH_FREQ_MAX
);
701 edge
->loop_nest
= nest
;
702 edge
->indirect_call
= 0;
703 if (caller
->call_site_hash
)
706 slot
= htab_find_slot_with_hash (caller
->call_site_hash
,
717 /* Remove the edge E from the list of the callers of the callee. */
720 cgraph_edge_remove_callee (struct cgraph_edge
*e
)
723 e
->prev_caller
->next_caller
= e
->next_caller
;
725 e
->next_caller
->prev_caller
= e
->prev_caller
;
727 e
->callee
->callers
= e
->next_caller
;
730 /* Remove the edge E from the list of the callees of the caller. */
733 cgraph_edge_remove_caller (struct cgraph_edge
*e
)
736 e
->prev_callee
->next_callee
= e
->next_callee
;
738 e
->next_callee
->prev_callee
= e
->prev_callee
;
740 e
->caller
->callees
= e
->next_callee
;
741 if (e
->caller
->call_site_hash
)
742 htab_remove_elt_with_hash (e
->caller
->call_site_hash
,
744 htab_hash_pointer (e
->call_stmt
));
747 /* Put the edge onto the free list. */
750 cgraph_free_edge (struct cgraph_edge
*e
)
754 /* Clear out the edge so we do not dangle pointers. */
755 memset (e
, 0, sizeof (*e
));
757 NEXT_FREE_EDGE (e
) = free_edges
;
761 /* Remove the edge E in the cgraph. */
764 cgraph_remove_edge (struct cgraph_edge
*e
)
766 /* Call all edge removal hooks. */
767 cgraph_call_edge_removal_hooks (e
);
769 /* Remove from callers list of the callee. */
770 cgraph_edge_remove_callee (e
);
772 /* Remove from callees list of the callers. */
773 cgraph_edge_remove_caller (e
);
775 /* Put the edge onto the free list. */
776 cgraph_free_edge (e
);
779 /* Redirect callee of E to N. The function does not update underlying
783 cgraph_redirect_edge_callee (struct cgraph_edge
*e
, struct cgraph_node
*n
)
785 /* Remove from callers list of the current callee. */
786 cgraph_edge_remove_callee (e
);
788 /* Insert to callers list of the new callee. */
789 e
->prev_caller
= NULL
;
791 n
->callers
->prev_caller
= e
;
792 e
->next_caller
= n
->callers
;
798 /* Update or remove the corresponding cgraph edge if a GIMPLE_CALL
799 OLD_STMT changed into NEW_STMT. */
802 cgraph_update_edges_for_call_stmt (gimple old_stmt
, gimple new_stmt
)
804 tree new_call
= (is_gimple_call (new_stmt
)) ? gimple_call_fn (new_stmt
) : 0;
805 tree old_call
= (is_gimple_call (old_stmt
)) ? gimple_call_fn (old_stmt
) : 0;
806 struct cgraph_node
*node
= cgraph_node (cfun
->decl
);
808 if (old_call
!= new_call
)
810 struct cgraph_edge
*e
= cgraph_edge (node
, old_stmt
);
811 struct cgraph_edge
*ne
= NULL
;
816 gcov_type count
= e
->count
;
817 int frequency
= e
->frequency
;
818 int loop_nest
= e
->loop_nest
;
820 cgraph_remove_edge (e
);
823 new_decl
= gimple_call_fndecl (new_stmt
);
826 ne
= cgraph_create_edge (node
, cgraph_node (new_decl
),
827 new_stmt
, count
, frequency
,
829 gcc_assert (ne
->inline_failed
);
834 else if (old_stmt
!= new_stmt
)
836 struct cgraph_edge
*e
= cgraph_edge (node
, old_stmt
);
839 cgraph_set_call_stmt (e
, new_stmt
);
844 /* Remove all callees from the node. */
847 cgraph_node_remove_callees (struct cgraph_node
*node
)
849 struct cgraph_edge
*e
, *f
;
851 /* It is sufficient to remove the edges from the lists of callers of
852 the callees. The callee list of the node can be zapped with one
854 for (e
= node
->callees
; e
; e
= f
)
857 cgraph_call_edge_removal_hooks (e
);
858 cgraph_edge_remove_callee (e
);
859 cgraph_free_edge (e
);
861 node
->callees
= NULL
;
862 if (node
->call_site_hash
)
864 htab_delete (node
->call_site_hash
);
865 node
->call_site_hash
= NULL
;
869 /* Remove all callers from the node. */
872 cgraph_node_remove_callers (struct cgraph_node
*node
)
874 struct cgraph_edge
*e
, *f
;
876 /* It is sufficient to remove the edges from the lists of callees of
877 the callers. The caller list of the node can be zapped with one
879 for (e
= node
->callers
; e
; e
= f
)
882 cgraph_call_edge_removal_hooks (e
);
883 cgraph_edge_remove_caller (e
);
884 cgraph_free_edge (e
);
886 node
->callers
= NULL
;
889 /* Release memory used to represent body of function NODE. */
892 cgraph_release_function_body (struct cgraph_node
*node
)
894 if (DECL_STRUCT_FUNCTION (node
->decl
))
896 tree old_decl
= current_function_decl
;
897 push_cfun (DECL_STRUCT_FUNCTION (node
->decl
));
900 current_function_decl
= node
->decl
;
902 delete_tree_cfg_annotations ();
904 current_function_decl
= old_decl
;
908 gcc_assert (dom_computed
[0] == DOM_NONE
);
909 gcc_assert (dom_computed
[1] == DOM_NONE
);
912 if (cfun
->value_histograms
)
914 gcc_assert (!current_loops
);
916 gimple_set_body (node
->decl
, NULL
);
917 VEC_free (ipa_opt_pass
, heap
,
918 DECL_STRUCT_FUNCTION (node
->decl
)->ipa_transforms_to_apply
);
919 /* Struct function hangs a lot of data that would leak if we didn't
920 removed all pointers to it. */
921 ggc_free (DECL_STRUCT_FUNCTION (node
->decl
));
922 DECL_STRUCT_FUNCTION (node
->decl
) = NULL
;
924 DECL_SAVED_TREE (node
->decl
) = NULL
;
925 DECL_INITIAL (node
->decl
) = error_mark_node
;
928 /* Remove the node from cgraph. */
931 cgraph_remove_node (struct cgraph_node
*node
)
934 bool kill_body
= false;
935 struct cgraph_node
*n
;
937 cgraph_call_node_removal_hooks (node
);
938 cgraph_node_remove_callers (node
);
939 cgraph_node_remove_callees (node
);
941 /* Incremental inlining access removed nodes stored in the postorder list.
943 node
->needed
= node
->reachable
= false;
944 for (n
= node
->nested
; n
; n
= n
->next_nested
)
949 struct cgraph_node
**node2
= &node
->origin
->nested
;
951 while (*node2
!= node
)
952 node2
= &(*node2
)->next_nested
;
953 *node2
= node
->next_nested
;
956 node
->previous
->next
= node
->next
;
958 cgraph_nodes
= node
->next
;
960 node
->next
->previous
= node
->previous
;
962 node
->previous
= NULL
;
963 slot
= htab_find_slot (cgraph_hash
, node
, NO_INSERT
);
966 if (node
->next_clone
)
968 struct cgraph_node
*new_node
= node
->next_clone
;
969 struct cgraph_node
*n
;
971 /* Make the next clone be the master clone */
972 for (n
= new_node
; n
; n
= n
->next_clone
)
973 n
->master_clone
= new_node
;
976 node
->next_clone
->prev_clone
= NULL
;
980 htab_clear_slot (cgraph_hash
, slot
);
986 node
->prev_clone
->next_clone
= node
->next_clone
;
987 if (node
->next_clone
)
988 node
->next_clone
->prev_clone
= node
->prev_clone
;
991 /* While all the clones are removed after being proceeded, the function
992 itself is kept in the cgraph even after it is compiled. Check whether
993 we are done with this body and reclaim it proactively if this is the case.
995 if (!kill_body
&& *slot
)
997 struct cgraph_node
*n
= (struct cgraph_node
*) *slot
;
998 if (!n
->next_clone
&& !n
->global
.inlined_to
999 && (cgraph_global_info_ready
1000 && (TREE_ASM_WRITTEN (n
->decl
) || DECL_EXTERNAL (n
->decl
))))
1003 if (assembler_name_hash
)
1005 tree name
= DECL_ASSEMBLER_NAME (node
->decl
);
1006 slot
= htab_find_slot_with_hash (assembler_name_hash
, name
,
1007 decl_assembler_name_hash (name
),
1009 /* Inline clones are not hashed. */
1010 if (slot
&& *slot
== node
)
1011 htab_clear_slot (assembler_name_hash
, slot
);
1015 cgraph_release_function_body (node
);
1017 if (node
->call_site_hash
)
1019 htab_delete (node
->call_site_hash
);
1020 node
->call_site_hash
= NULL
;
1023 /* Do not free the structure itself so the walk over chain can continue. */
1026 /* Notify finalize_compilation_unit that given node is reachable. */
1029 cgraph_mark_reachable_node (struct cgraph_node
*node
)
1031 if (!node
->reachable
&& node
->local
.finalized
)
1033 notice_global_symbol (node
->decl
);
1034 node
->reachable
= 1;
1035 gcc_assert (!cgraph_global_info_ready
);
1037 node
->next_needed
= cgraph_nodes_queue
;
1038 cgraph_nodes_queue
= node
;
1042 /* Likewise indicate that a node is needed, i.e. reachable via some
1046 cgraph_mark_needed_node (struct cgraph_node
*node
)
1049 cgraph_mark_reachable_node (node
);
1052 /* Return local info for the compiled function. */
1054 struct cgraph_local_info
*
1055 cgraph_local_info (tree decl
)
1057 struct cgraph_node
*node
;
1059 gcc_assert (TREE_CODE (decl
) == FUNCTION_DECL
);
1060 node
= cgraph_node (decl
);
1061 return &node
->local
;
1064 /* Return local info for the compiled function. */
1066 struct cgraph_global_info
*
1067 cgraph_global_info (tree decl
)
1069 struct cgraph_node
*node
;
1071 gcc_assert (TREE_CODE (decl
) == FUNCTION_DECL
&& cgraph_global_info_ready
);
1072 node
= cgraph_node (decl
);
1073 return &node
->global
;
1076 /* Return local info for the compiled function. */
1078 struct cgraph_rtl_info
*
1079 cgraph_rtl_info (tree decl
)
1081 struct cgraph_node
*node
;
1083 gcc_assert (TREE_CODE (decl
) == FUNCTION_DECL
);
1084 node
= cgraph_node (decl
);
1085 if (decl
!= current_function_decl
1086 && !TREE_ASM_WRITTEN (node
->decl
))
1091 /* Return name of the node used in debug output. */
1093 cgraph_node_name (struct cgraph_node
*node
)
1095 return lang_hooks
.decl_printable_name (node
->decl
, 2);
1098 /* Names used to print out the availability enum. */
1099 const char * const cgraph_availability_names
[] =
1100 {"unset", "not_available", "overwritable", "available", "local"};
1103 /* Dump call graph node NODE to file F. */
1106 dump_cgraph_node (FILE *f
, struct cgraph_node
*node
)
1108 struct cgraph_edge
*edge
;
1109 fprintf (f
, "%s/%i(%i):", cgraph_node_name (node
), node
->uid
, node
->pid
);
1110 if (node
->global
.inlined_to
)
1111 fprintf (f
, " (inline copy in %s/%i)",
1112 cgraph_node_name (node
->global
.inlined_to
),
1113 node
->global
.inlined_to
->uid
);
1114 if (cgraph_function_flags_ready
)
1115 fprintf (f
, " availability:%s",
1116 cgraph_availability_names
[cgraph_function_body_availability (node
)]);
1117 if (node
->master_clone
&& node
->master_clone
->uid
!= node
->uid
)
1118 fprintf (f
, "(%i)", node
->master_clone
->uid
);
1120 fprintf (f
, " executed "HOST_WIDEST_INT_PRINT_DEC
"x",
1121 (HOST_WIDEST_INT
)node
->count
);
1122 if (node
->local
.inline_summary
.self_insns
)
1123 fprintf (f
, " %i insns", node
->local
.inline_summary
.self_insns
);
1124 if (node
->global
.insns
&& node
->global
.insns
1125 != node
->local
.inline_summary
.self_insns
)
1126 fprintf (f
, " (%i after inlining)", node
->global
.insns
);
1127 if (node
->local
.inline_summary
.estimated_self_stack_size
)
1128 fprintf (f
, " %i bytes stack usage", (int)node
->local
.inline_summary
.estimated_self_stack_size
);
1129 if (node
->global
.estimated_stack_size
!= node
->local
.inline_summary
.estimated_self_stack_size
)
1130 fprintf (f
, " %i bytes after inlining", (int)node
->global
.estimated_stack_size
);
1132 fprintf (f
, " nested in: %s", cgraph_node_name (node
->origin
));
1134 fprintf (f
, " needed");
1135 else if (node
->reachable
)
1136 fprintf (f
, " reachable");
1137 if (gimple_has_body_p (node
->decl
))
1138 fprintf (f
, " body");
1140 fprintf (f
, " output");
1141 if (node
->local
.local
)
1142 fprintf (f
, " local");
1143 if (node
->local
.externally_visible
)
1144 fprintf (f
, " externally_visible");
1145 if (node
->local
.finalized
)
1146 fprintf (f
, " finalized");
1147 if (node
->local
.disregard_inline_limits
)
1148 fprintf (f
, " always_inline");
1149 else if (node
->local
.inlinable
)
1150 fprintf (f
, " inlinable");
1151 if (node
->local
.redefined_extern_inline
)
1152 fprintf (f
, " redefined_extern_inline");
1153 if (TREE_ASM_WRITTEN (node
->decl
))
1154 fprintf (f
, " asm_written");
1156 fprintf (f
, "\n called by: ");
1157 for (edge
= node
->callers
; edge
; edge
= edge
->next_caller
)
1159 fprintf (f
, "%s/%i ", cgraph_node_name (edge
->caller
),
1162 fprintf (f
, "("HOST_WIDEST_INT_PRINT_DEC
"x) ",
1163 (HOST_WIDEST_INT
)edge
->count
);
1164 if (edge
->frequency
)
1165 fprintf (f
, "(%.2f per call) ",
1166 edge
->frequency
/ (double)CGRAPH_FREQ_BASE
);
1167 if (!edge
->inline_failed
)
1168 fprintf(f
, "(inlined) ");
1169 if (edge
->indirect_call
)
1170 fprintf(f
, "(indirect) ");
1173 fprintf (f
, "\n calls: ");
1174 for (edge
= node
->callees
; edge
; edge
= edge
->next_callee
)
1176 fprintf (f
, "%s/%i ", cgraph_node_name (edge
->callee
),
1178 if (!edge
->inline_failed
)
1179 fprintf(f
, "(inlined) ");
1180 if (edge
->indirect_call
)
1181 fprintf(f
, "(indirect) ");
1183 fprintf (f
, "("HOST_WIDEST_INT_PRINT_DEC
"x) ",
1184 (HOST_WIDEST_INT
)edge
->count
);
1185 if (edge
->frequency
)
1186 fprintf (f
, "(%.2f per call) ",
1187 edge
->frequency
/ (double)CGRAPH_FREQ_BASE
);
1188 if (edge
->loop_nest
)
1189 fprintf (f
, "(nested in %i loops) ", edge
->loop_nest
);
1195 /* Dump call graph node NODE to stderr. */
1198 debug_cgraph_node (struct cgraph_node
*node
)
1200 dump_cgraph_node (stderr
, node
);
1204 /* Dump the callgraph to file F. */
1207 dump_cgraph (FILE *f
)
1209 struct cgraph_node
*node
;
1211 fprintf (f
, "callgraph:\n\n");
1212 for (node
= cgraph_nodes
; node
; node
= node
->next
)
1213 dump_cgraph_node (f
, node
);
1217 /* Dump the call graph to stderr. */
1222 dump_cgraph (stderr
);
1226 /* Set the DECL_ASSEMBLER_NAME and update cgraph hashtables. */
1229 change_decl_assembler_name (tree decl
, tree name
)
1231 gcc_assert (!assembler_name_hash
);
1232 if (!DECL_ASSEMBLER_NAME_SET_P (decl
))
1234 SET_DECL_ASSEMBLER_NAME (decl
, name
);
1237 if (name
== DECL_ASSEMBLER_NAME (decl
))
1240 if (TREE_SYMBOL_REFERENCED (DECL_ASSEMBLER_NAME (decl
))
1241 && DECL_RTL_SET_P (decl
))
1242 warning (0, "%D renamed after being referenced in assembly", decl
);
1244 SET_DECL_ASSEMBLER_NAME (decl
, name
);
1247 /* Add a top-level asm statement to the list. */
1249 struct cgraph_asm_node
*
1250 cgraph_add_asm_node (tree asm_str
)
1252 struct cgraph_asm_node
*node
;
1254 node
= GGC_CNEW (struct cgraph_asm_node
);
1255 node
->asm_str
= asm_str
;
1256 node
->order
= cgraph_order
++;
1258 if (cgraph_asm_nodes
== NULL
)
1259 cgraph_asm_nodes
= node
;
1261 cgraph_asm_last_node
->next
= node
;
1262 cgraph_asm_last_node
= node
;
1266 /* Return true when the DECL can possibly be inlined. */
1268 cgraph_function_possibly_inlined_p (tree decl
)
1270 if (!cgraph_global_info_ready
)
1271 return !DECL_UNINLINABLE (decl
);
1272 return DECL_POSSIBLY_INLINED (decl
);
1275 /* Create clone of E in the node N represented by CALL_EXPR the callgraph. */
1276 struct cgraph_edge
*
1277 cgraph_clone_edge (struct cgraph_edge
*e
, struct cgraph_node
*n
,
1278 gimple call_stmt
, gcov_type count_scale
, int freq_scale
,
1279 int loop_nest
, bool update_original
)
1281 struct cgraph_edge
*new_edge
;
1282 gcov_type count
= e
->count
* count_scale
/ REG_BR_PROB_BASE
;
1283 gcov_type freq
= e
->frequency
* (gcov_type
) freq_scale
/ CGRAPH_FREQ_BASE
;
1285 if (freq
> CGRAPH_FREQ_MAX
)
1286 freq
= CGRAPH_FREQ_MAX
;
1287 new_edge
= cgraph_create_edge (n
, e
->callee
, call_stmt
, count
, freq
,
1288 e
->loop_nest
+ loop_nest
);
1290 new_edge
->inline_failed
= e
->inline_failed
;
1291 new_edge
->indirect_call
= e
->indirect_call
;
1292 if (update_original
)
1294 e
->count
-= new_edge
->count
;
1298 cgraph_call_edge_duplication_hooks (e
, new_edge
);
1302 /* Create node representing clone of N executed COUNT times. Decrease
1303 the execution counts from original node too.
1305 When UPDATE_ORIGINAL is true, the counts are subtracted from the original
1306 function's profile to reflect the fact that part of execution is handled
1308 struct cgraph_node
*
1309 cgraph_clone_node (struct cgraph_node
*n
, gcov_type count
, int freq
,
1310 int loop_nest
, bool update_original
)
1312 struct cgraph_node
*new_node
= cgraph_create_node ();
1313 struct cgraph_edge
*e
;
1314 gcov_type count_scale
;
1316 new_node
->decl
= n
->decl
;
1317 new_node
->origin
= n
->origin
;
1318 if (new_node
->origin
)
1320 new_node
->next_nested
= new_node
->origin
->nested
;
1321 new_node
->origin
->nested
= new_node
;
1323 new_node
->analyzed
= n
->analyzed
;
1324 new_node
->local
= n
->local
;
1325 new_node
->global
= n
->global
;
1326 new_node
->rtl
= n
->rtl
;
1327 new_node
->master_clone
= n
->master_clone
;
1328 new_node
->count
= count
;
1331 if (new_node
->count
> n
->count
)
1332 count_scale
= REG_BR_PROB_BASE
;
1334 count_scale
= new_node
->count
* REG_BR_PROB_BASE
/ n
->count
;
1338 if (update_original
)
1345 for (e
= n
->callees
;e
; e
=e
->next_callee
)
1346 cgraph_clone_edge (e
, new_node
, e
->call_stmt
, count_scale
, freq
, loop_nest
,
1349 new_node
->next_clone
= n
->next_clone
;
1350 new_node
->prev_clone
= n
;
1351 n
->next_clone
= new_node
;
1352 if (new_node
->next_clone
)
1353 new_node
->next_clone
->prev_clone
= new_node
;
1355 cgraph_call_node_duplication_hooks (n
, new_node
);
1359 /* Return true if N is an master_clone, (see cgraph_master_clone). */
1362 cgraph_is_master_clone (struct cgraph_node
*n
)
1364 return (n
== cgraph_master_clone (n
));
1367 struct cgraph_node
*
1368 cgraph_master_clone (struct cgraph_node
*n
)
1370 enum availability avail
= cgraph_function_body_availability (n
);
1372 if (avail
== AVAIL_NOT_AVAILABLE
|| avail
== AVAIL_OVERWRITABLE
)
1375 if (!n
->master_clone
)
1376 n
->master_clone
= cgraph_node (n
->decl
);
1378 return n
->master_clone
;
1381 /* NODE is no longer nested function; update cgraph accordingly. */
1383 cgraph_unnest_node (struct cgraph_node
*node
)
1385 struct cgraph_node
**node2
= &node
->origin
->nested
;
1386 gcc_assert (node
->origin
);
1388 while (*node2
!= node
)
1389 node2
= &(*node2
)->next_nested
;
1390 *node2
= node
->next_nested
;
1391 node
->origin
= NULL
;
1394 /* Return function availability. See cgraph.h for description of individual
1397 cgraph_function_body_availability (struct cgraph_node
*node
)
1399 enum availability avail
;
1400 gcc_assert (cgraph_function_flags_ready
);
1401 if (!node
->analyzed
)
1402 avail
= AVAIL_NOT_AVAILABLE
;
1403 else if (node
->local
.local
)
1404 avail
= AVAIL_LOCAL
;
1405 else if (node
->local
.externally_visible
)
1406 avail
= AVAIL_AVAILABLE
;
1408 /* If the function can be overwritten, return OVERWRITABLE. Take
1409 care at least of two notable extensions - the COMDAT functions
1410 used to share template instantiations in C++ (this is symmetric
1411 to code cp_cannot_inline_tree_fn and probably shall be shared and
1412 the inlinability hooks completely eliminated).
1414 ??? Does the C++ one definition rule allow us to always return
1415 AVAIL_AVAILABLE here? That would be good reason to preserve this
1416 hook Similarly deal with extern inline functions - this is again
1417 necessary to get C++ shared functions having keyed templates
1418 right and in the C extension documentation we probably should
1419 document the requirement of both versions of function (extern
1420 inline and offline) having same side effect characteristics as
1421 good optimization is what this optimization is about. */
1423 else if (!(*targetm
.binds_local_p
) (node
->decl
)
1424 && !DECL_COMDAT (node
->decl
) && !DECL_EXTERNAL (node
->decl
))
1425 avail
= AVAIL_OVERWRITABLE
;
1426 else avail
= AVAIL_AVAILABLE
;
1431 /* Add the function FNDECL to the call graph.
1432 Unlike cgraph_finalize_function, this function is intended to be used
1433 by middle end and allows insertion of new function at arbitrary point
1434 of compilation. The function can be either in high, low or SSA form
1437 The function is assumed to be reachable and have address taken (so no
1438 API breaking optimizations are performed on it).
1440 Main work done by this function is to enqueue the function for later
1441 processing to avoid need the passes to be re-entrant. */
1444 cgraph_add_new_function (tree fndecl
, bool lowered
)
1446 struct cgraph_node
*node
;
1447 switch (cgraph_state
)
1449 case CGRAPH_STATE_CONSTRUCTION
:
1450 /* Just enqueue function to be processed at nearest occurrence. */
1451 node
= cgraph_node (fndecl
);
1452 node
->next_needed
= cgraph_new_nodes
;
1454 node
->lowered
= true;
1455 cgraph_new_nodes
= node
;
1458 case CGRAPH_STATE_IPA
:
1459 case CGRAPH_STATE_IPA_SSA
:
1460 case CGRAPH_STATE_EXPANSION
:
1461 /* Bring the function into finalized state and enqueue for later
1462 analyzing and compilation. */
1463 node
= cgraph_node (fndecl
);
1464 node
->local
.local
= false;
1465 node
->local
.finalized
= true;
1466 node
->reachable
= node
->needed
= true;
1467 if (!lowered
&& cgraph_state
== CGRAPH_STATE_EXPANSION
)
1469 push_cfun (DECL_STRUCT_FUNCTION (fndecl
));
1470 current_function_decl
= fndecl
;
1471 gimple_register_cfg_hooks ();
1472 tree_lowering_passes (fndecl
);
1473 bitmap_obstack_initialize (NULL
);
1474 if (!gimple_in_ssa_p (DECL_STRUCT_FUNCTION (fndecl
)))
1475 execute_pass_list (pass_early_local_passes
.pass
.sub
);
1476 bitmap_obstack_release (NULL
);
1478 current_function_decl
= NULL
;
1483 node
->lowered
= true;
1484 node
->next_needed
= cgraph_new_nodes
;
1485 cgraph_new_nodes
= node
;
1488 case CGRAPH_STATE_FINISHED
:
1489 /* At the very end of compilation we have to do all the work up
1491 push_cfun (DECL_STRUCT_FUNCTION (fndecl
));
1492 current_function_decl
= fndecl
;
1493 gimple_register_cfg_hooks ();
1495 tree_lowering_passes (fndecl
);
1496 bitmap_obstack_initialize (NULL
);
1497 if (!gimple_in_ssa_p (DECL_STRUCT_FUNCTION (fndecl
)))
1498 execute_pass_list (pass_early_local_passes
.pass
.sub
);
1499 bitmap_obstack_release (NULL
);
1500 tree_rest_of_compilation (fndecl
);
1502 current_function_decl
= NULL
;
1507 #include "gt-cgraph.h"