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