OSDN Git Service

* cgraph.c (cgraph_make_decl_local): Handle DECL_ONE_ONLY
[pf3gnuchains/gcc-fork.git] / gcc / ipa.c
1 /* Basic IPA optimizations and utilities.
2    Copyright (C) 2003, 2004, 2005, 2007, 2008, 2009, 2010, 2011
3    Free Software Foundation, Inc.
4
5 This file is part of GCC.
6
7 GCC is free software; you can redistribute it and/or modify it under
8 the terms of the GNU General Public License as published by the Free
9 Software Foundation; either version 3, or (at your option) any later
10 version.
11
12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13 WARRANTY; without even the implied warranty of MERCHANTABILITY or
14 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
15 for more details.
16
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING3.  If not see
19 <http://www.gnu.org/licenses/>.  */
20
21 #include "config.h"
22 #include "system.h"
23 #include "coretypes.h"
24 #include "tm.h"
25 #include "cgraph.h"
26 #include "tree-pass.h"
27 #include "timevar.h"
28 #include "gimple.h"
29 #include "ggc.h"
30 #include "flags.h"
31 #include "pointer-set.h"
32 #include "target.h"
33 #include "tree-iterator.h"
34 #include "ipa-utils.h"
35
36 /* Look for all functions inlined to NODE and update their inlined_to pointers
37    to INLINED_TO.  */
38
39 static void
40 update_inlined_to_pointer (struct cgraph_node *node, struct cgraph_node *inlined_to)
41 {
42   struct cgraph_edge *e;
43   for (e = node->callees; e; e = e->next_callee)
44     if (e->callee->global.inlined_to)
45       {
46         e->callee->global.inlined_to = inlined_to;
47         update_inlined_to_pointer (e->callee, inlined_to);
48       }
49 }
50
51 /* Add cgraph NODE to queue starting at FIRST.
52
53    The queue is linked via AUX pointers and terminated by pointer to 1.
54    We enqueue nodes at two occasions: when we find them reachable or when we find
55    their bodies needed for further clonning.  In the second case we mark them
56    by pointer to 2 after processing so they are re-queue when they become
57    reachable.  */
58
59 static void
60 enqueue_cgraph_node (struct cgraph_node *node, struct cgraph_node **first)
61 {
62   /* Node is still in queue; do nothing.  */
63   if (node->aux && node->aux != (void *) 2)
64     return;
65   /* Node was already processed as unreachable, re-enqueue
66      only if it became reachable now.  */
67   if (node->aux == (void *)2 && !node->reachable)
68     return;
69   node->aux = *first;
70   *first = node;
71 }
72
73 /* Add varpool NODE to queue starting at FIRST.  */
74
75 static void
76 enqueue_varpool_node (struct varpool_node *node, struct varpool_node **first)
77 {
78   node->aux = *first;
79   *first = node;
80 }
81
82 /* Process references.  */
83
84 static void
85 process_references (struct ipa_ref_list *list,
86                     struct cgraph_node **first,
87                     struct varpool_node **first_varpool,
88                     bool before_inlining_p)
89 {
90   int i;
91   struct ipa_ref *ref;
92   for (i = 0; ipa_ref_list_reference_iterate (list, i, ref); i++)
93     {
94       if (ref->refered_type == IPA_REF_CGRAPH)
95         {
96           struct cgraph_node *node = ipa_ref_node (ref);
97           if (!node->reachable
98               && node->analyzed
99               && (!DECL_EXTERNAL (node->decl)
100                   || before_inlining_p))
101             node->reachable = true;
102           enqueue_cgraph_node (node, first);
103         }
104       else
105         {
106           struct varpool_node *node = ipa_ref_varpool_node (ref);
107           if (!node->needed)
108             {
109               varpool_mark_needed_node (node);
110               enqueue_varpool_node (node, first_varpool);
111             }
112         }
113     }
114 }
115
116
117 /* Return true when NODE can not be local. Worker for cgraph_local_node_p.  */
118
119 static bool
120 cgraph_non_local_node_p_1 (struct cgraph_node *node, void *data ATTRIBUTE_UNUSED)
121 {
122    /* FIXME: Aliases can be local, but i386 gets thunks wrong then.  */
123    return !(cgraph_only_called_directly_or_aliased_p (node)
124             && !ipa_ref_has_aliases_p (&node->ref_list)
125             && node->analyzed
126             && !DECL_EXTERNAL (node->decl)
127             && !node->local.externally_visible
128             && !node->reachable_from_other_partition
129             && !node->in_other_partition);
130 }
131
132 /* Return true when function can be marked local.  */
133
134 static bool
135 cgraph_local_node_p (struct cgraph_node *node)
136 {
137    struct cgraph_node *n = cgraph_function_or_thunk_node (node, NULL);
138
139    /* FIXME: thunks can be considered local, but we need prevent i386
140       from attempting to change calling convention of them.  */
141    if (n->thunk.thunk_p)
142      return false;
143    return !cgraph_for_node_and_aliases (n,
144                                         cgraph_non_local_node_p_1, NULL, true);
145                                         
146 }
147
148 /* Return true when NODE has ADDR reference.  */
149
150 static bool
151 has_addr_references_p (struct cgraph_node *node,
152                        void *data ATTRIBUTE_UNUSED)
153 {
154   int i;
155   struct ipa_ref *ref;
156
157   for (i = 0; ipa_ref_list_refering_iterate (&node->ref_list, i, ref); i++)
158     if (ref->use == IPA_REF_ADDR)
159       return true;
160   return false;
161 }
162
163 /* Perform reachability analysis and reclaim all unreachable nodes.
164    If BEFORE_INLINING_P is true this function is called before inlining
165    decisions has been made.  If BEFORE_INLINING_P is false this function also
166    removes unneeded bodies of extern inline functions.  */
167
168 bool
169 cgraph_remove_unreachable_nodes (bool before_inlining_p, FILE *file)
170 {
171   struct cgraph_node *first = (struct cgraph_node *) (void *) 1;
172   struct varpool_node *first_varpool = (struct varpool_node *) (void *) 1;
173   struct cgraph_node *node, *next;
174   struct varpool_node *vnode, *vnext;
175   bool changed = false;
176
177 #ifdef ENABLE_CHECKING
178   verify_cgraph ();
179 #endif
180   if (file)
181     fprintf (file, "\nReclaiming functions:");
182 #ifdef ENABLE_CHECKING
183   for (node = cgraph_nodes; node; node = node->next)
184     gcc_assert (!node->aux);
185   for (vnode = varpool_nodes; vnode; vnode = vnode->next)
186     gcc_assert (!vnode->aux);
187 #endif
188   varpool_reset_queue ();
189   /* Mark functions whose bodies are obviously needed.
190      This is mostly when they can be referenced externally.  Inline clones
191      are special since their declarations are shared with master clone and thus
192      cgraph_can_remove_if_no_direct_calls_and_refs_p should not be called on them.  */
193   for (node = cgraph_nodes; node; node = node->next)
194     if (node->analyzed && !node->global.inlined_to
195         && (!cgraph_can_remove_if_no_direct_calls_and_refs_p (node)
196             /* Keep around virtual functions for possible devirtualization.  */
197             || (before_inlining_p
198                 && DECL_VIRTUAL_P (node->decl)
199                 && (DECL_COMDAT (node->decl) || DECL_EXTERNAL (node->decl)))
200             /* Also external functions with address taken are better to stay
201                for indirect inlining.  */
202             || (before_inlining_p
203                 && DECL_EXTERNAL (node->decl)
204                 && node->address_taken)))
205       {
206         gcc_assert (!node->global.inlined_to);
207         enqueue_cgraph_node (node, &first);
208         node->reachable = true;
209       }
210     else
211       {
212         gcc_assert (!node->aux);
213         node->reachable = false;
214       }
215
216   /* Mark variables that are obviously needed.  */
217   for (vnode = varpool_nodes; vnode; vnode = vnode->next)
218     {
219       vnode->next_needed = NULL;
220       vnode->prev_needed = NULL;
221       if ((vnode->analyzed || vnode->force_output)
222           && !varpool_can_remove_if_no_refs (vnode))
223         {
224           vnode->needed = false;
225           varpool_mark_needed_node (vnode);
226           enqueue_varpool_node (vnode, &first_varpool);
227         }
228       else
229         vnode->needed = false;
230     }
231
232   /* Perform reachability analysis.  As a special case do not consider
233      extern inline functions not inlined as live because we won't output
234      them at all. 
235
236      We maintain two worklist, one for cgraph nodes other for varpools and
237      are finished once both are empty.  */
238
239   while (first != (struct cgraph_node *) (void *) 1
240          || first_varpool != (struct varpool_node *) (void *) 1)
241     {
242       if (first != (struct cgraph_node *) (void *) 1)
243         {
244           struct cgraph_edge *e;
245           node = first;
246           first = (struct cgraph_node *) first->aux;
247           if (!node->reachable)
248             node->aux = (void *)2;
249
250           /* If we found this node reachable, first mark on the callees
251              reachable too, unless they are direct calls to extern inline functions
252              we decided to not inline.  */
253           if (node->reachable)
254             {
255               for (e = node->callees; e; e = e->next_callee)
256                 {
257                   if (!e->callee->reachable
258                       && node->analyzed
259                       && (!e->inline_failed
260                           || !DECL_EXTERNAL (e->callee->decl)
261                           || before_inlining_p))
262                     e->callee->reachable = true;
263                   enqueue_cgraph_node (e->callee, &first);
264                 }
265               process_references (&node->ref_list, &first, &first_varpool, before_inlining_p);
266             }
267
268           /* If any function in a comdat group is reachable, force
269              all other functions in the same comdat group to be
270              also reachable.  */
271           if (node->same_comdat_group
272               && node->reachable
273               && !node->global.inlined_to)
274             {
275               for (next = node->same_comdat_group;
276                    next != node;
277                    next = next->same_comdat_group)
278                 if (!next->reachable)
279                   {
280                     next->reachable = true;
281                     enqueue_cgraph_node (next, &first);
282                   }
283             }
284
285           /* We can freely remove inline clones even if they are cloned, however if
286              function is clone of real clone, we must keep it around in order to
287              make materialize_clones produce function body with the changes
288              applied.  */
289           while (node->clone_of && !node->clone_of->aux
290                  && !gimple_has_body_p (node->decl))
291             {
292               bool noninline = node->clone_of->decl != node->decl;
293               node = node->clone_of;
294               if (noninline && !node->reachable && !node->aux)
295                 {
296                   enqueue_cgraph_node (node, &first);
297                   break;
298                 }
299             }
300         }
301       if (first_varpool != (struct varpool_node *) (void *) 1)
302         {
303           vnode = first_varpool;
304           first_varpool = (struct varpool_node *)first_varpool->aux;
305           vnode->aux = NULL;
306           process_references (&vnode->ref_list, &first, &first_varpool, before_inlining_p);
307           /* If any function in a comdat group is reachable, force
308              all other functions in the same comdat group to be
309              also reachable.  */
310           if (vnode->same_comdat_group)
311             {
312               struct varpool_node *next;
313               for (next = vnode->same_comdat_group;
314                    next != vnode;
315                    next = next->same_comdat_group)
316                 if (!next->needed)
317                   {
318                     varpool_mark_needed_node (next);
319                     enqueue_varpool_node (next, &first_varpool);
320                   }
321             }
322         }
323     }
324
325   /* Remove unreachable nodes. 
326
327      Completely unreachable functions can be fully removed from the callgraph.
328      Extern inline functions that we decided to not inline need to become unanalyzed nodes of
329      callgraph (so we still have edges to them).  We remove function body then.
330
331      Also we need to care functions that are unreachable but we need to keep them around
332      for later clonning.  In this case we also turn them to unanalyzed nodes, but
333      keep the body around.  */
334   for (node = cgraph_nodes; node; node = next)
335     {
336       next = node->next;
337       if (node->aux && !node->reachable)
338         {
339           cgraph_node_remove_callees (node);
340           ipa_remove_all_references (&node->ref_list);
341           node->analyzed = false;
342         }
343       if (!node->aux)
344         {
345           struct cgraph_edge *e;
346           bool found = false;
347           int i;
348           struct ipa_ref *ref;
349
350           node->global.inlined_to = NULL;
351           if (file)
352             fprintf (file, " %s", cgraph_node_name (node));
353           /* See if there is reachable caller.  */
354           for (e = node->callers; e && !found; e = e->next_caller)
355             if (e->caller->reachable)
356               found = true;
357           for (i = 0; (ipa_ref_list_refering_iterate (&node->ref_list, i, ref)
358                        && !found); i++)
359             if (ref->refering_type == IPA_REF_CGRAPH
360                 && ipa_ref_refering_node (ref)->reachable)
361               found = true;
362             else if (ref->refering_type == IPA_REF_VARPOOL
363                      && ipa_ref_refering_varpool_node (ref)->needed)
364               found = true;
365
366           /* If so, we need to keep node in the callgraph.  */
367           if (found)
368             {
369               if (node->analyzed)
370                 {
371                   struct cgraph_node *clone;
372
373                   /* If there are still clones, we must keep body around.
374                      Otherwise we can just remove the body but keep the clone.  */
375                   for (clone = node->clones; clone;
376                        clone = clone->next_sibling_clone)
377                     if (clone->aux)
378                       break;
379                   if (!clone)
380                     {
381                       cgraph_release_function_body (node);
382                       if (node->prev_sibling_clone)
383                         node->prev_sibling_clone->next_sibling_clone = node->next_sibling_clone;
384                       else if (node->clone_of)
385                         node->clone_of->clones = node->next_sibling_clone;
386                       if (node->next_sibling_clone)
387                         node->next_sibling_clone->prev_sibling_clone = node->prev_sibling_clone;
388                       if (node->clone_of)
389                         node->former_clone_of = node->clone_of->decl;
390                       node->clone_of = NULL;
391                       node->next_sibling_clone = NULL;
392                       node->prev_sibling_clone = NULL;
393                     }
394                   else
395                     gcc_assert (!clone->in_other_partition);
396                   node->analyzed = false;
397                   changed = true;
398                   cgraph_node_remove_callees (node);
399                   ipa_remove_all_references (&node->ref_list);
400                 }
401             }
402           else
403             {
404               cgraph_remove_node (node);
405               changed = true;
406             }
407         }
408     }
409   for (node = cgraph_nodes; node; node = node->next)
410     {
411       /* Inline clones might be kept around so their materializing allows further
412          cloning.  If the function the clone is inlined into is removed, we need
413          to turn it into normal cone.  */
414       if (node->global.inlined_to
415           && !node->callers)
416         {
417           gcc_assert (node->clones);
418           node->global.inlined_to = NULL;
419           update_inlined_to_pointer (node, node);
420         }
421       node->aux = NULL;
422     }
423
424   if (file)
425     fprintf (file, "\n");
426
427   /* We must release unused extern inlines or sanity checking will fail.  Rest of transformations
428      are undesirable at -O0 since we do not want to remove anything.  */
429   if (!optimize)
430     return changed;
431
432   if (file)
433     fprintf (file, "Reclaiming variables:");
434   for (vnode = varpool_nodes; vnode; vnode = vnext)
435     {
436       vnext = vnode->next;
437       if (!vnode->needed)
438         {
439           if (file)
440             fprintf (file, " %s", varpool_node_name (vnode));
441           varpool_remove_node (vnode);
442           changed = true;
443         }
444     }
445
446   /* Now update address_taken flags and try to promote functions to be local.  */
447
448   if (file)
449     fprintf (file, "\nClearing address taken flags:");
450   for (node = cgraph_nodes; node; node = node->next)
451     if (node->address_taken
452         && !node->reachable_from_other_partition)
453       {
454         if (!cgraph_for_node_and_aliases (node, has_addr_references_p, NULL, true))
455           {
456             if (file)
457               fprintf (file, " %s", cgraph_node_name (node));
458             node->address_taken = false;
459             changed = true;
460             if (cgraph_local_node_p (node))
461               {
462                 node->local.local = true;
463                 if (file)
464                   fprintf (file, " (local)");
465               }
466           }
467       }
468   if (file)
469     fprintf (file, "\n");
470
471 #ifdef ENABLE_CHECKING
472   verify_cgraph ();
473 #endif
474
475   /* Reclaim alias pairs for functions that have disappeared from the
476      call graph.  */
477   remove_unreachable_alias_pairs ();
478
479   return changed;
480 }
481
482 /* Discover variables that have no longer address taken or that are read only
483    and update their flags.
484
485    FIXME: This can not be done in between gimplify and omp_expand since
486    readonly flag plays role on what is shared and what is not.  Currently we do
487    this transformation as part of whole program visibility and re-do at
488    ipa-reference pass (to take into account clonning), but it would
489    make sense to do it before early optimizations.  */
490
491 void
492 ipa_discover_readonly_nonaddressable_vars (void)
493 {
494   struct varpool_node *vnode;
495   if (dump_file)
496     fprintf (dump_file, "Clearing variable flags:");
497   for (vnode = varpool_nodes; vnode; vnode = vnode->next)
498     if (vnode->finalized && varpool_all_refs_explicit_p (vnode)
499         && (TREE_ADDRESSABLE (vnode->decl) || !TREE_READONLY (vnode->decl)))
500       {
501         bool written = false;
502         bool address_taken = false;
503         int i;
504         struct ipa_ref *ref;
505         for (i = 0; ipa_ref_list_refering_iterate (&vnode->ref_list, i, ref)
506                     && (!written || !address_taken); i++)
507           switch (ref->use)
508             {
509             case IPA_REF_ADDR:
510               address_taken = true;
511               break;
512             case IPA_REF_LOAD:
513               break;
514             case IPA_REF_STORE:
515               written = true;
516               break;
517             }
518         if (TREE_ADDRESSABLE (vnode->decl) && !address_taken)
519           {
520             if (dump_file)
521               fprintf (dump_file, " %s (addressable)", varpool_node_name (vnode));
522             TREE_ADDRESSABLE (vnode->decl) = 0;
523           }
524         if (!TREE_READONLY (vnode->decl) && !address_taken && !written
525             /* Making variable in explicit section readonly can cause section
526                type conflict. 
527                See e.g. gcc.c-torture/compile/pr23237.c */
528             && DECL_SECTION_NAME (vnode->decl) == NULL)
529           {
530             if (dump_file)
531               fprintf (dump_file, " %s (read-only)", varpool_node_name (vnode));
532             TREE_READONLY (vnode->decl) = 1;
533           }
534       }
535   if (dump_file)
536     fprintf (dump_file, "\n");
537 }
538
539 /* Return true when there is a reference to node and it is not vtable.  */
540 static bool
541 cgraph_address_taken_from_non_vtable_p (struct cgraph_node *node)
542 {
543   int i;
544   struct ipa_ref *ref;
545   for (i = 0; ipa_ref_list_reference_iterate (&node->ref_list, i, ref); i++)
546     {
547       struct varpool_node *node;
548       if (ref->refered_type == IPA_REF_CGRAPH)
549         return true;
550       node = ipa_ref_varpool_node (ref);
551       if (!DECL_VIRTUAL_P (node->decl))
552         return true;
553     }
554   return false;
555 }
556
557 /* COMDAT functions must be shared only if they have address taken,
558    otherwise we can produce our own private implementation with
559    -fwhole-program.  
560    Return true when turning COMDAT functoin static can not lead to wrong
561    code when the resulting object links with a library defining same COMDAT.
562
563    Virtual functions do have their addresses taken from the vtables,
564    but in C++ there is no way to compare their addresses for equality.  */
565
566 bool
567 cgraph_comdat_can_be_unshared_p (struct cgraph_node *node)
568 {
569   if ((cgraph_address_taken_from_non_vtable_p (node)
570        && !DECL_VIRTUAL_P (node->decl))
571       || !node->analyzed)
572     return false;
573   if (node->same_comdat_group)
574     {
575       struct cgraph_node *next;
576
577       /* If more than one function is in the same COMDAT group, it must
578          be shared even if just one function in the comdat group has
579          address taken.  */
580       for (next = node->same_comdat_group;
581            next != node; next = next->same_comdat_group)
582         if (cgraph_address_taken_from_non_vtable_p (next)
583             && !DECL_VIRTUAL_P (next->decl))
584           return false;
585     }
586   return true;
587 }
588
589 /* Return true when function NODE should be considered externally visible.  */
590
591 static bool
592 cgraph_externally_visible_p (struct cgraph_node *node,
593                              bool whole_program, bool aliased)
594 {
595   if (!node->local.finalized)
596     return false;
597   if (!DECL_COMDAT (node->decl)
598       && (!TREE_PUBLIC (node->decl) || DECL_EXTERNAL (node->decl)))
599     return false;
600
601   /* Do not even try to be smart about aliased nodes.  Until we properly
602      represent everything by same body alias, these are just evil.  */
603   if (aliased)
604     return true;
605
606   /* Do not try to localize built-in functions yet.  One of problems is that we
607      end up mangling their asm for WHOPR that makes it impossible to call them
608      using the implicit built-in declarations anymore.  Similarly this enables
609      us to remove them as unreachable before actual calls may appear during
610      expansion or folding.  */
611   if (DECL_BUILT_IN (node->decl))
612     return true;
613
614   /* FIXME: We get wrong symbols with asm aliases in callgraph and LTO.
615      This is because very little of code knows that assembler name needs to
616      mangled.  Avoid touching declarations with user asm name set to mask
617      some of the problems.  */
618   if (DECL_ASSEMBLER_NAME_SET_P (node->decl)
619       && IDENTIFIER_POINTER (DECL_ASSEMBLER_NAME (node->decl))[0]=='*')
620     return true;
621
622   /* If linker counts on us, we must preserve the function.  */
623   if (cgraph_used_from_object_file_p (node))
624     return true;
625   if (DECL_PRESERVE_P (node->decl))
626     return true;
627   if (lookup_attribute ("externally_visible", DECL_ATTRIBUTES (node->decl)))
628     return true;
629   if (TARGET_DLLIMPORT_DECL_ATTRIBUTES
630       && lookup_attribute ("dllexport", DECL_ATTRIBUTES (node->decl)))
631     return true;
632   if (node->resolution == LDPR_PREVAILING_DEF_IRONLY)
633     return false;
634   /* When doing LTO or whole program, we can bring COMDAT functoins static.
635      This improves code quality and we know we will duplicate them at most twice
636      (in the case that we are not using plugin and link with object file
637       implementing same COMDAT)  */
638   if ((in_lto_p || whole_program)
639       && DECL_COMDAT (node->decl)
640       && cgraph_comdat_can_be_unshared_p (node))
641     return false;
642
643   /* When doing link time optimizations, hidden symbols become local.  */
644   if (in_lto_p
645       && (DECL_VISIBILITY (node->decl) == VISIBILITY_HIDDEN
646           || DECL_VISIBILITY (node->decl) == VISIBILITY_INTERNAL)
647       /* Be sure that node is defined in IR file, not in other object
648          file.  In that case we don't set used_from_other_object_file.  */
649       && node->analyzed)
650     ;
651   else if (!whole_program)
652     return true;
653
654   if (MAIN_NAME_P (DECL_NAME (node->decl)))
655     return true;
656
657   return false;
658 }
659
660 /* Return true when variable VNODE should be considered externally visible.  */
661
662 static bool
663 varpool_externally_visible_p (struct varpool_node *vnode, bool aliased)
664 {
665   struct varpool_node *alias;
666   if (!DECL_COMDAT (vnode->decl) && !TREE_PUBLIC (vnode->decl))
667     return false;
668
669   /* Do not even try to be smart about aliased nodes.  Until we properly
670      represent everything by same body alias, these are just evil.  */
671   if (aliased)
672     return true;
673
674   /* If linker counts on us, we must preserve the function.  */
675   if (varpool_used_from_object_file_p (vnode))
676     return true;
677
678   /* FIXME: We get wrong symbols with asm aliases in callgraph and LTO.
679      This is because very little of code knows that assembler name needs to
680      mangled.  Avoid touching declarations with user asm name set to mask
681      some of the problems.  */
682   if (DECL_ASSEMBLER_NAME_SET_P (vnode->decl)
683       && IDENTIFIER_POINTER (DECL_ASSEMBLER_NAME (vnode->decl))[0]=='*')
684     return true;
685
686   if (DECL_PRESERVE_P (vnode->decl))
687     return true;
688   if (lookup_attribute ("externally_visible",
689                         DECL_ATTRIBUTES (vnode->decl)))
690     return true;
691   if (TARGET_DLLIMPORT_DECL_ATTRIBUTES
692       && lookup_attribute ("dllexport",
693                            DECL_ATTRIBUTES (vnode->decl)))
694     return true;
695
696   /* See if we have linker information about symbol not being used or
697      if we need to make guess based on the declaration.
698
699      Even if the linker clams the symbol is unused, never bring internal
700      symbols that are declared by user as used or externally visible.
701      This is needed for i.e. references from asm statements.   */
702   if (varpool_used_from_object_file_p (vnode))
703     return true;
704   for (alias = vnode->extra_name; alias; alias = alias->next)
705     if (alias->resolution != LDPR_PREVAILING_DEF_IRONLY)
706       break;
707   if (!alias && vnode->resolution == LDPR_PREVAILING_DEF_IRONLY)
708     return false;
709
710   /* As a special case, the COMDAT virutal tables can be unshared.
711      In LTO mode turn vtables into static variables.  The variable is readonly,
712      so this does not enable more optimization, but referring static var
713      is faster for dynamic linking.  Also this match logic hidding vtables
714      from LTO symbol tables.  */
715   if ((in_lto_p || flag_whole_program)
716       && !vnode->force_output
717       && DECL_COMDAT (vnode->decl) && DECL_VIRTUAL_P (vnode->decl))
718     return false;
719
720   /* When doing link time optimizations, hidden symbols become local.  */
721   if (in_lto_p
722       && (DECL_VISIBILITY (vnode->decl) == VISIBILITY_HIDDEN
723           || DECL_VISIBILITY (vnode->decl) == VISIBILITY_INTERNAL)
724       /* Be sure that node is defined in IR file, not in other object
725          file.  In that case we don't set used_from_other_object_file.  */
726       && vnode->finalized)
727     ;
728   else if (!flag_whole_program)
729     return true;
730
731   /* Do not attempt to privatize COMDATS by default.
732      This would break linking with C++ libraries sharing
733      inline definitions.
734
735      FIXME: We can do so for readonly vars with no address taken and
736      possibly also for vtables since no direct pointer comparsion is done.
737      It might be interesting to do so to reduce linking overhead.  */
738   if (DECL_COMDAT (vnode->decl) || DECL_WEAK (vnode->decl))
739     return true;
740   return false;
741 }
742
743 /* Dissolve the same_comdat_group list in which NODE resides.  */
744
745 static void
746 dissolve_same_comdat_group_list (struct cgraph_node *node)
747 {
748   struct cgraph_node *n = node, *next;
749   do
750     {
751       next = n->same_comdat_group;
752       n->same_comdat_group = NULL;
753       n = next;
754     }
755   while (n != node);
756 }
757
758 /* Mark visibility of all functions.
759
760    A local function is one whose calls can occur only in the current
761    compilation unit and all its calls are explicit, so we can change
762    its calling convention.  We simply mark all static functions whose
763    address is not taken as local.
764
765    We also change the TREE_PUBLIC flag of all declarations that are public
766    in language point of view but we want to overwrite this default
767    via visibilities for the backend point of view.  */
768
769 static unsigned int
770 function_and_variable_visibility (bool whole_program)
771 {
772   struct cgraph_node *node;
773   struct varpool_node *vnode;
774   struct pointer_set_t *aliased_nodes = pointer_set_create ();
775   struct pointer_set_t *aliased_vnodes = pointer_set_create ();
776   unsigned i;
777   alias_pair *p;
778
779   /* Discover aliased nodes.  */
780   FOR_EACH_VEC_ELT (alias_pair, alias_pairs, i, p)
781     {
782       if (dump_file)
783        fprintf (dump_file, "Alias %s->%s",
784                 IDENTIFIER_POINTER (DECL_ASSEMBLER_NAME (p->decl)),
785                 IDENTIFIER_POINTER (p->target));
786                 
787       if ((node = cgraph_node_for_asm (p->target)) != NULL
788           && !DECL_EXTERNAL (node->decl))
789         {
790           if (!node->analyzed)
791             continue;
792           /* Weakrefs alias symbols from other compilation unit.  In the case
793              the destination of weakref became available because of LTO, we must
794              mark it as needed.  */
795           if (in_lto_p
796               && lookup_attribute ("weakref", DECL_ATTRIBUTES (p->decl))
797               && !node->needed)
798             cgraph_mark_needed_node (node);
799           gcc_assert (node->needed);
800           pointer_set_insert (aliased_nodes, node);
801           if (dump_file)
802             fprintf (dump_file, "  node %s/%i",
803                      cgraph_node_name (node), node->uid);
804         }
805       else if ((vnode = varpool_node_for_asm (p->target)) != NULL
806                && !DECL_EXTERNAL (vnode->decl))
807         {
808           /* Weakrefs alias symbols from other compilation unit.  In the case
809              the destination of weakref became available because of LTO, we must
810              mark it as needed.  */
811           if (in_lto_p
812               && lookup_attribute ("weakref", DECL_ATTRIBUTES (p->decl))
813               && !vnode->needed)
814             varpool_mark_needed_node (vnode);
815           gcc_assert (vnode->needed);
816           pointer_set_insert (aliased_vnodes, vnode);
817           if (dump_file)
818             fprintf (dump_file, "  varpool node %s",
819                      varpool_node_name (vnode));
820         }
821       if (dump_file)
822        fprintf (dump_file, "\n");
823     }
824
825   for (node = cgraph_nodes; node; node = node->next)
826     {
827       int flags = flags_from_decl_or_type (node->decl);
828
829       /* Optimize away PURE and CONST constructors and destructors.  */
830       if (optimize
831           && (flags & (ECF_CONST | ECF_PURE))
832           && !(flags & ECF_LOOPING_CONST_OR_PURE))
833         {
834           DECL_STATIC_CONSTRUCTOR (node->decl) = 0;
835           DECL_STATIC_DESTRUCTOR (node->decl) = 0;
836         }
837
838       /* Frontends and alias code marks nodes as needed before parsing is finished.
839          We may end up marking as node external nodes where this flag is meaningless
840          strip it.  */
841       if (node->needed
842           && (DECL_EXTERNAL (node->decl) || !node->analyzed))
843         node->needed = 0;
844
845       /* C++ FE on lack of COMDAT support create local COMDAT functions
846          (that ought to be shared but can not due to object format
847          limitations).  It is neccesary to keep the flag to make rest of C++ FE
848          happy.  Clear the flag here to avoid confusion in middle-end.  */
849       if (DECL_COMDAT (node->decl) && !TREE_PUBLIC (node->decl))
850         DECL_COMDAT (node->decl) = 0;
851       /* For external decls stop tracking same_comdat_group, it doesn't matter
852          what comdat group they are in when they won't be emitted in this TU,
853          and simplifies later passes.  */
854       if (node->same_comdat_group && DECL_EXTERNAL (node->decl))
855         {
856 #ifdef ENABLE_CHECKING
857           struct cgraph_node *n;
858
859           for (n = node->same_comdat_group;
860                n != node;
861                n = n->same_comdat_group)
862               /* If at least one of same comdat group functions is external,
863                  all of them have to be, otherwise it is a front-end bug.  */
864               gcc_assert (DECL_EXTERNAL (n->decl));
865 #endif
866           dissolve_same_comdat_group_list (node);
867         }
868       gcc_assert ((!DECL_WEAK (node->decl) && !DECL_COMDAT (node->decl))
869                   || TREE_PUBLIC (node->decl) || DECL_EXTERNAL (node->decl));
870       if (cgraph_externally_visible_p (node, whole_program,
871                                        pointer_set_contains (aliased_nodes,
872                                                              node)))
873         {
874           gcc_assert (!node->global.inlined_to);
875           node->local.externally_visible = true;
876         }
877       else
878         node->local.externally_visible = false;
879       if (!node->local.externally_visible && node->analyzed
880           && !DECL_EXTERNAL (node->decl))
881         {
882           gcc_assert (whole_program || in_lto_p || !TREE_PUBLIC (node->decl));
883           cgraph_make_decl_local (node->decl);
884           node->resolution = LDPR_PREVAILING_DEF_IRONLY;
885           if (node->same_comdat_group)
886             /* cgraph_externally_visible_p has already checked all other nodes
887                in the group and they will all be made local.  We need to
888                dissolve the group at once so that the predicate does not
889                segfault though. */
890             dissolve_same_comdat_group_list (node);
891         }
892
893       if (node->thunk.thunk_p
894           && TREE_PUBLIC (node->decl))
895         {
896           struct cgraph_node *decl_node = node;
897
898           decl_node = cgraph_function_node (decl_node->callees->callee, NULL);
899
900           /* Thunks have the same visibility as function they are attached to.
901              For some reason C++ frontend don't seem to care. I.e. in 
902              g++.dg/torture/pr41257-2.C the thunk is not comdat while function
903              it is attached to is.
904
905              We also need to arrange the thunk into the same comdat group as
906              the function it reffers to.  */
907           if (DECL_ONE_ONLY (decl_node->decl))
908             {
909               DECL_COMDAT (node->decl) = DECL_COMDAT (decl_node->decl);
910               DECL_COMDAT_GROUP (node->decl) = DECL_COMDAT_GROUP (decl_node->decl);
911               if (DECL_ONE_ONLY (decl_node->decl) && !node->same_comdat_group)
912                 {
913                   node->same_comdat_group = decl_node;
914                   if (!decl_node->same_comdat_group)
915                     decl_node->same_comdat_group = node;
916                   else
917                     {
918                       struct cgraph_node *n;
919                       for (n = decl_node->same_comdat_group;
920                            n->same_comdat_group != decl_node;
921                            n = n->same_comdat_group)
922                         ;
923                       n->same_comdat_group = node;
924                     }
925                 }
926             }
927           if (DECL_EXTERNAL (decl_node->decl))
928             DECL_EXTERNAL (node->decl) = 1;
929         }
930     }
931   for (node = cgraph_nodes; node; node = node->next)
932     node->local.local = cgraph_local_node_p (node);
933   for (vnode = varpool_nodes; vnode; vnode = vnode->next)
934     {
935       /* weak flag makes no sense on local variables.  */
936       gcc_assert (!DECL_WEAK (vnode->decl)
937                   || TREE_PUBLIC (vnode->decl) || DECL_EXTERNAL (vnode->decl));
938       /* In several cases declarations can not be common:
939
940          - when declaration has initializer
941          - when it is in weak
942          - when it has specific section
943          - when it resides in non-generic address space.
944          - if declaration is local, it will get into .local common section
945            so common flag is not needed.  Frontends still produce these in
946            certain cases, such as for:
947
948              static int a __attribute__ ((common))
949
950          Canonicalize things here and clear the redundant flag.  */
951       if (DECL_COMMON (vnode->decl)
952           && (!(TREE_PUBLIC (vnode->decl) || DECL_EXTERNAL (vnode->decl))
953               || (DECL_INITIAL (vnode->decl)
954                   && DECL_INITIAL (vnode->decl) != error_mark_node)
955               || DECL_WEAK (vnode->decl)
956               || DECL_SECTION_NAME (vnode->decl) != NULL
957               || ! (ADDR_SPACE_GENERIC_P
958                     (TYPE_ADDR_SPACE (TREE_TYPE (vnode->decl))))))
959         DECL_COMMON (vnode->decl) = 0;
960     }
961   for (vnode = varpool_nodes_queue; vnode; vnode = vnode->next_needed)
962     {
963       if (!vnode->finalized)
964         continue;
965       if (vnode->needed
966           && varpool_externally_visible_p
967               (vnode, 
968                pointer_set_contains (aliased_vnodes, vnode)))
969         vnode->externally_visible = true;
970       else
971         vnode->externally_visible = false;
972       if (!vnode->externally_visible)
973         {
974           gcc_assert (in_lto_p || whole_program || !TREE_PUBLIC (vnode->decl));
975           cgraph_make_decl_local (vnode->decl);
976           vnode->resolution = LDPR_PREVAILING_DEF_IRONLY;
977         }
978      gcc_assert (TREE_STATIC (vnode->decl));
979     }
980   pointer_set_destroy (aliased_nodes);
981   pointer_set_destroy (aliased_vnodes);
982
983   if (dump_file)
984     {
985       fprintf (dump_file, "\nMarking local functions:");
986       for (node = cgraph_nodes; node; node = node->next)
987         if (node->local.local)
988           fprintf (dump_file, " %s", cgraph_node_name (node));
989       fprintf (dump_file, "\n\n");
990       fprintf (dump_file, "\nMarking externally visible functions:");
991       for (node = cgraph_nodes; node; node = node->next)
992         if (node->local.externally_visible)
993           fprintf (dump_file, " %s", cgraph_node_name (node));
994       fprintf (dump_file, "\n\n");
995       fprintf (dump_file, "\nMarking externally visible variables:");
996       for (vnode = varpool_nodes_queue; vnode; vnode = vnode->next_needed)
997         if (vnode->externally_visible)
998           fprintf (dump_file, " %s", varpool_node_name (vnode));
999       fprintf (dump_file, "\n\n");
1000     }
1001   cgraph_function_flags_ready = true;
1002   return 0;
1003 }
1004
1005 /* Local function pass handling visibilities.  This happens before LTO streaming
1006    so in particular -fwhole-program should be ignored at this level.  */
1007
1008 static unsigned int
1009 local_function_and_variable_visibility (void)
1010 {
1011   return function_and_variable_visibility (flag_whole_program && !flag_lto);
1012 }
1013
1014 struct simple_ipa_opt_pass pass_ipa_function_and_variable_visibility =
1015 {
1016  {
1017   SIMPLE_IPA_PASS,
1018   "visibility",                         /* name */
1019   NULL,                                 /* gate */
1020   local_function_and_variable_visibility,/* execute */
1021   NULL,                                 /* sub */
1022   NULL,                                 /* next */
1023   0,                                    /* static_pass_number */
1024   TV_CGRAPHOPT,                         /* tv_id */
1025   0,                                    /* properties_required */
1026   0,                                    /* properties_provided */
1027   0,                                    /* properties_destroyed */
1028   0,                                    /* todo_flags_start */
1029   TODO_remove_functions | TODO_dump_cgraph
1030   | TODO_ggc_collect                    /* todo_flags_finish */
1031  }
1032 };
1033
1034 /* Do not re-run on ltrans stage.  */
1035
1036 static bool
1037 gate_whole_program_function_and_variable_visibility (void)
1038 {
1039   return !flag_ltrans;
1040 }
1041
1042 /* Bring functionss local at LTO time whith -fwhole-program.  */
1043
1044 static unsigned int
1045 whole_program_function_and_variable_visibility (void)
1046 {
1047   struct cgraph_node *node;
1048   struct varpool_node *vnode;
1049
1050   function_and_variable_visibility (flag_whole_program);
1051
1052   for (node = cgraph_nodes; node; node = node->next)
1053     if ((node->local.externally_visible && !DECL_COMDAT (node->decl))
1054         && node->local.finalized)
1055       cgraph_mark_needed_node (node);
1056   for (vnode = varpool_nodes_queue; vnode; vnode = vnode->next_needed)
1057     if (vnode->externally_visible && !DECL_COMDAT (vnode->decl))
1058       varpool_mark_needed_node (vnode);
1059   if (dump_file)
1060     {
1061       fprintf (dump_file, "\nNeeded variables:");
1062       for (vnode = varpool_nodes_queue; vnode; vnode = vnode->next_needed)
1063         if (vnode->needed)
1064           fprintf (dump_file, " %s", varpool_node_name (vnode));
1065       fprintf (dump_file, "\n\n");
1066     }
1067   if (optimize)
1068     ipa_discover_readonly_nonaddressable_vars ();
1069   return 0;
1070 }
1071
1072 struct ipa_opt_pass_d pass_ipa_whole_program_visibility =
1073 {
1074  {
1075   IPA_PASS,
1076   "whole-program",                      /* name */
1077   gate_whole_program_function_and_variable_visibility,/* gate */
1078   whole_program_function_and_variable_visibility,/* execute */
1079   NULL,                                 /* sub */
1080   NULL,                                 /* next */
1081   0,                                    /* static_pass_number */
1082   TV_CGRAPHOPT,                         /* tv_id */
1083   0,                                    /* properties_required */
1084   0,                                    /* properties_provided */
1085   0,                                    /* properties_destroyed */
1086   0,                                    /* todo_flags_start */
1087   TODO_remove_functions | TODO_dump_cgraph
1088   | TODO_ggc_collect                    /* todo_flags_finish */
1089  },
1090  NULL,                                  /* generate_summary */
1091  NULL,                                  /* write_summary */
1092  NULL,                                  /* read_summary */
1093  NULL,                                  /* write_optimization_summary */
1094  NULL,                                  /* read_optimization_summary */
1095  NULL,                                  /* stmt_fixup */
1096  0,                                     /* TODOs */
1097  NULL,                                  /* function_transform */
1098  NULL,                                  /* variable_transform */
1099 };
1100
1101
1102 /* Simple ipa profile pass propagating frequencies across the callgraph.  */
1103
1104 static unsigned int
1105 ipa_profile (void)
1106 {
1107   struct cgraph_node **order = XCNEWVEC (struct cgraph_node *, cgraph_n_nodes);
1108   struct cgraph_edge *e;
1109   int order_pos;
1110   bool something_changed = false;
1111   int i;
1112
1113   order_pos = ipa_reverse_postorder (order);
1114   for (i = order_pos - 1; i >= 0; i--)
1115     {
1116       if (order[i]->local.local && cgraph_propagate_frequency (order[i]))
1117         {
1118           for (e = order[i]->callees; e; e = e->next_callee)
1119             if (e->callee->local.local && !e->callee->aux)
1120               {
1121                 something_changed = true;
1122                 e->callee->aux = (void *)1;
1123               }
1124         }
1125       order[i]->aux = NULL;
1126     }
1127
1128   while (something_changed)
1129     {
1130       something_changed = false;
1131       for (i = order_pos - 1; i >= 0; i--)
1132         {
1133           if (order[i]->aux && cgraph_propagate_frequency (order[i]))
1134             {
1135               for (e = order[i]->callees; e; e = e->next_callee)
1136                 if (e->callee->local.local && !e->callee->aux)
1137                   {
1138                     something_changed = true;
1139                     e->callee->aux = (void *)1;
1140                   }
1141             }
1142           order[i]->aux = NULL;
1143         }
1144     }
1145   free (order);
1146   return 0;
1147 }
1148
1149 static bool
1150 gate_ipa_profile (void)
1151 {
1152   return flag_ipa_profile;
1153 }
1154
1155 struct ipa_opt_pass_d pass_ipa_profile =
1156 {
1157  {
1158   IPA_PASS,
1159   "profile_estimate",                   /* name */
1160   gate_ipa_profile,                     /* gate */
1161   ipa_profile,                          /* execute */
1162   NULL,                                 /* sub */
1163   NULL,                                 /* next */
1164   0,                                    /* static_pass_number */
1165   TV_IPA_PROFILE,                       /* tv_id */
1166   0,                                    /* properties_required */
1167   0,                                    /* properties_provided */
1168   0,                                    /* properties_destroyed */
1169   0,                                    /* todo_flags_start */
1170   0                                     /* todo_flags_finish */
1171  },
1172  NULL,                                  /* generate_summary */
1173  NULL,                                  /* write_summary */
1174  NULL,                                  /* read_summary */
1175  NULL,                                  /* write_optimization_summary */
1176  NULL,                                  /* read_optimization_summary */
1177  NULL,                                  /* stmt_fixup */
1178  0,                                     /* TODOs */
1179  NULL,                                  /* function_transform */
1180  NULL                                   /* variable_transform */
1181 };
1182
1183 /* Generate and emit a static constructor or destructor.  WHICH must
1184    be one of 'I' (for a constructor) or 'D' (for a destructor).  BODY
1185    is a STATEMENT_LIST containing GENERIC statements.  PRIORITY is the
1186    initialization priority for this constructor or destructor. 
1187
1188    FINAL specify whether the externally visible name for collect2 should
1189    be produced. */
1190
1191 static void
1192 cgraph_build_static_cdtor_1 (char which, tree body, int priority, bool final)
1193 {
1194   static int counter = 0;
1195   char which_buf[16];
1196   tree decl, name, resdecl;
1197
1198   /* The priority is encoded in the constructor or destructor name.
1199      collect2 will sort the names and arrange that they are called at
1200      program startup.  */
1201   if (final)
1202     sprintf (which_buf, "%c_%.5d_%d", which, priority, counter++);
1203   else
1204   /* Proudce sane name but one not recognizable by collect2, just for the
1205      case we fail to inline the function.  */
1206     sprintf (which_buf, "sub_%c_%.5d_%d", which, priority, counter++);
1207   name = get_file_function_name (which_buf);
1208
1209   decl = build_decl (input_location, FUNCTION_DECL, name,
1210                      build_function_type_list (void_type_node, NULL_TREE));
1211   current_function_decl = decl;
1212
1213   resdecl = build_decl (input_location,
1214                         RESULT_DECL, NULL_TREE, void_type_node);
1215   DECL_ARTIFICIAL (resdecl) = 1;
1216   DECL_RESULT (decl) = resdecl;
1217   DECL_CONTEXT (resdecl) = decl;
1218
1219   allocate_struct_function (decl, false);
1220
1221   TREE_STATIC (decl) = 1;
1222   TREE_USED (decl) = 1;
1223   DECL_ARTIFICIAL (decl) = 1;
1224   DECL_NO_INSTRUMENT_FUNCTION_ENTRY_EXIT (decl) = 1;
1225   DECL_SAVED_TREE (decl) = body;
1226   if (!targetm.have_ctors_dtors && final)
1227     {
1228       TREE_PUBLIC (decl) = 1;
1229       DECL_PRESERVE_P (decl) = 1;
1230     }
1231   DECL_UNINLINABLE (decl) = 1;
1232
1233   DECL_INITIAL (decl) = make_node (BLOCK);
1234   TREE_USED (DECL_INITIAL (decl)) = 1;
1235
1236   DECL_SOURCE_LOCATION (decl) = input_location;
1237   cfun->function_end_locus = input_location;
1238
1239   switch (which)
1240     {
1241     case 'I':
1242       DECL_STATIC_CONSTRUCTOR (decl) = 1;
1243       decl_init_priority_insert (decl, priority);
1244       break;
1245     case 'D':
1246       DECL_STATIC_DESTRUCTOR (decl) = 1;
1247       decl_fini_priority_insert (decl, priority);
1248       break;
1249     default:
1250       gcc_unreachable ();
1251     }
1252
1253   gimplify_function_tree (decl);
1254
1255   cgraph_add_new_function (decl, false);
1256
1257   set_cfun (NULL);
1258   current_function_decl = NULL;
1259 }
1260
1261 /* Generate and emit a static constructor or destructor.  WHICH must
1262    be one of 'I' (for a constructor) or 'D' (for a destructor).  BODY
1263    is a STATEMENT_LIST containing GENERIC statements.  PRIORITY is the
1264    initialization priority for this constructor or destructor.  */
1265
1266 void
1267 cgraph_build_static_cdtor (char which, tree body, int priority)
1268 {
1269   cgraph_build_static_cdtor_1 (which, body, priority, false);
1270 }
1271
1272 /* A vector of FUNCTION_DECLs declared as static constructors.  */
1273 static VEC(tree, heap) *static_ctors;
1274 /* A vector of FUNCTION_DECLs declared as static destructors.  */
1275 static VEC(tree, heap) *static_dtors;
1276
1277 /* When target does not have ctors and dtors, we call all constructor
1278    and destructor by special initialization/destruction function
1279    recognized by collect2.
1280
1281    When we are going to build this function, collect all constructors and
1282    destructors and turn them into normal functions.  */
1283
1284 static void
1285 record_cdtor_fn (struct cgraph_node *node)
1286 {
1287   if (DECL_STATIC_CONSTRUCTOR (node->decl))
1288     VEC_safe_push (tree, heap, static_ctors, node->decl);
1289   if (DECL_STATIC_DESTRUCTOR (node->decl))
1290     VEC_safe_push (tree, heap, static_dtors, node->decl);
1291   node = cgraph_get_node (node->decl);
1292   DECL_DISREGARD_INLINE_LIMITS (node->decl) = 1;
1293 }
1294
1295 /* Define global constructors/destructor functions for the CDTORS, of
1296    which they are LEN.  The CDTORS are sorted by initialization
1297    priority.  If CTOR_P is true, these are constructors; otherwise,
1298    they are destructors.  */
1299
1300 static void
1301 build_cdtor (bool ctor_p, VEC (tree, heap) *cdtors)
1302 {
1303   size_t i,j;
1304   size_t len = VEC_length (tree, cdtors);
1305
1306   i = 0;
1307   while (i < len)
1308     {
1309       tree body;
1310       tree fn;
1311       priority_type priority;
1312
1313       priority = 0;
1314       body = NULL_TREE;
1315       j = i;
1316       do
1317         {
1318           priority_type p;
1319           fn = VEC_index (tree, cdtors, j);
1320           p = ctor_p ? DECL_INIT_PRIORITY (fn) : DECL_FINI_PRIORITY (fn);
1321           if (j == i)
1322             priority = p;
1323           else if (p != priority)
1324             break;
1325           j++;
1326         }
1327       while (j < len);
1328
1329       /* When there is only one cdtor and target supports them, do nothing.  */
1330       if (j == i + 1
1331           && targetm.have_ctors_dtors)
1332         {
1333           i++;
1334           continue;
1335         }
1336       /* Find the next batch of constructors/destructors with the same
1337          initialization priority.  */
1338       for (;i < j; i++)
1339         {
1340           tree call;
1341           fn = VEC_index (tree, cdtors, i);
1342           call = build_call_expr (fn, 0);
1343           if (ctor_p)
1344             DECL_STATIC_CONSTRUCTOR (fn) = 0;
1345           else
1346             DECL_STATIC_DESTRUCTOR (fn) = 0;
1347           /* We do not want to optimize away pure/const calls here.
1348              When optimizing, these should be already removed, when not
1349              optimizing, we want user to be able to breakpoint in them.  */
1350           TREE_SIDE_EFFECTS (call) = 1;
1351           append_to_statement_list (call, &body);
1352         }
1353       gcc_assert (body != NULL_TREE);
1354       /* Generate a function to call all the function of like
1355          priority.  */
1356       cgraph_build_static_cdtor_1 (ctor_p ? 'I' : 'D', body, priority, true);
1357     }
1358 }
1359
1360 /* Comparison function for qsort.  P1 and P2 are actually of type
1361    "tree *" and point to static constructors.  DECL_INIT_PRIORITY is
1362    used to determine the sort order.  */
1363
1364 static int
1365 compare_ctor (const void *p1, const void *p2)
1366 {
1367   tree f1;
1368   tree f2;
1369   int priority1;
1370   int priority2;
1371
1372   f1 = *(const tree *)p1;
1373   f2 = *(const tree *)p2;
1374   priority1 = DECL_INIT_PRIORITY (f1);
1375   priority2 = DECL_INIT_PRIORITY (f2);
1376
1377   if (priority1 < priority2)
1378     return -1;
1379   else if (priority1 > priority2)
1380     return 1;
1381   else
1382     /* Ensure a stable sort.  Constructors are executed in backwarding
1383        order to make LTO initialize braries first.  */
1384     return DECL_UID (f2) - DECL_UID (f1);
1385 }
1386
1387 /* Comparison function for qsort.  P1 and P2 are actually of type
1388    "tree *" and point to static destructors.  DECL_FINI_PRIORITY is
1389    used to determine the sort order.  */
1390
1391 static int
1392 compare_dtor (const void *p1, const void *p2)
1393 {
1394   tree f1;
1395   tree f2;
1396   int priority1;
1397   int priority2;
1398
1399   f1 = *(const tree *)p1;
1400   f2 = *(const tree *)p2;
1401   priority1 = DECL_FINI_PRIORITY (f1);
1402   priority2 = DECL_FINI_PRIORITY (f2);
1403
1404   if (priority1 < priority2)
1405     return -1;
1406   else if (priority1 > priority2)
1407     return 1;
1408   else
1409     /* Ensure a stable sort.  */
1410     return DECL_UID (f1) - DECL_UID (f2);
1411 }
1412
1413 /* Generate functions to call static constructors and destructors
1414    for targets that do not support .ctors/.dtors sections.  These
1415    functions have magic names which are detected by collect2.  */
1416
1417 static void
1418 build_cdtor_fns (void)
1419 {
1420   if (!VEC_empty (tree, static_ctors))
1421     {
1422       gcc_assert (!targetm.have_ctors_dtors || in_lto_p);
1423       VEC_qsort (tree, static_ctors, compare_ctor);
1424       build_cdtor (/*ctor_p=*/true, static_ctors);
1425     }
1426
1427   if (!VEC_empty (tree, static_dtors))
1428     {
1429       gcc_assert (!targetm.have_ctors_dtors || in_lto_p);
1430       VEC_qsort (tree, static_dtors, compare_dtor);
1431       build_cdtor (/*ctor_p=*/false, static_dtors);
1432     }
1433 }
1434
1435 /* Look for constructors and destructors and produce function calling them.
1436    This is needed for targets not supporting ctors or dtors, but we perform the
1437    transformation also at linktime to merge possibly numberous
1438    constructors/destructors into single function to improve code locality and
1439    reduce size.  */
1440
1441 static unsigned int
1442 ipa_cdtor_merge (void)
1443 {
1444   struct cgraph_node *node;
1445   for (node = cgraph_nodes; node; node = node->next)
1446     if (node->analyzed
1447         && (DECL_STATIC_CONSTRUCTOR (node->decl)
1448             || DECL_STATIC_DESTRUCTOR (node->decl)))
1449        record_cdtor_fn (node);
1450   build_cdtor_fns ();
1451   VEC_free (tree, heap, static_ctors);
1452   VEC_free (tree, heap, static_dtors);
1453   return 0;
1454 }
1455
1456 /* Perform the pass when we have no ctors/dtors support
1457    or at LTO time to merge multiple constructors into single
1458    function.  */
1459
1460 static bool
1461 gate_ipa_cdtor_merge (void)
1462 {
1463   return !targetm.have_ctors_dtors || (optimize && in_lto_p);
1464 }
1465
1466 struct ipa_opt_pass_d pass_ipa_cdtor_merge =
1467 {
1468  {
1469   IPA_PASS,
1470   "cdtor",                              /* name */
1471   gate_ipa_cdtor_merge,                 /* gate */
1472   ipa_cdtor_merge,                      /* execute */
1473   NULL,                                 /* sub */
1474   NULL,                                 /* next */
1475   0,                                    /* static_pass_number */
1476   TV_CGRAPHOPT,                         /* tv_id */
1477   0,                                    /* properties_required */
1478   0,                                    /* properties_provided */
1479   0,                                    /* properties_destroyed */
1480   0,                                    /* todo_flags_start */
1481   0                                     /* todo_flags_finish */
1482  },
1483  NULL,                                  /* generate_summary */
1484  NULL,                                  /* write_summary */
1485  NULL,                                  /* read_summary */
1486  NULL,                                  /* write_optimization_summary */
1487  NULL,                                  /* read_optimization_summary */
1488  NULL,                                  /* stmt_fixup */
1489  0,                                     /* TODOs */
1490  NULL,                                  /* function_transform */
1491  NULL                                   /* variable_transform */
1492 };