]>
Commit | Line | Data |
---|---|---|
1c4a429a | 1 | /* Callgraph handling code. |
2bafad93 JJ |
2 | Copyright (C) 2003, 2004, 2005, 2006, 2007, 2008 |
3 | Free Software Foundation, Inc. | |
1c4a429a JH |
4 | Contributed by Jan Hubicka |
5 | ||
6 | This file is part of GCC. | |
7 | ||
8 | GCC is free software; you can redistribute it and/or modify it under | |
9 | the terms of the GNU General Public License as published by the Free | |
9dcd6f09 | 10 | Software Foundation; either version 3, or (at your option) any later |
1c4a429a JH |
11 | version. |
12 | ||
13 | GCC is distributed in the hope that it will be useful, but WITHOUT ANY | |
14 | WARRANTY; without even the implied warranty of MERCHANTABILITY or | |
15 | FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License | |
16 | for more details. | |
17 | ||
18 | You should have received a copy of the GNU General Public License | |
9dcd6f09 NC |
19 | along with GCC; see the file COPYING3. If not see |
20 | <http://www.gnu.org/licenses/>. */ | |
1c4a429a JH |
21 | |
22 | #ifndef GCC_CGRAPH_H | |
23 | #define GCC_CGRAPH_H | |
6674a6ce | 24 | #include "tree.h" |
e42922b1 | 25 | #include "basic-block.h" |
1c4a429a | 26 | |
6b02a499 JH |
27 | enum availability |
28 | { | |
29 | /* Not yet set by cgraph_function_body_availability. */ | |
30 | AVAIL_UNSET, | |
31 | /* Function body/variable initializer is unknown. */ | |
32 | AVAIL_NOT_AVAILABLE, | |
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. */ | |
38 | AVAIL_OVERWRITABLE, | |
39 | /* Function body/variable initializer is known and will be used in final | |
40 | program. */ | |
41 | AVAIL_AVAILABLE, | |
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. */ | |
46 | AVAIL_LOCAL | |
47 | }; | |
48 | ||
8a4a83ed JH |
49 | extern const char * const cgraph_availability_names[]; |
50 | ||
dafc5b82 | 51 | /* Information about the function collected locally. |
25c84396 | 52 | Available after function is analyzed. */ |
dafc5b82 | 53 | |
ed2df68b | 54 | struct cgraph_local_info GTY(()) |
dafc5b82 | 55 | { |
95622280 JH |
56 | struct inline_summary { |
57 | /* Estimated stack frame consumption by the function. */ | |
58 | HOST_WIDE_INT estimated_self_stack_size; | |
ff28a94d | 59 | |
95622280 JH |
60 | /* Size of the function before inlining. */ |
61 | int self_insns; | |
62 | } inline_summary; | |
6674a6ce | 63 | |
e0bb17a8 | 64 | /* Set when function function is visible in current compilation unit only |
e2209b03 | 65 | and its address is never taken. */ |
b4e19405 | 66 | unsigned local : 1; |
6674a6ce | 67 | |
e7d6beb0 | 68 | /* Set when function is visible by other units. */ |
b4e19405 | 69 | unsigned externally_visible : 1; |
e7d6beb0 | 70 | |
f6981e16 | 71 | /* Set once it has been finalized so we consider it to be output. */ |
b4e19405 | 72 | unsigned finalized : 1; |
b58b1157 | 73 | |
b3c3af2f | 74 | /* False when there something makes inlining impossible (such as va_arg). */ |
b4e19405 | 75 | unsigned inlinable : 1; |
6674a6ce | 76 | |
e2209b03 | 77 | /* True when function should be inlined independently on its size. */ |
b4e19405 | 78 | unsigned disregard_inline_limits : 1; |
6674a6ce | 79 | |
95c755e9 JH |
80 | /* True when the function has been originally extern inline, but it is |
81 | redefined now. */ | |
b4e19405 | 82 | unsigned redefined_extern_inline : 1; |
6674a6ce KZ |
83 | |
84 | /* True if statics_read_for_function and | |
85 | statics_written_for_function contain valid data. */ | |
b4e19405 | 86 | unsigned for_functions_valid : 1; |
8634c649 JJ |
87 | |
88 | /* True if the function is going to be emitted in some other translation | |
89 | unit, referenced from vtable. */ | |
b4e19405 | 90 | unsigned vtable_method : 1; |
dafc5b82 JH |
91 | }; |
92 | ||
93 | /* Information about the function that needs to be computed globally | |
94 | once compilation is finished. Available only with -funit-at-time. */ | |
95 | ||
ed2df68b | 96 | struct cgraph_global_info GTY(()) |
dafc5b82 | 97 | { |
ff28a94d JH |
98 | /* Estimated stack frame consumption by the function. */ |
99 | HOST_WIDE_INT estimated_stack_size; | |
100 | /* Expected offset of the stack frame of inlined function. */ | |
101 | HOST_WIDE_INT stack_frame_offset; | |
102 | ||
18c6ada9 JH |
103 | /* For inline clones this points to the function they will be inlined into. */ |
104 | struct cgraph_node *inlined_to; | |
105 | ||
b58b1157 JH |
106 | /* Estimated size of the function after inlining. */ |
107 | int insns; | |
108 | ||
670cd5c5 JH |
109 | /* Estimated growth after inlining. INT_MIN if not computed. */ |
110 | int estimated_growth; | |
111 | ||
18c6ada9 | 112 | /* Set iff the function has been inlined at least once. */ |
1bb17c21 | 113 | bool inlined; |
dafc5b82 JH |
114 | }; |
115 | ||
b255a036 JH |
116 | /* Information about the function that is propagated by the RTL backend. |
117 | Available only for functions that has been already assembled. */ | |
118 | ||
ed2df68b | 119 | struct cgraph_rtl_info GTY(()) |
b255a036 | 120 | { |
6de9cd9a | 121 | int preferred_incoming_stack_boundary; |
b255a036 JH |
122 | }; |
123 | ||
ba228239 | 124 | /* The cgraph data structure. |
e0bb17a8 | 125 | Each function decl has assigned cgraph_node listing callees and callers. */ |
1c4a429a | 126 | |
d1bd0ded | 127 | struct cgraph_node GTY((chain_next ("%h.next"), chain_prev ("%h.previous"))) |
1c4a429a JH |
128 | { |
129 | tree decl; | |
130 | struct cgraph_edge *callees; | |
131 | struct cgraph_edge *callers; | |
ed2df68b JH |
132 | struct cgraph_node *next; |
133 | struct cgraph_node *previous; | |
1c4a429a JH |
134 | /* For nested functions points to function the node is nested in. */ |
135 | struct cgraph_node *origin; | |
136 | /* Points to first nested function, if any. */ | |
137 | struct cgraph_node *nested; | |
138 | /* Pointer to the next function with same origin, if any. */ | |
139 | struct cgraph_node *next_nested; | |
8bd87c4e JH |
140 | /* Pointer to the next function in cgraph_nodes_queue. */ |
141 | struct cgraph_node *next_needed; | |
18c6ada9 JH |
142 | /* Pointer to the next clone. */ |
143 | struct cgraph_node *next_clone; | |
1655dc9d | 144 | struct cgraph_node *prev_clone; |
6b02a499 JH |
145 | /* Pointer to a single unique cgraph node for this function. If the |
146 | function is to be output, this is the copy that will survive. */ | |
147 | struct cgraph_node *master_clone; | |
70d539ce JH |
148 | /* For functions with many calls sites it holds map from call expression |
149 | to the edge to speed up cgraph_edge function. */ | |
150 | htab_t GTY((param_is (struct cgraph_edge))) call_site_hash; | |
c22cacf3 | 151 | |
1431042e | 152 | PTR GTY ((skip)) aux; |
1c4a429a | 153 | |
95c755e9 JH |
154 | struct cgraph_local_info local; |
155 | struct cgraph_global_info global; | |
156 | struct cgraph_rtl_info rtl; | |
c22cacf3 | 157 | |
e42922b1 JH |
158 | /* Expected number of executions: calculated in profile.c. */ |
159 | gcov_type count; | |
95c755e9 JH |
160 | /* Unique id of the node. */ |
161 | int uid; | |
474eccc6 ILT |
162 | /* Ordering of all cgraph nodes. */ |
163 | int order; | |
b4e19405 | 164 | |
1c4a429a | 165 | /* Set when function must be output - it is externally visible |
e2209b03 | 166 | or its address is taken. */ |
b4e19405 | 167 | unsigned needed : 1; |
1c4a429a | 168 | /* Set when function is reachable by call from other function |
e0bb17a8 | 169 | that is either reachable or needed. */ |
b4e19405 | 170 | unsigned reachable : 1; |
50674e96 | 171 | /* Set once the function is lowered (i.e. its CFG is built). */ |
b4e19405 | 172 | unsigned lowered : 1; |
25c84396 RH |
173 | /* Set once the function has been instantiated and its callee |
174 | lists created. */ | |
b4e19405 | 175 | unsigned analyzed : 1; |
1c4a429a | 176 | /* Set when function is scheduled to be assembled. */ |
b4e19405 | 177 | unsigned output : 1; |
12527dce | 178 | /* Set for aliases once they got through assemble_alias. */ |
b4e19405 | 179 | unsigned alias : 1; |
ea99e0be JH |
180 | |
181 | /* In non-unit-at-a-time mode the function body of inline candidates is saved | |
182 | into clone before compiling so the function in original form can be | |
183 | inlined later. This pointer points to the clone. */ | |
184 | tree inline_decl; | |
6bad2617 TB |
185 | |
186 | /* unique id for profiling. pid is not suitable because of different | |
187 | number of cfg nodes with -fprofile-generate and -fprofile-use */ | |
188 | int pid; | |
1c4a429a JH |
189 | }; |
190 | ||
2563c224 | 191 | struct cgraph_edge GTY((chain_next ("%h.next_caller"), chain_prev ("%h.prev_caller"))) |
1c4a429a | 192 | { |
ed2df68b JH |
193 | struct cgraph_node *caller; |
194 | struct cgraph_node *callee; | |
2563c224 | 195 | struct cgraph_edge *prev_caller; |
1c4a429a | 196 | struct cgraph_edge *next_caller; |
2563c224 | 197 | struct cgraph_edge *prev_callee; |
1c4a429a | 198 | struct cgraph_edge *next_callee; |
e0704a46 | 199 | tree call_stmt; |
18c6ada9 | 200 | PTR GTY ((skip (""))) aux; |
dc0bfe6a JH |
201 | /* When NULL, inline this call. When non-NULL, points to the explanation |
202 | why function was not inlined. */ | |
203 | const char *inline_failed; | |
e42922b1 JH |
204 | /* Expected number of executions: calculated in profile.c. */ |
205 | gcov_type count; | |
45a80bb9 JH |
206 | /* Expected frequency of executions within the function. |
207 | When set to CGRAPH_FREQ_BASE, the edge is expected to be called once | |
208 | per function call. The range is 0 to CGRAPH_FREQ_MAX. */ | |
209 | int frequency; | |
e42922b1 JH |
210 | /* Depth of loop nest, 1 means no loop nest. */ |
211 | int loop_nest; | |
1c4a429a JH |
212 | }; |
213 | ||
45a80bb9 JH |
214 | #define CGRAPH_FREQ_BASE 1000 |
215 | #define CGRAPH_FREQ_MAX 100000 | |
216 | ||
b2c0ad40 KH |
217 | typedef struct cgraph_edge *cgraph_edge_p; |
218 | ||
219 | DEF_VEC_P(cgraph_edge_p); | |
220 | DEF_VEC_ALLOC_P(cgraph_edge_p,heap); | |
221 | ||
8a4a83ed JH |
222 | /* The varpool data structure. |
223 | Each static variable decl has assigned varpool_node. */ | |
e69529cd | 224 | |
8a4a83ed | 225 | struct varpool_node GTY(()) |
e69529cd JH |
226 | { |
227 | tree decl; | |
8a4a83ed JH |
228 | /* Pointer to the next function in varpool_nodes. */ |
229 | struct varpool_node *next; | |
230 | /* Pointer to the next function in varpool_nodes_queue. */ | |
231 | struct varpool_node *next_needed; | |
474eccc6 ILT |
232 | /* Ordering of all cgraph nodes. */ |
233 | int order; | |
e69529cd JH |
234 | |
235 | /* Set when function must be output - it is externally visible | |
e2209b03 | 236 | or its address is taken. */ |
b4e19405 | 237 | unsigned needed : 1; |
cd9c7bd2 JH |
238 | /* Needed variables might become dead by optimization. This flag |
239 | forces the variable to be output even if it appears dead otherwise. */ | |
b4e19405 | 240 | unsigned force_output : 1; |
cd9c7bd2 JH |
241 | /* Set once the variable has been instantiated and its callee |
242 | lists created. */ | |
b4e19405 | 243 | unsigned analyzed : 1; |
e69529cd | 244 | /* Set once it has been finalized so we consider it to be output. */ |
b4e19405 | 245 | unsigned finalized : 1; |
6b02a499 | 246 | /* Set when variable is scheduled to be assembled. */ |
b4e19405 | 247 | unsigned output : 1; |
e7d6beb0 | 248 | /* Set when function is visible by other units. */ |
b4e19405 | 249 | unsigned externally_visible : 1; |
1a612e0a | 250 | /* Set for aliases once they got through assemble_alias. */ |
b4e19405 | 251 | unsigned alias : 1; |
e69529cd JH |
252 | }; |
253 | ||
474eccc6 ILT |
254 | /* Every top level asm statement is put into a cgraph_asm_node. */ |
255 | ||
256 | struct cgraph_asm_node GTY(()) | |
257 | { | |
258 | /* Next asm node. */ | |
259 | struct cgraph_asm_node *next; | |
260 | /* String for this asm node. */ | |
261 | tree asm_str; | |
262 | /* Ordering of all cgraph nodes. */ | |
263 | int order; | |
264 | }; | |
265 | ||
ed2df68b JH |
266 | extern GTY(()) struct cgraph_node *cgraph_nodes; |
267 | extern GTY(()) int cgraph_n_nodes; | |
b58b1157 | 268 | extern GTY(()) int cgraph_max_uid; |
6bad2617 | 269 | extern GTY(()) int cgraph_max_pid; |
dafc5b82 | 270 | extern bool cgraph_global_info_ready; |
f45e0ad1 JH |
271 | enum cgraph_state |
272 | { | |
273 | /* Callgraph is being constructed. It is safe to add new functions. */ | |
274 | CGRAPH_STATE_CONSTRUCTION, | |
275 | /* Callgraph is built and IPA passes are being run. */ | |
276 | CGRAPH_STATE_IPA, | |
7a388ee4 JH |
277 | /* Callgraph is built and all functions are transformed to SSA form. */ |
278 | CGRAPH_STATE_IPA_SSA, | |
f45e0ad1 JH |
279 | /* Functions are now ordered and being passed to RTL expanders. */ |
280 | CGRAPH_STATE_EXPANSION, | |
281 | /* All cgraph expansion is done. */ | |
282 | CGRAPH_STATE_FINISHED | |
283 | }; | |
284 | extern enum cgraph_state cgraph_state; | |
e7d6beb0 | 285 | extern bool cgraph_function_flags_ready; |
ed2df68b | 286 | extern GTY(()) struct cgraph_node *cgraph_nodes_queue; |
f45e0ad1 | 287 | extern GTY(()) struct cgraph_node *cgraph_new_nodes; |
1c4a429a | 288 | |
474eccc6 ILT |
289 | extern GTY(()) struct cgraph_asm_node *cgraph_asm_nodes; |
290 | extern GTY(()) int cgraph_order; | |
e69529cd | 291 | |
1c4a429a | 292 | /* In cgraph.c */ |
439f7bc3 | 293 | void dump_cgraph (FILE *); |
c4e622b6 | 294 | void debug_cgraph (void); |
18c6ada9 | 295 | void dump_cgraph_node (FILE *, struct cgraph_node *); |
c4e622b6 | 296 | void debug_cgraph_node (struct cgraph_node *); |
ea99e0be | 297 | void cgraph_insert_node_to_hashtable (struct cgraph_node *node); |
18c6ada9 | 298 | void cgraph_remove_edge (struct cgraph_edge *); |
439f7bc3 | 299 | void cgraph_remove_node (struct cgraph_node *); |
3a40c18a | 300 | void cgraph_release_function_body (struct cgraph_node *); |
2563c224 | 301 | void cgraph_node_remove_callees (struct cgraph_node *node); |
18c6ada9 JH |
302 | struct cgraph_edge *cgraph_create_edge (struct cgraph_node *, |
303 | struct cgraph_node *, | |
45a80bb9 | 304 | tree, gcov_type, int, int); |
e42922b1 | 305 | struct cgraph_node *cgraph_node (tree); |
bedb9fc0 | 306 | struct cgraph_node *cgraph_node_for_asm (tree asmname); |
e42922b1 | 307 | struct cgraph_edge *cgraph_edge (struct cgraph_node *, tree); |
70d539ce | 308 | void cgraph_set_call_stmt (struct cgraph_edge *, tree); |
2bafad93 | 309 | void cgraph_update_edges_for_call_stmt (tree, tree, tree); |
439f7bc3 AJ |
310 | struct cgraph_local_info *cgraph_local_info (tree); |
311 | struct cgraph_global_info *cgraph_global_info (tree); | |
312 | struct cgraph_rtl_info *cgraph_rtl_info (tree); | |
313 | const char * cgraph_node_name (struct cgraph_node *); | |
c5a4444c | 314 | struct cgraph_edge * cgraph_clone_edge (struct cgraph_edge *, |
c22cacf3 | 315 | struct cgraph_node *, |
45a80bb9 JH |
316 | tree, gcov_type, int, int, bool); |
317 | struct cgraph_node * cgraph_clone_node (struct cgraph_node *, gcov_type, int, | |
c5a4444c | 318 | int, bool); |
1c4a429a | 319 | |
18c6ada9 | 320 | void cgraph_redirect_edge_callee (struct cgraph_edge *, struct cgraph_node *); |
e69529cd | 321 | |
474eccc6 ILT |
322 | struct cgraph_asm_node *cgraph_add_asm_node (tree); |
323 | ||
1bb17c21 | 324 | bool cgraph_function_possibly_inlined_p (tree); |
e42922b1 | 325 | void cgraph_unnest_node (struct cgraph_node *); |
1bb17c21 | 326 | |
6b02a499 | 327 | enum availability cgraph_function_body_availability (struct cgraph_node *); |
6b02a499 JH |
328 | bool cgraph_is_master_clone (struct cgraph_node *); |
329 | struct cgraph_node *cgraph_master_clone (struct cgraph_node *); | |
f45e0ad1 | 330 | void cgraph_add_new_function (tree, bool); |
6b02a499 | 331 | |
1c4a429a | 332 | /* In cgraphunit.c */ |
6b00c969 | 333 | void cgraph_finalize_function (tree, bool); |
439f7bc3 | 334 | void cgraph_finalize_compilation_unit (void); |
439f7bc3 | 335 | void cgraph_optimize (void); |
8dafba3c RH |
336 | void cgraph_mark_needed_node (struct cgraph_node *); |
337 | void cgraph_mark_reachable_node (struct cgraph_node *); | |
18c6ada9 JH |
338 | bool cgraph_inline_p (struct cgraph_edge *, const char **reason); |
339 | bool cgraph_preserve_function_body_p (tree); | |
340 | void verify_cgraph (void); | |
341 | void verify_cgraph_node (struct cgraph_node *); | |
35b6fdcf | 342 | void cgraph_build_static_cdtor (char which, tree body, int priority); |
6674a6ce | 343 | void cgraph_reset_static_var_maps (void); |
9b3e897d | 344 | void init_cgraph (void); |
57fb5341 | 345 | struct cgraph_node *cgraph_function_versioning (struct cgraph_node *, |
c22cacf3 | 346 | VEC(cgraph_edge_p,heap)*, |
b2c0ad40 | 347 | varray_type); |
953ff289 | 348 | void cgraph_analyze_function (struct cgraph_node *); |
ea99e0be | 349 | struct cgraph_node *save_inline_function_body (struct cgraph_node *); |
8a4a83ed | 350 | void record_references_in_initializer (tree); |
f45e0ad1 | 351 | bool cgraph_process_new_functions (void); |
1c4a429a | 352 | |
917948d3 ZD |
353 | /* In cgraphbuild.c */ |
354 | unsigned int rebuild_cgraph_edges (void); | |
355 | ||
ca31b95f JH |
356 | /* In ipa.c */ |
357 | bool cgraph_remove_unreachable_nodes (bool, FILE *); | |
358 | int cgraph_postorder (struct cgraph_node **); | |
359 | ||
8a4a83ed JH |
360 | /* In varpool.c */ |
361 | ||
362 | extern GTY(()) struct varpool_node *varpool_nodes_queue; | |
363 | extern GTY(()) struct varpool_node *varpool_nodes; | |
364 | ||
365 | struct varpool_node *varpool_node (tree); | |
366 | struct varpool_node *varpool_node_for_asm (tree asmname); | |
367 | void varpool_mark_needed_node (struct varpool_node *); | |
368 | void dump_varpool (FILE *); | |
369 | void dump_varpool_node (FILE *, struct varpool_node *); | |
370 | ||
371 | void varpool_finalize_decl (tree); | |
372 | bool decide_is_variable_needed (struct varpool_node *, tree); | |
373 | enum availability cgraph_variable_initializer_availability (struct varpool_node *); | |
374 | ||
375 | bool varpool_assemble_pending_decls (void); | |
376 | bool varpool_assemble_decl (struct varpool_node *node); | |
377 | bool varpool_analyze_pending_decls (void); | |
378 | void varpool_output_debug_info (void); | |
379 | void varpool_remove_unreferenced_decls (void); | |
380 | ||
68e56cc4 JH |
381 | /* Walk all reachable static variables. */ |
382 | #define FOR_EACH_STATIC_VARIABLE(node) \ | |
383 | for ((node) = varpool_nodes_queue; (node); (node) = (node)->next_needed) | |
384 | ||
385 | /* Return first reachable static variable with initializer. */ | |
386 | static inline struct varpool_node * | |
387 | varpool_first_static_initializer (void) | |
388 | { | |
389 | struct varpool_node *node; | |
390 | for (node = varpool_nodes_queue; node; node = node->next_needed) | |
391 | { | |
392 | gcc_assert (TREE_CODE (node->decl) == VAR_DECL); | |
393 | if (DECL_INITIAL (node->decl)) | |
394 | return node; | |
395 | } | |
396 | return NULL; | |
397 | } | |
398 | ||
399 | /* Return next reachable static variable with initializer after NODE. */ | |
400 | static inline struct varpool_node * | |
401 | varpool_next_static_initializer (struct varpool_node *node) | |
402 | { | |
403 | for (node = node->next_needed; node; node = node->next_needed) | |
404 | { | |
405 | gcc_assert (TREE_CODE (node->decl) == VAR_DECL); | |
406 | if (DECL_INITIAL (node->decl)) | |
407 | return node; | |
408 | } | |
409 | return NULL; | |
410 | } | |
411 | ||
412 | /* Walk all static variables with initializer set. */ | |
413 | #define FOR_EACH_STATIC_INITIALIZER(node) \ | |
414 | for ((node) = varpool_first_static_initializer (); (node); \ | |
415 | (node) = varpool_next_static_initializer (node)) | |
416 | ||
ca31b95f | 417 | /* In ipa-inline.c */ |
06191a23 JH |
418 | void cgraph_clone_inlined_nodes (struct cgraph_edge *, bool, bool); |
419 | void cgraph_mark_inline_edge (struct cgraph_edge *, bool); | |
9de21a23 | 420 | bool cgraph_default_inline_p (struct cgraph_node *, const char **); |
43d861a5 RL |
421 | |
422 | ||
423 | /* Create a new static variable of type TYPE. */ | |
424 | tree add_new_static_var (tree type); | |
425 | ||
1c4a429a | 426 | #endif /* GCC_CGRAPH_H */ |