1 /* Callgraph construction.
2 Copyright (C) 2003-2013 Free Software Foundation, Inc.
3 Contributed by Jan Hubicka
4
5 This file is part of GCC.
6
7 GCC is free software; you can redistribute it and/or modify it under
8 the terms of the GNU General Public License as published by the Free
9 Software Foundation; either version 3, or (at your option) any later
10 version.
11
12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13 WARRANTY; without even the implied warranty of MERCHANTABILITY or
14 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
15 for more details.
16
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING3. If not see
19 <http://www.gnu.org/licenses/>. */
20
21 #include "config.h"
22 #include "system.h"
23 #include "coretypes.h"
24 #include "tm.h"
25 #include "tree.h"
26 #include "tree-flow.h"
27 #include "langhooks.h"
28 #include "pointer-set.h"
29 #include "cgraph.h"
30 #include "intl.h"
31 #include "gimple.h"
32 #include "tree-pass.h"
33 #include "ipa-utils.h"
34 #include "except.h"
35 #include "ipa-inline.h"
36
37 /* Context of record_reference. */
38 struct record_reference_ctx
39 {
40 bool only_vars;
41 struct varpool_node *varpool_node;
42 };
43
44 /* Walk tree and record all calls and references to functions/variables.
45 Called via walk_tree: TP is pointer to tree to be examined.
46 When DATA is non-null, record references to callgraph.
47 */
48
49 static tree
record_reference(tree * tp,int * walk_subtrees,void * data)50 record_reference (tree *tp, int *walk_subtrees, void *data)
51 {
52 tree t = *tp;
53 tree decl;
54 struct record_reference_ctx *ctx = (struct record_reference_ctx *)data;
55
56 t = canonicalize_constructor_val (t, NULL);
57 if (!t)
58 t = *tp;
59 else if (t != *tp)
60 *tp = t;
61
62 switch (TREE_CODE (t))
63 {
64 case VAR_DECL:
65 case FUNCTION_DECL:
66 gcc_unreachable ();
67 break;
68
69 case FDESC_EXPR:
70 case ADDR_EXPR:
71 /* Record dereferences to the functions. This makes the
72 functions reachable unconditionally. */
73 decl = get_base_var (*tp);
74 if (TREE_CODE (decl) == FUNCTION_DECL)
75 {
76 struct cgraph_node *node = cgraph_get_create_node (decl);
77 if (!ctx->only_vars)
78 cgraph_mark_address_taken_node (node);
79 ipa_record_reference ((symtab_node)ctx->varpool_node,
80 (symtab_node)node,
81 IPA_REF_ADDR, NULL);
82 }
83
84 if (TREE_CODE (decl) == VAR_DECL)
85 {
86 struct varpool_node *vnode = varpool_node_for_decl (decl);
87 ipa_record_reference ((symtab_node)ctx->varpool_node,
88 (symtab_node)vnode,
89 IPA_REF_ADDR, NULL);
90 }
91 *walk_subtrees = 0;
92 break;
93
94 default:
95 /* Save some cycles by not walking types and declaration as we
96 won't find anything useful there anyway. */
97 if (IS_TYPE_OR_DECL_P (*tp))
98 {
99 *walk_subtrees = 0;
100 break;
101 }
102 break;
103 }
104
105 return NULL_TREE;
106 }
107
108 /* Record references to typeinfos in the type list LIST. */
109
110 static void
record_type_list(struct cgraph_node * node,tree list)111 record_type_list (struct cgraph_node *node, tree list)
112 {
113 for (; list; list = TREE_CHAIN (list))
114 {
115 tree type = TREE_VALUE (list);
116
117 if (TYPE_P (type))
118 type = lookup_type_for_runtime (type);
119 STRIP_NOPS (type);
120 if (TREE_CODE (type) == ADDR_EXPR)
121 {
122 type = TREE_OPERAND (type, 0);
123 if (TREE_CODE (type) == VAR_DECL)
124 {
125 struct varpool_node *vnode = varpool_node_for_decl (type);
126 ipa_record_reference ((symtab_node)node,
127 (symtab_node)vnode,
128 IPA_REF_ADDR, NULL);
129 }
130 }
131 }
132 }
133
134 /* Record all references we will introduce by producing EH tables
135 for NODE. */
136
137 static void
record_eh_tables(struct cgraph_node * node,struct function * fun)138 record_eh_tables (struct cgraph_node *node, struct function *fun)
139 {
140 eh_region i;
141
142 if (DECL_FUNCTION_PERSONALITY (node->symbol.decl))
143 {
144 struct cgraph_node *per_node;
145
146 per_node = cgraph_get_create_node (DECL_FUNCTION_PERSONALITY (node->symbol.decl));
147 ipa_record_reference ((symtab_node)node, (symtab_node)per_node, IPA_REF_ADDR, NULL);
148 cgraph_mark_address_taken_node (per_node);
149 }
150
151 i = fun->eh->region_tree;
152 if (!i)
153 return;
154
155 while (1)
156 {
157 switch (i->type)
158 {
159 case ERT_CLEANUP:
160 case ERT_MUST_NOT_THROW:
161 break;
162
163 case ERT_TRY:
164 {
165 eh_catch c;
166 for (c = i->u.eh_try.first_catch; c; c = c->next_catch)
167 record_type_list (node, c->type_list);
168 }
169 break;
170
171 case ERT_ALLOWED_EXCEPTIONS:
172 record_type_list (node, i->u.allowed.type_list);
173 break;
174 }
175 /* If there are sub-regions, process them. */
176 if (i->inner)
177 i = i->inner;
178 /* If there are peers, process them. */
179 else if (i->next_peer)
180 i = i->next_peer;
181 /* Otherwise, step back up the tree to the next peer. */
182 else
183 {
184 do
185 {
186 i = i->outer;
187 if (i == NULL)
188 return;
189 }
190 while (i->next_peer == NULL);
191 i = i->next_peer;
192 }
193 }
194 }
195
196 /* Computes the frequency of the call statement so that it can be stored in
197 cgraph_edge. BB is the basic block of the call statement. */
198 int
compute_call_stmt_bb_frequency(tree decl,basic_block bb)199 compute_call_stmt_bb_frequency (tree decl, basic_block bb)
200 {
201 int entry_freq = ENTRY_BLOCK_PTR_FOR_FUNCTION
202 (DECL_STRUCT_FUNCTION (decl))->frequency;
203 int freq = bb->frequency;
204
205 if (profile_status_for_function (DECL_STRUCT_FUNCTION (decl)) == PROFILE_ABSENT)
206 return CGRAPH_FREQ_BASE;
207
208 if (!entry_freq)
209 entry_freq = 1, freq++;
210
211 freq = freq * CGRAPH_FREQ_BASE / entry_freq;
212 if (freq > CGRAPH_FREQ_MAX)
213 freq = CGRAPH_FREQ_MAX;
214
215 return freq;
216 }
217
218 /* Mark address taken in STMT. */
219
220 static bool
mark_address(gimple stmt,tree addr,void * data)221 mark_address (gimple stmt, tree addr, void *data)
222 {
223 addr = get_base_address (addr);
224 if (TREE_CODE (addr) == FUNCTION_DECL)
225 {
226 struct cgraph_node *node = cgraph_get_create_node (addr);
227 cgraph_mark_address_taken_node (node);
228 ipa_record_reference ((symtab_node)data,
229 (symtab_node)node,
230 IPA_REF_ADDR, stmt);
231 }
232 else if (addr && TREE_CODE (addr) == VAR_DECL
233 && (TREE_STATIC (addr) || DECL_EXTERNAL (addr)))
234 {
235 struct varpool_node *vnode = varpool_node_for_decl (addr);
236
237 ipa_record_reference ((symtab_node)data,
238 (symtab_node)vnode,
239 IPA_REF_ADDR, stmt);
240 }
241
242 return false;
243 }
244
245 /* Mark load of T. */
246
247 static bool
mark_load(gimple stmt,tree t,void * data)248 mark_load (gimple stmt, tree t, void *data)
249 {
250 t = get_base_address (t);
251 if (t && TREE_CODE (t) == FUNCTION_DECL)
252 {
253 /* ??? This can happen on platforms with descriptors when these are
254 directly manipulated in the code. Pretend that it's an address. */
255 struct cgraph_node *node = cgraph_get_create_node (t);
256 cgraph_mark_address_taken_node (node);
257 ipa_record_reference ((symtab_node)data,
258 (symtab_node)node,
259 IPA_REF_ADDR, stmt);
260 }
261 else if (t && TREE_CODE (t) == VAR_DECL
262 && (TREE_STATIC (t) || DECL_EXTERNAL (t)))
263 {
264 struct varpool_node *vnode = varpool_node_for_decl (t);
265
266 ipa_record_reference ((symtab_node)data,
267 (symtab_node)vnode,
268 IPA_REF_LOAD, stmt);
269 }
270 return false;
271 }
272
273 /* Mark store of T. */
274
275 static bool
mark_store(gimple stmt,tree t,void * data)276 mark_store (gimple stmt, tree t, void *data)
277 {
278 t = get_base_address (t);
279 if (t && TREE_CODE (t) == VAR_DECL
280 && (TREE_STATIC (t) || DECL_EXTERNAL (t)))
281 {
282 struct varpool_node *vnode = varpool_node_for_decl (t);
283
284 ipa_record_reference ((symtab_node)data,
285 (symtab_node)vnode,
286 IPA_REF_STORE, stmt);
287 }
288 return false;
289 }
290
291 /* Create cgraph edges for function calls.
292 Also look for functions and variables having addresses taken. */
293
294 static unsigned int
build_cgraph_edges(void)295 build_cgraph_edges (void)
296 {
297 basic_block bb;
298 struct cgraph_node *node = cgraph_get_node (current_function_decl);
299 struct pointer_set_t *visited_nodes = pointer_set_create ();
300 gimple_stmt_iterator gsi;
301 tree decl;
302 unsigned ix;
303
304 /* Create the callgraph edges and record the nodes referenced by the function.
305 body. */
306 FOR_EACH_BB (bb)
307 {
308 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
309 {
310 gimple stmt = gsi_stmt (gsi);
311 tree decl;
312
313 if (is_gimple_call (stmt))
314 {
315 int freq = compute_call_stmt_bb_frequency (current_function_decl,
316 bb);
317 decl = gimple_call_fndecl (stmt);
318 if (decl)
319 cgraph_create_edge (node, cgraph_get_create_node (decl),
320 stmt, bb->count, freq);
321 else
322 cgraph_create_indirect_edge (node, stmt,
323 gimple_call_flags (stmt),
324 bb->count, freq);
325 }
326 walk_stmt_load_store_addr_ops (stmt, node, mark_load,
327 mark_store, mark_address);
328 if (gimple_code (stmt) == GIMPLE_OMP_PARALLEL
329 && gimple_omp_parallel_child_fn (stmt))
330 {
331 tree fn = gimple_omp_parallel_child_fn (stmt);
332 ipa_record_reference ((symtab_node)node,
333 (symtab_node)cgraph_get_create_node (fn),
334 IPA_REF_ADDR, stmt);
335 }
336 if (gimple_code (stmt) == GIMPLE_OMP_TASK)
337 {
338 tree fn = gimple_omp_task_child_fn (stmt);
339 if (fn)
340 ipa_record_reference ((symtab_node)node,
341 (symtab_node) cgraph_get_create_node (fn),
342 IPA_REF_ADDR, stmt);
343 fn = gimple_omp_task_copy_fn (stmt);
344 if (fn)
345 ipa_record_reference ((symtab_node)node,
346 (symtab_node)cgraph_get_create_node (fn),
347 IPA_REF_ADDR, stmt);
348 }
349 }
350 for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
351 walk_stmt_load_store_addr_ops (gsi_stmt (gsi), node,
352 mark_load, mark_store, mark_address);
353 }
354
355 /* Look for initializers of constant variables and private statics. */
356 FOR_EACH_LOCAL_DECL (cfun, ix, decl)
357 if (TREE_CODE (decl) == VAR_DECL
358 && (TREE_STATIC (decl) && !DECL_EXTERNAL (decl))
359 && !DECL_HAS_VALUE_EXPR_P (decl))
360 varpool_finalize_decl (decl);
361 record_eh_tables (node, cfun);
362
363 pointer_set_destroy (visited_nodes);
364 return 0;
365 }
366
367 struct gimple_opt_pass pass_build_cgraph_edges =
368 {
369 {
370 GIMPLE_PASS,
371 "*build_cgraph_edges", /* name */
372 OPTGROUP_NONE, /* optinfo_flags */
373 NULL, /* gate */
374 build_cgraph_edges, /* execute */
375 NULL, /* sub */
376 NULL, /* next */
377 0, /* static_pass_number */
378 TV_NONE, /* tv_id */
379 PROP_cfg, /* properties_required */
380 0, /* properties_provided */
381 0, /* properties_destroyed */
382 0, /* todo_flags_start */
383 0 /* todo_flags_finish */
384 }
385 };
386
387 /* Record references to functions and other variables present in the
388 initial value of DECL, a variable.
389 When ONLY_VARS is true, we mark needed only variables, not functions. */
390
391 void
record_references_in_initializer(tree decl,bool only_vars)392 record_references_in_initializer (tree decl, bool only_vars)
393 {
394 struct pointer_set_t *visited_nodes = pointer_set_create ();
395 struct varpool_node *node = varpool_node_for_decl (decl);
396 struct record_reference_ctx ctx = {false, NULL};
397
398 ctx.varpool_node = node;
399 ctx.only_vars = only_vars;
400 walk_tree (&DECL_INITIAL (decl), record_reference,
401 &ctx, visited_nodes);
402 pointer_set_destroy (visited_nodes);
403 }
404
405 /* Rebuild cgraph edges for current function node. This needs to be run after
406 passes that don't update the cgraph. */
407
408 unsigned int
rebuild_cgraph_edges(void)409 rebuild_cgraph_edges (void)
410 {
411 basic_block bb;
412 struct cgraph_node *node = cgraph_get_node (current_function_decl);
413 gimple_stmt_iterator gsi;
414
415 cgraph_node_remove_callees (node);
416 ipa_remove_all_references (&node->symbol.ref_list);
417
418 node->count = ENTRY_BLOCK_PTR->count;
419
420 FOR_EACH_BB (bb)
421 {
422 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
423 {
424 gimple stmt = gsi_stmt (gsi);
425 tree decl;
426
427 if (is_gimple_call (stmt))
428 {
429 int freq = compute_call_stmt_bb_frequency (current_function_decl,
430 bb);
431 decl = gimple_call_fndecl (stmt);
432 if (decl)
433 cgraph_create_edge (node, cgraph_get_create_node (decl), stmt,
434 bb->count, freq);
435 else
436 cgraph_create_indirect_edge (node, stmt,
437 gimple_call_flags (stmt),
438 bb->count, freq);
439 }
440 walk_stmt_load_store_addr_ops (stmt, node, mark_load,
441 mark_store, mark_address);
442
443 }
444 for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
445 walk_stmt_load_store_addr_ops (gsi_stmt (gsi), node,
446 mark_load, mark_store, mark_address);
447 }
448 record_eh_tables (node, cfun);
449 gcc_assert (!node->global.inlined_to);
450
451 return 0;
452 }
453
454 /* Rebuild cgraph edges for current function node. This needs to be run after
455 passes that don't update the cgraph. */
456
457 void
cgraph_rebuild_references(void)458 cgraph_rebuild_references (void)
459 {
460 basic_block bb;
461 struct cgraph_node *node = cgraph_get_node (current_function_decl);
462 gimple_stmt_iterator gsi;
463
464 ipa_remove_all_references (&node->symbol.ref_list);
465
466 node->count = ENTRY_BLOCK_PTR->count;
467
468 FOR_EACH_BB (bb)
469 {
470 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
471 {
472 gimple stmt = gsi_stmt (gsi);
473
474 walk_stmt_load_store_addr_ops (stmt, node, mark_load,
475 mark_store, mark_address);
476
477 }
478 for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
479 walk_stmt_load_store_addr_ops (gsi_stmt (gsi), node,
480 mark_load, mark_store, mark_address);
481 }
482 record_eh_tables (node, cfun);
483 }
484
485 struct gimple_opt_pass pass_rebuild_cgraph_edges =
486 {
487 {
488 GIMPLE_PASS,
489 "*rebuild_cgraph_edges", /* name */
490 OPTGROUP_NONE, /* optinfo_flags */
491 NULL, /* gate */
492 rebuild_cgraph_edges, /* execute */
493 NULL, /* sub */
494 NULL, /* next */
495 0, /* static_pass_number */
496 TV_CGRAPH, /* tv_id */
497 PROP_cfg, /* properties_required */
498 0, /* properties_provided */
499 0, /* properties_destroyed */
500 0, /* todo_flags_start */
501 0, /* todo_flags_finish */
502 }
503 };
504
505
506 static unsigned int
remove_cgraph_callee_edges(void)507 remove_cgraph_callee_edges (void)
508 {
509 cgraph_node_remove_callees (cgraph_get_node (current_function_decl));
510 return 0;
511 }
512
513 struct gimple_opt_pass pass_remove_cgraph_callee_edges =
514 {
515 {
516 GIMPLE_PASS,
517 "*remove_cgraph_callee_edges", /* name */
518 OPTGROUP_NONE, /* optinfo_flags */
519 NULL, /* gate */
520 remove_cgraph_callee_edges, /* execute */
521 NULL, /* sub */
522 NULL, /* next */
523 0, /* static_pass_number */
524 TV_NONE, /* tv_id */
525 0, /* properties_required */
526 0, /* properties_provided */
527 0, /* properties_destroyed */
528 0, /* todo_flags_start */
529 0, /* todo_flags_finish */
530 }
531 };
532