1 /* Basic IPA optimizations and utilities.
2 Copyright (C) 2003, 2004, 2005, 2007, 2008, 2009, 2010
3 Free Software Foundation, Inc.
5 This file is part of GCC.
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
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
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/>. */
23 #include "coretypes.h"
26 #include "tree-pass.h"
31 #include "pointer-set.h"
33 #include "tree-iterator.h"
35 /* Fill array order with all nodes with output flag set in the reverse
39 cgraph_postorder (struct cgraph_node **order)
41 struct cgraph_node *node, *node2;
44 struct cgraph_edge *edge, last;
47 struct cgraph_node **stack =
48 XCNEWVEC (struct cgraph_node *, cgraph_n_nodes);
50 /* We have to deal with cycles nicely, so use a depth first traversal
51 output algorithm. Ignore the fact that some functions won't need
52 to be output and put them into order as well, so we get dependencies
53 right through inline functions. */
54 for (node = cgraph_nodes; node; node = node->next)
56 for (pass = 0; pass < 2; pass++)
57 for (node = cgraph_nodes; node; node = node->next)
60 || (!cgraph_only_called_directly_p (node)
61 && !node->address_taken)))
67 node->aux = node->callers;
70 while (node2->aux != &last)
72 edge = (struct cgraph_edge *) node2->aux;
73 if (edge->next_caller)
74 node2->aux = edge->next_caller;
77 /* Break possible cycles involving always-inline
78 functions by ignoring edges from always-inline
79 functions to non-always-inline functions. */
80 if (edge->caller->local.disregard_inline_limits
81 && !edge->callee->local.disregard_inline_limits)
83 if (!edge->caller->aux)
85 if (!edge->caller->callers)
86 edge->caller->aux = &last;
88 edge->caller->aux = edge->caller->callers;
89 stack[stack_size++] = node2;
94 if (node2->aux == &last)
96 order[order_pos++] = node2;
98 node2 = stack[--stack_size];
105 for (node = cgraph_nodes; node; node = node->next)
110 /* Look for all functions inlined to NODE and update their inlined_to pointers
114 update_inlined_to_pointer (struct cgraph_node *node, struct cgraph_node *inlined_to)
116 struct cgraph_edge *e;
117 for (e = node->callees; e; e = e->next_callee)
118 if (e->callee->global.inlined_to)
120 e->callee->global.inlined_to = inlined_to;
121 update_inlined_to_pointer (e->callee, inlined_to);
125 /* Add cgraph NODE to queue starting at FIRST.
127 The queue is linked via AUX pointers and terminated by pointer to 1.
128 We enqueue nodes at two occasions: when we find them reachable or when we find
129 their bodies needed for further clonning. In the second case we mark them
130 by pointer to 2 after processing so they are re-queue when they become
134 enqueue_cgraph_node (struct cgraph_node *node, struct cgraph_node **first)
136 /* Node is still in queue; do nothing. */
137 if (node->aux && node->aux != (void *) 2)
139 /* Node was already processed as unreachable, re-enqueue
140 only if it became reachable now. */
141 if (node->aux == (void *)2 && !node->reachable)
147 /* Add varpool NODE to queue starting at FIRST. */
150 enqueue_varpool_node (struct varpool_node *node, struct varpool_node **first)
156 /* Process references. */
159 process_references (struct ipa_ref_list *list,
160 struct cgraph_node **first,
161 struct varpool_node **first_varpool,
162 bool before_inlining_p)
166 for (i = 0; ipa_ref_list_reference_iterate (list, i, ref); i++)
168 if (ref->refered_type == IPA_REF_CGRAPH)
170 struct cgraph_node *node = ipa_ref_node (ref);
172 && (!DECL_EXTERNAL (node->decl)
173 || before_inlining_p))
175 node->reachable = true;
176 enqueue_cgraph_node (node, first);
181 struct varpool_node *node = ipa_ref_varpool_node (ref);
184 varpool_mark_needed_node (node);
185 enqueue_varpool_node (node, first_varpool);
191 /* Return true when function NODE can be removed from callgraph
192 if all direct calls are eliminated. */
195 varpool_can_remove_if_no_refs (struct varpool_node *node)
197 return (!node->force_output && !node->used_from_other_partition
198 && (DECL_COMDAT (node->decl) || !node->externally_visible));
201 /* Return true when function can be marked local. */
204 cgraph_local_node_p (struct cgraph_node *node)
206 return (cgraph_only_called_directly_p (node)
208 && !DECL_EXTERNAL (node->decl)
209 && !node->local.externally_visible
210 && !node->reachable_from_other_partition
211 && !node->in_other_partition);
214 /* Perform reachability analysis and reclaim all unreachable nodes.
215 If BEFORE_INLINING_P is true this function is called before inlining
216 decisions has been made. If BEFORE_INLINING_P is false this function also
217 removes unneeded bodies of extern inline functions. */
220 cgraph_remove_unreachable_nodes (bool before_inlining_p, FILE *file)
222 struct cgraph_node *first = (struct cgraph_node *) (void *) 1;
223 struct varpool_node *first_varpool = (struct varpool_node *) (void *) 1;
224 struct cgraph_node *node, *next;
225 struct varpool_node *vnode, *vnext;
226 bool changed = false;
228 #ifdef ENABLE_CHECKING
232 fprintf (file, "\nReclaiming functions:");
233 #ifdef ENABLE_CHECKING
234 for (node = cgraph_nodes; node; node = node->next)
235 gcc_assert (!node->aux);
236 for (vnode = varpool_nodes; vnode; vnode = vnode->next)
237 gcc_assert (!vnode->aux);
239 varpool_reset_queue ();
240 for (node = cgraph_nodes; node; node = node->next)
241 if (!cgraph_can_remove_if_no_direct_calls_and_refs_p (node)
242 && ((!DECL_EXTERNAL (node->decl))
243 || before_inlining_p))
245 gcc_assert (!node->global.inlined_to);
246 enqueue_cgraph_node (node, &first);
247 node->reachable = true;
251 gcc_assert (!node->aux);
252 node->reachable = false;
254 for (vnode = varpool_nodes; vnode; vnode = vnode->next)
256 vnode->next_needed = NULL;
257 vnode->prev_needed = NULL;
258 if (!varpool_can_remove_if_no_refs (vnode))
260 vnode->needed = false;
261 varpool_mark_needed_node (vnode);
262 enqueue_varpool_node (vnode, &first_varpool);
265 vnode->needed = false;
268 /* Perform reachability analysis. As a special case do not consider
269 extern inline functions not inlined as live because we won't output
272 We maintain two worklist, one for cgraph nodes other for varpools and
273 are finished once both are empty. */
275 while (first != (struct cgraph_node *) (void *) 1
276 || first_varpool != (struct varpool_node *) (void *) 1)
278 if (first != (struct cgraph_node *) (void *) 1)
280 struct cgraph_edge *e;
282 first = (struct cgraph_node *) first->aux;
283 if (!node->reachable)
284 node->aux = (void *)2;
286 /* If we found this node reachable, first mark on the callees
287 reachable too, unless they are direct calls to extern inline functions
288 we decided to not inline. */
291 for (e = node->callees; e; e = e->next_callee)
292 if (!e->callee->reachable
294 && (!e->inline_failed || !e->callee->analyzed
295 || (!DECL_EXTERNAL (e->callee->decl))
296 || before_inlining_p))
298 e->callee->reachable = true;
299 enqueue_cgraph_node (e->callee, &first);
301 process_references (&node->ref_list, &first, &first_varpool, before_inlining_p);
304 /* If any function in a comdat group is reachable, force
305 all other functions in the same comdat group to be
307 if (node->same_comdat_group
309 && !node->global.inlined_to)
311 for (next = node->same_comdat_group;
313 next = next->same_comdat_group)
314 if (!next->reachable)
316 next->reachable = true;
317 enqueue_cgraph_node (next, &first);
321 /* We can freely remove inline clones even if they are cloned, however if
322 function is clone of real clone, we must keep it around in order to
323 make materialize_clones produce function body with the changes
325 while (node->clone_of && !node->clone_of->aux
326 && !gimple_has_body_p (node->decl))
328 bool noninline = node->clone_of->decl != node->decl;
329 node = node->clone_of;
330 if (noninline && !node->reachable && !node->aux)
332 enqueue_cgraph_node (node, &first);
337 if (first_varpool != (struct varpool_node *) (void *) 1)
339 vnode = first_varpool;
340 first_varpool = (struct varpool_node *)first_varpool->aux;
342 process_references (&vnode->ref_list, &first, &first_varpool, before_inlining_p);
343 /* If any function in a comdat group is reachable, force
344 all other functions in the same comdat group to be
346 if (vnode->same_comdat_group)
348 struct varpool_node *next;
349 for (next = vnode->same_comdat_group;
351 next = next->same_comdat_group)
354 varpool_mark_needed_node (next);
355 enqueue_varpool_node (next, &first_varpool);
361 /* Remove unreachable nodes.
363 Completely unreachable functions can be fully removed from the callgraph.
364 Extern inline functions that we decided to not inline need to become unanalyzed nodes of
365 callgraph (so we still have edges to them). We remove function body then.
367 Also we need to care functions that are unreachable but we need to keep them around
368 for later clonning. In this case we also turn them to unanalyzed nodes, but
369 keep the body around. */
370 for (node = cgraph_nodes; node; node = next)
373 if (node->aux && !node->reachable)
375 cgraph_node_remove_callees (node);
376 ipa_remove_all_references (&node->ref_list);
377 node->analyzed = false;
378 node->local.inlinable = false;
382 node->global.inlined_to = NULL;
384 fprintf (file, " %s", cgraph_node_name (node));
385 if (!node->analyzed || !DECL_EXTERNAL (node->decl) || before_inlining_p)
386 cgraph_remove_node (node);
389 struct cgraph_edge *e;
391 /* See if there is reachable caller. */
392 for (e = node->callers; e; e = e->next_caller)
393 if (e->caller->reachable)
396 /* If so, we need to keep node in the callgraph. */
397 if (e || node->needed)
399 struct cgraph_node *clone;
401 /* If there are still clones, we must keep body around.
402 Otherwise we can just remove the body but keep the clone. */
403 for (clone = node->clones; clone;
404 clone = clone->next_sibling_clone)
409 cgraph_release_function_body (node);
410 node->local.inlinable = false;
411 if (node->prev_sibling_clone)
412 node->prev_sibling_clone->next_sibling_clone = node->next_sibling_clone;
413 else if (node->clone_of)
414 node->clone_of->clones = node->next_sibling_clone;
415 if (node->next_sibling_clone)
416 node->next_sibling_clone->prev_sibling_clone = node->prev_sibling_clone;
417 #ifdef ENABLE_CHECKING
419 node->former_clone_of = node->clone_of->decl;
421 node->clone_of = NULL;
422 node->next_sibling_clone = NULL;
423 node->prev_sibling_clone = NULL;
426 gcc_assert (!clone->in_other_partition);
427 node->analyzed = false;
428 cgraph_node_remove_callees (node);
429 ipa_remove_all_references (&node->ref_list);
432 cgraph_remove_node (node);
437 for (node = cgraph_nodes; node; node = node->next)
439 /* Inline clones might be kept around so their materializing allows further
440 cloning. If the function the clone is inlined into is removed, we need
441 to turn it into normal cone. */
442 if (node->global.inlined_to
445 gcc_assert (node->clones);
446 node->global.inlined_to = NULL;
447 update_inlined_to_pointer (node, node);
453 fprintf (file, "\n");
455 /* We must release unused extern inlines or sanity checking will fail. Rest of transformations
456 are undesirable at -O0 since we do not want to remove anything. */
461 fprintf (file, "Reclaiming variables:");
462 for (vnode = varpool_nodes; vnode; vnode = vnext)
468 fprintf (file, " %s", varpool_node_name (vnode));
469 varpool_remove_node (vnode);
474 /* Now update address_taken flags and try to promote functions to be local. */
477 fprintf (file, "\nClearing address taken flags:");
478 for (node = cgraph_nodes; node; node = node->next)
479 if (node->address_taken
480 && !node->reachable_from_other_partition)
485 for (i = 0; ipa_ref_list_refering_iterate (&node->ref_list, i, ref)
488 gcc_assert (ref->use == IPA_REF_ADDR);
494 fprintf (file, " %s", cgraph_node_name (node));
495 node->address_taken = false;
497 if (cgraph_local_node_p (node))
499 node->local.local = true;
501 fprintf (file, " (local)");
506 #ifdef ENABLE_CHECKING
510 /* Reclaim alias pairs for functions that have disappeared from the
512 remove_unreachable_alias_pairs ();
517 /* Discover variables that have no longer address taken or that are read only
518 and update their flags.
520 FIXME: This can not be done in between gimplify and omp_expand since
521 readonly flag plays role on what is shared and what is not. Currently we do
522 this transformation as part of whole program visibility and re-do at
523 ipa-reference pass (to take into account clonning), but it would
524 make sense to do it before early optimizations. */
527 ipa_discover_readonly_nonaddressable_vars (void)
529 struct varpool_node *vnode;
531 fprintf (dump_file, "Clearing variable flags:");
532 for (vnode = varpool_nodes; vnode; vnode = vnode->next)
533 if (vnode->finalized && varpool_all_refs_explicit_p (vnode)
534 && (TREE_ADDRESSABLE (vnode->decl) || !TREE_READONLY (vnode->decl)))
536 bool written = false;
537 bool address_taken = false;
540 for (i = 0; ipa_ref_list_refering_iterate (&vnode->ref_list, i, ref)
541 && (!written || !address_taken); i++)
545 address_taken = true;
553 if (TREE_ADDRESSABLE (vnode->decl) && !address_taken)
556 fprintf (dump_file, " %s (addressable)", varpool_node_name (vnode));
557 TREE_ADDRESSABLE (vnode->decl) = 0;
559 if (!TREE_READONLY (vnode->decl) && !address_taken && !written
560 /* Making variable in explicit section readonly can cause section
562 See e.g. gcc.c-torture/compile/pr23237.c */
563 && DECL_SECTION_NAME (vnode->decl) == NULL)
566 fprintf (dump_file, " %s (read-only)", varpool_node_name (vnode));
567 TREE_READONLY (vnode->decl) = 1;
568 vnode->const_value_known |= varpool_decide_const_value_known (vnode);
572 fprintf (dump_file, "\n");
575 /* Return true when function NODE should be considered externally visible. */
578 cgraph_externally_visible_p (struct cgraph_node *node, bool whole_program, bool aliased)
580 if (!node->local.finalized)
582 if (!DECL_COMDAT (node->decl)
583 && (!TREE_PUBLIC (node->decl) || DECL_EXTERNAL (node->decl)))
586 /* Do not even try to be smart about aliased nodes. Until we properly
587 represent everything by same body alias, these are just evil. */
591 /* When doing link time optimizations, hidden symbols become local. */
592 if (in_lto_p && DECL_VISIBILITY (node->decl) == VISIBILITY_HIDDEN
593 /* Be sure that node is defined in IR file, not in other object
594 file. In that case we don't set used_from_other_object_file. */
597 else if (!whole_program)
599 /* COMDAT functions must be shared only if they have address taken,
600 otherwise we can produce our own private implementation with
602 else if (DECL_COMDAT (node->decl))
604 if (node->address_taken || !node->analyzed)
606 if (node->same_comdat_group)
608 struct cgraph_node *next;
610 /* If more than one function is in the same COMDAT group, it must
611 be shared even if just one function in the comdat group has
613 for (next = node->same_comdat_group;
615 next = next->same_comdat_group)
616 if (next->address_taken || !next->analyzed)
620 if (node->local.used_from_object_file)
622 if (DECL_PRESERVE_P (node->decl))
624 if (MAIN_NAME_P (DECL_NAME (node->decl)))
626 if (lookup_attribute ("externally_visible", DECL_ATTRIBUTES (node->decl)))
631 /* Dissolve the same_comdat_group list in which NODE resides. */
634 dissolve_same_comdat_group_list (struct cgraph_node *node)
636 struct cgraph_node *n = node, *next;
639 next = n->same_comdat_group;
640 n->same_comdat_group = NULL;
646 /* Mark visibility of all functions.
648 A local function is one whose calls can occur only in the current
649 compilation unit and all its calls are explicit, so we can change
650 its calling convention. We simply mark all static functions whose
651 address is not taken as local.
653 We also change the TREE_PUBLIC flag of all declarations that are public
654 in language point of view but we want to overwrite this default
655 via visibilities for the backend point of view. */
658 function_and_variable_visibility (bool whole_program)
660 struct cgraph_node *node;
661 struct varpool_node *vnode;
662 struct pointer_set_t *aliased_nodes = pointer_set_create ();
663 struct pointer_set_t *aliased_vnodes = pointer_set_create ();
667 /* Discover aliased nodes. */
668 FOR_EACH_VEC_ELT (alias_pair, alias_pairs, i, p)
671 fprintf (dump_file, "Alias %s->%s",
672 IDENTIFIER_POINTER (DECL_ASSEMBLER_NAME (p->decl)),
673 IDENTIFIER_POINTER (p->target));
675 if ((node = cgraph_node_for_asm (p->target)) != NULL)
677 gcc_assert (node->needed);
678 pointer_set_insert (aliased_nodes, node);
680 fprintf (dump_file, " node %s/%i",
681 cgraph_node_name (node), node->uid);
683 else if ((vnode = varpool_node_for_asm (p->target)) != NULL)
685 gcc_assert (vnode->needed);
686 pointer_set_insert (aliased_vnodes, vnode);
688 fprintf (dump_file, " varpool node %s",
689 varpool_node_name (vnode));
692 fprintf (dump_file, "\n");
695 for (node = cgraph_nodes; node; node = node->next)
697 /* C++ FE on lack of COMDAT support create local COMDAT functions
698 (that ought to be shared but can not due to object format
699 limitations). It is neccesary to keep the flag to make rest of C++ FE
700 happy. Clear the flag here to avoid confusion in middle-end. */
701 if (DECL_COMDAT (node->decl) && !TREE_PUBLIC (node->decl))
702 DECL_COMDAT (node->decl) = 0;
703 /* For external decls stop tracking same_comdat_group, it doesn't matter
704 what comdat group they are in when they won't be emitted in this TU,
705 and simplifies later passes. */
706 if (node->same_comdat_group && DECL_EXTERNAL (node->decl))
708 #ifdef ENABLE_CHECKING
709 struct cgraph_node *n;
711 for (n = node->same_comdat_group;
713 n = n->same_comdat_group)
714 /* If at least one of same comdat group functions is external,
715 all of them have to be, otherwise it is a front-end bug. */
716 gcc_assert (DECL_EXTERNAL (n->decl));
718 dissolve_same_comdat_group_list (node);
720 gcc_assert ((!DECL_WEAK (node->decl) && !DECL_COMDAT (node->decl))
721 || TREE_PUBLIC (node->decl) || DECL_EXTERNAL (node->decl));
722 if (cgraph_externally_visible_p (node, whole_program,
723 pointer_set_contains (aliased_nodes,
726 gcc_assert (!node->global.inlined_to);
727 node->local.externally_visible = true;
730 node->local.externally_visible = false;
731 if (!node->local.externally_visible && node->analyzed
732 && !DECL_EXTERNAL (node->decl))
734 struct cgraph_node *alias;
735 gcc_assert (whole_program || in_lto_p || !TREE_PUBLIC (node->decl));
736 cgraph_make_decl_local (node->decl);
737 for (alias = node->same_body; alias; alias = alias->next)
738 cgraph_make_decl_local (alias->decl);
739 if (node->same_comdat_group)
740 /* cgraph_externally_visible_p has already checked all other nodes
741 in the group and they will all be made local. We need to
742 dissolve the group at once so that the predicate does not
744 dissolve_same_comdat_group_list (node);
746 node->local.local = cgraph_local_node_p (node);
748 for (vnode = varpool_nodes; vnode; vnode = vnode->next)
750 /* weak flag makes no sense on local variables. */
751 gcc_assert (!DECL_WEAK (vnode->decl)
752 || TREE_PUBLIC (vnode->decl) || DECL_EXTERNAL (vnode->decl));
753 /* In several cases declarations can not be common:
755 - when declaration has initializer
757 - when it has specific section
758 - when it resides in non-generic address space.
759 - if declaration is local, it will get into .local common section
760 so common flag is not needed. Frontends still produce these in
761 certain cases, such as for:
763 static int a __attribute__ ((common))
765 Canonicalize things here and clear the redundant flag. */
766 if (DECL_COMMON (vnode->decl)
767 && (!(TREE_PUBLIC (vnode->decl) || DECL_EXTERNAL (vnode->decl))
768 || (DECL_INITIAL (vnode->decl)
769 && DECL_INITIAL (vnode->decl) != error_mark_node)
770 || DECL_WEAK (vnode->decl)
771 || DECL_SECTION_NAME (vnode->decl) != NULL
772 || ! (ADDR_SPACE_GENERIC_P
773 (TYPE_ADDR_SPACE (TREE_TYPE (vnode->decl))))))
774 DECL_COMMON (vnode->decl) = 0;
775 /* Even extern variables might have initializers known.
776 See, for example testsuite/g++.dg/opt/static3.C */
777 vnode->const_value_known |= varpool_decide_const_value_known (vnode);
779 for (vnode = varpool_nodes_queue; vnode; vnode = vnode->next_needed)
781 if (!vnode->finalized)
784 && (DECL_COMDAT (vnode->decl) || TREE_PUBLIC (vnode->decl))
786 /* We can privatize comdat readonly variables whose address is
787 not taken, but doing so is not going to bring us
788 optimization oppurtunities until we start reordering
790 || DECL_COMDAT (vnode->decl)
791 || DECL_WEAK (vnode->decl))
792 /* When doing linktime optimizations, all hidden symbols will
795 || DECL_VISIBILITY (vnode->decl) != VISIBILITY_HIDDEN
796 /* We can get prevailing decision in other object file.
797 In this case we do not sed used_from_object_file. */
798 || !vnode->finalized))
799 || DECL_PRESERVE_P (vnode->decl)
800 || vnode->used_from_object_file
801 || pointer_set_contains (aliased_vnodes, vnode)
802 || lookup_attribute ("externally_visible",
803 DECL_ATTRIBUTES (vnode->decl))))
804 vnode->externally_visible = true;
806 vnode->externally_visible = false;
807 if (!vnode->externally_visible)
809 gcc_assert (in_lto_p || whole_program || !TREE_PUBLIC (vnode->decl));
810 cgraph_make_decl_local (vnode->decl);
812 vnode->const_value_known |= varpool_decide_const_value_known (vnode);
813 gcc_assert (TREE_STATIC (vnode->decl));
815 pointer_set_destroy (aliased_nodes);
816 pointer_set_destroy (aliased_vnodes);
820 fprintf (dump_file, "\nMarking local functions:");
821 for (node = cgraph_nodes; node; node = node->next)
822 if (node->local.local)
823 fprintf (dump_file, " %s", cgraph_node_name (node));
824 fprintf (dump_file, "\n\n");
825 fprintf (dump_file, "\nMarking externally visible functions:");
826 for (node = cgraph_nodes; node; node = node->next)
827 if (node->local.externally_visible)
828 fprintf (dump_file, " %s", cgraph_node_name (node));
829 fprintf (dump_file, "\n\n");
830 fprintf (dump_file, "\nMarking externally visible variables:");
831 for (vnode = varpool_nodes_queue; vnode; vnode = vnode->next_needed)
832 if (vnode->externally_visible)
833 fprintf (dump_file, " %s", varpool_node_name (vnode));
834 fprintf (dump_file, "\n\n");
836 cgraph_function_flags_ready = true;
840 /* Local function pass handling visibilities. This happens before LTO streaming
841 so in particular -fwhole-program should be ignored at this level. */
844 local_function_and_variable_visibility (void)
846 return function_and_variable_visibility (flag_whole_program && !flag_lto && !flag_whopr);
849 struct simple_ipa_opt_pass pass_ipa_function_and_variable_visibility =
853 "visibility", /* name */
855 local_function_and_variable_visibility,/* execute */
858 0, /* static_pass_number */
859 TV_CGRAPHOPT, /* tv_id */
860 0, /* properties_required */
861 0, /* properties_provided */
862 0, /* properties_destroyed */
863 0, /* todo_flags_start */
864 TODO_remove_functions | TODO_dump_cgraph
865 | TODO_ggc_collect /* todo_flags_finish */
869 /* Do not re-run on ltrans stage. */
872 gate_whole_program_function_and_variable_visibility (void)
877 /* Bring functionss local at LTO time whith -fwhole-program. */
880 whole_program_function_and_variable_visibility (void)
882 struct cgraph_node *node;
883 struct varpool_node *vnode;
885 function_and_variable_visibility (flag_whole_program);
887 for (node = cgraph_nodes; node; node = node->next)
888 if ((node->local.externally_visible && !DECL_COMDAT (node->decl))
889 && node->local.finalized)
890 cgraph_mark_needed_node (node);
891 for (vnode = varpool_nodes_queue; vnode; vnode = vnode->next_needed)
892 if (vnode->externally_visible && !DECL_COMDAT (vnode->decl))
893 varpool_mark_needed_node (vnode);
896 fprintf (dump_file, "\nNeeded variables:");
897 for (vnode = varpool_nodes_queue; vnode; vnode = vnode->next_needed)
899 fprintf (dump_file, " %s", varpool_node_name (vnode));
900 fprintf (dump_file, "\n\n");
903 ipa_discover_readonly_nonaddressable_vars ();
907 struct ipa_opt_pass_d pass_ipa_whole_program_visibility =
911 "whole-program", /* name */
912 gate_whole_program_function_and_variable_visibility,/* gate */
913 whole_program_function_and_variable_visibility,/* execute */
916 0, /* static_pass_number */
917 TV_CGRAPHOPT, /* tv_id */
918 0, /* properties_required */
919 0, /* properties_provided */
920 0, /* properties_destroyed */
921 0, /* todo_flags_start */
922 TODO_remove_functions | TODO_dump_cgraph
923 | TODO_ggc_collect /* todo_flags_finish */
925 NULL, /* generate_summary */
926 NULL, /* write_summary */
927 NULL, /* read_summary */
928 NULL, /* write_optimization_summary */
929 NULL, /* read_optimization_summary */
930 NULL, /* stmt_fixup */
932 NULL, /* function_transform */
933 NULL, /* variable_transform */
936 /* Hash a cgraph node set element. */
939 hash_cgraph_node_set_element (const void *p)
941 const_cgraph_node_set_element element = (const_cgraph_node_set_element) p;
942 return htab_hash_pointer (element->node);
945 /* Compare two cgraph node set elements. */
948 eq_cgraph_node_set_element (const void *p1, const void *p2)
950 const_cgraph_node_set_element e1 = (const_cgraph_node_set_element) p1;
951 const_cgraph_node_set_element e2 = (const_cgraph_node_set_element) p2;
953 return e1->node == e2->node;
956 /* Create a new cgraph node set. */
959 cgraph_node_set_new (void)
961 cgraph_node_set new_node_set;
963 new_node_set = ggc_alloc_cgraph_node_set_def ();
964 new_node_set->hashtab = htab_create_ggc (10,
965 hash_cgraph_node_set_element,
966 eq_cgraph_node_set_element,
968 new_node_set->nodes = NULL;
972 /* Add cgraph_node NODE to cgraph_node_set SET. */
975 cgraph_node_set_add (cgraph_node_set set, struct cgraph_node *node)
978 cgraph_node_set_element element;
979 struct cgraph_node_set_element_def dummy;
982 slot = htab_find_slot (set->hashtab, &dummy, INSERT);
984 if (*slot != HTAB_EMPTY_ENTRY)
986 element = (cgraph_node_set_element) *slot;
987 gcc_assert (node == element->node
988 && (VEC_index (cgraph_node_ptr, set->nodes, element->index)
993 /* Insert node into hash table. */
994 element = ggc_alloc_cgraph_node_set_element_def ();
995 element->node = node;
996 element->index = VEC_length (cgraph_node_ptr, set->nodes);
999 /* Insert into node vector. */
1000 VEC_safe_push (cgraph_node_ptr, gc, set->nodes, node);
1003 /* Remove cgraph_node NODE from cgraph_node_set SET. */
1006 cgraph_node_set_remove (cgraph_node_set set, struct cgraph_node *node)
1008 void **slot, **last_slot;
1009 cgraph_node_set_element element, last_element;
1010 struct cgraph_node *last_node;
1011 struct cgraph_node_set_element_def dummy;
1014 slot = htab_find_slot (set->hashtab, &dummy, NO_INSERT);
1018 element = (cgraph_node_set_element) *slot;
1019 gcc_assert (VEC_index (cgraph_node_ptr, set->nodes, element->index)
1022 /* Remove from vector. We do this by swapping node with the last element
1024 last_node = VEC_pop (cgraph_node_ptr, set->nodes);
1025 if (last_node != node)
1027 dummy.node = last_node;
1028 last_slot = htab_find_slot (set->hashtab, &dummy, NO_INSERT);
1029 last_element = (cgraph_node_set_element) *last_slot;
1030 gcc_assert (last_element);
1032 /* Move the last element to the original spot of NODE. */
1033 last_element->index = element->index;
1034 VEC_replace (cgraph_node_ptr, set->nodes, last_element->index,
1038 /* Remove element from hash table. */
1039 htab_clear_slot (set->hashtab, slot);
1043 /* Find NODE in SET and return an iterator to it if found. A null iterator
1044 is returned if NODE is not in SET. */
1046 cgraph_node_set_iterator
1047 cgraph_node_set_find (cgraph_node_set set, struct cgraph_node *node)
1050 struct cgraph_node_set_element_def dummy;
1051 cgraph_node_set_element element;
1052 cgraph_node_set_iterator csi;
1055 slot = htab_find_slot (set->hashtab, &dummy, NO_INSERT);
1057 csi.index = (unsigned) ~0;
1060 element = (cgraph_node_set_element) *slot;
1061 gcc_assert (VEC_index (cgraph_node_ptr, set->nodes, element->index)
1063 csi.index = element->index;
1070 /* Dump content of SET to file F. */
1073 dump_cgraph_node_set (FILE *f, cgraph_node_set set)
1075 cgraph_node_set_iterator iter;
1077 for (iter = csi_start (set); !csi_end_p (iter); csi_next (&iter))
1079 struct cgraph_node *node = csi_node (iter);
1080 fprintf (f, " %s/%i", cgraph_node_name (node), node->uid);
1085 /* Dump content of SET to stderr. */
1088 debug_cgraph_node_set (cgraph_node_set set)
1090 dump_cgraph_node_set (stderr, set);
1093 /* Hash a varpool node set element. */
1096 hash_varpool_node_set_element (const void *p)
1098 const_varpool_node_set_element element = (const_varpool_node_set_element) p;
1099 return htab_hash_pointer (element->node);
1102 /* Compare two varpool node set elements. */
1105 eq_varpool_node_set_element (const void *p1, const void *p2)
1107 const_varpool_node_set_element e1 = (const_varpool_node_set_element) p1;
1108 const_varpool_node_set_element e2 = (const_varpool_node_set_element) p2;
1110 return e1->node == e2->node;
1113 /* Create a new varpool node set. */
1116 varpool_node_set_new (void)
1118 varpool_node_set new_node_set;
1120 new_node_set = ggc_alloc_varpool_node_set_def ();
1121 new_node_set->hashtab = htab_create_ggc (10,
1122 hash_varpool_node_set_element,
1123 eq_varpool_node_set_element,
1125 new_node_set->nodes = NULL;
1126 return new_node_set;
1129 /* Add varpool_node NODE to varpool_node_set SET. */
1132 varpool_node_set_add (varpool_node_set set, struct varpool_node *node)
1135 varpool_node_set_element element;
1136 struct varpool_node_set_element_def dummy;
1139 slot = htab_find_slot (set->hashtab, &dummy, INSERT);
1141 if (*slot != HTAB_EMPTY_ENTRY)
1143 element = (varpool_node_set_element) *slot;
1144 gcc_assert (node == element->node
1145 && (VEC_index (varpool_node_ptr, set->nodes, element->index)
1150 /* Insert node into hash table. */
1151 element = ggc_alloc_varpool_node_set_element_def ();
1152 element->node = node;
1153 element->index = VEC_length (varpool_node_ptr, set->nodes);
1156 /* Insert into node vector. */
1157 VEC_safe_push (varpool_node_ptr, gc, set->nodes, node);
1160 /* Remove varpool_node NODE from varpool_node_set SET. */
1163 varpool_node_set_remove (varpool_node_set set, struct varpool_node *node)
1165 void **slot, **last_slot;
1166 varpool_node_set_element element, last_element;
1167 struct varpool_node *last_node;
1168 struct varpool_node_set_element_def dummy;
1171 slot = htab_find_slot (set->hashtab, &dummy, NO_INSERT);
1175 element = (varpool_node_set_element) *slot;
1176 gcc_assert (VEC_index (varpool_node_ptr, set->nodes, element->index)
1179 /* Remove from vector. We do this by swapping node with the last element
1181 last_node = VEC_pop (varpool_node_ptr, set->nodes);
1182 if (last_node != node)
1184 dummy.node = last_node;
1185 last_slot = htab_find_slot (set->hashtab, &dummy, NO_INSERT);
1186 last_element = (varpool_node_set_element) *last_slot;
1187 gcc_assert (last_element);
1189 /* Move the last element to the original spot of NODE. */
1190 last_element->index = element->index;
1191 VEC_replace (varpool_node_ptr, set->nodes, last_element->index,
1195 /* Remove element from hash table. */
1196 htab_clear_slot (set->hashtab, slot);
1200 /* Find NODE in SET and return an iterator to it if found. A null iterator
1201 is returned if NODE is not in SET. */
1203 varpool_node_set_iterator
1204 varpool_node_set_find (varpool_node_set set, struct varpool_node *node)
1207 struct varpool_node_set_element_def dummy;
1208 varpool_node_set_element element;
1209 varpool_node_set_iterator vsi;
1212 slot = htab_find_slot (set->hashtab, &dummy, NO_INSERT);
1214 vsi.index = (unsigned) ~0;
1217 element = (varpool_node_set_element) *slot;
1218 gcc_assert (VEC_index (varpool_node_ptr, set->nodes, element->index)
1220 vsi.index = element->index;
1227 /* Dump content of SET to file F. */
1230 dump_varpool_node_set (FILE *f, varpool_node_set set)
1232 varpool_node_set_iterator iter;
1234 for (iter = vsi_start (set); !vsi_end_p (iter); vsi_next (&iter))
1236 struct varpool_node *node = vsi_node (iter);
1237 fprintf (f, " %s", varpool_node_name (node));
1242 /* Dump content of SET to stderr. */
1245 debug_varpool_node_set (varpool_node_set set)
1247 dump_varpool_node_set (stderr, set);
1251 /* Simple ipa profile pass propagating frequencies across the callgraph. */
1256 struct cgraph_node **order = XCNEWVEC (struct cgraph_node *, cgraph_n_nodes);
1257 struct cgraph_edge *e;
1259 bool something_changed = false;
1262 order_pos = cgraph_postorder (order);
1263 for (i = order_pos - 1; i >= 0; i--)
1265 if (order[i]->local.local && cgraph_propagate_frequency (order[i]))
1267 for (e = order[i]->callees; e; e = e->next_callee)
1268 if (e->callee->local.local && !e->callee->aux)
1270 something_changed = true;
1271 e->callee->aux = (void *)1;
1274 order[i]->aux = NULL;
1277 while (something_changed)
1279 something_changed = false;
1280 for (i = order_pos - 1; i >= 0; i--)
1282 if (order[i]->aux && cgraph_propagate_frequency (order[i]))
1284 for (e = order[i]->callees; e; e = e->next_callee)
1285 if (e->callee->local.local && !e->callee->aux)
1287 something_changed = true;
1288 e->callee->aux = (void *)1;
1291 order[i]->aux = NULL;
1299 gate_ipa_profile (void)
1301 return flag_ipa_profile;
1304 struct ipa_opt_pass_d pass_ipa_profile =
1308 "ipa-profile", /* name */
1309 gate_ipa_profile, /* gate */
1310 ipa_profile, /* execute */
1313 0, /* static_pass_number */
1314 TV_IPA_PROFILE, /* tv_id */
1315 0, /* properties_required */
1316 0, /* properties_provided */
1317 0, /* properties_destroyed */
1318 0, /* todo_flags_start */
1319 0 /* todo_flags_finish */
1321 NULL, /* generate_summary */
1322 NULL, /* write_summary */
1323 NULL, /* read_summary */
1324 NULL, /* write_optimization_summary */
1325 NULL, /* read_optimization_summary */
1326 NULL, /* stmt_fixup */
1328 NULL, /* function_transform */
1329 NULL /* variable_transform */
1332 /* Generate and emit a static constructor or destructor. WHICH must
1333 be one of 'I' (for a constructor) or 'D' (for a destructor). BODY
1334 is a STATEMENT_LIST containing GENERIC statements. PRIORITY is the
1335 initialization priority for this constructor or destructor. */
1338 cgraph_build_static_cdtor (char which, tree body, int priority)
1340 static int counter = 0;
1342 tree decl, name, resdecl;
1344 /* The priority is encoded in the constructor or destructor name.
1345 collect2 will sort the names and arrange that they are called at
1347 sprintf (which_buf, "%c_%.5d_%d", which, priority, counter++);
1348 name = get_file_function_name (which_buf);
1350 decl = build_decl (input_location, FUNCTION_DECL, name,
1351 build_function_type_list (void_type_node, NULL_TREE));
1352 current_function_decl = decl;
1354 resdecl = build_decl (input_location,
1355 RESULT_DECL, NULL_TREE, void_type_node);
1356 DECL_ARTIFICIAL (resdecl) = 1;
1357 DECL_RESULT (decl) = resdecl;
1358 DECL_CONTEXT (resdecl) = decl;
1360 allocate_struct_function (decl, false);
1362 TREE_STATIC (decl) = 1;
1363 TREE_USED (decl) = 1;
1364 DECL_ARTIFICIAL (decl) = 1;
1365 DECL_NO_INSTRUMENT_FUNCTION_ENTRY_EXIT (decl) = 1;
1366 DECL_SAVED_TREE (decl) = body;
1367 if (!targetm.have_ctors_dtors)
1369 TREE_PUBLIC (decl) = 1;
1370 DECL_PRESERVE_P (decl) = 1;
1372 DECL_UNINLINABLE (decl) = 1;
1374 DECL_INITIAL (decl) = make_node (BLOCK);
1375 TREE_USED (DECL_INITIAL (decl)) = 1;
1377 DECL_SOURCE_LOCATION (decl) = input_location;
1378 cfun->function_end_locus = input_location;
1383 DECL_STATIC_CONSTRUCTOR (decl) = 1;
1384 decl_init_priority_insert (decl, priority);
1387 DECL_STATIC_DESTRUCTOR (decl) = 1;
1388 decl_fini_priority_insert (decl, priority);
1394 gimplify_function_tree (decl);
1396 cgraph_add_new_function (decl, false);
1399 current_function_decl = NULL;
1403 /* A vector of FUNCTION_DECLs declared as static constructors. */
1404 static VEC(tree, heap) *static_ctors;
1405 /* A vector of FUNCTION_DECLs declared as static destructors. */
1406 static VEC(tree, heap) *static_dtors;
1408 /* When target does not have ctors and dtors, we call all constructor
1409 and destructor by special initialization/destruction function
1410 recognized by collect2.
1412 When we are going to build this function, collect all constructors and
1413 destructors and turn them into normal functions. */
1416 record_cdtor_fn (struct cgraph_node *node)
1418 if (DECL_STATIC_CONSTRUCTOR (node->decl))
1419 VEC_safe_push (tree, heap, static_ctors, node->decl);
1420 if (DECL_STATIC_DESTRUCTOR (node->decl))
1421 VEC_safe_push (tree, heap, static_dtors, node->decl);
1422 node = cgraph_node (node->decl);
1423 node->local.disregard_inline_limits = 1;
1426 /* Define global constructors/destructor functions for the CDTORS, of
1427 which they are LEN. The CDTORS are sorted by initialization
1428 priority. If CTOR_P is true, these are constructors; otherwise,
1429 they are destructors. */
1432 build_cdtor (bool ctor_p, VEC (tree, heap) *cdtors)
1435 size_t len = VEC_length (tree, cdtors);
1442 priority_type priority;
1450 fn = VEC_index (tree, cdtors, j);
1451 p = ctor_p ? DECL_INIT_PRIORITY (fn) : DECL_FINI_PRIORITY (fn);
1454 else if (p != priority)
1460 /* When there is only one cdtor and target supports them, do nothing. */
1462 && targetm.have_ctors_dtors)
1467 /* Find the next batch of constructors/destructors with the same
1468 initialization priority. */
1472 fn = VEC_index (tree, cdtors, i);
1473 call = build_call_expr (fn, 0);
1475 DECL_STATIC_CONSTRUCTOR (fn) = 0;
1477 DECL_STATIC_DESTRUCTOR (fn) = 0;
1478 /* We do not want to optimize away pure/const calls here.
1479 When optimizing, these should be already removed, when not
1480 optimizing, we want user to be able to breakpoint in them. */
1481 TREE_SIDE_EFFECTS (call) = 1;
1482 append_to_statement_list (call, &body);
1485 gcc_assert (body != NULL_TREE);
1486 /* Generate a function to call all the function of like
1488 cgraph_build_static_cdtor (ctor_p ? 'I' : 'D', body, priority);
1492 /* Comparison function for qsort. P1 and P2 are actually of type
1493 "tree *" and point to static constructors. DECL_INIT_PRIORITY is
1494 used to determine the sort order. */
1497 compare_ctor (const void *p1, const void *p2)
1504 f1 = *(const tree *)p1;
1505 f2 = *(const tree *)p2;
1506 priority1 = DECL_INIT_PRIORITY (f1);
1507 priority2 = DECL_INIT_PRIORITY (f2);
1509 if (priority1 < priority2)
1511 else if (priority1 > priority2)
1514 /* Ensure a stable sort. Constructors are executed in backwarding
1515 order to make LTO initialize braries first. */
1516 return DECL_UID (f2) - DECL_UID (f1);
1519 /* Comparison function for qsort. P1 and P2 are actually of type
1520 "tree *" and point to static destructors. DECL_FINI_PRIORITY is
1521 used to determine the sort order. */
1524 compare_dtor (const void *p1, const void *p2)
1531 f1 = *(const tree *)p1;
1532 f2 = *(const tree *)p2;
1533 priority1 = DECL_FINI_PRIORITY (f1);
1534 priority2 = DECL_FINI_PRIORITY (f2);
1536 if (priority1 < priority2)
1538 else if (priority1 > priority2)
1541 /* Ensure a stable sort. */
1542 return DECL_UID (f1) - DECL_UID (f2);
1545 /* Generate functions to call static constructors and destructors
1546 for targets that do not support .ctors/.dtors sections. These
1547 functions have magic names which are detected by collect2. */
1550 build_cdtor_fns (void)
1552 if (!VEC_empty (tree, static_ctors))
1554 gcc_assert (!targetm.have_ctors_dtors || in_lto_p);
1555 qsort (VEC_address (tree, static_ctors),
1556 VEC_length (tree, static_ctors),
1559 build_cdtor (/*ctor_p=*/true, static_ctors);
1562 if (!VEC_empty (tree, static_dtors))
1564 gcc_assert (!targetm.have_ctors_dtors || in_lto_p);
1565 qsort (VEC_address (tree, static_dtors),
1566 VEC_length (tree, static_dtors),
1569 build_cdtor (/*ctor_p=*/false, static_dtors);
1573 /* Look for constructors and destructors and produce function calling them.
1574 This is needed for targets not supporting ctors or dtors, but we perform the
1575 transformation also at linktime to merge possibly numberous
1576 constructors/destructors into single function to improve code locality and
1580 ipa_cdtor_merge (void)
1582 struct cgraph_node *node;
1583 for (node = cgraph_nodes; node; node = node->next)
1585 && (DECL_STATIC_CONSTRUCTOR (node->decl)
1586 || DECL_STATIC_DESTRUCTOR (node->decl)))
1587 record_cdtor_fn (node);
1589 VEC_free (tree, heap, static_ctors);
1590 VEC_free (tree, heap, static_dtors);
1594 /* Perform the pass when we have no ctors/dtors support
1595 or at LTO time to merge multiple constructors into single
1599 gate_ipa_cdtor_merge (void)
1601 return !targetm.have_ctors_dtors || (optimize && in_lto_p);
1604 struct ipa_opt_pass_d pass_ipa_cdtor_merge =
1609 gate_ipa_cdtor_merge, /* gate */
1610 ipa_cdtor_merge, /* execute */
1613 0, /* static_pass_number */
1614 TV_CGRAPHOPT, /* tv_id */
1615 0, /* properties_required */
1616 0, /* properties_provided */
1617 0, /* properties_destroyed */
1618 0, /* todo_flags_start */
1619 0 /* todo_flags_finish */
1621 NULL, /* generate_summary */
1622 NULL, /* write_summary */
1623 NULL, /* read_summary */
1624 NULL, /* write_optimization_summary */
1625 NULL, /* read_optimization_summary */
1626 NULL, /* stmt_fixup */
1628 NULL, /* function_transform */
1629 NULL /* variable_transform */