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 /* Keep around virtual functions for possible devirtualization. */
243 || (!before_inlining_p
244 && !node->global.inlined_to
245 && DECL_VIRTUAL_P (node->decl)
246 && (DECL_COMDAT (node->decl) || DECL_EXTERNAL (node->decl))))
247 && ((!DECL_EXTERNAL (node->decl))
248 || before_inlining_p))
250 gcc_assert (!node->global.inlined_to);
251 enqueue_cgraph_node (node, &first);
252 node->reachable = true;
256 gcc_assert (!node->aux);
257 node->reachable = false;
259 for (vnode = varpool_nodes; vnode; vnode = vnode->next)
261 vnode->next_needed = NULL;
262 vnode->prev_needed = NULL;
263 if (!varpool_can_remove_if_no_refs (vnode))
265 vnode->needed = false;
266 varpool_mark_needed_node (vnode);
267 enqueue_varpool_node (vnode, &first_varpool);
270 vnode->needed = false;
273 /* Perform reachability analysis. As a special case do not consider
274 extern inline functions not inlined as live because we won't output
277 We maintain two worklist, one for cgraph nodes other for varpools and
278 are finished once both are empty. */
280 while (first != (struct cgraph_node *) (void *) 1
281 || first_varpool != (struct varpool_node *) (void *) 1)
283 if (first != (struct cgraph_node *) (void *) 1)
285 struct cgraph_edge *e;
287 first = (struct cgraph_node *) first->aux;
288 if (!node->reachable)
289 node->aux = (void *)2;
291 /* If we found this node reachable, first mark on the callees
292 reachable too, unless they are direct calls to extern inline functions
293 we decided to not inline. */
296 for (e = node->callees; e; e = e->next_callee)
297 if (!e->callee->reachable
299 && (!e->inline_failed || !e->callee->analyzed
300 || (!DECL_EXTERNAL (e->callee->decl))
301 || before_inlining_p))
303 e->callee->reachable = true;
304 enqueue_cgraph_node (e->callee, &first);
306 process_references (&node->ref_list, &first, &first_varpool, before_inlining_p);
309 /* If any function in a comdat group is reachable, force
310 all other functions in the same comdat group to be
312 if (node->same_comdat_group
314 && !node->global.inlined_to)
316 for (next = node->same_comdat_group;
318 next = next->same_comdat_group)
319 if (!next->reachable)
321 next->reachable = true;
322 enqueue_cgraph_node (next, &first);
326 /* We can freely remove inline clones even if they are cloned, however if
327 function is clone of real clone, we must keep it around in order to
328 make materialize_clones produce function body with the changes
330 while (node->clone_of && !node->clone_of->aux
331 && !gimple_has_body_p (node->decl))
333 bool noninline = node->clone_of->decl != node->decl;
334 node = node->clone_of;
335 if (noninline && !node->reachable && !node->aux)
337 enqueue_cgraph_node (node, &first);
342 if (first_varpool != (struct varpool_node *) (void *) 1)
344 vnode = first_varpool;
345 first_varpool = (struct varpool_node *)first_varpool->aux;
347 process_references (&vnode->ref_list, &first, &first_varpool, before_inlining_p);
348 /* If any function in a comdat group is reachable, force
349 all other functions in the same comdat group to be
351 if (vnode->same_comdat_group)
353 struct varpool_node *next;
354 for (next = vnode->same_comdat_group;
356 next = next->same_comdat_group)
359 varpool_mark_needed_node (next);
360 enqueue_varpool_node (next, &first_varpool);
366 /* Remove unreachable nodes.
368 Completely unreachable functions can be fully removed from the callgraph.
369 Extern inline functions that we decided to not inline need to become unanalyzed nodes of
370 callgraph (so we still have edges to them). We remove function body then.
372 Also we need to care functions that are unreachable but we need to keep them around
373 for later clonning. In this case we also turn them to unanalyzed nodes, but
374 keep the body around. */
375 for (node = cgraph_nodes; node; node = next)
378 if (node->aux && !node->reachable)
380 cgraph_node_remove_callees (node);
381 ipa_remove_all_references (&node->ref_list);
382 node->analyzed = false;
383 node->local.inlinable = false;
387 struct cgraph_edge *e;
392 node->global.inlined_to = NULL;
394 fprintf (file, " %s", cgraph_node_name (node));
395 /* See if there is reachable caller. */
396 for (e = node->callers; e && !found; e = e->next_caller)
397 if (e->caller->reachable)
399 for (i = 0; (ipa_ref_list_refering_iterate (&node->ref_list, i, ref)
401 if (ref->refering_type == IPA_REF_CGRAPH
402 && ipa_ref_refering_node (ref)->reachable)
404 else if (ref->refering_type == IPA_REF_VARPOOL
405 && ipa_ref_refering_varpool_node (ref)->needed)
408 /* If so, we need to keep node in the callgraph. */
409 if (found || node->needed)
413 struct cgraph_node *clone;
415 /* If there are still clones, we must keep body around.
416 Otherwise we can just remove the body but keep the clone. */
417 for (clone = node->clones; clone;
418 clone = clone->next_sibling_clone)
423 cgraph_release_function_body (node);
424 node->local.inlinable = false;
425 if (node->prev_sibling_clone)
426 node->prev_sibling_clone->next_sibling_clone = node->next_sibling_clone;
427 else if (node->clone_of)
428 node->clone_of->clones = node->next_sibling_clone;
429 if (node->next_sibling_clone)
430 node->next_sibling_clone->prev_sibling_clone = node->prev_sibling_clone;
431 #ifdef ENABLE_CHECKING
433 node->former_clone_of = node->clone_of->decl;
435 node->clone_of = NULL;
436 node->next_sibling_clone = NULL;
437 node->prev_sibling_clone = NULL;
440 gcc_assert (!clone->in_other_partition);
441 node->analyzed = false;
443 cgraph_node_remove_callees (node);
444 ipa_remove_all_references (&node->ref_list);
449 cgraph_remove_node (node);
454 for (node = cgraph_nodes; node; node = node->next)
456 /* Inline clones might be kept around so their materializing allows further
457 cloning. If the function the clone is inlined into is removed, we need
458 to turn it into normal cone. */
459 if (node->global.inlined_to
462 gcc_assert (node->clones);
463 node->global.inlined_to = NULL;
464 update_inlined_to_pointer (node, node);
470 fprintf (file, "\n");
472 /* We must release unused extern inlines or sanity checking will fail. Rest of transformations
473 are undesirable at -O0 since we do not want to remove anything. */
478 fprintf (file, "Reclaiming variables:");
479 for (vnode = varpool_nodes; vnode; vnode = vnext)
485 fprintf (file, " %s", varpool_node_name (vnode));
486 varpool_remove_node (vnode);
491 /* Now update address_taken flags and try to promote functions to be local. */
494 fprintf (file, "\nClearing address taken flags:");
495 for (node = cgraph_nodes; node; node = node->next)
496 if (node->address_taken
497 && !node->reachable_from_other_partition)
502 for (i = 0; ipa_ref_list_refering_iterate (&node->ref_list, i, ref)
505 gcc_assert (ref->use == IPA_REF_ADDR);
511 fprintf (file, " %s", cgraph_node_name (node));
512 node->address_taken = false;
514 if (cgraph_local_node_p (node))
516 node->local.local = true;
518 fprintf (file, " (local)");
523 #ifdef ENABLE_CHECKING
527 /* Reclaim alias pairs for functions that have disappeared from the
529 remove_unreachable_alias_pairs ();
534 /* Discover variables that have no longer address taken or that are read only
535 and update their flags.
537 FIXME: This can not be done in between gimplify and omp_expand since
538 readonly flag plays role on what is shared and what is not. Currently we do
539 this transformation as part of whole program visibility and re-do at
540 ipa-reference pass (to take into account clonning), but it would
541 make sense to do it before early optimizations. */
544 ipa_discover_readonly_nonaddressable_vars (void)
546 struct varpool_node *vnode;
548 fprintf (dump_file, "Clearing variable flags:");
549 for (vnode = varpool_nodes; vnode; vnode = vnode->next)
550 if (vnode->finalized && varpool_all_refs_explicit_p (vnode)
551 && (TREE_ADDRESSABLE (vnode->decl) || !TREE_READONLY (vnode->decl)))
553 bool written = false;
554 bool address_taken = false;
557 for (i = 0; ipa_ref_list_refering_iterate (&vnode->ref_list, i, ref)
558 && (!written || !address_taken); i++)
562 address_taken = true;
570 if (TREE_ADDRESSABLE (vnode->decl) && !address_taken)
573 fprintf (dump_file, " %s (addressable)", varpool_node_name (vnode));
574 TREE_ADDRESSABLE (vnode->decl) = 0;
576 if (!TREE_READONLY (vnode->decl) && !address_taken && !written
577 /* Making variable in explicit section readonly can cause section
579 See e.g. gcc.c-torture/compile/pr23237.c */
580 && DECL_SECTION_NAME (vnode->decl) == NULL)
583 fprintf (dump_file, " %s (read-only)", varpool_node_name (vnode));
584 TREE_READONLY (vnode->decl) = 1;
588 fprintf (dump_file, "\n");
591 /* Return true when function NODE should be considered externally visible. */
594 cgraph_externally_visible_p (struct cgraph_node *node, bool whole_program, bool aliased)
596 if (!node->local.finalized)
598 if (!DECL_COMDAT (node->decl)
599 && (!TREE_PUBLIC (node->decl) || DECL_EXTERNAL (node->decl)))
602 /* Do not even try to be smart about aliased nodes. Until we properly
603 represent everything by same body alias, these are just evil. */
607 /* If linker counts on us, we must preserve the function. */
608 if (cgraph_used_from_object_file_p (node))
610 /* When doing link time optimizations, hidden symbols become local. */
612 && (DECL_VISIBILITY (node->decl) == VISIBILITY_HIDDEN
613 || DECL_VISIBILITY (node->decl) == VISIBILITY_INTERNAL)
614 /* Be sure that node is defined in IR file, not in other object
615 file. In that case we don't set used_from_other_object_file. */
618 else if (!whole_program)
620 /* COMDAT functions must be shared only if they have address taken,
621 otherwise we can produce our own private implementation with
623 else if (DECL_COMDAT (node->decl))
625 if (node->address_taken || !node->analyzed)
627 if (node->same_comdat_group)
629 struct cgraph_node *next;
631 /* If more than one function is in the same COMDAT group, it must
632 be shared even if just one function in the comdat group has
634 for (next = node->same_comdat_group;
636 next = next->same_comdat_group)
637 if (next->address_taken || !next->analyzed)
641 if (DECL_PRESERVE_P (node->decl))
643 if (MAIN_NAME_P (DECL_NAME (node->decl)))
645 if (lookup_attribute ("externally_visible", DECL_ATTRIBUTES (node->decl)))
650 /* Dissolve the same_comdat_group list in which NODE resides. */
653 dissolve_same_comdat_group_list (struct cgraph_node *node)
655 struct cgraph_node *n = node, *next;
658 next = n->same_comdat_group;
659 n->same_comdat_group = NULL;
665 /* Mark visibility of all functions.
667 A local function is one whose calls can occur only in the current
668 compilation unit and all its calls are explicit, so we can change
669 its calling convention. We simply mark all static functions whose
670 address is not taken as local.
672 We also change the TREE_PUBLIC flag of all declarations that are public
673 in language point of view but we want to overwrite this default
674 via visibilities for the backend point of view. */
677 function_and_variable_visibility (bool whole_program)
679 struct cgraph_node *node;
680 struct varpool_node *vnode;
681 struct pointer_set_t *aliased_nodes = pointer_set_create ();
682 struct pointer_set_t *aliased_vnodes = pointer_set_create ();
686 /* Discover aliased nodes. */
687 FOR_EACH_VEC_ELT (alias_pair, alias_pairs, i, p)
690 fprintf (dump_file, "Alias %s->%s",
691 IDENTIFIER_POINTER (DECL_ASSEMBLER_NAME (p->decl)),
692 IDENTIFIER_POINTER (p->target));
694 if ((node = cgraph_node_for_asm (p->target)) != NULL)
696 gcc_assert (node->needed);
697 pointer_set_insert (aliased_nodes, node);
699 fprintf (dump_file, " node %s/%i",
700 cgraph_node_name (node), node->uid);
702 else if ((vnode = varpool_node_for_asm (p->target)) != NULL)
704 gcc_assert (vnode->needed);
705 pointer_set_insert (aliased_vnodes, vnode);
707 fprintf (dump_file, " varpool node %s",
708 varpool_node_name (vnode));
711 fprintf (dump_file, "\n");
714 for (node = cgraph_nodes; node; node = node->next)
716 /* C++ FE on lack of COMDAT support create local COMDAT functions
717 (that ought to be shared but can not due to object format
718 limitations). It is neccesary to keep the flag to make rest of C++ FE
719 happy. Clear the flag here to avoid confusion in middle-end. */
720 if (DECL_COMDAT (node->decl) && !TREE_PUBLIC (node->decl))
721 DECL_COMDAT (node->decl) = 0;
722 /* For external decls stop tracking same_comdat_group, it doesn't matter
723 what comdat group they are in when they won't be emitted in this TU,
724 and simplifies later passes. */
725 if (node->same_comdat_group && DECL_EXTERNAL (node->decl))
727 #ifdef ENABLE_CHECKING
728 struct cgraph_node *n;
730 for (n = node->same_comdat_group;
732 n = n->same_comdat_group)
733 /* If at least one of same comdat group functions is external,
734 all of them have to be, otherwise it is a front-end bug. */
735 gcc_assert (DECL_EXTERNAL (n->decl));
737 dissolve_same_comdat_group_list (node);
739 gcc_assert ((!DECL_WEAK (node->decl) && !DECL_COMDAT (node->decl))
740 || TREE_PUBLIC (node->decl) || DECL_EXTERNAL (node->decl));
741 if (cgraph_externally_visible_p (node, whole_program,
742 pointer_set_contains (aliased_nodes,
745 gcc_assert (!node->global.inlined_to);
746 node->local.externally_visible = true;
749 node->local.externally_visible = false;
750 if (!node->local.externally_visible && node->analyzed
751 && !DECL_EXTERNAL (node->decl))
753 struct cgraph_node *alias;
754 gcc_assert (whole_program || in_lto_p || !TREE_PUBLIC (node->decl));
755 cgraph_make_decl_local (node->decl);
756 node->resolution = LDPR_PREVAILING_DEF_IRONLY;
757 for (alias = node->same_body; alias; alias = alias->next)
758 cgraph_make_decl_local (alias->decl);
759 if (node->same_comdat_group)
760 /* cgraph_externally_visible_p has already checked all other nodes
761 in the group and they will all be made local. We need to
762 dissolve the group at once so that the predicate does not
764 dissolve_same_comdat_group_list (node);
766 node->local.local = cgraph_local_node_p (node);
768 for (vnode = varpool_nodes; vnode; vnode = vnode->next)
770 /* weak flag makes no sense on local variables. */
771 gcc_assert (!DECL_WEAK (vnode->decl)
772 || TREE_PUBLIC (vnode->decl) || DECL_EXTERNAL (vnode->decl));
773 /* In several cases declarations can not be common:
775 - when declaration has initializer
777 - when it has specific section
778 - when it resides in non-generic address space.
779 - if declaration is local, it will get into .local common section
780 so common flag is not needed. Frontends still produce these in
781 certain cases, such as for:
783 static int a __attribute__ ((common))
785 Canonicalize things here and clear the redundant flag. */
786 if (DECL_COMMON (vnode->decl)
787 && (!(TREE_PUBLIC (vnode->decl) || DECL_EXTERNAL (vnode->decl))
788 || (DECL_INITIAL (vnode->decl)
789 && DECL_INITIAL (vnode->decl) != error_mark_node)
790 || DECL_WEAK (vnode->decl)
791 || DECL_SECTION_NAME (vnode->decl) != NULL
792 || ! (ADDR_SPACE_GENERIC_P
793 (TYPE_ADDR_SPACE (TREE_TYPE (vnode->decl))))))
794 DECL_COMMON (vnode->decl) = 0;
796 for (vnode = varpool_nodes_queue; vnode; vnode = vnode->next_needed)
798 if (!vnode->finalized)
801 && (DECL_COMDAT (vnode->decl) || TREE_PUBLIC (vnode->decl))
803 /* We can privatize comdat readonly variables whose address is
804 not taken, but doing so is not going to bring us
805 optimization oppurtunities until we start reordering
807 || DECL_COMDAT (vnode->decl)
808 || DECL_WEAK (vnode->decl))
809 /* When doing linktime optimizations, all hidden symbols will
812 || (DECL_VISIBILITY (vnode->decl) != VISIBILITY_HIDDEN
813 && DECL_VISIBILITY (vnode->decl) != VISIBILITY_INTERNAL)
814 /* We can get prevailing decision in other object file.
815 In this case we do not sed used_from_object_file. */
816 || !vnode->finalized))
817 || DECL_PRESERVE_P (vnode->decl)
818 || varpool_used_from_object_file_p (vnode)
819 || pointer_set_contains (aliased_vnodes, vnode)
820 || lookup_attribute ("externally_visible",
821 DECL_ATTRIBUTES (vnode->decl))))
822 vnode->externally_visible = true;
824 vnode->externally_visible = false;
825 if (!vnode->externally_visible)
827 gcc_assert (in_lto_p || whole_program || !TREE_PUBLIC (vnode->decl));
828 cgraph_make_decl_local (vnode->decl);
829 vnode->resolution = LDPR_PREVAILING_DEF_IRONLY;
831 gcc_assert (TREE_STATIC (vnode->decl));
833 pointer_set_destroy (aliased_nodes);
834 pointer_set_destroy (aliased_vnodes);
838 fprintf (dump_file, "\nMarking local functions:");
839 for (node = cgraph_nodes; node; node = node->next)
840 if (node->local.local)
841 fprintf (dump_file, " %s", cgraph_node_name (node));
842 fprintf (dump_file, "\n\n");
843 fprintf (dump_file, "\nMarking externally visible functions:");
844 for (node = cgraph_nodes; node; node = node->next)
845 if (node->local.externally_visible)
846 fprintf (dump_file, " %s", cgraph_node_name (node));
847 fprintf (dump_file, "\n\n");
848 fprintf (dump_file, "\nMarking externally visible variables:");
849 for (vnode = varpool_nodes_queue; vnode; vnode = vnode->next_needed)
850 if (vnode->externally_visible)
851 fprintf (dump_file, " %s", varpool_node_name (vnode));
852 fprintf (dump_file, "\n\n");
854 cgraph_function_flags_ready = true;
858 /* Local function pass handling visibilities. This happens before LTO streaming
859 so in particular -fwhole-program should be ignored at this level. */
862 local_function_and_variable_visibility (void)
864 return function_and_variable_visibility (flag_whole_program && !flag_lto && !flag_whopr);
867 struct simple_ipa_opt_pass pass_ipa_function_and_variable_visibility =
871 "visibility", /* name */
873 local_function_and_variable_visibility,/* execute */
876 0, /* static_pass_number */
877 TV_CGRAPHOPT, /* tv_id */
878 0, /* properties_required */
879 0, /* properties_provided */
880 0, /* properties_destroyed */
881 0, /* todo_flags_start */
882 TODO_remove_functions | TODO_dump_cgraph
883 | TODO_ggc_collect /* todo_flags_finish */
887 /* Do not re-run on ltrans stage. */
890 gate_whole_program_function_and_variable_visibility (void)
895 /* Bring functionss local at LTO time whith -fwhole-program. */
898 whole_program_function_and_variable_visibility (void)
900 struct cgraph_node *node;
901 struct varpool_node *vnode;
903 function_and_variable_visibility (flag_whole_program);
905 for (node = cgraph_nodes; node; node = node->next)
906 if ((node->local.externally_visible && !DECL_COMDAT (node->decl))
907 && node->local.finalized)
908 cgraph_mark_needed_node (node);
909 for (vnode = varpool_nodes_queue; vnode; vnode = vnode->next_needed)
910 if (vnode->externally_visible && !DECL_COMDAT (vnode->decl))
911 varpool_mark_needed_node (vnode);
914 fprintf (dump_file, "\nNeeded variables:");
915 for (vnode = varpool_nodes_queue; vnode; vnode = vnode->next_needed)
917 fprintf (dump_file, " %s", varpool_node_name (vnode));
918 fprintf (dump_file, "\n\n");
921 ipa_discover_readonly_nonaddressable_vars ();
925 struct ipa_opt_pass_d pass_ipa_whole_program_visibility =
929 "whole-program", /* name */
930 gate_whole_program_function_and_variable_visibility,/* gate */
931 whole_program_function_and_variable_visibility,/* execute */
934 0, /* static_pass_number */
935 TV_CGRAPHOPT, /* tv_id */
936 0, /* properties_required */
937 0, /* properties_provided */
938 0, /* properties_destroyed */
939 0, /* todo_flags_start */
940 TODO_remove_functions | TODO_dump_cgraph
941 | TODO_ggc_collect /* todo_flags_finish */
943 NULL, /* generate_summary */
944 NULL, /* write_summary */
945 NULL, /* read_summary */
946 NULL, /* write_optimization_summary */
947 NULL, /* read_optimization_summary */
948 NULL, /* stmt_fixup */
950 NULL, /* function_transform */
951 NULL, /* variable_transform */
954 /* Hash a cgraph node set element. */
957 hash_cgraph_node_set_element (const void *p)
959 const_cgraph_node_set_element element = (const_cgraph_node_set_element) p;
960 return htab_hash_pointer (element->node);
963 /* Compare two cgraph node set elements. */
966 eq_cgraph_node_set_element (const void *p1, const void *p2)
968 const_cgraph_node_set_element e1 = (const_cgraph_node_set_element) p1;
969 const_cgraph_node_set_element e2 = (const_cgraph_node_set_element) p2;
971 return e1->node == e2->node;
974 /* Create a new cgraph node set. */
977 cgraph_node_set_new (void)
979 cgraph_node_set new_node_set;
981 new_node_set = ggc_alloc_cgraph_node_set_def ();
982 new_node_set->hashtab = htab_create_ggc (10,
983 hash_cgraph_node_set_element,
984 eq_cgraph_node_set_element,
986 new_node_set->nodes = NULL;
990 /* Add cgraph_node NODE to cgraph_node_set SET. */
993 cgraph_node_set_add (cgraph_node_set set, struct cgraph_node *node)
996 cgraph_node_set_element element;
997 struct cgraph_node_set_element_def dummy;
1000 slot = htab_find_slot (set->hashtab, &dummy, INSERT);
1002 if (*slot != HTAB_EMPTY_ENTRY)
1004 element = (cgraph_node_set_element) *slot;
1005 gcc_assert (node == element->node
1006 && (VEC_index (cgraph_node_ptr, set->nodes, element->index)
1011 /* Insert node into hash table. */
1012 element = ggc_alloc_cgraph_node_set_element_def ();
1013 element->node = node;
1014 element->index = VEC_length (cgraph_node_ptr, set->nodes);
1017 /* Insert into node vector. */
1018 VEC_safe_push (cgraph_node_ptr, gc, set->nodes, node);
1021 /* Remove cgraph_node NODE from cgraph_node_set SET. */
1024 cgraph_node_set_remove (cgraph_node_set set, struct cgraph_node *node)
1026 void **slot, **last_slot;
1027 cgraph_node_set_element element, last_element;
1028 struct cgraph_node *last_node;
1029 struct cgraph_node_set_element_def dummy;
1032 slot = htab_find_slot (set->hashtab, &dummy, NO_INSERT);
1036 element = (cgraph_node_set_element) *slot;
1037 gcc_assert (VEC_index (cgraph_node_ptr, set->nodes, element->index)
1040 /* Remove from vector. We do this by swapping node with the last element
1042 last_node = VEC_pop (cgraph_node_ptr, set->nodes);
1043 if (last_node != node)
1045 dummy.node = last_node;
1046 last_slot = htab_find_slot (set->hashtab, &dummy, NO_INSERT);
1047 last_element = (cgraph_node_set_element) *last_slot;
1048 gcc_assert (last_element);
1050 /* Move the last element to the original spot of NODE. */
1051 last_element->index = element->index;
1052 VEC_replace (cgraph_node_ptr, set->nodes, last_element->index,
1056 /* Remove element from hash table. */
1057 htab_clear_slot (set->hashtab, slot);
1061 /* Find NODE in SET and return an iterator to it if found. A null iterator
1062 is returned if NODE is not in SET. */
1064 cgraph_node_set_iterator
1065 cgraph_node_set_find (cgraph_node_set set, struct cgraph_node *node)
1068 struct cgraph_node_set_element_def dummy;
1069 cgraph_node_set_element element;
1070 cgraph_node_set_iterator csi;
1073 slot = htab_find_slot (set->hashtab, &dummy, NO_INSERT);
1075 csi.index = (unsigned) ~0;
1078 element = (cgraph_node_set_element) *slot;
1079 gcc_assert (VEC_index (cgraph_node_ptr, set->nodes, element->index)
1081 csi.index = element->index;
1088 /* Dump content of SET to file F. */
1091 dump_cgraph_node_set (FILE *f, cgraph_node_set set)
1093 cgraph_node_set_iterator iter;
1095 for (iter = csi_start (set); !csi_end_p (iter); csi_next (&iter))
1097 struct cgraph_node *node = csi_node (iter);
1098 fprintf (f, " %s/%i", cgraph_node_name (node), node->uid);
1103 /* Dump content of SET to stderr. */
1106 debug_cgraph_node_set (cgraph_node_set set)
1108 dump_cgraph_node_set (stderr, set);
1111 /* Hash a varpool node set element. */
1114 hash_varpool_node_set_element (const void *p)
1116 const_varpool_node_set_element element = (const_varpool_node_set_element) p;
1117 return htab_hash_pointer (element->node);
1120 /* Compare two varpool node set elements. */
1123 eq_varpool_node_set_element (const void *p1, const void *p2)
1125 const_varpool_node_set_element e1 = (const_varpool_node_set_element) p1;
1126 const_varpool_node_set_element e2 = (const_varpool_node_set_element) p2;
1128 return e1->node == e2->node;
1131 /* Create a new varpool node set. */
1134 varpool_node_set_new (void)
1136 varpool_node_set new_node_set;
1138 new_node_set = ggc_alloc_varpool_node_set_def ();
1139 new_node_set->hashtab = htab_create_ggc (10,
1140 hash_varpool_node_set_element,
1141 eq_varpool_node_set_element,
1143 new_node_set->nodes = NULL;
1144 return new_node_set;
1147 /* Add varpool_node NODE to varpool_node_set SET. */
1150 varpool_node_set_add (varpool_node_set set, struct varpool_node *node)
1153 varpool_node_set_element element;
1154 struct varpool_node_set_element_def dummy;
1157 slot = htab_find_slot (set->hashtab, &dummy, INSERT);
1159 if (*slot != HTAB_EMPTY_ENTRY)
1161 element = (varpool_node_set_element) *slot;
1162 gcc_assert (node == element->node
1163 && (VEC_index (varpool_node_ptr, set->nodes, element->index)
1168 /* Insert node into hash table. */
1169 element = ggc_alloc_varpool_node_set_element_def ();
1170 element->node = node;
1171 element->index = VEC_length (varpool_node_ptr, set->nodes);
1174 /* Insert into node vector. */
1175 VEC_safe_push (varpool_node_ptr, gc, set->nodes, node);
1178 /* Remove varpool_node NODE from varpool_node_set SET. */
1181 varpool_node_set_remove (varpool_node_set set, struct varpool_node *node)
1183 void **slot, **last_slot;
1184 varpool_node_set_element element, last_element;
1185 struct varpool_node *last_node;
1186 struct varpool_node_set_element_def dummy;
1189 slot = htab_find_slot (set->hashtab, &dummy, NO_INSERT);
1193 element = (varpool_node_set_element) *slot;
1194 gcc_assert (VEC_index (varpool_node_ptr, set->nodes, element->index)
1197 /* Remove from vector. We do this by swapping node with the last element
1199 last_node = VEC_pop (varpool_node_ptr, set->nodes);
1200 if (last_node != node)
1202 dummy.node = last_node;
1203 last_slot = htab_find_slot (set->hashtab, &dummy, NO_INSERT);
1204 last_element = (varpool_node_set_element) *last_slot;
1205 gcc_assert (last_element);
1207 /* Move the last element to the original spot of NODE. */
1208 last_element->index = element->index;
1209 VEC_replace (varpool_node_ptr, set->nodes, last_element->index,
1213 /* Remove element from hash table. */
1214 htab_clear_slot (set->hashtab, slot);
1218 /* Find NODE in SET and return an iterator to it if found. A null iterator
1219 is returned if NODE is not in SET. */
1221 varpool_node_set_iterator
1222 varpool_node_set_find (varpool_node_set set, struct varpool_node *node)
1225 struct varpool_node_set_element_def dummy;
1226 varpool_node_set_element element;
1227 varpool_node_set_iterator vsi;
1230 slot = htab_find_slot (set->hashtab, &dummy, NO_INSERT);
1232 vsi.index = (unsigned) ~0;
1235 element = (varpool_node_set_element) *slot;
1236 gcc_assert (VEC_index (varpool_node_ptr, set->nodes, element->index)
1238 vsi.index = element->index;
1245 /* Dump content of SET to file F. */
1248 dump_varpool_node_set (FILE *f, varpool_node_set set)
1250 varpool_node_set_iterator iter;
1252 for (iter = vsi_start (set); !vsi_end_p (iter); vsi_next (&iter))
1254 struct varpool_node *node = vsi_node (iter);
1255 fprintf (f, " %s", varpool_node_name (node));
1260 /* Dump content of SET to stderr. */
1263 debug_varpool_node_set (varpool_node_set set)
1265 dump_varpool_node_set (stderr, set);
1269 /* Simple ipa profile pass propagating frequencies across the callgraph. */
1274 struct cgraph_node **order = XCNEWVEC (struct cgraph_node *, cgraph_n_nodes);
1275 struct cgraph_edge *e;
1277 bool something_changed = false;
1280 order_pos = cgraph_postorder (order);
1281 for (i = order_pos - 1; i >= 0; i--)
1283 if (order[i]->local.local && cgraph_propagate_frequency (order[i]))
1285 for (e = order[i]->callees; e; e = e->next_callee)
1286 if (e->callee->local.local && !e->callee->aux)
1288 something_changed = true;
1289 e->callee->aux = (void *)1;
1292 order[i]->aux = NULL;
1295 while (something_changed)
1297 something_changed = false;
1298 for (i = order_pos - 1; i >= 0; i--)
1300 if (order[i]->aux && cgraph_propagate_frequency (order[i]))
1302 for (e = order[i]->callees; e; e = e->next_callee)
1303 if (e->callee->local.local && !e->callee->aux)
1305 something_changed = true;
1306 e->callee->aux = (void *)1;
1309 order[i]->aux = NULL;
1317 gate_ipa_profile (void)
1319 return flag_ipa_profile;
1322 struct ipa_opt_pass_d pass_ipa_profile =
1326 "ipa-profile", /* name */
1327 gate_ipa_profile, /* gate */
1328 ipa_profile, /* execute */
1331 0, /* static_pass_number */
1332 TV_IPA_PROFILE, /* tv_id */
1333 0, /* properties_required */
1334 0, /* properties_provided */
1335 0, /* properties_destroyed */
1336 0, /* todo_flags_start */
1337 0 /* todo_flags_finish */
1339 NULL, /* generate_summary */
1340 NULL, /* write_summary */
1341 NULL, /* read_summary */
1342 NULL, /* write_optimization_summary */
1343 NULL, /* read_optimization_summary */
1344 NULL, /* stmt_fixup */
1346 NULL, /* function_transform */
1347 NULL /* variable_transform */
1350 /* Generate and emit a static constructor or destructor. WHICH must
1351 be one of 'I' (for a constructor) or 'D' (for a destructor). BODY
1352 is a STATEMENT_LIST containing GENERIC statements. PRIORITY is the
1353 initialization priority for this constructor or destructor. */
1356 cgraph_build_static_cdtor (char which, tree body, int priority)
1358 static int counter = 0;
1360 tree decl, name, resdecl;
1362 /* The priority is encoded in the constructor or destructor name.
1363 collect2 will sort the names and arrange that they are called at
1365 sprintf (which_buf, "%c_%.5d_%d", which, priority, counter++);
1366 name = get_file_function_name (which_buf);
1368 decl = build_decl (input_location, FUNCTION_DECL, name,
1369 build_function_type_list (void_type_node, NULL_TREE));
1370 current_function_decl = decl;
1372 resdecl = build_decl (input_location,
1373 RESULT_DECL, NULL_TREE, void_type_node);
1374 DECL_ARTIFICIAL (resdecl) = 1;
1375 DECL_RESULT (decl) = resdecl;
1376 DECL_CONTEXT (resdecl) = decl;
1378 allocate_struct_function (decl, false);
1380 TREE_STATIC (decl) = 1;
1381 TREE_USED (decl) = 1;
1382 DECL_ARTIFICIAL (decl) = 1;
1383 DECL_NO_INSTRUMENT_FUNCTION_ENTRY_EXIT (decl) = 1;
1384 DECL_SAVED_TREE (decl) = body;
1385 if (!targetm.have_ctors_dtors)
1387 TREE_PUBLIC (decl) = 1;
1388 DECL_PRESERVE_P (decl) = 1;
1390 DECL_UNINLINABLE (decl) = 1;
1392 DECL_INITIAL (decl) = make_node (BLOCK);
1393 TREE_USED (DECL_INITIAL (decl)) = 1;
1395 DECL_SOURCE_LOCATION (decl) = input_location;
1396 cfun->function_end_locus = input_location;
1401 DECL_STATIC_CONSTRUCTOR (decl) = 1;
1402 decl_init_priority_insert (decl, priority);
1405 DECL_STATIC_DESTRUCTOR (decl) = 1;
1406 decl_fini_priority_insert (decl, priority);
1412 gimplify_function_tree (decl);
1414 cgraph_add_new_function (decl, false);
1417 current_function_decl = NULL;
1421 /* A vector of FUNCTION_DECLs declared as static constructors. */
1422 static VEC(tree, heap) *static_ctors;
1423 /* A vector of FUNCTION_DECLs declared as static destructors. */
1424 static VEC(tree, heap) *static_dtors;
1426 /* When target does not have ctors and dtors, we call all constructor
1427 and destructor by special initialization/destruction function
1428 recognized by collect2.
1430 When we are going to build this function, collect all constructors and
1431 destructors and turn them into normal functions. */
1434 record_cdtor_fn (struct cgraph_node *node)
1436 if (DECL_STATIC_CONSTRUCTOR (node->decl))
1437 VEC_safe_push (tree, heap, static_ctors, node->decl);
1438 if (DECL_STATIC_DESTRUCTOR (node->decl))
1439 VEC_safe_push (tree, heap, static_dtors, node->decl);
1440 node = cgraph_node (node->decl);
1441 node->local.disregard_inline_limits = 1;
1444 /* Define global constructors/destructor functions for the CDTORS, of
1445 which they are LEN. The CDTORS are sorted by initialization
1446 priority. If CTOR_P is true, these are constructors; otherwise,
1447 they are destructors. */
1450 build_cdtor (bool ctor_p, VEC (tree, heap) *cdtors)
1453 size_t len = VEC_length (tree, cdtors);
1460 priority_type priority;
1468 fn = VEC_index (tree, cdtors, j);
1469 p = ctor_p ? DECL_INIT_PRIORITY (fn) : DECL_FINI_PRIORITY (fn);
1472 else if (p != priority)
1478 /* When there is only one cdtor and target supports them, do nothing. */
1480 && targetm.have_ctors_dtors)
1485 /* Find the next batch of constructors/destructors with the same
1486 initialization priority. */
1490 fn = VEC_index (tree, cdtors, i);
1491 call = build_call_expr (fn, 0);
1493 DECL_STATIC_CONSTRUCTOR (fn) = 0;
1495 DECL_STATIC_DESTRUCTOR (fn) = 0;
1496 /* We do not want to optimize away pure/const calls here.
1497 When optimizing, these should be already removed, when not
1498 optimizing, we want user to be able to breakpoint in them. */
1499 TREE_SIDE_EFFECTS (call) = 1;
1500 append_to_statement_list (call, &body);
1502 gcc_assert (body != NULL_TREE);
1503 /* Generate a function to call all the function of like
1505 cgraph_build_static_cdtor (ctor_p ? 'I' : 'D', body, priority);
1509 /* Comparison function for qsort. P1 and P2 are actually of type
1510 "tree *" and point to static constructors. DECL_INIT_PRIORITY is
1511 used to determine the sort order. */
1514 compare_ctor (const void *p1, const void *p2)
1521 f1 = *(const tree *)p1;
1522 f2 = *(const tree *)p2;
1523 priority1 = DECL_INIT_PRIORITY (f1);
1524 priority2 = DECL_INIT_PRIORITY (f2);
1526 if (priority1 < priority2)
1528 else if (priority1 > priority2)
1531 /* Ensure a stable sort. Constructors are executed in backwarding
1532 order to make LTO initialize braries first. */
1533 return DECL_UID (f2) - DECL_UID (f1);
1536 /* Comparison function for qsort. P1 and P2 are actually of type
1537 "tree *" and point to static destructors. DECL_FINI_PRIORITY is
1538 used to determine the sort order. */
1541 compare_dtor (const void *p1, const void *p2)
1548 f1 = *(const tree *)p1;
1549 f2 = *(const tree *)p2;
1550 priority1 = DECL_FINI_PRIORITY (f1);
1551 priority2 = DECL_FINI_PRIORITY (f2);
1553 if (priority1 < priority2)
1555 else if (priority1 > priority2)
1558 /* Ensure a stable sort. */
1559 return DECL_UID (f1) - DECL_UID (f2);
1562 /* Generate functions to call static constructors and destructors
1563 for targets that do not support .ctors/.dtors sections. These
1564 functions have magic names which are detected by collect2. */
1567 build_cdtor_fns (void)
1569 if (!VEC_empty (tree, static_ctors))
1571 gcc_assert (!targetm.have_ctors_dtors || in_lto_p);
1572 VEC_qsort (tree, static_ctors, compare_ctor);
1573 build_cdtor (/*ctor_p=*/true, static_ctors);
1576 if (!VEC_empty (tree, static_dtors))
1578 gcc_assert (!targetm.have_ctors_dtors || in_lto_p);
1579 VEC_qsort (tree, static_dtors, compare_dtor);
1580 build_cdtor (/*ctor_p=*/false, static_dtors);
1584 /* Look for constructors and destructors and produce function calling them.
1585 This is needed for targets not supporting ctors or dtors, but we perform the
1586 transformation also at linktime to merge possibly numberous
1587 constructors/destructors into single function to improve code locality and
1591 ipa_cdtor_merge (void)
1593 struct cgraph_node *node;
1594 for (node = cgraph_nodes; node; node = node->next)
1596 && (DECL_STATIC_CONSTRUCTOR (node->decl)
1597 || DECL_STATIC_DESTRUCTOR (node->decl)))
1598 record_cdtor_fn (node);
1600 VEC_free (tree, heap, static_ctors);
1601 VEC_free (tree, heap, static_dtors);
1605 /* Perform the pass when we have no ctors/dtors support
1606 or at LTO time to merge multiple constructors into single
1610 gate_ipa_cdtor_merge (void)
1612 return !targetm.have_ctors_dtors || (optimize && in_lto_p);
1615 struct ipa_opt_pass_d pass_ipa_cdtor_merge =
1620 gate_ipa_cdtor_merge, /* gate */
1621 ipa_cdtor_merge, /* execute */
1624 0, /* static_pass_number */
1625 TV_CGRAPHOPT, /* tv_id */
1626 0, /* properties_required */
1627 0, /* properties_provided */
1628 0, /* properties_destroyed */
1629 0, /* todo_flags_start */
1630 0 /* todo_flags_finish */
1632 NULL, /* generate_summary */
1633 NULL, /* write_summary */
1634 NULL, /* read_summary */
1635 NULL, /* write_optimization_summary */
1636 NULL, /* read_optimization_summary */
1637 NULL, /* stmt_fixup */
1639 NULL, /* function_transform */
1640 NULL /* variable_transform */