1 /* Callgraph handling code.
2 Copyright (C) 2003, 2004, 2005, 2006, 2007, 2008, 2009
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/>. */
25 #include "basic-block.h"
29 /* Not yet set by cgraph_function_body_availability. */
31 /* Function body/variable initializer is unknown. */
33 /* Function body/variable initializer is known but might be replaced
34 by a different one from other compilation unit and thus needs to
35 be dealt with a care. Like AVAIL_NOT_AVAILABLE it can have
36 arbitrary side effects on escaping variables and functions, while
37 like AVAILABLE it might access static variables. */
39 /* Function body/variable initializer is known and will be used in final
42 /* Function body/variable initializer is known and all it's uses are explicitly
43 visible within current unit (ie it's address is never taken and it is not
44 exported to other units).
45 Currently used only for functions. */
49 extern const char * const cgraph_availability_names
[];
51 /* Function inlining information. */
53 struct GTY(()) inline_summary
55 /* Estimated stack frame consumption by the function. */
56 HOST_WIDE_INT estimated_self_stack_size
;
58 /* Size of the function body. */
60 /* How many instructions are likely going to disappear after inlining. */
61 int size_inlining_benefit
;
62 /* Estimated time spent executing the function body. */
64 /* How much time is going to be saved by inlining. */
65 int time_inlining_benefit
;
68 /* Information about the function collected locally.
69 Available after function is analyzed. */
71 struct GTY(()) cgraph_local_info
{
72 struct inline_summary inline_summary
;
74 /* Set when function function is visible in current compilation unit only
75 and its address is never taken. */
78 /* Set when function is visible by other units. */
79 unsigned externally_visible
: 1;
81 /* Set once it has been finalized so we consider it to be output. */
82 unsigned finalized
: 1;
84 /* False when there something makes inlining impossible (such as va_arg). */
85 unsigned inlinable
: 1;
87 /* True when function should be inlined independently on its size. */
88 unsigned disregard_inline_limits
: 1;
90 /* True when the function has been originally extern inline, but it is
92 unsigned redefined_extern_inline
: 1;
94 /* True if statics_read_for_function and
95 statics_written_for_function contain valid data. */
96 unsigned for_functions_valid
: 1;
98 /* True if the function is going to be emitted in some other translation
99 unit, referenced from vtable. */
100 unsigned vtable_method
: 1;
103 /* Information about the function that needs to be computed globally
104 once compilation is finished. Available only with -funit-at-a-time. */
106 struct GTY(()) cgraph_global_info
{
107 /* Estimated stack frame consumption by the function. */
108 HOST_WIDE_INT estimated_stack_size
;
109 /* Expected offset of the stack frame of inlined function. */
110 HOST_WIDE_INT stack_frame_offset
;
112 /* For inline clones this points to the function they will be
114 struct cgraph_node
*inlined_to
;
116 /* Estimated size of the function after inlining. */
120 /* Estimated growth after inlining. INT_MIN if not computed. */
121 int estimated_growth
;
123 /* Set iff the function has been inlined at least once. */
127 /* Information about the function that is propagated by the RTL backend.
128 Available only for functions that has been already assembled. */
130 struct GTY(()) cgraph_rtl_info
{
131 unsigned int preferred_incoming_stack_boundary
;
134 /* Represent which DECL tree (or reference to such tree)
135 will be replaced by another tree while versioning. */
136 struct GTY(()) ipa_replace_map
138 /* The tree that will be replaced. */
140 /* The new (replacing) tree. */
142 /* True when a substitution should be done, false otherwise. */
144 /* True when we replace a reference to old_tree. */
147 typedef struct ipa_replace_map
*ipa_replace_map_p
;
148 DEF_VEC_P(ipa_replace_map_p
);
149 DEF_VEC_ALLOC_P(ipa_replace_map_p
,gc
);
151 struct GTY(()) cgraph_clone_info
153 VEC(ipa_replace_map_p
,gc
)* tree_map
;
155 bitmap combined_args_to_skip
;
158 /* The cgraph data structure.
159 Each function decl has assigned cgraph_node listing callees and callers. */
161 struct GTY((chain_next ("%h.next"), chain_prev ("%h.previous"))) cgraph_node
{
163 struct cgraph_edge
*callees
;
164 struct cgraph_edge
*callers
;
165 struct cgraph_node
*next
;
166 struct cgraph_node
*previous
;
167 /* For nested functions points to function the node is nested in. */
168 struct cgraph_node
*origin
;
169 /* Points to first nested function, if any. */
170 struct cgraph_node
*nested
;
171 /* Pointer to the next function with same origin, if any. */
172 struct cgraph_node
*next_nested
;
173 /* Pointer to the next function in cgraph_nodes_queue. */
174 struct cgraph_node
*next_needed
;
175 /* Pointer to the next clone. */
176 struct cgraph_node
*next_sibling_clone
;
177 struct cgraph_node
*prev_sibling_clone
;
178 struct cgraph_node
*clones
;
179 struct cgraph_node
*clone_of
;
180 /* For functions with many calls sites it holds map from call expression
181 to the edge to speed up cgraph_edge function. */
182 htab_t
GTY((param_is (struct cgraph_edge
))) call_site_hash
;
184 PTR
GTY ((skip
)) aux
;
186 struct cgraph_local_info local
;
187 struct cgraph_global_info global
;
188 struct cgraph_rtl_info rtl
;
189 struct cgraph_clone_info clone
;
191 /* Expected number of executions: calculated in profile.c. */
193 /* Unique id of the node. */
195 /* Ordering of all cgraph nodes. */
198 /* unique id for profiling. pid is not suitable because of different
199 number of cfg nodes with -fprofile-generate and -fprofile-use */
202 /* Set when function must be output - it is externally visible
203 or its address is taken. */
205 /* Set when function has address taken. */
206 unsigned address_taken
: 1;
207 /* Set when decl is an abstract function pointed to by the
208 ABSTRACT_DECL_ORIGIN of a reachable function. */
209 unsigned abstract_and_needed
: 1;
210 /* Set when function is reachable by call from other function
211 that is either reachable or needed. */
212 unsigned reachable
: 1;
213 /* Set once the function is lowered (i.e. its CFG is built). */
214 unsigned lowered
: 1;
215 /* Set once the function has been instantiated and its callee
217 unsigned analyzed
: 1;
218 /* Set when function is scheduled to be processed by local passes. */
219 unsigned process
: 1;
220 /* Set for aliases once they got through assemble_alias. */
222 /* Set for nodes that was constructed and finalized by frontend. */
223 unsigned finalized_by_frontend
: 1;
226 typedef struct cgraph_node
*cgraph_node_ptr
;
228 DEF_VEC_P(cgraph_node_ptr
);
229 DEF_VEC_ALLOC_P(cgraph_node_ptr
,heap
);
230 DEF_VEC_ALLOC_P(cgraph_node_ptr
,gc
);
232 /* A cgraph node set is a collection of cgraph nodes. A cgraph node
233 can appear in multiple sets. */
234 struct GTY(()) cgraph_node_set_def
236 htab_t
GTY((param_is (struct cgraph_node_set_element_def
))) hashtab
;
237 VEC(cgraph_node_ptr
, gc
) *nodes
;
238 PTR
GTY ((skip
)) aux
;
241 typedef struct cgraph_node_set_def
*cgraph_node_set
;
243 DEF_VEC_P(cgraph_node_set
);
244 DEF_VEC_ALLOC_P(cgraph_node_set
,gc
);
245 DEF_VEC_ALLOC_P(cgraph_node_set
,heap
);
247 /* A cgraph node set element contains an index in the vector of nodes in
249 struct GTY(()) cgraph_node_set_element_def
251 struct cgraph_node
*node
;
255 typedef struct cgraph_node_set_element_def
*cgraph_node_set_element
;
256 typedef const struct cgraph_node_set_element_def
*const_cgraph_node_set_element
;
258 /* Iterator structure for cgraph node sets. */
263 } cgraph_node_set_iterator
;
265 #define DEFCIFCODE(code, string) CIF_ ## code,
266 /* Reasons for inlining failures. */
268 #include "cif-code.def"
270 } cgraph_inline_failed_t
;
272 struct GTY((chain_next ("%h.next_caller"), chain_prev ("%h.prev_caller"))) cgraph_edge
{
273 struct cgraph_node
*caller
;
274 struct cgraph_node
*callee
;
275 struct cgraph_edge
*prev_caller
;
276 struct cgraph_edge
*next_caller
;
277 struct cgraph_edge
*prev_callee
;
278 struct cgraph_edge
*next_callee
;
280 PTR
GTY ((skip (""))) aux
;
281 /* When equal to CIF_OK, inline this call. Otherwise, points to the
282 explanation why function was not inlined. */
283 cgraph_inline_failed_t inline_failed
;
284 /* Expected number of executions: calculated in profile.c. */
286 /* Expected frequency of executions within the function.
287 When set to CGRAPH_FREQ_BASE, the edge is expected to be called once
288 per function call. The range is 0 to CGRAPH_FREQ_MAX. */
290 /* Depth of loop nest, 1 means no loop nest. */
291 unsigned int loop_nest
: 30;
292 /* Whether this edge describes a call that was originally indirect. */
293 unsigned int indirect_call
: 1;
294 /* Can this call throw externally? */
295 unsigned int can_throw_external
: 1;
296 /* Unique id of the edge. */
300 #define CGRAPH_FREQ_BASE 1000
301 #define CGRAPH_FREQ_MAX 100000
303 typedef struct cgraph_edge
*cgraph_edge_p
;
305 DEF_VEC_P(cgraph_edge_p
);
306 DEF_VEC_ALLOC_P(cgraph_edge_p
,heap
);
308 /* The varpool data structure.
309 Each static variable decl has assigned varpool_node. */
311 struct GTY((chain_next ("%h.next"))) varpool_node
{
313 /* Pointer to the next function in varpool_nodes. */
314 struct varpool_node
*next
;
315 /* Pointer to the next function in varpool_nodes_queue. */
316 struct varpool_node
*next_needed
;
317 /* Ordering of all cgraph nodes. */
320 /* Set when function must be output - it is externally visible
321 or its address is taken. */
323 /* Needed variables might become dead by optimization. This flag
324 forces the variable to be output even if it appears dead otherwise. */
325 unsigned force_output
: 1;
326 /* Set once the variable has been instantiated and its callee
328 unsigned analyzed
: 1;
329 /* Set once it has been finalized so we consider it to be output. */
330 unsigned finalized
: 1;
331 /* Set when variable is scheduled to be assembled. */
333 /* Set when function is visible by other units. */
334 unsigned externally_visible
: 1;
335 /* Set for aliases once they got through assemble_alias. */
339 /* Every top level asm statement is put into a cgraph_asm_node. */
341 struct GTY(()) cgraph_asm_node
{
343 struct cgraph_asm_node
*next
;
344 /* String for this asm node. */
346 /* Ordering of all cgraph nodes. */
350 extern GTY(()) struct cgraph_node
*cgraph_nodes
;
351 extern GTY(()) int cgraph_n_nodes
;
352 extern GTY(()) int cgraph_max_uid
;
353 extern GTY(()) int cgraph_edge_max_uid
;
354 extern GTY(()) int cgraph_max_pid
;
355 extern bool cgraph_global_info_ready
;
358 /* Callgraph is being constructed. It is safe to add new functions. */
359 CGRAPH_STATE_CONSTRUCTION
,
360 /* Callgraph is built and IPA passes are being run. */
362 /* Callgraph is built and all functions are transformed to SSA form. */
363 CGRAPH_STATE_IPA_SSA
,
364 /* Functions are now ordered and being passed to RTL expanders. */
365 CGRAPH_STATE_EXPANSION
,
366 /* All cgraph expansion is done. */
367 CGRAPH_STATE_FINISHED
369 extern enum cgraph_state cgraph_state
;
370 extern bool cgraph_function_flags_ready
;
371 extern GTY(()) struct cgraph_node
*cgraph_nodes_queue
;
372 extern GTY(()) struct cgraph_node
*cgraph_new_nodes
;
374 extern GTY(()) struct cgraph_asm_node
*cgraph_asm_nodes
;
375 extern GTY(()) int cgraph_order
;
378 void dump_cgraph (FILE *);
379 void debug_cgraph (void);
380 void dump_cgraph_node (FILE *, struct cgraph_node
*);
381 void debug_cgraph_node (struct cgraph_node
*);
382 void cgraph_insert_node_to_hashtable (struct cgraph_node
*node
);
383 void cgraph_remove_edge (struct cgraph_edge
*);
384 void cgraph_remove_node (struct cgraph_node
*);
385 void cgraph_remove_node_and_inline_clones (struct cgraph_node
*);
386 void cgraph_release_function_body (struct cgraph_node
*);
387 void cgraph_node_remove_callees (struct cgraph_node
*node
);
388 struct cgraph_edge
*cgraph_create_edge (struct cgraph_node
*,
389 struct cgraph_node
*,
390 gimple
, gcov_type
, int, int);
391 struct cgraph_node
*cgraph_node (tree
);
392 struct cgraph_node
*cgraph_node_for_asm (tree asmname
);
393 struct cgraph_edge
*cgraph_edge (struct cgraph_node
*, gimple
);
394 void cgraph_set_call_stmt (struct cgraph_edge
*, gimple
);
395 void cgraph_set_call_stmt_including_clones (struct cgraph_node
*, gimple
, gimple
);
396 void cgraph_create_edge_including_clones (struct cgraph_node
*,
397 struct cgraph_node
*,
398 gimple
, gcov_type
, int, int,
399 cgraph_inline_failed_t
);
400 void cgraph_update_edges_for_call_stmt (gimple
, tree
, gimple
);
401 struct cgraph_local_info
*cgraph_local_info (tree
);
402 struct cgraph_global_info
*cgraph_global_info (tree
);
403 struct cgraph_rtl_info
*cgraph_rtl_info (tree
);
404 const char * cgraph_node_name (struct cgraph_node
*);
405 struct cgraph_edge
* cgraph_clone_edge (struct cgraph_edge
*,
406 struct cgraph_node
*,
407 gimple
, gcov_type
, int, int, bool);
408 struct cgraph_node
* cgraph_clone_node (struct cgraph_node
*, gcov_type
, int,
411 void cgraph_redirect_edge_callee (struct cgraph_edge
*, struct cgraph_node
*);
413 struct cgraph_asm_node
*cgraph_add_asm_node (tree
);
415 bool cgraph_function_possibly_inlined_p (tree
);
416 void cgraph_unnest_node (struct cgraph_node
*);
418 enum availability
cgraph_function_body_availability (struct cgraph_node
*);
419 void cgraph_add_new_function (tree
, bool);
420 const char* cgraph_inline_failed_string (cgraph_inline_failed_t
);
421 struct cgraph_node
* cgraph_create_virtual_clone (struct cgraph_node
*old_node
,
422 VEC(cgraph_edge_p
,heap
)*,
423 VEC(ipa_replace_map_p
,gc
)* tree_map
,
424 bitmap args_to_skip
);
426 /* In cgraphunit.c */
427 void cgraph_finalize_function (tree
, bool);
428 void cgraph_mark_if_needed (tree
);
429 void cgraph_finalize_compilation_unit (void);
430 void cgraph_mark_needed_node (struct cgraph_node
*);
431 void cgraph_mark_address_taken_node (struct cgraph_node
*);
432 void cgraph_mark_reachable_node (struct cgraph_node
*);
433 bool cgraph_inline_p (struct cgraph_edge
*, cgraph_inline_failed_t
*reason
);
434 bool cgraph_preserve_function_body_p (tree
);
435 void verify_cgraph (void);
436 void verify_cgraph_node (struct cgraph_node
*);
437 void cgraph_build_static_cdtor (char which
, tree body
, int priority
);
438 void cgraph_reset_static_var_maps (void);
439 void init_cgraph (void);
440 struct cgraph_node
*cgraph_function_versioning (struct cgraph_node
*,
441 VEC(cgraph_edge_p
,heap
)*,
442 VEC(ipa_replace_map_p
,gc
)*,
444 void tree_function_versioning (tree
, tree
, VEC (ipa_replace_map_p
,gc
)*, bool, bitmap
);
445 struct cgraph_node
*save_inline_function_body (struct cgraph_node
*);
446 void record_references_in_initializer (tree
);
447 bool cgraph_process_new_functions (void);
449 typedef void (*cgraph_edge_hook
)(struct cgraph_edge
*, void *);
450 typedef void (*cgraph_node_hook
)(struct cgraph_node
*, void *);
451 typedef void (*cgraph_2edge_hook
)(struct cgraph_edge
*, struct cgraph_edge
*,
453 typedef void (*cgraph_2node_hook
)(struct cgraph_node
*, struct cgraph_node
*,
455 struct cgraph_edge_hook_list
;
456 struct cgraph_node_hook_list
;
457 struct cgraph_2edge_hook_list
;
458 struct cgraph_2node_hook_list
;
459 struct cgraph_edge_hook_list
*cgraph_add_edge_removal_hook (cgraph_edge_hook
, void *);
460 void cgraph_remove_edge_removal_hook (struct cgraph_edge_hook_list
*);
461 struct cgraph_node_hook_list
*cgraph_add_node_removal_hook (cgraph_node_hook
,
463 void cgraph_remove_node_removal_hook (struct cgraph_node_hook_list
*);
464 struct cgraph_node_hook_list
*cgraph_add_function_insertion_hook (cgraph_node_hook
,
466 void cgraph_remove_function_insertion_hook (struct cgraph_node_hook_list
*);
467 void cgraph_call_function_insertion_hooks (struct cgraph_node
*node
);
468 struct cgraph_2edge_hook_list
*cgraph_add_edge_duplication_hook (cgraph_2edge_hook
, void *);
469 void cgraph_remove_edge_duplication_hook (struct cgraph_2edge_hook_list
*);
470 struct cgraph_2node_hook_list
*cgraph_add_node_duplication_hook (cgraph_2node_hook
, void *);
471 void cgraph_remove_node_duplication_hook (struct cgraph_2node_hook_list
*);
472 void cgraph_materialize_all_clones (void);
474 /* In cgraphbuild.c */
475 unsigned int rebuild_cgraph_edges (void);
476 int compute_call_stmt_bb_frequency (tree
, basic_block bb
);
479 bool cgraph_remove_unreachable_nodes (bool, FILE *);
480 int cgraph_postorder (struct cgraph_node
**);
481 cgraph_node_set
cgraph_node_set_new (void);
482 cgraph_node_set_iterator
cgraph_node_set_find (cgraph_node_set
,
483 struct cgraph_node
*);
484 void cgraph_node_set_add (cgraph_node_set
, struct cgraph_node
*);
485 void cgraph_node_set_remove (cgraph_node_set
, struct cgraph_node
*);
486 void dump_cgraph_node_set (FILE *, cgraph_node_set
);
487 void debug_cgraph_node_set (cgraph_node_set
);
491 bool cgraph_maybe_hot_edge_p (struct cgraph_edge
*e
);
494 extern GTY(()) struct varpool_node
*varpool_nodes_queue
;
495 extern GTY(()) struct varpool_node
*varpool_nodes
;
497 struct varpool_node
*varpool_node (tree
);
498 struct varpool_node
*varpool_node_for_asm (tree asmname
);
499 void varpool_mark_needed_node (struct varpool_node
*);
500 void debug_varpool (void);
501 void dump_varpool (FILE *);
502 void dump_varpool_node (FILE *, struct varpool_node
*);
504 void varpool_finalize_decl (tree
);
505 bool decide_is_variable_needed (struct varpool_node
*, tree
);
506 enum availability
cgraph_variable_initializer_availability (struct varpool_node
*);
507 void cgraph_make_node_local (struct cgraph_node
*);
508 bool cgraph_node_can_be_local_p (struct cgraph_node
*);
510 bool varpool_assemble_pending_decls (void);
511 bool varpool_assemble_decl (struct varpool_node
*node
);
512 bool varpool_analyze_pending_decls (void);
513 void varpool_remove_unreferenced_decls (void);
514 void varpool_empty_needed_queue (void);
516 /* Walk all reachable static variables. */
517 #define FOR_EACH_STATIC_VARIABLE(node) \
518 for ((node) = varpool_nodes_queue; (node); (node) = (node)->next_needed)
520 /* Return first reachable static variable with initializer. */
521 static inline struct varpool_node
*
522 varpool_first_static_initializer (void)
524 struct varpool_node
*node
;
525 for (node
= varpool_nodes_queue
; node
; node
= node
->next_needed
)
527 gcc_assert (TREE_CODE (node
->decl
) == VAR_DECL
);
528 if (DECL_INITIAL (node
->decl
))
534 /* Return next reachable static variable with initializer after NODE. */
535 static inline struct varpool_node
*
536 varpool_next_static_initializer (struct varpool_node
*node
)
538 for (node
= node
->next_needed
; node
; node
= node
->next_needed
)
540 gcc_assert (TREE_CODE (node
->decl
) == VAR_DECL
);
541 if (DECL_INITIAL (node
->decl
))
547 /* Walk all static variables with initializer set. */
548 #define FOR_EACH_STATIC_INITIALIZER(node) \
549 for ((node) = varpool_first_static_initializer (); (node); \
550 (node) = varpool_next_static_initializer (node))
552 /* In ipa-inline.c */
553 void cgraph_clone_inlined_nodes (struct cgraph_edge
*, bool, bool);
554 unsigned int compute_inline_parameters (struct cgraph_node
*);
557 /* Create a new static variable of type TYPE. */
558 tree
add_new_static_var (tree type
);
561 /* Return true if iterator CSI points to nothing. */
563 csi_end_p (cgraph_node_set_iterator csi
)
565 return csi
.index
>= VEC_length (cgraph_node_ptr
, csi
.set
->nodes
);
568 /* Advance iterator CSI. */
570 csi_next (cgraph_node_set_iterator
*csi
)
575 /* Return the node pointed to by CSI. */
576 static inline struct cgraph_node
*
577 csi_node (cgraph_node_set_iterator csi
)
579 return VEC_index (cgraph_node_ptr
, csi
.set
->nodes
, csi
.index
);
582 /* Return an iterator to the first node in SET. */
583 static inline cgraph_node_set_iterator
584 csi_start (cgraph_node_set set
)
586 cgraph_node_set_iterator csi
;
593 /* Return true if SET contains NODE. */
595 cgraph_node_in_set_p (struct cgraph_node
*node
, cgraph_node_set set
)
597 cgraph_node_set_iterator csi
;
598 csi
= cgraph_node_set_find (set
, node
);
599 return !csi_end_p (csi
);
602 /* Return number of nodes in SET. */
604 cgraph_node_set_size (cgraph_node_set set
)
606 return htab_elements (set
->hashtab
);
609 /* Uniquize all constants that appear in memory.
610 Each constant in memory thus far output is recorded
611 in `const_desc_table'. */
613 struct GTY(()) constant_descriptor_tree
{
614 /* A MEM for the constant. */
617 /* The value of the constant. */
620 /* Hash of value. Computing the hash from value each time
621 hashfn is called can't work properly, as that means recursive
622 use of the hash table during hash table expansion. */
626 /* Constant pool accessor function. */
627 htab_t
constant_pool_htab (void);
629 #endif /* GCC_CGRAPH_H */