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"
84 #include "tree-gimple.h"
85 #include "tree-dump.h"
86 #include "tree-flow.h"
88 static void cgraph_node_remove_callers (struct cgraph_node
*node
);
89 static inline void cgraph_edge_remove_caller (struct cgraph_edge
*e
);
90 static inline void cgraph_edge_remove_callee (struct cgraph_edge
*e
);
92 /* Hash table used to convert declarations into nodes. */
93 static GTY((param_is (struct cgraph_node
))) htab_t cgraph_hash
;
94 /* Hash table used to convert assembler names into nodes. */
95 static GTY((param_is (struct cgraph_node
))) htab_t assembler_name_hash
;
97 /* The linked list of cgraph nodes. */
98 struct cgraph_node
*cgraph_nodes
;
100 /* Queue of cgraph nodes scheduled to be lowered. */
101 struct cgraph_node
*cgraph_nodes_queue
;
103 /* Queue of cgraph nodes scheduled to be added into cgraph. This is a
104 secondary queue used during optimization to accommodate passes that
105 may generate new functions that need to be optimized and expanded. */
106 struct cgraph_node
*cgraph_new_nodes
;
108 /* Number of nodes in existence. */
111 /* Maximal uid used in cgraph nodes. */
114 /* Maximal uid used in cgraph edges. */
115 int cgraph_edge_max_uid
;
117 /* Maximal pid used for profiling */
120 /* Set when whole unit has been analyzed so we can access global info. */
121 bool cgraph_global_info_ready
= false;
123 /* What state callgraph is in right now. */
124 enum cgraph_state cgraph_state
= CGRAPH_STATE_CONSTRUCTION
;
126 /* Set when the cgraph is fully build and the basic flags are computed. */
127 bool cgraph_function_flags_ready
= false;
129 /* Linked list of cgraph asm nodes. */
130 struct cgraph_asm_node
*cgraph_asm_nodes
;
132 /* Last node in cgraph_asm_nodes. */
133 static GTY(()) struct cgraph_asm_node
*cgraph_asm_last_node
;
135 /* The order index of the next cgraph node to be created. This is
136 used so that we can sort the cgraph nodes in order by when we saw
137 them, to support -fno-toplevel-reorder. */
140 /* List of hooks trigerred on cgraph_edge events. */
141 struct cgraph_edge_hook_list
{
142 cgraph_edge_hook hook
;
144 struct cgraph_edge_hook_list
*next
;
147 /* List of hooks trigerred on cgraph_node events. */
148 struct cgraph_node_hook_list
{
149 cgraph_node_hook hook
;
151 struct cgraph_node_hook_list
*next
;
154 /* List of hooks trigerred on events involving two cgraph_edges. */
155 struct cgraph_2edge_hook_list
{
156 cgraph_2edge_hook hook
;
158 struct cgraph_2edge_hook_list
*next
;
161 /* List of hooks trigerred on events involving two cgraph_nodes. */
162 struct cgraph_2node_hook_list
{
163 cgraph_2node_hook hook
;
165 struct cgraph_2node_hook_list
*next
;
168 /* List of hooks triggered when an edge is removed. */
169 struct cgraph_edge_hook_list
*first_cgraph_edge_removal_hook
;
170 /* List of hooks triggered when a node is removed. */
171 struct cgraph_node_hook_list
*first_cgraph_node_removal_hook
;
172 /* List of hooks triggered when an edge is duplicated. */
173 struct cgraph_2edge_hook_list
*first_cgraph_edge_duplicated_hook
;
174 /* List of hooks triggered when a node is duplicated. */
175 struct cgraph_2node_hook_list
*first_cgraph_node_duplicated_hook
;
178 /* Register HOOK to be called with DATA on each removed edge. */
179 struct cgraph_edge_hook_list
*
180 cgraph_add_edge_removal_hook (cgraph_edge_hook hook
, void *data
)
182 struct cgraph_edge_hook_list
*entry
;
183 struct cgraph_edge_hook_list
**ptr
= &first_cgraph_edge_removal_hook
;
185 entry
= (struct cgraph_edge_hook_list
*) xmalloc (sizeof (*entry
));
195 /* Remove ENTRY from the list of hooks called on removing edges. */
197 cgraph_remove_edge_removal_hook (struct cgraph_edge_hook_list
*entry
)
199 struct cgraph_edge_hook_list
**ptr
= &first_cgraph_edge_removal_hook
;
201 while (*ptr
!= entry
)
206 /* Call all edge removal hooks. */
208 cgraph_call_edge_removal_hooks (struct cgraph_edge
*e
)
210 struct cgraph_edge_hook_list
*entry
= first_cgraph_edge_removal_hook
;
213 entry
->hook (e
, entry
->data
);
218 /* Register HOOK to be called with DATA on each removed node. */
219 struct cgraph_node_hook_list
*
220 cgraph_add_node_removal_hook (cgraph_node_hook hook
, void *data
)
222 struct cgraph_node_hook_list
*entry
;
223 struct cgraph_node_hook_list
**ptr
= &first_cgraph_node_removal_hook
;
225 entry
= (struct cgraph_node_hook_list
*) xmalloc (sizeof (*entry
));
235 /* Remove ENTRY from the list of hooks called on removing nodes. */
237 cgraph_remove_node_removal_hook (struct cgraph_node_hook_list
*entry
)
239 struct cgraph_node_hook_list
**ptr
= &first_cgraph_node_removal_hook
;
241 while (*ptr
!= entry
)
246 /* Call all node removal hooks. */
248 cgraph_call_node_removal_hooks (struct cgraph_node
*node
)
250 struct cgraph_node_hook_list
*entry
= first_cgraph_node_removal_hook
;
253 entry
->hook (node
, entry
->data
);
258 /* Register HOOK to be called with DATA on each duplicated edge. */
259 struct cgraph_2edge_hook_list
*
260 cgraph_add_edge_duplication_hook (cgraph_2edge_hook hook
, void *data
)
262 struct cgraph_2edge_hook_list
*entry
;
263 struct cgraph_2edge_hook_list
**ptr
= &first_cgraph_edge_duplicated_hook
;
265 entry
= (struct cgraph_2edge_hook_list
*) xmalloc (sizeof (*entry
));
275 /* Remove ENTRY from the list of hooks called on duplicating edges. */
277 cgraph_remove_edge_duplication_hook (struct cgraph_2edge_hook_list
*entry
)
279 struct cgraph_2edge_hook_list
**ptr
= &first_cgraph_edge_duplicated_hook
;
281 while (*ptr
!= entry
)
286 /* Call all edge duplication hooks. */
288 cgraph_call_edge_duplication_hooks (struct cgraph_edge
*cs1
,
289 struct cgraph_edge
*cs2
)
291 struct cgraph_2edge_hook_list
*entry
= first_cgraph_edge_duplicated_hook
;
294 entry
->hook (cs1
, cs2
, entry
->data
);
299 /* Register HOOK to be called with DATA on each duplicated node. */
300 struct cgraph_2node_hook_list
*
301 cgraph_add_node_duplication_hook (cgraph_2node_hook hook
, void *data
)
303 struct cgraph_2node_hook_list
*entry
;
304 struct cgraph_2node_hook_list
**ptr
= &first_cgraph_node_duplicated_hook
;
306 entry
= (struct cgraph_2node_hook_list
*) xmalloc (sizeof (*entry
));
316 /* Remove ENTRY from the list of hooks called on duplicating nodes. */
318 cgraph_remove_node_duplication_hook (struct cgraph_2node_hook_list
*entry
)
320 struct cgraph_2node_hook_list
**ptr
= &first_cgraph_node_duplicated_hook
;
322 while (*ptr
!= entry
)
327 /* Call all node duplication hooks. */
329 cgraph_call_node_duplication_hooks (struct cgraph_node
*node1
,
330 struct cgraph_node
*node2
)
332 struct cgraph_2node_hook_list
*entry
= first_cgraph_node_duplicated_hook
;
335 entry
->hook (node1
, node2
, entry
->data
);
340 /* Returns a hash code for P. */
343 hash_node (const void *p
)
345 const struct cgraph_node
*n
= (const struct cgraph_node
*) p
;
346 return (hashval_t
) DECL_UID (n
->decl
);
349 /* Returns nonzero if P1 and P2 are equal. */
352 eq_node (const void *p1
, const void *p2
)
354 const struct cgraph_node
*n1
= (const struct cgraph_node
*) p1
;
355 const struct cgraph_node
*n2
= (const struct cgraph_node
*) p2
;
356 return DECL_UID (n1
->decl
) == DECL_UID (n2
->decl
);
359 /* Allocate new callgraph node and insert it into basic data structures. */
361 static struct cgraph_node
*
362 cgraph_create_node (void)
364 struct cgraph_node
*node
;
366 node
= GGC_CNEW (struct cgraph_node
);
367 node
->next
= cgraph_nodes
;
368 node
->uid
= cgraph_max_uid
++;
370 node
->order
= cgraph_order
++;
372 cgraph_nodes
->previous
= node
;
373 node
->previous
= NULL
;
374 node
->global
.estimated_growth
= INT_MIN
;
380 /* Return cgraph node assigned to DECL. Create new one when needed. */
383 cgraph_node (tree decl
)
385 struct cgraph_node key
, *node
, **slot
;
387 gcc_assert (TREE_CODE (decl
) == FUNCTION_DECL
);
390 cgraph_hash
= htab_create_ggc (10, hash_node
, eq_node
, NULL
);
394 slot
= (struct cgraph_node
**) htab_find_slot (cgraph_hash
, &key
, INSERT
);
399 if (!node
->master_clone
)
400 node
->master_clone
= node
;
404 node
= cgraph_create_node ();
407 if (DECL_CONTEXT (decl
) && TREE_CODE (DECL_CONTEXT (decl
)) == FUNCTION_DECL
)
409 node
->origin
= cgraph_node (DECL_CONTEXT (decl
));
410 node
->next_nested
= node
->origin
->nested
;
411 node
->origin
->nested
= node
;
412 node
->master_clone
= node
;
415 /* This code can go away once flag_unit_at_a_mode is removed. */
416 if (assembler_name_hash
)
418 tree name
= DECL_ASSEMBLER_NAME (node
->decl
);
419 slot
= ((struct cgraph_node
**)
420 htab_find_slot_with_hash (assembler_name_hash
, name
,
421 decl_assembler_name_hash (name
),
429 /* Insert already constructed node into hashtable. */
432 cgraph_insert_node_to_hashtable (struct cgraph_node
*node
)
434 struct cgraph_node
**slot
;
436 slot
= (struct cgraph_node
**) htab_find_slot (cgraph_hash
, node
, INSERT
);
442 /* Returns a hash code for P. */
445 hash_node_by_assembler_name (const void *p
)
447 const struct cgraph_node
*n
= (const struct cgraph_node
*) p
;
448 return (hashval_t
) decl_assembler_name_hash (DECL_ASSEMBLER_NAME (n
->decl
));
451 /* Returns nonzero if P1 and P2 are equal. */
454 eq_assembler_name (const void *p1
, const void *p2
)
456 const struct cgraph_node
*n1
= (const struct cgraph_node
*) p1
;
457 const_tree name
= (const_tree
)p2
;
458 return (decl_assembler_name_equal (n1
->decl
, name
));
461 /* Return the cgraph node that has ASMNAME for its DECL_ASSEMBLER_NAME.
462 Return NULL if there's no such node. */
465 cgraph_node_for_asm (tree asmname
)
467 struct cgraph_node
*node
;
470 if (!assembler_name_hash
)
472 assembler_name_hash
=
473 htab_create_ggc (10, hash_node_by_assembler_name
, eq_assembler_name
,
475 for (node
= cgraph_nodes
; node
; node
= node
->next
)
476 if (!node
->global
.inlined_to
)
478 tree name
= DECL_ASSEMBLER_NAME (node
->decl
);
479 slot
= htab_find_slot_with_hash (assembler_name_hash
, name
,
480 decl_assembler_name_hash (name
),
482 /* We can have multiple declarations with same assembler name. For C++
483 it is __builtin_strlen and strlen, for instance. Do we need to
484 record them all? Original implementation marked just first one
485 so lets hope for the best. */
492 slot
= htab_find_slot_with_hash (assembler_name_hash
, asmname
,
493 decl_assembler_name_hash (asmname
),
497 return (struct cgraph_node
*) *slot
;
501 /* Returns a hash value for X (which really is a die_struct). */
504 edge_hash (const void *x
)
506 return htab_hash_pointer (((const struct cgraph_edge
*) x
)->call_stmt
);
509 /* Return nonzero if decl_id of die_struct X is the same as UID of decl *Y. */
512 edge_eq (const void *x
, const void *y
)
514 return ((const struct cgraph_edge
*) x
)->call_stmt
== y
;
517 /* Return callgraph edge representing CALL_EXPR statement. */
519 cgraph_edge (struct cgraph_node
*node
, tree call_stmt
)
521 struct cgraph_edge
*e
, *e2
;
524 if (node
->call_site_hash
)
525 return (struct cgraph_edge
*)
526 htab_find_with_hash (node
->call_site_hash
, call_stmt
,
527 htab_hash_pointer (call_stmt
));
529 /* This loop may turn out to be performance problem. In such case adding
530 hashtables into call nodes with very many edges is probably best
531 solution. It is not good idea to add pointer into CALL_EXPR itself
532 because we want to make possible having multiple cgraph nodes representing
533 different clones of the same body before the body is actually cloned. */
534 for (e
= node
->callees
; e
; e
= e
->next_callee
)
536 if (e
->call_stmt
== call_stmt
)
542 node
->call_site_hash
= htab_create_ggc (120, edge_hash
, edge_eq
, NULL
);
543 for (e2
= node
->callees
; e2
; e2
= e2
->next_callee
)
546 slot
= htab_find_slot_with_hash (node
->call_site_hash
,
548 htab_hash_pointer (e2
->call_stmt
),
557 /* Change call_stmt of edge E to NEW_STMT. */
560 cgraph_set_call_stmt (struct cgraph_edge
*e
, tree new_stmt
)
562 if (e
->caller
->call_site_hash
)
564 htab_remove_elt_with_hash (e
->caller
->call_site_hash
,
566 htab_hash_pointer (e
->call_stmt
));
568 e
->call_stmt
= new_stmt
;
569 if (e
->caller
->call_site_hash
)
572 slot
= htab_find_slot_with_hash (e
->caller
->call_site_hash
,
575 (e
->call_stmt
), INSERT
);
581 /* Create edge from CALLER to CALLEE in the cgraph. */
584 cgraph_create_edge (struct cgraph_node
*caller
, struct cgraph_node
*callee
,
585 tree call_stmt
, gcov_type count
, int freq
, int nest
)
587 struct cgraph_edge
*edge
= GGC_NEW (struct cgraph_edge
);
588 #ifdef ENABLE_CHECKING
589 struct cgraph_edge
*e
;
591 for (e
= caller
->callees
; e
; e
= e
->next_callee
)
592 gcc_assert (e
->call_stmt
!= call_stmt
);
595 gcc_assert (get_call_expr_in (call_stmt
));
597 if (!DECL_SAVED_TREE (callee
->decl
))
598 edge
->inline_failed
= N_("function body not available");
599 else if (callee
->local
.redefined_extern_inline
)
600 edge
->inline_failed
= N_("redefined extern inline functions are not "
601 "considered for inlining");
602 else if (callee
->local
.inlinable
)
603 edge
->inline_failed
= N_("function not considered for inlining");
605 edge
->inline_failed
= N_("function not inlinable");
609 edge
->caller
= caller
;
610 edge
->callee
= callee
;
611 edge
->call_stmt
= call_stmt
;
612 edge
->prev_caller
= NULL
;
613 edge
->next_caller
= callee
->callers
;
615 callee
->callers
->prev_caller
= edge
;
616 edge
->prev_callee
= NULL
;
617 edge
->next_callee
= caller
->callees
;
619 caller
->callees
->prev_callee
= edge
;
620 caller
->callees
= edge
;
621 callee
->callers
= edge
;
623 gcc_assert (count
>= 0);
624 edge
->frequency
= freq
;
625 gcc_assert (freq
>= 0);
626 gcc_assert (freq
<= CGRAPH_FREQ_MAX
);
627 edge
->loop_nest
= nest
;
628 edge
->uid
= cgraph_edge_max_uid
++;
629 if (caller
->call_site_hash
)
632 slot
= htab_find_slot_with_hash (caller
->call_site_hash
,
643 /* Remove the edge E from the list of the callers of the callee. */
646 cgraph_edge_remove_callee (struct cgraph_edge
*e
)
649 e
->prev_caller
->next_caller
= e
->next_caller
;
651 e
->next_caller
->prev_caller
= e
->prev_caller
;
653 e
->callee
->callers
= e
->next_caller
;
656 /* Remove the edge E from the list of the callees of the caller. */
659 cgraph_edge_remove_caller (struct cgraph_edge
*e
)
662 e
->prev_callee
->next_callee
= e
->next_callee
;
664 e
->next_callee
->prev_callee
= e
->prev_callee
;
666 e
->caller
->callees
= e
->next_callee
;
667 if (e
->caller
->call_site_hash
)
668 htab_remove_elt_with_hash (e
->caller
->call_site_hash
,
670 htab_hash_pointer (e
->call_stmt
));
673 /* Remove the edge E in the cgraph. */
676 cgraph_remove_edge (struct cgraph_edge
*e
)
678 cgraph_call_edge_removal_hooks (e
);
679 /* Remove from callers list of the callee. */
680 cgraph_edge_remove_callee (e
);
682 /* Remove from callees list of the callers. */
683 cgraph_edge_remove_caller (e
);
686 /* Redirect callee of E to N. The function does not update underlying
690 cgraph_redirect_edge_callee (struct cgraph_edge
*e
, struct cgraph_node
*n
)
692 /* Remove from callers list of the current callee. */
693 cgraph_edge_remove_callee (e
);
695 /* Insert to callers list of the new callee. */
696 e
->prev_caller
= NULL
;
698 n
->callers
->prev_caller
= e
;
699 e
->next_caller
= n
->callers
;
704 /* Update or remove corresponding cgraph edge if a call OLD_CALL
705 in OLD_STMT changed into NEW_STMT. */
708 cgraph_update_edges_for_call_stmt (tree old_stmt
, tree old_call
,
711 tree new_call
= get_call_expr_in (new_stmt
);
712 struct cgraph_node
*node
= cgraph_node (cfun
->decl
);
714 if (old_call
!= new_call
)
716 struct cgraph_edge
*e
= cgraph_edge (node
, old_stmt
);
717 struct cgraph_edge
*ne
= NULL
;
722 gcov_type count
= e
->count
;
723 int frequency
= e
->frequency
;
724 int loop_nest
= e
->loop_nest
;
726 cgraph_remove_edge (e
);
729 new_decl
= get_callee_fndecl (new_call
);
732 ne
= cgraph_create_edge (node
, cgraph_node (new_decl
),
733 new_stmt
, count
, frequency
,
735 gcc_assert (ne
->inline_failed
);
740 else if (old_stmt
!= new_stmt
)
742 struct cgraph_edge
*e
= cgraph_edge (node
, old_stmt
);
745 cgraph_set_call_stmt (e
, new_stmt
);
749 /* Remove all callees from the node. */
752 cgraph_node_remove_callees (struct cgraph_node
*node
)
754 struct cgraph_edge
*e
;
756 /* It is sufficient to remove the edges from the lists of callers of
757 the callees. The callee list of the node can be zapped with one
759 for (e
= node
->callees
; e
; e
= e
->next_callee
)
761 cgraph_call_edge_removal_hooks (e
);
762 cgraph_edge_remove_callee (e
);
764 node
->callees
= NULL
;
765 if (node
->call_site_hash
)
767 htab_delete (node
->call_site_hash
);
768 node
->call_site_hash
= NULL
;
772 /* Remove all callers from the node. */
775 cgraph_node_remove_callers (struct cgraph_node
*node
)
777 struct cgraph_edge
*e
;
779 /* It is sufficient to remove the edges from the lists of callees of
780 the callers. The caller list of the node can be zapped with one
782 for (e
= node
->callers
; e
; e
= e
->next_caller
)
784 cgraph_call_edge_removal_hooks (e
);
785 cgraph_edge_remove_caller (e
);
787 node
->callers
= NULL
;
790 /* Release memory used to represent body of function NODE. */
793 cgraph_release_function_body (struct cgraph_node
*node
)
795 if (DECL_STRUCT_FUNCTION (node
->decl
)
796 && DECL_STRUCT_FUNCTION (node
->decl
)->gimple_df
)
798 tree old_decl
= current_function_decl
;
799 push_cfun (DECL_STRUCT_FUNCTION (node
->decl
));
800 current_function_decl
= node
->decl
;
802 delete_tree_cfg_annotations ();
804 current_function_decl
= old_decl
;
807 DECL_SAVED_TREE (node
->decl
) = NULL
;
808 DECL_STRUCT_FUNCTION (node
->decl
) = NULL
;
809 DECL_INITIAL (node
->decl
) = error_mark_node
;
812 /* Remove the node from cgraph. */
815 cgraph_remove_node (struct cgraph_node
*node
)
818 bool kill_body
= false;
820 cgraph_call_node_removal_hooks (node
);
821 cgraph_node_remove_callers (node
);
822 cgraph_node_remove_callees (node
);
824 /* Incremental inlining access removed nodes stored in the postorder list.
826 node
->needed
= node
->reachable
= false;
828 cgraph_remove_node (node
->nested
);
831 struct cgraph_node
**node2
= &node
->origin
->nested
;
833 while (*node2
!= node
)
834 node2
= &(*node2
)->next_nested
;
835 *node2
= node
->next_nested
;
838 node
->previous
->next
= node
->next
;
840 cgraph_nodes
= node
->next
;
842 node
->next
->previous
= node
->previous
;
844 node
->previous
= NULL
;
845 slot
= htab_find_slot (cgraph_hash
, node
, NO_INSERT
);
848 if (node
->next_clone
)
850 struct cgraph_node
*new_node
= node
->next_clone
;
851 struct cgraph_node
*n
;
853 /* Make the next clone be the master clone */
854 for (n
= new_node
; n
; n
= n
->next_clone
)
855 n
->master_clone
= new_node
;
858 node
->next_clone
->prev_clone
= NULL
;
862 htab_clear_slot (cgraph_hash
, slot
);
868 node
->prev_clone
->next_clone
= node
->next_clone
;
869 if (node
->next_clone
)
870 node
->next_clone
->prev_clone
= node
->prev_clone
;
873 /* While all the clones are removed after being proceeded, the function
874 itself is kept in the cgraph even after it is compiled. Check whether
875 we are done with this body and reclaim it proactively if this is the case.
877 if (!kill_body
&& *slot
)
879 struct cgraph_node
*n
= (struct cgraph_node
*) *slot
;
880 if (!n
->next_clone
&& !n
->global
.inlined_to
881 && (cgraph_global_info_ready
882 && (TREE_ASM_WRITTEN (n
->decl
) || DECL_EXTERNAL (n
->decl
))))
885 if (assembler_name_hash
)
887 tree name
= DECL_ASSEMBLER_NAME (node
->decl
);
888 slot
= htab_find_slot_with_hash (assembler_name_hash
, name
,
889 decl_assembler_name_hash (name
),
891 /* Inline clones are not hashed. */
892 if (slot
&& *slot
== node
)
893 htab_clear_slot (assembler_name_hash
, slot
);
896 if (kill_body
&& flag_unit_at_a_time
)
897 cgraph_release_function_body (node
);
899 if (node
->call_site_hash
)
901 htab_delete (node
->call_site_hash
);
902 node
->call_site_hash
= NULL
;
905 /* Do not free the structure itself so the walk over chain can continue. */
908 /* Notify finalize_compilation_unit that given node is reachable. */
911 cgraph_mark_reachable_node (struct cgraph_node
*node
)
913 if (!node
->reachable
&& node
->local
.finalized
)
915 notice_global_symbol (node
->decl
);
917 gcc_assert (!cgraph_global_info_ready
);
919 node
->next_needed
= cgraph_nodes_queue
;
920 cgraph_nodes_queue
= node
;
924 /* Likewise indicate that a node is needed, i.e. reachable via some
928 cgraph_mark_needed_node (struct cgraph_node
*node
)
931 cgraph_mark_reachable_node (node
);
934 /* Return local info for the compiled function. */
936 struct cgraph_local_info
*
937 cgraph_local_info (tree decl
)
939 struct cgraph_node
*node
;
941 gcc_assert (TREE_CODE (decl
) == FUNCTION_DECL
);
942 node
= cgraph_node (decl
);
946 /* Return local info for the compiled function. */
948 struct cgraph_global_info
*
949 cgraph_global_info (tree decl
)
951 struct cgraph_node
*node
;
953 gcc_assert (TREE_CODE (decl
) == FUNCTION_DECL
&& cgraph_global_info_ready
);
954 node
= cgraph_node (decl
);
955 return &node
->global
;
958 /* Return local info for the compiled function. */
960 struct cgraph_rtl_info
*
961 cgraph_rtl_info (tree decl
)
963 struct cgraph_node
*node
;
965 gcc_assert (TREE_CODE (decl
) == FUNCTION_DECL
);
966 node
= cgraph_node (decl
);
967 if (decl
!= current_function_decl
968 && !TREE_ASM_WRITTEN (node
->decl
))
973 /* Return name of the node used in debug output. */
975 cgraph_node_name (struct cgraph_node
*node
)
977 return lang_hooks
.decl_printable_name (node
->decl
, 2);
980 /* Names used to print out the availability enum. */
981 const char * const cgraph_availability_names
[] =
982 {"unset", "not_available", "overwritable", "available", "local"};
985 /* Dump call graph node NODE to file F. */
988 dump_cgraph_node (FILE *f
, struct cgraph_node
*node
)
990 struct cgraph_edge
*edge
;
991 fprintf (f
, "%s/%i(%i):", cgraph_node_name (node
), node
->uid
, node
->pid
);
992 if (node
->global
.inlined_to
)
993 fprintf (f
, " (inline copy in %s/%i)",
994 cgraph_node_name (node
->global
.inlined_to
),
995 node
->global
.inlined_to
->uid
);
996 if (cgraph_function_flags_ready
)
997 fprintf (f
, " availability:%s",
998 cgraph_availability_names
[cgraph_function_body_availability (node
)]);
999 if (node
->master_clone
&& node
->master_clone
->uid
!= node
->uid
)
1000 fprintf (f
, "(%i)", node
->master_clone
->uid
);
1002 fprintf (f
, " executed "HOST_WIDEST_INT_PRINT_DEC
"x",
1003 (HOST_WIDEST_INT
)node
->count
);
1004 if (node
->local
.inline_summary
.self_insns
)
1005 fprintf (f
, " %i insns", node
->local
.inline_summary
.self_insns
);
1006 if (node
->global
.insns
&& node
->global
.insns
1007 != node
->local
.inline_summary
.self_insns
)
1008 fprintf (f
, " (%i after inlining)", node
->global
.insns
);
1009 if (node
->local
.inline_summary
.estimated_self_stack_size
)
1010 fprintf (f
, " %i bytes stack usage", (int)node
->local
.inline_summary
.estimated_self_stack_size
);
1011 if (node
->global
.estimated_stack_size
!= node
->local
.inline_summary
.estimated_self_stack_size
)
1012 fprintf (f
, " %i bytes after inlining", (int)node
->global
.estimated_stack_size
);
1014 fprintf (f
, " nested in: %s", cgraph_node_name (node
->origin
));
1016 fprintf (f
, " needed");
1017 else if (node
->reachable
)
1018 fprintf (f
, " reachable");
1019 if (DECL_SAVED_TREE (node
->decl
))
1020 fprintf (f
, " tree");
1022 fprintf (f
, " output");
1023 if (node
->local
.local
)
1024 fprintf (f
, " local");
1025 if (node
->local
.externally_visible
)
1026 fprintf (f
, " externally_visible");
1027 if (node
->local
.finalized
)
1028 fprintf (f
, " finalized");
1029 if (node
->local
.disregard_inline_limits
)
1030 fprintf (f
, " always_inline");
1031 else if (node
->local
.inlinable
)
1032 fprintf (f
, " inlinable");
1033 if (node
->local
.redefined_extern_inline
)
1034 fprintf (f
, " redefined_extern_inline");
1035 if (TREE_ASM_WRITTEN (node
->decl
))
1036 fprintf (f
, " asm_written");
1038 fprintf (f
, "\n called by: ");
1039 for (edge
= node
->callers
; edge
; edge
= edge
->next_caller
)
1041 fprintf (f
, "%s/%i ", cgraph_node_name (edge
->caller
),
1044 fprintf (f
, "("HOST_WIDEST_INT_PRINT_DEC
"x) ",
1045 (HOST_WIDEST_INT
)edge
->count
);
1046 if (edge
->frequency
)
1047 fprintf (f
, "(%.2f per call) ",
1048 edge
->frequency
/ (double)CGRAPH_FREQ_BASE
);
1049 if (!edge
->inline_failed
)
1050 fprintf(f
, "(inlined) ");
1053 fprintf (f
, "\n calls: ");
1054 for (edge
= node
->callees
; edge
; edge
= edge
->next_callee
)
1056 fprintf (f
, "%s/%i ", cgraph_node_name (edge
->callee
),
1058 if (!edge
->inline_failed
)
1059 fprintf(f
, "(inlined) ");
1061 fprintf (f
, "("HOST_WIDEST_INT_PRINT_DEC
"x) ",
1062 (HOST_WIDEST_INT
)edge
->count
);
1063 if (edge
->frequency
)
1064 fprintf (f
, "(%.2f per call) ",
1065 edge
->frequency
/ (double)CGRAPH_FREQ_BASE
);
1066 if (edge
->loop_nest
)
1067 fprintf (f
, "(nested in %i loops) ", edge
->loop_nest
);
1073 /* Dump call graph node NODE to stderr. */
1076 debug_cgraph_node (struct cgraph_node
*node
)
1078 dump_cgraph_node (stderr
, node
);
1082 /* Dump the callgraph to file F. */
1085 dump_cgraph (FILE *f
)
1087 struct cgraph_node
*node
;
1089 fprintf (f
, "callgraph:\n\n");
1090 for (node
= cgraph_nodes
; node
; node
= node
->next
)
1091 dump_cgraph_node (f
, node
);
1095 /* Dump the call graph to stderr. */
1100 dump_cgraph (stderr
);
1104 /* Set the DECL_ASSEMBLER_NAME and update cgraph hashtables. */
1107 change_decl_assembler_name (tree decl
, tree name
)
1109 gcc_assert (!assembler_name_hash
);
1110 if (!DECL_ASSEMBLER_NAME_SET_P (decl
))
1112 SET_DECL_ASSEMBLER_NAME (decl
, name
);
1115 if (name
== DECL_ASSEMBLER_NAME (decl
))
1118 if (TREE_SYMBOL_REFERENCED (DECL_ASSEMBLER_NAME (decl
))
1119 && DECL_RTL_SET_P (decl
))
1120 warning (0, "%D renamed after being referenced in assembly", decl
);
1122 SET_DECL_ASSEMBLER_NAME (decl
, name
);
1125 /* Add a top-level asm statement to the list. */
1127 struct cgraph_asm_node
*
1128 cgraph_add_asm_node (tree asm_str
)
1130 struct cgraph_asm_node
*node
;
1132 node
= GGC_CNEW (struct cgraph_asm_node
);
1133 node
->asm_str
= asm_str
;
1134 node
->order
= cgraph_order
++;
1136 if (cgraph_asm_nodes
== NULL
)
1137 cgraph_asm_nodes
= node
;
1139 cgraph_asm_last_node
->next
= node
;
1140 cgraph_asm_last_node
= node
;
1144 /* Return true when the DECL can possibly be inlined. */
1146 cgraph_function_possibly_inlined_p (tree decl
)
1148 if (!cgraph_global_info_ready
)
1149 return (DECL_INLINE (decl
) && !flag_really_no_inline
);
1150 return DECL_POSSIBLY_INLINED (decl
);
1153 /* Create clone of E in the node N represented by CALL_EXPR the callgraph. */
1154 struct cgraph_edge
*
1155 cgraph_clone_edge (struct cgraph_edge
*e
, struct cgraph_node
*n
,
1156 tree call_stmt
, gcov_type count_scale
, int freq_scale
,
1157 int loop_nest
, bool update_original
)
1159 struct cgraph_edge
*new;
1160 gcov_type count
= e
->count
* count_scale
/ REG_BR_PROB_BASE
;
1161 gcov_type freq
= e
->frequency
* (gcov_type
) freq_scale
/ CGRAPH_FREQ_BASE
;
1163 if (freq
> CGRAPH_FREQ_MAX
)
1164 freq
= CGRAPH_FREQ_MAX
;
1165 new = cgraph_create_edge (n
, e
->callee
, call_stmt
, count
, freq
,
1166 e
->loop_nest
+ loop_nest
);
1168 new->inline_failed
= e
->inline_failed
;
1169 if (update_original
)
1171 e
->count
-= new->count
;
1175 cgraph_call_edge_duplication_hooks (e
, new);
1179 /* Create node representing clone of N executed COUNT times. Decrease
1180 the execution counts from original node too.
1182 When UPDATE_ORIGINAL is true, the counts are subtracted from the original
1183 function's profile to reflect the fact that part of execution is handled
1185 struct cgraph_node
*
1186 cgraph_clone_node (struct cgraph_node
*n
, gcov_type count
, int freq
, int loop_nest
,
1187 bool update_original
)
1189 struct cgraph_node
*new = cgraph_create_node ();
1190 struct cgraph_edge
*e
;
1191 gcov_type count_scale
;
1193 new->decl
= n
->decl
;
1194 new->origin
= n
->origin
;
1197 new->next_nested
= new->origin
->nested
;
1198 new->origin
->nested
= new;
1200 new->analyzed
= n
->analyzed
;
1201 new->local
= n
->local
;
1202 new->global
= n
->global
;
1204 new->master_clone
= n
->master_clone
;
1207 count_scale
= new->count
* REG_BR_PROB_BASE
/ n
->count
;
1210 if (update_original
)
1217 for (e
= n
->callees
;e
; e
=e
->next_callee
)
1218 cgraph_clone_edge (e
, new, e
->call_stmt
, count_scale
, freq
, loop_nest
,
1221 new->next_clone
= n
->next_clone
;
1222 new->prev_clone
= n
;
1223 n
->next_clone
= new;
1224 if (new->next_clone
)
1225 new->next_clone
->prev_clone
= new;
1227 cgraph_call_node_duplication_hooks (n
, new);
1231 /* Return true if N is an master_clone, (see cgraph_master_clone). */
1234 cgraph_is_master_clone (struct cgraph_node
*n
)
1236 return (n
== cgraph_master_clone (n
));
1239 struct cgraph_node
*
1240 cgraph_master_clone (struct cgraph_node
*n
)
1242 enum availability avail
= cgraph_function_body_availability (n
);
1244 if (avail
== AVAIL_NOT_AVAILABLE
|| avail
== AVAIL_OVERWRITABLE
)
1247 if (!n
->master_clone
)
1248 n
->master_clone
= cgraph_node (n
->decl
);
1250 return n
->master_clone
;
1253 /* NODE is no longer nested function; update cgraph accordingly. */
1255 cgraph_unnest_node (struct cgraph_node
*node
)
1257 struct cgraph_node
**node2
= &node
->origin
->nested
;
1258 gcc_assert (node
->origin
);
1260 while (*node2
!= node
)
1261 node2
= &(*node2
)->next_nested
;
1262 *node2
= node
->next_nested
;
1263 node
->origin
= NULL
;
1266 /* Return function availability. See cgraph.h for description of individual
1269 cgraph_function_body_availability (struct cgraph_node
*node
)
1271 enum availability avail
;
1272 gcc_assert (cgraph_function_flags_ready
);
1273 if (!node
->analyzed
)
1274 avail
= AVAIL_NOT_AVAILABLE
;
1275 else if (node
->local
.local
)
1276 avail
= AVAIL_LOCAL
;
1277 else if (node
->local
.externally_visible
)
1278 avail
= AVAIL_AVAILABLE
;
1280 /* If the function can be overwritten, return OVERWRITABLE. Take
1281 care at least of two notable extensions - the COMDAT functions
1282 used to share template instantiations in C++ (this is symmetric
1283 to code cp_cannot_inline_tree_fn and probably shall be shared and
1284 the inlinability hooks completely eliminated).
1286 ??? Does the C++ one definition rule allow us to always return
1287 AVAIL_AVAILABLE here? That would be good reason to preserve this
1288 hook Similarly deal with extern inline functions - this is again
1289 necessary to get C++ shared functions having keyed templates
1290 right and in the C extension documentation we probably should
1291 document the requirement of both versions of function (extern
1292 inline and offline) having same side effect characteristics as
1293 good optimization is what this optimization is about. */
1295 else if (!(*targetm
.binds_local_p
) (node
->decl
)
1296 && !DECL_COMDAT (node
->decl
) && !DECL_EXTERNAL (node
->decl
))
1297 avail
= AVAIL_OVERWRITABLE
;
1298 else avail
= AVAIL_AVAILABLE
;
1303 /* Add the function FNDECL to the call graph.
1304 Unlike cgraph_finalize_function, this function is intended to be used
1305 by middle end and allows insertion of new function at arbitrary point
1306 of compilation. The function can be either in high, low or SSA form
1309 The function is assumed to be reachable and have address taken (so no
1310 API breaking optimizations are performed on it).
1312 Main work done by this function is to enqueue the function for later
1313 processing to avoid need the passes to be re-entrant. */
1316 cgraph_add_new_function (tree fndecl
, bool lowered
)
1318 struct cgraph_node
*node
;
1319 switch (cgraph_state
)
1321 case CGRAPH_STATE_CONSTRUCTION
:
1322 /* Just enqueue function to be processed at nearest occurrence. */
1323 node
= cgraph_node (fndecl
);
1324 node
->next_needed
= cgraph_new_nodes
;
1326 node
->lowered
= true;
1327 cgraph_new_nodes
= node
;
1330 case CGRAPH_STATE_IPA
:
1331 case CGRAPH_STATE_IPA_SSA
:
1332 case CGRAPH_STATE_EXPANSION
:
1333 /* Bring the function into finalized state and enqueue for later
1334 analyzing and compilation. */
1335 node
= cgraph_node (fndecl
);
1336 node
->local
.local
= false;
1337 node
->local
.finalized
= true;
1338 node
->reachable
= node
->needed
= true;
1339 if (!lowered
&& cgraph_state
== CGRAPH_STATE_EXPANSION
)
1341 push_cfun (DECL_STRUCT_FUNCTION (fndecl
));
1342 current_function_decl
= fndecl
;
1343 tree_register_cfg_hooks ();
1344 tree_lowering_passes (fndecl
);
1345 bitmap_obstack_initialize (NULL
);
1346 if (!gimple_in_ssa_p (DECL_STRUCT_FUNCTION (fndecl
)))
1347 execute_pass_list (pass_early_local_passes
.pass
.sub
);
1348 bitmap_obstack_release (NULL
);
1350 current_function_decl
= NULL
;
1355 node
->lowered
= true;
1356 node
->next_needed
= cgraph_new_nodes
;
1357 cgraph_new_nodes
= node
;
1360 case CGRAPH_STATE_FINISHED
:
1361 /* At the very end of compilation we have to do all the work up
1363 push_cfun (DECL_STRUCT_FUNCTION (fndecl
));
1364 current_function_decl
= fndecl
;
1365 tree_register_cfg_hooks ();
1367 tree_lowering_passes (fndecl
);
1368 bitmap_obstack_initialize (NULL
);
1369 if (!gimple_in_ssa_p (DECL_STRUCT_FUNCTION (fndecl
)) && optimize
)
1370 execute_pass_list (pass_early_local_passes
.pass
.sub
);
1371 bitmap_obstack_release (NULL
);
1372 tree_rest_of_compilation (fndecl
);
1374 current_function_decl
= NULL
;
1379 #include "gt-cgraph.h"