1 /* Callgraph handling code.
2 Copyright (C) 2003, 2004 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 2, 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 COPYING. If not, write to the Free
19 Software Foundation, 59 Temple Place - Suite 330, Boston, MA
20 02111-1307, USA. */
21
22 #include "config.h"
23 #include "system.h"
24 #include "coretypes.h"
25 #include "tm.h"
26 #include "tree.h"
27 #include "langhooks.h"
28 #include "hashtab.h"
29 #include "toplev.h"
30 #include "flags.h"
31 #include "ggc.h"
32 #include "debug.h"
33 #include "target.h"
34 #include "cgraph.h"
35 #include "varray.h"
36 #include "output.h"
37 #include "intl.h"
38
39
40 /* Hash table used to convert declarations into nodes. */
41 static GTY((param_is (struct cgraph_node))) htab_t cgraph_hash;
42
43 /* The linked list of cgraph nodes. */
44 struct cgraph_node *cgraph_nodes;
45
46 /* Queue of cgraph nodes scheduled to be lowered. */
47 struct cgraph_node *cgraph_nodes_queue;
48
49 /* Number of nodes in existence. */
50 int cgraph_n_nodes;
51
52 /* Maximal uid used in cgraph nodes. */
53 int cgraph_max_uid;
54
55 /* Set when whole unit has been analyzed so we can access global info. */
56 bool cgraph_global_info_ready = false;
57
58 /* Hash table used to convert declarations into nodes. */
59 static GTY((param_is (struct cgraph_varpool_node))) htab_t cgraph_varpool_hash;
60
61 /* Queue of cgraph nodes scheduled to be lowered and output. */
62 struct cgraph_varpool_node *cgraph_varpool_nodes_queue;
63
64 /* Number of nodes in existence. */
65 int cgraph_varpool_n_nodes;
66
67 /* The linked list of cgraph varpool nodes. */
68 static GTY(()) struct cgraph_varpool_node *cgraph_varpool_nodes;
69
70 static struct cgraph_edge *create_edge (struct cgraph_node *,
71 struct cgraph_node *);
72 static hashval_t hash_node (const void *);
73 static int eq_node (const void *, const void *);
74
75 /* Returns a hash code for P. */
76
77 static hashval_t
hash_node(const void * p)78 hash_node (const void *p)
79 {
80 return ((hashval_t)
81 IDENTIFIER_HASH_VALUE (DECL_ASSEMBLER_NAME
82 (((struct cgraph_node *) p)->decl)));
83 }
84
85 /* Returns nonzero if P1 and P2 are equal. */
86
87 static int
eq_node(const void * p1,const void * p2)88 eq_node (const void *p1, const void *p2)
89 {
90 return ((DECL_ASSEMBLER_NAME (((struct cgraph_node *) p1)->decl)) ==
91 (tree) p2);
92 }
93
94 /* Return cgraph node assigned to DECL. Create new one when needed. */
95 struct cgraph_node *
cgraph_node(tree decl)96 cgraph_node (tree decl)
97 {
98 struct cgraph_node *node;
99 struct cgraph_node **slot;
100
101 if (TREE_CODE (decl) != FUNCTION_DECL)
102 abort ();
103
104 if (!cgraph_hash)
105 cgraph_hash = htab_create_ggc (10, hash_node, eq_node, NULL);
106
107 slot = (struct cgraph_node **)
108 htab_find_slot_with_hash (cgraph_hash, DECL_ASSEMBLER_NAME (decl),
109 IDENTIFIER_HASH_VALUE
110 (DECL_ASSEMBLER_NAME (decl)), INSERT);
111 if (*slot)
112 return *slot;
113 node = ggc_alloc_cleared (sizeof (*node));
114 node->decl = decl;
115 node->next = cgraph_nodes;
116 node->uid = cgraph_max_uid++;
117 if (cgraph_nodes)
118 cgraph_nodes->previous = node;
119 node->previous = NULL;
120 cgraph_nodes = node;
121 cgraph_n_nodes++;
122 *slot = node;
123 if (DECL_CONTEXT (decl) && TREE_CODE (DECL_CONTEXT (decl)) == FUNCTION_DECL)
124 {
125 node->origin = cgraph_node (DECL_CONTEXT (decl));
126 node->next_nested = node->origin->nested;
127 node->origin->nested = node;
128 }
129 return node;
130 }
131
132 /* Try to find existing function for identifier ID. */
133 struct cgraph_node *
cgraph_node_for_identifier(tree id)134 cgraph_node_for_identifier (tree id)
135 {
136 struct cgraph_node **slot;
137
138 if (TREE_CODE (id) != IDENTIFIER_NODE)
139 abort ();
140
141 if (!cgraph_hash)
142 return NULL;
143
144 slot = (struct cgraph_node **)
145 htab_find_slot_with_hash (cgraph_hash, id,
146 IDENTIFIER_HASH_VALUE (id), NO_INSERT);
147 if (!slot)
148 return NULL;
149 return *slot;
150 }
151
152 /* Create edge from CALLER to CALLEE in the cgraph. */
153
154 static struct cgraph_edge *
create_edge(struct cgraph_node * caller,struct cgraph_node * callee)155 create_edge (struct cgraph_node *caller, struct cgraph_node *callee)
156 {
157 struct cgraph_edge *edge = ggc_alloc (sizeof (struct cgraph_edge));
158 struct cgraph_edge *edge2;
159
160 if (!DECL_SAVED_TREE (callee->decl))
161 edge->inline_failed = N_("function body not available");
162 else if (callee->local.redefined_extern_inline)
163 edge->inline_failed = N_("redefined extern inline functions are not "
164 "considered for inlining");
165 else if (callee->local.inlinable)
166 edge->inline_failed = N_("function not considered for inlining");
167 else
168 edge->inline_failed = N_("function not inlinable");
169
170 /* At the moment we don't associate calls with specific CALL_EXPRs
171 as we probably ought to, so we must preserve inline_call flags to
172 be the same in all copies of the same edge. */
173 if (cgraph_global_info_ready)
174 for (edge2 = caller->callees; edge2; edge2 = edge2->next_callee)
175 if (edge2->callee == callee)
176 {
177 edge->inline_failed = edge2->inline_failed;
178 break;
179 }
180
181 edge->caller = caller;
182 edge->callee = callee;
183 edge->next_caller = callee->callers;
184 edge->next_callee = caller->callees;
185 caller->callees = edge;
186 callee->callers = edge;
187 return edge;
188 }
189
190 /* Remove the edge from CALLER to CALLEE in the cgraph. */
191
192 void
cgraph_remove_edge(struct cgraph_node * caller,struct cgraph_node * callee)193 cgraph_remove_edge (struct cgraph_node *caller, struct cgraph_node *callee)
194 {
195 struct cgraph_edge **edge, **edge2;
196
197 for (edge = &callee->callers; *edge && (*edge)->caller != caller;
198 edge = &((*edge)->next_caller))
199 continue;
200 if (!*edge)
201 abort ();
202 *edge = (*edge)->next_caller;
203 for (edge2 = &caller->callees; *edge2 && (*edge2)->callee != callee;
204 edge2 = &(*edge2)->next_callee)
205 continue;
206 if (!*edge2)
207 abort ();
208 *edge2 = (*edge2)->next_callee;
209 }
210
211 /* Remove the node from cgraph. */
212
213 void
cgraph_remove_node(struct cgraph_node * node)214 cgraph_remove_node (struct cgraph_node *node)
215 {
216 void **slot;
217 while (node->callers)
218 cgraph_remove_edge (node->callers->caller, node);
219 while (node->callees)
220 cgraph_remove_edge (node, node->callees->callee);
221 while (node->nested)
222 cgraph_remove_node (node->nested);
223 if (node->origin)
224 {
225 struct cgraph_node **node2 = &node->origin->nested;
226
227 while (*node2 != node)
228 node2 = &(*node2)->next_nested;
229 *node2 = node->next_nested;
230 }
231 if (node->previous)
232 node->previous->next = node->next;
233 else
234 cgraph_nodes = node->next;
235 if (node->next)
236 node->next->previous = node->previous;
237 DECL_SAVED_TREE (node->decl) = NULL;
238 DECL_SAVED_INSNS (node->decl) = NULL;
239 DECL_ARGUMENTS (node->decl) = NULL;
240 DECL_INITIAL (node->decl) = error_mark_node;
241 slot =
242 htab_find_slot_with_hash (cgraph_hash, DECL_ASSEMBLER_NAME (node->decl),
243 IDENTIFIER_HASH_VALUE (DECL_ASSEMBLER_NAME
244 (node->decl)), NO_INSERT);
245 if (slot == 0)
246 {
247 /* We use DECL_ASSEMBLER_NAME as key, which may not work in
248 all cases. See PR/15666. Gcc 3.5 uses DECL_UID as key,
249 which doesn't have this problem. */
250 if (!DECL_BUILT_IN (node->decl))
251 abort ();
252 }
253 else
254 htab_clear_slot (cgraph_hash, slot);
255 /* Do not free the structure itself so the walk over chain can continue. */
256 }
257
258 /* Notify finalize_compilation_unit that given node is reachable. */
259
260 void
cgraph_mark_reachable_node(struct cgraph_node * node)261 cgraph_mark_reachable_node (struct cgraph_node *node)
262 {
263 if (!node->reachable && node->local.finalized)
264 {
265 notice_global_symbol (node->decl);
266 node->reachable = 1;
267
268 node->next_needed = cgraph_nodes_queue;
269 cgraph_nodes_queue = node;
270
271 /* At the moment frontend automatically emits all nested functions. */
272 if (node->nested)
273 {
274 struct cgraph_node *node2;
275
276 for (node2 = node->nested; node2; node2 = node2->next_nested)
277 if (!node2->reachable)
278 cgraph_mark_reachable_node (node2);
279 }
280 }
281 }
282
283 /* Likewise indicate that a node is needed, i.e. reachable via some
284 external means. */
285
286 void
cgraph_mark_needed_node(struct cgraph_node * node)287 cgraph_mark_needed_node (struct cgraph_node *node)
288 {
289 node->needed = 1;
290 cgraph_mark_reachable_node (node);
291 }
292
293 /* Record call from CALLER to CALLEE. */
294
295 struct cgraph_edge *
cgraph_record_call(tree caller,tree callee)296 cgraph_record_call (tree caller, tree callee)
297 {
298 return create_edge (cgraph_node (caller), cgraph_node (callee));
299 }
300
301 void
cgraph_remove_call(tree caller,tree callee)302 cgraph_remove_call (tree caller, tree callee)
303 {
304 cgraph_remove_edge (cgraph_node (caller), cgraph_node (callee));
305 }
306
307 /* Return true when CALLER_DECL calls CALLEE_DECL. */
308
309 bool
cgraph_calls_p(tree caller_decl,tree callee_decl)310 cgraph_calls_p (tree caller_decl, tree callee_decl)
311 {
312 struct cgraph_node *caller = cgraph_node (caller_decl);
313 struct cgraph_node *callee = cgraph_node (callee_decl);
314 struct cgraph_edge *edge;
315
316 for (edge = callee->callers; edge && (edge)->caller != caller;
317 edge = (edge->next_caller))
318 continue;
319 return edge != NULL;
320 }
321
322 /* Return local info for the compiled function. */
323
324 struct cgraph_local_info *
cgraph_local_info(tree decl)325 cgraph_local_info (tree decl)
326 {
327 struct cgraph_node *node;
328 if (TREE_CODE (decl) != FUNCTION_DECL)
329 abort ();
330 node = cgraph_node (decl);
331 return &node->local;
332 }
333
334 /* Return local info for the compiled function. */
335
336 struct cgraph_global_info *
cgraph_global_info(tree decl)337 cgraph_global_info (tree decl)
338 {
339 struct cgraph_node *node;
340 if (TREE_CODE (decl) != FUNCTION_DECL || !cgraph_global_info_ready)
341 abort ();
342 node = cgraph_node (decl);
343 return &node->global;
344 }
345
346 /* Return local info for the compiled function. */
347
348 struct cgraph_rtl_info *
cgraph_rtl_info(tree decl)349 cgraph_rtl_info (tree decl)
350 {
351 struct cgraph_node *node;
352 if (TREE_CODE (decl) != FUNCTION_DECL)
353 abort ();
354 node = cgraph_node (decl);
355 if (decl != current_function_decl
356 && !TREE_ASM_WRITTEN (node->decl))
357 return NULL;
358 return &node->rtl;
359 }
360
361 /* Return name of the node used in debug output. */
362 const char *
cgraph_node_name(struct cgraph_node * node)363 cgraph_node_name (struct cgraph_node *node)
364 {
365 return (*lang_hooks.decl_printable_name) (node->decl, 2);
366 }
367
368 /* Dump the callgraph. */
369
370 void
dump_cgraph(FILE * f)371 dump_cgraph (FILE *f)
372 {
373 struct cgraph_node *node;
374
375 fprintf (f, "callgraph:\n\n");
376 for (node = cgraph_nodes; node; node = node->next)
377 {
378 struct cgraph_edge *edge;
379 fprintf (f, "%s:", cgraph_node_name (node));
380 if (node->local.self_insns)
381 fprintf (f, " %i insns", node->local.self_insns);
382 if (node->global.insns && node->global.insns != node->local.self_insns)
383 fprintf (f, " (%i after inlining)", node->global.insns);
384 if (node->origin)
385 fprintf (f, " nested in: %s", cgraph_node_name (node->origin));
386 if (node->needed)
387 fprintf (f, " needed");
388 else if (node->reachable)
389 fprintf (f, " reachable");
390 if (DECL_SAVED_TREE (node->decl))
391 fprintf (f, " tree");
392
393 if (node->local.local)
394 fprintf (f, " local");
395 if (node->local.disregard_inline_limits)
396 fprintf (f, " always_inline");
397 else if (node->local.inlinable)
398 fprintf (f, " inlinable");
399 if (node->global.cloned_times > 1)
400 fprintf (f, " cloned %ix", node->global.cloned_times);
401
402 fprintf (f, "\n called by: ");
403 for (edge = node->callers; edge; edge = edge->next_caller)
404 {
405 fprintf (f, "%s ", cgraph_node_name (edge->caller));
406 if (!edge->inline_failed)
407 fprintf(f, "(inlined) ");
408 }
409
410 fprintf (f, "\n calls: ");
411 for (edge = node->callees; edge; edge = edge->next_callee)
412 {
413 fprintf (f, "%s ", cgraph_node_name (edge->callee));
414 if (!edge->inline_failed)
415 fprintf(f, "(inlined) ");
416 }
417 fprintf (f, "\n");
418 }
419 }
420
421 /* Returns a hash code for P. */
422
423 static hashval_t
cgraph_varpool_hash_node(const void * p)424 cgraph_varpool_hash_node (const void *p)
425 {
426 return ((hashval_t)
427 IDENTIFIER_HASH_VALUE (DECL_ASSEMBLER_NAME
428 (((struct cgraph_varpool_node *) p)->decl)));
429 }
430
431 /* Returns nonzero if P1 and P2 are equal. */
432
433 static int
eq_cgraph_varpool_node(const void * p1,const void * p2)434 eq_cgraph_varpool_node (const void *p1, const void *p2)
435 {
436 return ((DECL_ASSEMBLER_NAME (((struct cgraph_varpool_node *) p1)->decl)) ==
437 (tree) p2);
438 }
439
440 /* Return cgraph_varpool node assigned to DECL. Create new one when needed. */
441 struct cgraph_varpool_node *
cgraph_varpool_node(tree decl)442 cgraph_varpool_node (tree decl)
443 {
444 struct cgraph_varpool_node *node;
445 struct cgraph_varpool_node **slot;
446
447 if (!DECL_P (decl) || TREE_CODE (decl) == FUNCTION_DECL)
448 abort ();
449
450 if (!cgraph_varpool_hash)
451 cgraph_varpool_hash = htab_create_ggc (10, cgraph_varpool_hash_node,
452 eq_cgraph_varpool_node, NULL);
453 slot = (struct cgraph_varpool_node **)
454 htab_find_slot_with_hash (cgraph_varpool_hash, DECL_ASSEMBLER_NAME (decl),
455 IDENTIFIER_HASH_VALUE (DECL_ASSEMBLER_NAME (decl)),
456 INSERT);
457 if (*slot)
458 return *slot;
459 node = ggc_alloc_cleared (sizeof (*node));
460 node->decl = decl;
461 cgraph_varpool_n_nodes++;
462 cgraph_varpool_nodes = node;
463 *slot = node;
464 return node;
465 }
466
467 /* Set the DECL_ASSEMBLER_NAME and update cgraph hashtables. */
468 void
change_decl_assembler_name(tree decl,tree name)469 change_decl_assembler_name (tree decl, tree name)
470 {
471 struct cgraph_node *node = NULL;
472 struct cgraph_varpool_node *vnode = NULL;
473 void **slot;
474
475 if (!DECL_ASSEMBLER_NAME_SET_P (decl))
476 {
477 SET_DECL_ASSEMBLER_NAME (decl, name);
478 return;
479 }
480 if (name == DECL_ASSEMBLER_NAME (decl))
481 return;
482
483 if (TREE_SYMBOL_REFERENCED (DECL_ASSEMBLER_NAME (decl))
484 && DECL_RTL_SET_P (decl))
485 warning ("%D renamed after being referenced in assembly", decl);
486
487 if (TREE_CODE (decl) == FUNCTION_DECL && cgraph_hash)
488 {
489 /* Take a look whether declaration is in the cgraph structure. */
490 slot =
491 htab_find_slot_with_hash (cgraph_hash, DECL_ASSEMBLER_NAME (decl),
492 IDENTIFIER_HASH_VALUE (DECL_ASSEMBLER_NAME
493 (decl)), NO_INSERT);
494 if (slot)
495 node = *slot;
496
497 /* It is, verify that we are the canonical node for this decl. */
498 if (node && node->decl == decl)
499 {
500 node = *slot;
501 htab_clear_slot (cgraph_hash, slot);
502 }
503 else
504 node = NULL;
505 }
506 if (TREE_CODE (decl) == VAR_DECL && TREE_STATIC (decl) && cgraph_varpool_hash)
507 {
508 /* Take a look whether declaration is in the cgraph structure. */
509 slot =
510 htab_find_slot_with_hash (cgraph_varpool_hash, DECL_ASSEMBLER_NAME (decl),
511 IDENTIFIER_HASH_VALUE (DECL_ASSEMBLER_NAME
512 (decl)), NO_INSERT);
513 if (slot)
514 vnode = *slot;
515
516 /* It is, verify that we are the canonical vnode for this decl. */
517 if (vnode && vnode->decl == decl)
518 {
519 vnode = *slot;
520 htab_clear_slot (cgraph_varpool_hash, slot);
521 }
522 else
523 vnode = NULL;
524 }
525 SET_DECL_ASSEMBLER_NAME (decl, name);
526 if (node)
527 {
528 slot =
529 htab_find_slot_with_hash (cgraph_hash, name,
530 IDENTIFIER_HASH_VALUE (name), INSERT);
531 if (*slot)
532 abort ();
533 *slot = node;
534 }
535 if (vnode)
536 {
537 slot =
538 htab_find_slot_with_hash (cgraph_varpool_hash, name,
539 IDENTIFIER_HASH_VALUE (name), INSERT);
540 if (*slot)
541 abort ();
542 *slot = vnode;
543 }
544 }
545
546 /* Try to find existing function for identifier ID. */
547 struct cgraph_varpool_node *
cgraph_varpool_node_for_identifier(tree id)548 cgraph_varpool_node_for_identifier (tree id)
549 {
550 struct cgraph_varpool_node **slot;
551
552 if (TREE_CODE (id) != IDENTIFIER_NODE)
553 abort ();
554
555 if (!cgraph_varpool_hash)
556 return NULL;
557
558 slot = (struct cgraph_varpool_node **)
559 htab_find_slot_with_hash (cgraph_varpool_hash, id,
560 IDENTIFIER_HASH_VALUE (id), NO_INSERT);
561 if (!slot)
562 return NULL;
563 return *slot;
564 }
565
566 /* Notify finalize_compilation_unit that given node is reachable
567 or needed. */
568 void
cgraph_varpool_mark_needed_node(struct cgraph_varpool_node * node)569 cgraph_varpool_mark_needed_node (struct cgraph_varpool_node *node)
570 {
571 if (!node->needed && node->finalized)
572 {
573 node->next_needed = cgraph_varpool_nodes_queue;
574 cgraph_varpool_nodes_queue = node;
575 notice_global_symbol (node->decl);
576 }
577 node->needed = 1;
578 }
579
580 void
cgraph_varpool_finalize_decl(tree decl)581 cgraph_varpool_finalize_decl (tree decl)
582 {
583 struct cgraph_varpool_node *node = cgraph_varpool_node (decl);
584
585 /* The first declaration of a variable that comes through this function
586 decides whether it is global (in C, has external linkage)
587 or local (in C, has internal linkage). So do nothing more
588 if this function has already run. */
589 if (node->finalized)
590 return;
591 if (node->needed)
592 {
593 node->next_needed = cgraph_varpool_nodes_queue;
594 cgraph_varpool_nodes_queue = node;
595 notice_global_symbol (decl);
596 }
597 node->finalized = true;
598
599 if (/* Externally visible variables must be output. The exception are
600 COMDAT functions that must be output only when they are needed. */
601 (TREE_PUBLIC (decl) && !DECL_COMDAT (decl))
602 /* Function whose name is output to the assembler file must be produced.
603 It is possible to assemble the name later after finalizing the function
604 and the fact is noticed in assemble_name then. */
605 || (DECL_ASSEMBLER_NAME_SET_P (decl)
606 && TREE_SYMBOL_REFERENCED (DECL_ASSEMBLER_NAME (decl))))
607 {
608 cgraph_varpool_mark_needed_node (node);
609 }
610 }
611
612 bool
cgraph_varpool_assemble_pending_decls(void)613 cgraph_varpool_assemble_pending_decls (void)
614 {
615 bool changed = false;
616
617 while (cgraph_varpool_nodes_queue)
618 {
619 tree decl = cgraph_varpool_nodes_queue->decl;
620 struct cgraph_varpool_node *node = cgraph_varpool_nodes_queue;
621
622 cgraph_varpool_nodes_queue = cgraph_varpool_nodes_queue->next_needed;
623 if (!TREE_ASM_WRITTEN (decl))
624 {
625 assemble_variable (decl, 0, 1, 0);
626 changed = true;
627 }
628 node->next_needed = NULL;
629 }
630 return changed;
631 }
632
633 /* Return true when the DECL can possibly be inlined. */
634 bool
cgraph_function_possibly_inlined_p(tree decl)635 cgraph_function_possibly_inlined_p (tree decl)
636 {
637 if (!cgraph_global_info_ready)
638 return (DECL_INLINE (decl)
639 && (!flag_really_no_inline
640 || (*lang_hooks.tree_inlining.disregard_inline_limits) (decl)));
641 return cgraph_node (decl)->global.inlined;
642 }
643
644 #include "gt-cgraph.h"
645