1 /* Callgraph handling code.
2 Copyright (C) 2003, 2004, 2005, 2006, 2007, 2008, 2010, 2011
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/>. */
24 #include "coretypes.h"
28 #include "langhooks.h"
29 #include "diagnostic-core.h"
37 #include "tree-flow.h"
40 /* This file contains basic routines manipulating variable pool.
42 Varpool acts as interface in between the front-end and middle-end
43 and drives the decision process on what variables and when are
46 The varpool nodes are allocated lazily for declarations
47 either by frontend or at callgraph construction time.
48 All variables supposed to be output into final file needs to be
49 explicitly marked by frontend via VARPOOL_FINALIZE_DECL function. */
51 /* Queue of cgraph nodes scheduled to be lowered and output.
52 The queue is maintained via mark_needed_node, linked via node->next_needed
55 LAST_NEEDED_NODE points to the end of queue, so it can be
56 maintained in forward order. GTY is needed to make it friendly to
59 During compilation we construct the queue of needed variables
60 twice: first time it is during cgraph construction, second time it is at the
61 end of compilation in VARPOOL_REMOVE_UNREFERENCED_DECLS so we can avoid
62 optimized out variables being output.
64 Each variable is thus first analyzed and then later possibly output.
65 FIRST_UNANALYZED_NODE points to first node in queue that was not analyzed
66 yet and is moved via VARPOOL_ANALYZE_PENDING_DECLS. */
68 symtab_node x_varpool_nodes_queue
;
69 static GTY(()) symtab_node x_varpool_last_needed_node
;
70 #define varpool_last_needed_node ((struct varpool_node *)x_varpool_last_needed_node)
71 static GTY(()) symtab_node x_varpool_first_unanalyzed_node
;
72 #define varpool_first_unanalyzed_node ((struct varpool_node *)x_varpool_first_unanalyzed_node)
74 /* Lists all assembled variables to be sent to debugger output later on. */
75 static GTY(()) struct varpool_node
*varpool_assembled_nodes_queue
;
77 /* Return varpool node assigned to DECL. Create new one when needed. */
79 varpool_node (tree decl
)
81 struct varpool_node
*node
= varpool_get_node (decl
);
82 gcc_assert (TREE_CODE (decl
) == VAR_DECL
83 && (TREE_STATIC (decl
) || DECL_EXTERNAL (decl
) || in_lto_p
));
87 node
= ggc_alloc_cleared_varpool_node ();
88 node
->symbol
.type
= SYMTAB_VARIABLE
;
89 node
->symbol
.decl
= decl
;
90 symtab_register_node ((symtab_node
)node
);
94 /* Remove node from the varpool. */
96 varpool_remove_node (struct varpool_node
*node
)
98 gcc_assert (!varpool_assembled_nodes_queue
);
99 symtab_unregister_node ((symtab_node
)node
);
100 if (varpool_first_unanalyzed_node
== node
)
101 x_varpool_first_unanalyzed_node
= (symtab_node
)node
->next_needed
;
102 if (node
->next_needed
)
103 node
->next_needed
->prev_needed
= node
->prev_needed
;
104 else if (node
->prev_needed
)
106 gcc_assert (varpool_last_needed_node
);
107 x_varpool_last_needed_node
= (symtab_node
)node
->prev_needed
;
109 if (node
->prev_needed
)
110 node
->prev_needed
->next_needed
= node
->next_needed
;
111 else if (node
->next_needed
)
113 gcc_assert (varpool_nodes_queue
== node
);
114 x_varpool_nodes_queue
= (symtab_node
)node
->next_needed
;
119 /* Dump given cgraph node. */
121 dump_varpool_node (FILE *f
, struct varpool_node
*node
)
123 dump_symtab_base (f
, (symtab_node
)node
);
124 fprintf (f
, " Availability: %s\n",
125 cgraph_function_flags_ready
126 ? cgraph_availability_names
[cgraph_variable_initializer_availability (node
)]
128 fprintf (f
, " Varpool flags:");
129 if (DECL_INITIAL (node
->symbol
.decl
))
130 fprintf (f
, " initialized");
132 fprintf (f
, " needed");
134 fprintf (f
, " analyzed");
136 fprintf (f
, " finalized");
138 fprintf (f
, " output");
142 /* Dump the variable pool. */
144 dump_varpool (FILE *f
)
146 struct varpool_node
*node
;
148 fprintf (f
, "variable pool:\n\n");
149 FOR_EACH_VARIABLE (node
)
150 dump_varpool_node (f
, node
);
153 /* Dump the variable pool to stderr. */
158 dump_varpool (stderr
);
161 /* Given an assembler name, lookup node. */
162 struct varpool_node
*
163 varpool_node_for_asm (tree asmname
)
165 symtab_node node
= symtab_node_for_asm (asmname
);
166 if (node
&& symtab_variable_p (node
))
167 return varpool (node
);
171 /* Helper function for finalization code - add node into lists so it will
172 be analyzed and compiled. */
174 varpool_enqueue_needed_node (struct varpool_node
*node
)
176 if (varpool_last_needed_node
)
178 varpool_last_needed_node
->next_needed
= node
;
179 node
->prev_needed
= varpool_last_needed_node
;
181 x_varpool_last_needed_node
= (symtab_node
)node
;
182 node
->next_needed
= NULL
;
183 if (!varpool_nodes_queue
)
184 x_varpool_nodes_queue
= (symtab_node
)node
;
185 if (!varpool_first_unanalyzed_node
)
186 x_varpool_first_unanalyzed_node
= (symtab_node
)node
;
187 notice_global_symbol (node
->symbol
.decl
);
190 /* Notify finalize_compilation_unit that given node is reachable
193 varpool_mark_needed_node (struct varpool_node
*node
)
195 if (!node
->needed
&& node
->finalized
196 && !TREE_ASM_WRITTEN (node
->symbol
.decl
))
197 varpool_enqueue_needed_node (node
);
201 /* Reset the queue of needed nodes. */
203 varpool_reset_queue (void)
205 x_varpool_last_needed_node
= NULL
;
206 x_varpool_nodes_queue
= NULL
;
207 x_varpool_first_unanalyzed_node
= NULL
;
210 /* Determine if variable DECL is needed. That is, visible to something
211 either outside this translation unit, something magic in the system
214 decide_is_variable_needed (struct varpool_node
*node
, tree decl
)
216 /* If the user told us it is used, then it must be so. */
217 if (node
->force_output
)
220 gcc_assert (!DECL_EXTERNAL (decl
));
222 /* Externally visible variables must be output. The exception is
223 COMDAT variables that must be output only when they are needed. */
224 if (TREE_PUBLIC (decl
)
225 && !DECL_COMDAT (decl
)
226 && !DECL_EXTERNAL (decl
))
232 /* Return if DECL is constant and its initial value is known (so we can do
233 constant folding using DECL_INITIAL (decl)). */
236 const_value_known_p (tree decl
)
238 if (TREE_CODE (decl
) != VAR_DECL
239 &&TREE_CODE (decl
) != CONST_DECL
)
242 if (TREE_CODE (decl
) == CONST_DECL
243 || DECL_IN_CONSTANT_POOL (decl
))
246 gcc_assert (TREE_CODE (decl
) == VAR_DECL
);
248 if (!TREE_READONLY (decl
) || TREE_THIS_VOLATILE (decl
))
251 /* Gimplifier takes away constructors of local vars */
252 if (!TREE_STATIC (decl
) && !DECL_EXTERNAL (decl
))
253 return DECL_INITIAL (decl
) != NULL
;
255 gcc_assert (TREE_STATIC (decl
) || DECL_EXTERNAL (decl
));
257 /* Variables declared 'const' without an initializer
258 have zero as the initializer if they may not be
259 overridden at link or run time. */
260 if (!DECL_INITIAL (decl
)
261 && (DECL_EXTERNAL (decl
)
262 || decl_replaceable_p (decl
)))
265 /* Variables declared `const' with an initializer are considered
266 to not be overwritable with different initializer by default.
268 ??? Previously we behaved so for scalar variables but not for array
273 /* Mark DECL as finalized. By finalizing the declaration, frontend instruct the
274 middle end to output the variable to asm file, if needed or externally
277 varpool_finalize_decl (tree decl
)
279 struct varpool_node
*node
= varpool_node (decl
);
281 gcc_assert (TREE_STATIC (decl
));
283 /* The first declaration of a variable that comes through this function
284 decides whether it is global (in C, has external linkage)
285 or local (in C, has internal linkage). So do nothing more
286 if this function has already run. */
289 if (cgraph_global_info_ready
)
290 varpool_assemble_pending_decls ();
294 varpool_enqueue_needed_node (node
);
295 node
->finalized
= true;
296 if (TREE_THIS_VOLATILE (decl
) || DECL_PRESERVE_P (decl
)
297 /* Traditionally we do not eliminate static variables when not
298 optimizing and when not doing toplevel reoder. */
299 || (!flag_toplevel_reorder
&& !DECL_COMDAT (node
->symbol
.decl
)
300 && !DECL_ARTIFICIAL (node
->symbol
.decl
)))
301 node
->force_output
= true;
303 if (decide_is_variable_needed (node
, decl
))
304 varpool_mark_needed_node (node
);
305 if (cgraph_global_info_ready
)
306 varpool_assemble_pending_decls ();
309 /* Add the variable DECL to the varpool.
310 Unlike varpool_finalize_decl function is intended to be used
311 by middle end and allows insertion of new variable at arbitrary point
314 varpool_add_new_variable (tree decl
)
316 struct varpool_node
*node
;
317 varpool_finalize_decl (decl
);
318 node
= varpool_node (decl
);
319 if (varpool_externally_visible_p (node
, false))
320 node
->symbol
.externally_visible
= true;
323 /* Return variable availability. See cgraph.h for description of individual
326 cgraph_variable_initializer_availability (struct varpool_node
*node
)
328 gcc_assert (cgraph_function_flags_ready
);
329 if (!node
->finalized
)
330 return AVAIL_NOT_AVAILABLE
;
331 if (!TREE_PUBLIC (node
->symbol
.decl
))
332 return AVAIL_AVAILABLE
;
333 /* If the variable can be overwritten, return OVERWRITABLE. Takes
334 care of at least two notable extensions - the COMDAT variables
335 used to share template instantiations in C++. */
336 if (!decl_replaceable_p (node
->symbol
.decl
))
337 return AVAIL_OVERWRITABLE
;
338 return AVAIL_AVAILABLE
;
341 /* Walk the decls we marked as necessary and see if they reference new
342 variables or functions and add them into the worklists. */
344 varpool_analyze_pending_decls (void)
346 bool changed
= false;
348 timevar_push (TV_VARPOOL
);
349 while (varpool_first_unanalyzed_node
)
351 struct varpool_node
*node
= varpool_first_unanalyzed_node
, *next
;
352 tree decl
= node
->symbol
.decl
;
353 bool analyzed
= node
->analyzed
;
355 varpool_first_unanalyzed_node
->analyzed
= true;
357 x_varpool_first_unanalyzed_node
= (symtab_node
)varpool_first_unanalyzed_node
->next_needed
;
359 /* When reading back varpool at LTO time, we re-construct the queue in order
360 to have "needed" list right by inserting all needed nodes into varpool.
361 We however don't want to re-analyze already analyzed nodes. */
364 gcc_assert (!in_lto_p
|| cgraph_function_flags_ready
);
365 /* Compute the alignment early so function body expanders are
366 already informed about increased alignment. */
367 align_variable (decl
, 0);
369 if (node
->alias
&& node
->alias_of
)
371 struct varpool_node
*tgt
= varpool_node (node
->alias_of
);
372 struct varpool_node
*n
;
374 for (n
= tgt
; n
&& n
->alias
;
375 n
= n
->analyzed
? varpool_alias_aliased_node (n
) : NULL
)
378 error ("variable %q+D part of alias cycle", node
->symbol
.decl
);
382 if (!VEC_length (ipa_ref_t
, node
->symbol
.ref_list
.references
))
383 ipa_record_reference (NULL
, node
, NULL
, tgt
, IPA_REF_ALIAS
, NULL
);
384 /* C++ FE sometimes change linkage flags after producing same body aliases. */
385 if (node
->extra_name_alias
)
387 DECL_WEAK (node
->symbol
.decl
) = DECL_WEAK (node
->alias_of
);
388 TREE_PUBLIC (node
->symbol
.decl
) = TREE_PUBLIC (node
->alias_of
);
389 DECL_EXTERNAL (node
->symbol
.decl
) = DECL_EXTERNAL (node
->alias_of
);
390 DECL_VISIBILITY (node
->symbol
.decl
) = DECL_VISIBILITY (node
->alias_of
);
391 if (TREE_PUBLIC (node
->symbol
.decl
))
393 DECL_COMDAT (node
->symbol
.decl
) = DECL_COMDAT (node
->alias_of
);
394 DECL_COMDAT_GROUP (node
->symbol
.decl
) = DECL_COMDAT_GROUP (node
->alias_of
);
395 if (DECL_ONE_ONLY (node
->alias_of
)
396 && !node
->symbol
.same_comdat_group
)
398 node
->symbol
.same_comdat_group
= (symtab_node
)tgt
;
399 if (!tgt
->symbol
.same_comdat_group
)
400 tgt
->symbol
.same_comdat_group
= (symtab_node
)node
;
404 for (n
= tgt
->symbol
.same_comdat_group
;
405 n
->symbol
.same_comdat_group
!= (symtab_node
)tgt
;
406 n
= n
->symbol
.same_comdat_group
)
408 n
->symbol
.same_comdat_group
= (symtab_node
)node
;
414 else if (DECL_INITIAL (decl
))
415 record_references_in_initializer (decl
, analyzed
);
416 if (node
->symbol
.same_comdat_group
)
418 for (next
= varpool (node
->symbol
.same_comdat_group
);
420 next
= varpool (next
->symbol
.same_comdat_group
))
421 varpool_mark_needed_node (next
);
425 timevar_pop (TV_VARPOOL
);
429 /* Assemble thunks and aliases asociated to NODE. */
432 assemble_aliases (struct varpool_node
*node
)
436 for (i
= 0; ipa_ref_list_refering_iterate (&node
->symbol
.ref_list
, i
, ref
); i
++)
437 if (ref
->use
== IPA_REF_ALIAS
)
439 struct varpool_node
*alias
= ipa_ref_refering_varpool_node (ref
);
440 assemble_alias (alias
->symbol
.decl
,
441 DECL_ASSEMBLER_NAME (alias
->alias_of
));
442 assemble_aliases (alias
);
446 /* Output one variable, if necessary. Return whether we output it. */
448 varpool_assemble_decl (struct varpool_node
*node
)
450 tree decl
= node
->symbol
.decl
;
452 if (!TREE_ASM_WRITTEN (decl
)
454 && !node
->symbol
.in_other_partition
455 && !DECL_EXTERNAL (decl
)
456 && (TREE_CODE (decl
) != VAR_DECL
|| !DECL_HAS_VALUE_EXPR_P (decl
)))
458 assemble_variable (decl
, 0, 1, 0);
459 if (TREE_ASM_WRITTEN (decl
))
461 node
->next_needed
= varpool_assembled_nodes_queue
;
462 node
->prev_needed
= NULL
;
463 if (varpool_assembled_nodes_queue
)
464 varpool_assembled_nodes_queue
->prev_needed
= node
;
465 varpool_assembled_nodes_queue
= node
;
467 assemble_aliases (node
);
475 /* Optimization of function bodies might've rendered some variables as
476 unnecessary so we want to avoid these from being compiled.
478 This is done by pruning the queue and keeping only the variables that
479 really appear needed (ie they are either externally visible or referenced
480 by compiled function). Re-doing the reachability analysis on variables
481 brings back the remaining variables referenced by these. */
483 varpool_remove_unreferenced_decls (void)
485 struct varpool_node
*next
, *node
= varpool_nodes_queue
;
487 varpool_reset_queue ();
494 next
= node
->next_needed
;
498 && (!varpool_can_remove_if_no_refs (node
)
499 /* We just expanded all function bodies. See if any of
500 them needed the variable. */
501 || DECL_RTL_SET_P (node
->symbol
.decl
)))
502 varpool_mark_needed_node (node
);
506 /* Make sure we mark alias targets as used targets. */
508 varpool_analyze_pending_decls ();
511 /* For variables in named sections make sure get_variable_section
512 is called before we switch to those sections. Then section
513 conflicts between read-only and read-only requiring relocations
514 sections can be resolved. */
516 varpool_finalize_named_section_flags (struct varpool_node
*node
)
518 if (!TREE_ASM_WRITTEN (node
->symbol
.decl
)
520 && !node
->symbol
.in_other_partition
521 && !DECL_EXTERNAL (node
->symbol
.decl
)
522 && TREE_CODE (node
->symbol
.decl
) == VAR_DECL
523 && !DECL_HAS_VALUE_EXPR_P (node
->symbol
.decl
)
524 && DECL_SECTION_NAME (node
->symbol
.decl
))
525 get_variable_section (node
->symbol
.decl
, false);
528 /* Output all variables enqueued to be assembled. */
530 varpool_assemble_pending_decls (void)
532 bool changed
= false;
533 struct varpool_node
*node
;
538 timevar_push (TV_VAROUT
);
539 /* EH might mark decls as needed during expansion. This should be safe since
540 we don't create references to new function, but it should not be used
542 varpool_analyze_pending_decls ();
544 FOR_EACH_DEFINED_VARIABLE (node
)
545 varpool_finalize_named_section_flags (node
);
547 while (varpool_nodes_queue
)
549 struct varpool_node
*node
= varpool_nodes_queue
;
551 x_varpool_nodes_queue
= (symtab_node
)(varpool_nodes_queue
->next_needed
);
552 if (varpool_assemble_decl (node
))
556 node
->prev_needed
= NULL
;
557 node
->next_needed
= NULL
;
560 /* varpool_nodes_queue is now empty, clear the pointer to the last element
562 x_varpool_last_needed_node
= NULL
;
563 timevar_pop (TV_VAROUT
);
567 /* Remove all elements from the queue so we can re-use it for debug output. */
569 varpool_empty_needed_queue (void)
571 /* EH might mark decls as needed during expansion. This should be safe since
572 we don't create references to new function, but it should not be used
574 varpool_analyze_pending_decls ();
576 while (varpool_nodes_queue
)
578 struct varpool_node
*node
= varpool_nodes_queue
;
579 x_varpool_nodes_queue
= (symtab_node
)varpool_nodes_queue
->next_needed
;
580 node
->next_needed
= NULL
;
581 node
->prev_needed
= NULL
;
583 /* varpool_nodes_queue is now empty, clear the pointer to the last element
585 x_varpool_last_needed_node
= NULL
;
588 /* Create a new global variable of type TYPE. */
590 add_new_static_var (tree type
)
593 struct varpool_node
*new_node
;
595 new_decl
= create_tmp_var (type
, NULL
);
596 DECL_NAME (new_decl
) = create_tmp_var_name (NULL
);
597 TREE_READONLY (new_decl
) = 0;
598 TREE_STATIC (new_decl
) = 1;
599 TREE_USED (new_decl
) = 1;
600 DECL_CONTEXT (new_decl
) = NULL_TREE
;
601 DECL_ABSTRACT (new_decl
) = 0;
602 lang_hooks
.dup_lang_specific_decl (new_decl
);
603 create_var_ann (new_decl
);
604 new_node
= varpool_node (new_decl
);
605 varpool_mark_needed_node (new_node
);
606 add_referenced_var (new_decl
);
607 varpool_finalize_decl (new_decl
);
609 return new_node
->symbol
.decl
;
612 /* Attempt to mark ALIAS as an alias to DECL. Return TRUE if successful.
613 Extra name aliases are output whenever DECL is output. */
615 struct varpool_node
*
616 varpool_create_variable_alias (tree alias
, tree decl
)
618 struct varpool_node
*alias_node
;
620 gcc_assert (TREE_CODE (decl
) == VAR_DECL
);
621 gcc_assert (TREE_CODE (alias
) == VAR_DECL
);
622 alias_node
= varpool_node (alias
);
623 alias_node
->alias
= 1;
624 if (!DECL_EXTERNAL (alias
))
625 alias_node
->finalized
= 1;
626 alias_node
->alias_of
= decl
;
627 if ((!DECL_EXTERNAL (alias
)
628 && decide_is_variable_needed (alias_node
, alias
))
629 || alias_node
->needed
)
630 varpool_mark_needed_node (alias_node
);
634 /* Attempt to mark ALIAS as an alias to DECL. Return TRUE if successful.
635 Extra name aliases are output whenever DECL is output. */
637 struct varpool_node
*
638 varpool_extra_name_alias (tree alias
, tree decl
)
640 struct varpool_node
*alias_node
;
642 #ifndef ASM_OUTPUT_DEF
643 /* If aliases aren't supported by the assembler, fail. */
646 alias_node
= varpool_create_variable_alias (alias
, decl
);
647 alias_node
->extra_name_alias
= true;
651 /* Return true when NODE is known to be used from other (non-LTO) object file.
652 Known only when doing LTO via linker plugin. */
655 varpool_used_from_object_file_p (struct varpool_node
*node
)
657 if (!TREE_PUBLIC (node
->symbol
.decl
))
659 if (resolution_used_from_other_file_p (node
->symbol
.resolution
))
664 /* Call calback on NODE and aliases asociated to NODE.
665 When INCLUDE_OVERWRITABLE is false, overwritable aliases and thunks are
669 varpool_for_node_and_aliases (struct varpool_node
*node
,
670 bool (*callback
) (struct varpool_node
*, void *),
672 bool include_overwritable
)
677 if (callback (node
, data
))
679 for (i
= 0; ipa_ref_list_refering_iterate (&node
->symbol
.ref_list
, i
, ref
); i
++)
680 if (ref
->use
== IPA_REF_ALIAS
)
682 struct varpool_node
*alias
= ipa_ref_refering_varpool_node (ref
);
683 if (include_overwritable
684 || cgraph_variable_initializer_availability (alias
) > AVAIL_OVERWRITABLE
)
685 if (varpool_for_node_and_aliases (alias
, callback
, data
,
686 include_overwritable
))
691 #include "gt-varpool.h"