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