gcc/ipa.c

   1 /* Basic IPA optimizations and utilities.
   2    Copyright (C) 2003, 2004, 2005, 2007, 2008, 2009, 2010
   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
  32 /* Fill array order with all nodes with output flag set in the reverse
  33    topological order.  */
  34
  35 int
  36 cgraph_postorder (struct cgraph_node **order)
  37 {
  38   struct cgraph_node *node, *node2;
  39   int stack_size = 0;
  40   int order_pos = 0;
  41   struct cgraph_edge *edge, last;
  42   int pass;
  43
  44   struct cgraph_node **stack =
  45     XCNEWVEC (struct cgraph_node *, cgraph_n_nodes);
  46
  47   /* We have to deal with cycles nicely, so use a depth first traversal
  48      output algorithm.  Ignore the fact that some functions won't need
  49      to be output and put them into order as well, so we get dependencies
  50      right through inline functions.  */
  51   for (node = cgraph_nodes; node; node = node->next)
  52     node->aux = NULL;
  53   for (pass = 0; pass < 2; pass++)
  54     for (node = cgraph_nodes; node; node = node->next)
  55       if (!node->aux
  56           && (pass
  57               || (!cgraph_only_called_directly_p (node)
  58                   && !node->address_taken)))
  59         {
  60           node2 = node;
  61           if (!node->callers)
  62             node->aux = &last;
  63           else
  64             node->aux = node->callers;
  65           while (node2)
  66             {
  67               while (node2->aux != &last)
  68                 {
  69                   edge = (struct cgraph_edge *) node2->aux;
  70                   if (edge->next_caller)
  71                     node2->aux = edge->next_caller;
  72                   else
  73                     node2->aux = &last;
  74                   /* Break possible cycles involving always-inline
  75                      functions by ignoring edges from always-inline
  76                      functions to non-always-inline functions.  */
  77                   if (edge->caller->local.disregard_inline_limits
  78                       && !edge->callee->local.disregard_inline_limits)
  79                     continue;
  80                   if (!edge->caller->aux)
  81                     {
  82                       if (!edge->caller->callers)
  83                         edge->caller->aux = &last;
  84                       else
  85                         edge->caller->aux = edge->caller->callers;
  86                       stack[stack_size++] = node2;
  87                       node2 = edge->caller;
  88                       break;
  89                     }
  90                 }
  91               if (node2->aux == &last)
  92                 {
  93                   order[order_pos++] = node2;
  94                   if (stack_size)
  95                     node2 = stack[--stack_size];
  96                   else
  97                     node2 = NULL;
  98                 }
  99             }
 100         }
 101   free (stack);
 102   for (node = cgraph_nodes; node; node = node->next)
 103     node->aux = NULL;
 104   return order_pos;
 105 }
 106
 107 /* Look for all functions inlined to NODE and update their inlined_to pointers
 108    to INLINED_TO.  */
 109
 110 static void
 111 update_inlined_to_pointer (struct cgraph_node *node, struct cgraph_node *inlined_to)
 112 {
 113   struct cgraph_edge *e;
 114   for (e = node->callees; e; e = e->next_callee)
 115     if (e->callee->global.inlined_to)
 116       {
 117         e->callee->global.inlined_to = inlined_to;
 118         update_inlined_to_pointer (e->callee, inlined_to);
 119       }
 120 }
 121
 122 /* Add cgraph NODE to queue starting at FIRST.
 123
 124    The queue is linked via AUX pointers and terminated by pointer to 1.
 125    We enqueue nodes at two occasions: when we find them reachable or when we find
 126    their bodies needed for further clonning.  In the second case we mark them
 127    by pointer to 2 after processing so they are re-queue when they become
 128    reachable.  */
 129
 130 static void
 131 enqueue_cgraph_node (struct cgraph_node *node, struct cgraph_node **first)
 132 {
 133   /* Node is still in queue; do nothing.  */
 134   if (node->aux && node->aux != (void *) 2)
 135     return;
 136   /* Node was already processed as unreachable, re-enqueue
 137      only if it became reachable now.  */
 138   if (node->aux == (void *)2 && !node->reachable)
 139     return;
 140   node->aux = *first;
 141   *first = node;
 142 }
 143
 144 /* Add varpool NODE to queue starting at FIRST.  */
 145
 146 static void
 147 enqueue_varpool_node (struct varpool_node *node, struct varpool_node **first)
 148 {
 149   node->aux = *first;
 150   *first = node;
 151 }
 152
 153 /* Process references.  */
 154
 155 static void
 156 process_references (struct ipa_ref_list *list,
 157                     struct cgraph_node **first,
 158                     struct varpool_node **first_varpool,
 159                     bool before_inlining_p)
 160 {
 161   int i;
 162   struct ipa_ref *ref;
 163   for (i = 0; ipa_ref_list_reference_iterate (list, i, ref); i++)
 164     {
 165       if (ref->refered_type == IPA_REF_CGRAPH)
 166         {
 167           struct cgraph_node *node = ipa_ref_node (ref);
 168           if (!node->reachable
 169               && (!DECL_EXTERNAL (node->decl)
 170                   || before_inlining_p))
 171             {
 172               node->reachable = true;
 173               enqueue_cgraph_node (node, first);
 174             }
 175         }
 176       else
 177         {
 178           struct varpool_node *node = ipa_ref_varpool_node (ref);
 179           if (!node->needed)
 180             {
 181               varpool_mark_needed_node (node);
 182               enqueue_varpool_node (node, first_varpool);
 183             }
 184         }
 185     }
 186 }
 187
 188 /* Return true when function NODE can be removed from callgraph
 189    if all direct calls are eliminated.  */
 190
 191 static inline bool
 192 varpool_can_remove_if_no_refs (struct varpool_node *node)
 193 {
 194   return (!node->force_output && !node->used_from_other_partition
 195           && (DECL_COMDAT (node->decl) || !node->externally_visible));
 196 }
 197
 198 /* Return true when function can be marked local.  */
 199
 200 static bool
 201 cgraph_local_node_p (struct cgraph_node *node)
 202 {
 203    return (cgraph_only_called_directly_p (node)
 204            && node->analyzed
 205            && !DECL_EXTERNAL (node->decl)
 206            && !node->local.externally_visible
 207            && !node->reachable_from_other_partition
 208            && !node->in_other_partition);
 209 }
 210
 211 /* Perform reachability analysis and reclaim all unreachable nodes.
 212    If BEFORE_INLINING_P is true this function is called before inlining
 213    decisions has been made.  If BEFORE_INLINING_P is false this function also
 214    removes unneeded bodies of extern inline functions.  */
 215
 216 bool
 217 cgraph_remove_unreachable_nodes (bool before_inlining_p, FILE *file)
 218 {
 219   struct cgraph_node *first = (struct cgraph_node *) (void *) 1;
 220   struct varpool_node *first_varpool = (struct varpool_node *) (void *) 1;
 221   struct cgraph_node *node, *next;
 222   struct varpool_node *vnode, *vnext;
 223   bool changed = false;
 224
 225 #ifdef ENABLE_CHECKING
 226   verify_cgraph ();
 227 #endif
 228   if (file)
 229     fprintf (file, "\nReclaiming functions:");
 230 #ifdef ENABLE_CHECKING
 231   for (node = cgraph_nodes; node; node = node->next)
 232     gcc_assert (!node->aux);
 233   for (vnode = varpool_nodes; vnode; vnode = vnode->next)
 234     gcc_assert (!vnode->aux);
 235 #endif
 236   varpool_reset_queue ();
 237   for (node = cgraph_nodes; node; node = node->next)
 238     if (!cgraph_can_remove_if_no_direct_calls_and_refs_p (node)
 239         && ((!DECL_EXTERNAL (node->decl))
 240             || before_inlining_p))
 241       {
 242         gcc_assert (!node->global.inlined_to);
 243         enqueue_cgraph_node (node, &first);
 244         node->reachable = true;
 245       }
 246     else
 247       {
 248         gcc_assert (!node->aux);
 249         node->reachable = false;
 250       }
 251   for (vnode = varpool_nodes; vnode; vnode = vnode->next)
 252     {
 253       vnode->next_needed = NULL;
 254       vnode->prev_needed = NULL;
 255       if (!varpool_can_remove_if_no_refs (vnode))
 256         {
 257           vnode->needed = false;
 258           varpool_mark_needed_node (vnode);
 259           enqueue_varpool_node (vnode, &first_varpool);
 260         }
 261       else
 262         vnode->needed = false;
 263     }
 264
 265   /* Perform reachability analysis.  As a special case do not consider
 266      extern inline functions not inlined as live because we won't output
 267      them at all.
 268
 269      We maintain two worklist, one for cgraph nodes other for varpools and
 270      are finished once both are empty.  */
 271
 272   while (first != (struct cgraph_node *) (void *) 1
 273          || first_varpool != (struct varpool_node *) (void *) 1)
 274     {
 275       if (first != (struct cgraph_node *) (void *) 1)
 276         {
 277           struct cgraph_edge *e;
 278           node = first;
 279           first = (struct cgraph_node *) first->aux;
 280           if (!node->reachable)
 281             node->aux = (void *)2;
 282
 283           /* If we found this node reachable, first mark on the callees
 284              reachable too, unless they are direct calls to extern inline functions
 285              we decided to not inline.  */
 286           if (node->reachable)
 287             for (e = node->callees; e; e = e->next_callee)
 288               if (!e->callee->reachable
 289                   && node->analyzed
 290                   && (!e->inline_failed || !e->callee->analyzed
 291                       || (!DECL_EXTERNAL (e->callee->decl))
 292                       || before_inlining_p))
 293                 {
 294                   e->callee->reachable = true;
 295                   enqueue_cgraph_node (e->callee, &first);
 296                 }
 297
 298           /* If any function in a comdat group is reachable, force
 299              all other functions in the same comdat group to be
 300              also reachable.  */
 301           if (node->same_comdat_group
 302               && node->reachable
 303               && !node->global.inlined_to)
 304             {
 305               for (next = node->same_comdat_group;
 306                    next != node;
 307                    next = next->same_comdat_group)
 308                 if (!next->reachable)
 309                   {
 310                     next->reachable = true;
 311                     enqueue_cgraph_node (next, &first);
 312                   }
 313             }
 314
 315           /* We can freely remove inline clones even if they are cloned, however if
 316              function is clone of real clone, we must keep it around in order to
 317              make materialize_clones produce function body with the changes
 318              applied.  */
 319           while (node->clone_of && !node->clone_of->aux && !gimple_has_body_p (node->decl))
 320             {
 321               bool noninline = node->clone_of->decl != node->decl;
 322               node = node->clone_of;
 323               if (noninline && !node->reachable && !node->aux)
 324                 {
 325                   enqueue_cgraph_node (node, &first);
 326                   break;
 327                 }
 328             }
 329           process_references (&node->ref_list, &first, &first_varpool, before_inlining_p);
 330         }
 331       if (first_varpool != (struct varpool_node *) (void *) 1)
 332         {
 333           vnode = first_varpool;
 334           first_varpool = (struct varpool_node *)first_varpool->aux;
 335           vnode->aux = NULL;
 336           process_references (&vnode->ref_list, &first, &first_varpool, before_inlining_p);
 337         }
 338     }
 339
 340   /* Remove unreachable nodes.
 341
 342      Completely unreachable functions can be fully removed from the callgraph.
 343      Extern inline functions that we decided to not inline need to become unanalyzed nodes of
 344      callgraph (so we still have edges to them).  We remove function body then.
 345
 346      Also we need to care functions that are unreachable but we need to keep them around
 347      for later clonning.  In this case we also turn them to unanalyzed nodes, but
 348      keep the body around.  */
 349   for (node = cgraph_nodes; node; node = next)
 350     {
 351       next = node->next;
 352       if (node->aux && !node->reachable)
 353         {
 354           cgraph_node_remove_callees (node);
 355           node->analyzed = false;
 356           node->local.inlinable = false;
 357         }
 358       if (!node->aux)
 359         {
 360           node->global.inlined_to = NULL;
 361           if (file)
 362             fprintf (file, " %s", cgraph_node_name (node));
 363           if (!node->analyzed || !DECL_EXTERNAL (node->decl) || before_inlining_p)
 364             cgraph_remove_node (node);
 365           else
 366             {
 367               struct cgraph_edge *e;
 368
 369               /* See if there is reachable caller.  */
 370               for (e = node->callers; e; e = e->next_caller)
 371                 if (e->caller->reachable)
 372                   break;
 373
 374               /* If so, we need to keep node in the callgraph.  */
 375               if (e || node->needed)
 376                 {
 377                   struct cgraph_node *clone;
 378
 379                   /* If there are still clones, we must keep body around.
 380                      Otherwise we can just remove the body but keep the clone.  */
 381                   for (clone = node->clones; clone;
 382                        clone = clone->next_sibling_clone)
 383                     if (clone->aux)
 384                       break;
 385                   if (!clone)
 386                     {
 387                       cgraph_release_function_body (node);
 388                       node->analyzed = false;
 389                       node->local.inlinable = false;
 390                     }
 391                   else
 392                     gcc_assert (!clone->in_other_partition);
 393                   cgraph_node_remove_callees (node);
 394                   ipa_remove_all_references (&node->ref_list);
 395                   if (node->prev_sibling_clone)
 396                     node->prev_sibling_clone->next_sibling_clone = node->next_sibling_clone;
 397                   else if (node->clone_of)
 398                     node->clone_of->clones = node->next_sibling_clone;
 399                   if (node->next_sibling_clone)
 400                     node->next_sibling_clone->prev_sibling_clone = node->prev_sibling_clone;
 401                   node->clone_of = NULL;
 402                   node->next_sibling_clone = NULL;
 403                   node->prev_sibling_clone = NULL;
 404                 }
 405               else
 406                 cgraph_remove_node (node);
 407             }
 408           changed = true;
 409         }
 410     }
 411   for (node = cgraph_nodes; node; node = node->next)
 412     {
 413       /* Inline clones might be kept around so their materializing allows further
 414          cloning.  If the function the clone is inlined into is removed, we need
 415          to turn it into normal cone.  */
 416       if (node->global.inlined_to
 417           && !node->callers)
 418         {
 419           gcc_assert (node->clones);
 420           node->global.inlined_to = NULL;
 421           update_inlined_to_pointer (node, node);
 422         }
 423       node->aux = NULL;
 424     }
 425
 426   if (file)
 427     fprintf (file, "\n");
 428
 429   /* We must release unused extern inlines or sanity checking will fail.  Rest of transformations
 430      are undesirable at -O0 since we do not want to remove anything.  */
 431   if (!optimize)
 432     return changed;
 433
 434   if (file)
 435     fprintf (file, "Reclaiming variables:");
 436   for (vnode = varpool_nodes; vnode; vnode = vnext)
 437     {
 438       vnext = vnode->next;
 439       if (!vnode->needed)
 440         {
 441           if (file)
 442             fprintf (file, " %s", varpool_node_name (vnode));
 443           varpool_remove_node (vnode);
 444           changed = true;
 445         }
 446     }
 447
 448   /* Now update address_taken flags and try to promote functions to be local.  */
 449
 450   if (file)
 451     fprintf (file, "\nClearing address taken flags:");
 452   for (node = cgraph_nodes; node; node = node->next)
 453     if (node->address_taken
 454         && !node->reachable_from_other_partition)
 455       {
 456         int i;
 457         struct ipa_ref *ref;
 458         bool found = false;
 459         for (i = 0; ipa_ref_list_refering_iterate (&node->ref_list, i, ref)
 460                     && !found; i++)
 461           {
 462             gcc_assert (ref->use == IPA_REF_ADDR);
 463             found = true;
 464           }
 465         if (!found)
 466           {
 467             if (file)
 468               fprintf (file, " %s", cgraph_node_name (node));
 469             node->address_taken = false;
 470             changed = true;
 471             if (cgraph_local_node_p (node))
 472               {
 473                 node->local.local = true;
 474                 if (file)
 475                   fprintf (file, " (local)");
 476               }
 477           }
 478       }
 479
 480 #ifdef ENABLE_CHECKING
 481   verify_cgraph ();
 482 #endif
 483
 484   /* Reclaim alias pairs for functions that have disappeared from the
 485      call graph.  */
 486   remove_unreachable_alias_pairs ();
 487
 488   return changed;
 489 }
 490
 491 /* Discover variables that have no longer address taken or that are read only
 492    and update their flags.
 493
 494    FIXME: This can not be done in between gimplify and omp_expand since
 495    readonly flag plays role on what is shared and what is not.  Currently we do
 496    this transformation as part of ipa-reference pass, but it would make sense
 497    to do it before early optimizations.  */
 498
 499 void
 500 ipa_discover_readonly_nonaddressable_vars (void)
 501 {
 502   struct varpool_node *vnode;
 503   if (dump_file)
 504     fprintf (dump_file, "Clearing variable flags:");
 505   for (vnode = varpool_nodes; vnode; vnode = vnode->next)
 506     if (vnode->finalized && varpool_all_refs_explicit_p (vnode)
 507         && (TREE_ADDRESSABLE (vnode->decl) || !TREE_READONLY (vnode->decl)))
 508       {
 509         bool written = false;
 510         bool address_taken = false;
 511         int i;
 512         struct ipa_ref *ref;
 513         for (i = 0; ipa_ref_list_refering_iterate (&vnode->ref_list, i, ref)
 514                     && (!written || !address_taken); i++)
 515           switch (ref->use)
 516             {
 517             case IPA_REF_ADDR:
 518               address_taken = true;
 519               break;
 520             case IPA_REF_LOAD:
 521               break;
 522             case IPA_REF_STORE:
 523               written = true;
 524               break;
 525             }
 526         if (TREE_ADDRESSABLE (vnode->decl) && !address_taken)
 527           {
 528             if (dump_file)
 529               fprintf (dump_file, " %s (addressable)", varpool_node_name (vnode));
 530             TREE_ADDRESSABLE (vnode->decl) = 0;
 531           }
 532         if (!TREE_READONLY (vnode->decl) && !address_taken && !written
 533             /* Making variable in explicit section readonly can cause section
 534                type conflict.
 535                See e.g. gcc.c-torture/compile/pr23237.c */
 536             && DECL_SECTION_NAME (vnode->decl) == NULL)
 537           {
 538             if (dump_file)
 539               fprintf (dump_file, " %s (read-only)", varpool_node_name (vnode));
 540             TREE_READONLY (vnode->decl) = 1;
 541           }
 542       }
 543   if (dump_file)
 544     fprintf (dump_file, "\n");
 545 }
 546
 547 /* Return true when function NODE should be considered externally visible.  */
 548
 549 static bool
 550 cgraph_externally_visible_p (struct cgraph_node *node, bool whole_program)
 551 {
 552   if (!node->local.finalized)
 553     return false;
 554   if (!DECL_COMDAT (node->decl)
 555       && (!TREE_PUBLIC (node->decl) || DECL_EXTERNAL (node->decl)))
 556     return false;
 557   if (!whole_program)
 558     return true;
 559   if (DECL_PRESERVE_P (node->decl))
 560     return true;
 561   /* COMDAT functions must be shared only if they have address taken,
 562      otherwise we can produce our own private implementation with
 563      -fwhole-program.  */
 564   if (DECL_COMDAT (node->decl))
 565     {
 566       if (node->address_taken || !node->analyzed)
 567         return true;
 568       if (node->same_comdat_group)
 569         {
 570           struct cgraph_node *next;
 571
 572           /* If more than one function is in the same COMDAT group, it must
 573              be shared even if just one function in the comdat group has
 574              address taken.  */
 575           for (next = node->same_comdat_group;
 576                next != node;
 577                next = next->same_comdat_group)
 578             if (next->address_taken || !next->analyzed)
 579               return true;
 580         }
 581     }
 582   if (MAIN_NAME_P (DECL_NAME (node->decl)))
 583     return true;
 584   if (lookup_attribute ("externally_visible", DECL_ATTRIBUTES (node->decl)))
 585     return true;
 586   return false;
 587 }
 588
 589 /* Dissolve the same_comdat_group list in which NODE resides.  */
 590
 591 static void
 592 dissolve_same_comdat_group_list (struct cgraph_node *node)
 593 {
 594   struct cgraph_node *n = node, *next;
 595   do
 596     {
 597       next = n->same_comdat_group;
 598       n->same_comdat_group = NULL;
 599       n = next;
 600     }
 601   while (n != node);
 602 }
 603
 604 /* Mark visibility of all functions.
 605
 606    A local function is one whose calls can occur only in the current
 607    compilation unit and all its calls are explicit, so we can change
 608    its calling convention.  We simply mark all static functions whose
 609    address is not taken as local.
 610
 611    We also change the TREE_PUBLIC flag of all declarations that are public
 612    in language point of view but we want to overwrite this default
 613    via visibilities for the backend point of view.  */
 614
 615 static unsigned int
 616 function_and_variable_visibility (bool whole_program)
 617 {
 618   struct cgraph_node *node;
 619   struct varpool_node *vnode;
 620
 621   for (node = cgraph_nodes; node; node = node->next)
 622     {
 623       /* C++ FE on lack of COMDAT support create local COMDAT functions
 624          (that ought to be shared but can not due to object format
 625          limitations).  It is neccesary to keep the flag to make rest of C++ FE
 626          happy.  Clear the flag here to avoid confusion in middle-end.  */
 627       if (DECL_COMDAT (node->decl) && !TREE_PUBLIC (node->decl))
 628         DECL_COMDAT (node->decl) = 0;
 629       /* For external decls stop tracking same_comdat_group, it doesn't matter
 630          what comdat group they are in when they won't be emitted in this TU,
 631          and simplifies later passes.  */
 632       if (node->same_comdat_group && DECL_EXTERNAL (node->decl))
 633         {
 634 #ifdef ENABLE_CHECKING
 635           struct cgraph_node *n;
 636
 637           for (n = node->same_comdat_group;
 638                n != node;
 639                n = n->same_comdat_group)
 640               /* If at least one of same comdat group functions is external,
 641                  all of them have to be, otherwise it is a front-end bug.  */
 642               gcc_assert (DECL_EXTERNAL (n->decl));
 643 #endif
 644           dissolve_same_comdat_group_list (node);
 645         }
 646       gcc_assert ((!DECL_WEAK (node->decl) && !DECL_COMDAT (node->decl))
 647                   || TREE_PUBLIC (node->decl) || DECL_EXTERNAL (node->decl));
 648       if (cgraph_externally_visible_p (node, whole_program))
 649         {
 650           gcc_assert (!node->global.inlined_to);
 651           node->local.externally_visible = true;
 652         }
 653       else
 654         node->local.externally_visible = false;
 655       if (!node->local.externally_visible && node->analyzed
 656           && !DECL_EXTERNAL (node->decl))
 657         {
 658           struct cgraph_node *alias;
 659           gcc_assert (whole_program || !TREE_PUBLIC (node->decl));
 660           cgraph_make_decl_local (node->decl);
 661           for (alias = node->same_body; alias; alias = alias->next)
 662             cgraph_make_decl_local (alias->decl);
 663           if (node->same_comdat_group)
 664             /* cgraph_externally_visible_p has already checked all other nodes
 665                in the group and they will all be made local.  We need to
 666                dissolve the group at once so that the predicate does not
 667                segfault though. */
 668             dissolve_same_comdat_group_list (node);
 669         }
 670       node->local.local = cgraph_local_node_p (node);
 671     }
 672   for (vnode = varpool_nodes; vnode; vnode = vnode->next)
 673     {
 674       /* weak flag makes no sense on local variables.  */
 675       gcc_assert (!DECL_WEAK (vnode->decl)
 676                   || TREE_PUBLIC (vnode->decl) || DECL_EXTERNAL (vnode->decl));
 677       /* In several cases declarations can not be common:
 678
 679          - when declaration has initializer
 680          - when it is in weak
 681          - when it has specific section
 682          - when it resides in non-generic address space.
 683          - if declaration is local, it will get into .local common section
 684            so common flag is not needed.  Frontends still produce these in
 685            certain cases, such as for:
 686
 687              static int a __attribute__ ((common))
 688
 689          Canonicalize things here and clear the redundant flag.  */
 690       if (DECL_COMMON (vnode->decl)
 691           && (!(TREE_PUBLIC (vnode->decl) || DECL_EXTERNAL (vnode->decl))
 692               || (DECL_INITIAL (vnode->decl)
 693                   && DECL_INITIAL (vnode->decl) != error_mark_node)
 694               || DECL_WEAK (vnode->decl)
 695               || DECL_SECTION_NAME (vnode->decl) != NULL
 696               || ! (ADDR_SPACE_GENERIC_P
 697                     (TYPE_ADDR_SPACE (TREE_TYPE (vnode->decl))))))
 698         DECL_COMMON (vnode->decl) = 0;
 699     }
 700   for (vnode = varpool_nodes_queue; vnode; vnode = vnode->next_needed)
 701     {
 702       if (!vnode->finalized)
 703         continue;
 704       if (vnode->needed
 705           && (DECL_COMDAT (vnode->decl) || TREE_PUBLIC (vnode->decl))
 706           && (!whole_program
 707               /* We can privatize comdat readonly variables whose address is not taken,
 708                  but doing so is not going to bring us optimization oppurtunities until
 709                  we start reordering datastructures.  */
 710               || DECL_COMDAT (vnode->decl)
 711               || DECL_WEAK (vnode->decl)
 712               || lookup_attribute ("externally_visible",
 713                                    DECL_ATTRIBUTES (vnode->decl))))
 714         vnode->externally_visible = true;
 715       else
 716         vnode->externally_visible = false;
 717       if (!vnode->externally_visible)
 718         {
 719           gcc_assert (whole_program || !TREE_PUBLIC (vnode->decl));
 720           cgraph_make_decl_local (vnode->decl);
 721         }
 722      gcc_assert (TREE_STATIC (vnode->decl));
 723     }
 724
 725   if (dump_file)
 726     {
 727       fprintf (dump_file, "\nMarking local functions:");
 728       for (node = cgraph_nodes; node; node = node->next)
 729         if (node->local.local)
 730           fprintf (dump_file, " %s", cgraph_node_name (node));
 731       fprintf (dump_file, "\n\n");
 732       fprintf (dump_file, "\nMarking externally visible functions:");
 733       for (node = cgraph_nodes; node; node = node->next)
 734         if (node->local.externally_visible)
 735           fprintf (dump_file, " %s", cgraph_node_name (node));
 736       fprintf (dump_file, "\n\n");
 737       fprintf (dump_file, "\nMarking externally visible variables:");
 738       for (vnode = varpool_nodes_queue; vnode; vnode = vnode->next_needed)
 739         if (vnode->externally_visible)
 740           fprintf (dump_file, " %s", varpool_node_name (vnode));
 741       fprintf (dump_file, "\n\n");
 742     }
 743   cgraph_function_flags_ready = true;
 744   return 0;
 745 }
 746
 747 /* Local function pass handling visibilities.  This happens before LTO streaming
 748    so in particular -fwhole-program should be ignored at this level.  */
 749
 750 static unsigned int
 751 local_function_and_variable_visibility (void)
 752 {
 753   return function_and_variable_visibility (flag_whole_program && !flag_lto && !flag_whopr);
 754 }
 755
 756 struct simple_ipa_opt_pass pass_ipa_function_and_variable_visibility =
 757 {
 758  {
 759   SIMPLE_IPA_PASS,
 760   "visibility",                         /* name */
 761   NULL,                                 /* gate */
 762   local_function_and_variable_visibility,/* execute */
 763   NULL,                                 /* sub */
 764   NULL,                                 /* next */
 765   0,                                    /* static_pass_number */
 766   TV_CGRAPHOPT,                         /* tv_id */
 767   0,                                    /* properties_required */
 768   0,                                    /* properties_provided */
 769   0,                                    /* properties_destroyed */
 770   0,                                    /* todo_flags_start */
 771   TODO_remove_functions | TODO_dump_cgraph
 772   | TODO_ggc_collect                    /* todo_flags_finish */
 773  }
 774 };
 775
 776 /* Do not re-run on ltrans stage.  */
 777
 778 static bool
 779 gate_whole_program_function_and_variable_visibility (void)
 780 {
 781   return !flag_ltrans;
 782 }
 783
 784 /* Bring functionss local at LTO time whith -fwhole-program.  */
 785
 786 static unsigned int
 787 whole_program_function_and_variable_visibility (void)
 788 {
 789   struct cgraph_node *node;
 790   struct varpool_node *vnode;
 791
 792   function_and_variable_visibility (flag_whole_program);
 793
 794   for (node = cgraph_nodes; node; node = node->next)
 795     if ((node->local.externally_visible && !DECL_COMDAT (node->decl))
 796         && node->local.finalized)
 797       cgraph_mark_needed_node (node);
 798   for (vnode = varpool_nodes_queue; vnode; vnode = vnode->next_needed)
 799     if (vnode->externally_visible && !DECL_COMDAT (vnode->decl))
 800       varpool_mark_needed_node (vnode);
 801   if (dump_file)
 802     {
 803       fprintf (dump_file, "\nNeeded variables:");
 804       for (vnode = varpool_nodes_queue; vnode; vnode = vnode->next_needed)
 805         if (vnode->needed)
 806           fprintf (dump_file, " %s", varpool_node_name (vnode));
 807       fprintf (dump_file, "\n\n");
 808     }
 809   return 0;
 810 }
 811
 812 struct ipa_opt_pass_d pass_ipa_whole_program_visibility =
 813 {
 814  {
 815   IPA_PASS,
 816   "whole-program",                      /* name */
 817   gate_whole_program_function_and_variable_visibility,/* gate */
 818   whole_program_function_and_variable_visibility,/* execute */
 819   NULL,                                 /* sub */
 820   NULL,                                 /* next */
 821   0,                                    /* static_pass_number */
 822   TV_CGRAPHOPT,                         /* tv_id */
 823   0,                                    /* properties_required */
 824   0,                                    /* properties_provided */
 825   0,                                    /* properties_destroyed */
 826   0,                                    /* todo_flags_start */
 827   TODO_remove_functions | TODO_dump_cgraph
 828   | TODO_ggc_collect                    /* todo_flags_finish */
 829  },
 830  NULL,                                  /* generate_summary */
 831  NULL,                                  /* write_summary */
 832  NULL,                                  /* read_summary */
 833  NULL,                                  /* write_optimization_summary */
 834  NULL,                                  /* read_optimization_summary */
 835  NULL,                                  /* stmt_fixup */
 836  0,                                     /* TODOs */
 837  NULL,                                  /* function_transform */
 838  NULL,                                  /* variable_transform */
 839 };
 840
 841 /* Hash a cgraph node set element.  */
 842
 843 static hashval_t
 844 hash_cgraph_node_set_element (const void *p)
 845 {
 846   const_cgraph_node_set_element element = (const_cgraph_node_set_element) p;
 847   return htab_hash_pointer (element->node);
 848 }
 849
 850 /* Compare two cgraph node set elements.  */
 851
 852 static int
 853 eq_cgraph_node_set_element (const void *p1, const void *p2)
 854 {
 855   const_cgraph_node_set_element e1 = (const_cgraph_node_set_element) p1;
 856   const_cgraph_node_set_element e2 = (const_cgraph_node_set_element) p2;
 857
 858   return e1->node == e2->node;
 859 }
 860
 861 /* Create a new cgraph node set.  */
 862
 863 cgraph_node_set
 864 cgraph_node_set_new (void)
 865 {
 866   cgraph_node_set new_node_set;
 867
 868   new_node_set = GGC_NEW (struct cgraph_node_set_def);
 869   new_node_set->hashtab = htab_create_ggc (10,
 870                                            hash_cgraph_node_set_element,
 871                                            eq_cgraph_node_set_element,
 872                                            NULL);
 873   new_node_set->nodes = NULL;
 874   return new_node_set;
 875 }
 876
 877 /* Add cgraph_node NODE to cgraph_node_set SET.  */
 878
 879 void
 880 cgraph_node_set_add (cgraph_node_set set, struct cgraph_node *node)
 881 {
 882   void **slot;
 883   cgraph_node_set_element element;
 884   struct cgraph_node_set_element_def dummy;
 885
 886   dummy.node = node;
 887   slot = htab_find_slot (set->hashtab, &dummy, INSERT);
 888
 889   if (*slot != HTAB_EMPTY_ENTRY)
 890     {
 891       element = (cgraph_node_set_element) *slot;
 892       gcc_assert (node == element->node
 893                   && (VEC_index (cgraph_node_ptr, set->nodes, element->index)
 894                       == node));
 895       return;
 896     }
 897
 898   /* Insert node into hash table.  */
 899   element =
 900     (cgraph_node_set_element) GGC_NEW (struct cgraph_node_set_element_def);
 901   element->node = node;
 902   element->index = VEC_length (cgraph_node_ptr, set->nodes);
 903   *slot = element;
 904
 905   /* Insert into node vector.  */
 906   VEC_safe_push (cgraph_node_ptr, gc, set->nodes, node);
 907 }
 908
 909 /* Remove cgraph_node NODE from cgraph_node_set SET.  */
 910
 911 void
 912 cgraph_node_set_remove (cgraph_node_set set, struct cgraph_node *node)
 913 {
 914   void **slot, **last_slot;
 915   cgraph_node_set_element element, last_element;
 916   struct cgraph_node *last_node;
 917   struct cgraph_node_set_element_def dummy;
 918
 919   dummy.node = node;
 920   slot = htab_find_slot (set->hashtab, &dummy, NO_INSERT);
 921   if (slot == NULL)
 922     return;
 923
 924   element = (cgraph_node_set_element) *slot;
 925   gcc_assert (VEC_index (cgraph_node_ptr, set->nodes, element->index)
 926               == node);
 927
 928   /* Remove from vector. We do this by swapping node with the last element
 929      of the vector.  */
 930   last_node = VEC_pop (cgraph_node_ptr, set->nodes);
 931   if (last_node != node)
 932     {
 933       dummy.node = last_node;
 934       last_slot = htab_find_slot (set->hashtab, &dummy, NO_INSERT);
 935       last_element = (cgraph_node_set_element) *last_slot;
 936       gcc_assert (last_element);
 937
 938       /* Move the last element to the original spot of NODE.  */
 939       last_element->index = element->index;
 940       VEC_replace (cgraph_node_ptr, set->nodes, last_element->index,
 941                    last_node);
 942     }
 943
 944   /* Remove element from hash table.  */
 945   htab_clear_slot (set->hashtab, slot);
 946   ggc_free (element);
 947 }
 948
 949 /* Find NODE in SET and return an iterator to it if found.  A null iterator
 950    is returned if NODE is not in SET.  */
 951
 952 cgraph_node_set_iterator
 953 cgraph_node_set_find (cgraph_node_set set, struct cgraph_node *node)
 954 {
 955   void **slot;
 956   struct cgraph_node_set_element_def dummy;
 957   cgraph_node_set_element element;
 958   cgraph_node_set_iterator csi;
 959
 960   dummy.node = node;
 961   slot = htab_find_slot (set->hashtab, &dummy, NO_INSERT);
 962   if (slot == NULL)
 963     csi.index = (unsigned) ~0;
 964   else
 965     {
 966       element = (cgraph_node_set_element) *slot;
 967       gcc_assert (VEC_index (cgraph_node_ptr, set->nodes, element->index)
 968                   == node);
 969       csi.index = element->index;
 970     }
 971   csi.set = set;
 972
 973   return csi;
 974 }
 975
 976 /* Dump content of SET to file F.  */
 977
 978 void
 979 dump_cgraph_node_set (FILE *f, cgraph_node_set set)
 980 {
 981   cgraph_node_set_iterator iter;
 982
 983   for (iter = csi_start (set); !csi_end_p (iter); csi_next (&iter))
 984     {
 985       struct cgraph_node *node = csi_node (iter);
 986       dump_cgraph_node (f, node);
 987     }
 988 }
 989
 990 /* Dump content of SET to stderr.  */
 991
 992 void
 993 debug_cgraph_node_set (cgraph_node_set set)
 994 {
 995   dump_cgraph_node_set (stderr, set);
 996 }
 997
 998 /* Hash a varpool node set element.  */
 999
1000 static hashval_t
1001 hash_varpool_node_set_element (const void *p)
1002 {
1003   const_varpool_node_set_element element = (const_varpool_node_set_element) p;
1004   return htab_hash_pointer (element->node);
1005 }
1006
1007 /* Compare two varpool node set elements.  */
1008
1009 static int
1010 eq_varpool_node_set_element (const void *p1, const void *p2)
1011 {
1012   const_varpool_node_set_element e1 = (const_varpool_node_set_element) p1;
1013   const_varpool_node_set_element e2 = (const_varpool_node_set_element) p2;
1014
1015   return e1->node == e2->node;
1016 }
1017
1018 /* Create a new varpool node set.  */
1019
1020 varpool_node_set
1021 varpool_node_set_new (void)
1022 {
1023   varpool_node_set new_node_set;
1024
1025   new_node_set = GGC_NEW (struct varpool_node_set_def);
1026   new_node_set->hashtab = htab_create_ggc (10,
1027                                            hash_varpool_node_set_element,
1028                                            eq_varpool_node_set_element,
1029                                            NULL);
1030   new_node_set->nodes = NULL;
1031   return new_node_set;
1032 }
1033
1034 /* Add varpool_node NODE to varpool_node_set SET.  */
1035
1036 void
1037 varpool_node_set_add (varpool_node_set set, struct varpool_node *node)
1038 {
1039   void **slot;
1040   varpool_node_set_element element;
1041   struct varpool_node_set_element_def dummy;
1042
1043   dummy.node = node;
1044   slot = htab_find_slot (set->hashtab, &dummy, INSERT);
1045
1046   if (*slot != HTAB_EMPTY_ENTRY)
1047     {
1048       element = (varpool_node_set_element) *slot;
1049       gcc_assert (node == element->node
1050                   && (VEC_index (varpool_node_ptr, set->nodes, element->index)
1051                       == node));
1052       return;
1053     }
1054
1055   /* Insert node into hash table.  */
1056   element =
1057     (varpool_node_set_element) GGC_NEW (struct varpool_node_set_element_def);
1058   element->node = node;
1059   element->index = VEC_length (varpool_node_ptr, set->nodes);
1060   *slot = element;
1061
1062   /* Insert into node vector.  */
1063   VEC_safe_push (varpool_node_ptr, gc, set->nodes, node);
1064 }
1065
1066 /* Remove varpool_node NODE from varpool_node_set SET.  */
1067
1068 void
1069 varpool_node_set_remove (varpool_node_set set, struct varpool_node *node)
1070 {
1071   void **slot, **last_slot;
1072   varpool_node_set_element element, last_element;
1073   struct varpool_node *last_node;
1074   struct varpool_node_set_element_def dummy;
1075
1076   dummy.node = node;
1077   slot = htab_find_slot (set->hashtab, &dummy, NO_INSERT);
1078   if (slot == NULL)
1079     return;
1080
1081   element = (varpool_node_set_element) *slot;
1082   gcc_assert (VEC_index (varpool_node_ptr, set->nodes, element->index)
1083               == node);
1084
1085   /* Remove from vector. We do this by swapping node with the last element
1086      of the vector.  */
1087   last_node = VEC_pop (varpool_node_ptr, set->nodes);
1088   if (last_node != node)
1089     {
1090       dummy.node = last_node;
1091       last_slot = htab_find_slot (set->hashtab, &dummy, NO_INSERT);
1092       last_element = (varpool_node_set_element) *last_slot;
1093       gcc_assert (last_element);
1094
1095       /* Move the last element to the original spot of NODE.  */
1096       last_element->index = element->index;
1097       VEC_replace (varpool_node_ptr, set->nodes, last_element->index,
1098                    last_node);
1099     }
1100
1101   /* Remove element from hash table.  */
1102   htab_clear_slot (set->hashtab, slot);
1103   ggc_free (element);
1104 }
1105
1106 /* Find NODE in SET and return an iterator to it if found.  A null iterator
1107    is returned if NODE is not in SET.  */
1108
1109 varpool_node_set_iterator
1110 varpool_node_set_find (varpool_node_set set, struct varpool_node *node)
1111 {
1112   void **slot;
1113   struct varpool_node_set_element_def dummy;
1114   varpool_node_set_element element;
1115   varpool_node_set_iterator vsi;
1116
1117   dummy.node = node;
1118   slot = htab_find_slot (set->hashtab, &dummy, NO_INSERT);
1119   if (slot == NULL)
1120     vsi.index = (unsigned) ~0;
1121   else
1122     {
1123       element = (varpool_node_set_element) *slot;
1124       gcc_assert (VEC_index (varpool_node_ptr, set->nodes, element->index)
1125                   == node);
1126       vsi.index = element->index;
1127     }
1128   vsi.set = set;
1129
1130   return vsi;
1131 }
1132
1133 /* Dump content of SET to file F.  */
1134
1135 void
1136 dump_varpool_node_set (FILE *f, varpool_node_set set)
1137 {
1138   varpool_node_set_iterator iter;
1139
1140   for (iter = vsi_start (set); !vsi_end_p (iter); vsi_next (&iter))
1141     {
1142       struct varpool_node *node = vsi_node (iter);
1143       dump_varpool_node (f, node);
1144     }
1145 }
1146
1147 /* Dump content of SET to stderr.  */
1148
1149 void
1150 debug_varpool_node_set (varpool_node_set set)
1151 {
1152   dump_varpool_node_set (stderr, set);
1153 }
1154
1155
1156 /* Simple ipa profile pass propagating frequencies across the callgraph.  */
1157
1158 static unsigned int
1159 ipa_profile (void)
1160 {
1161   struct cgraph_node **order = XCNEWVEC (struct cgraph_node *, cgraph_n_nodes);
1162   struct cgraph_edge *e;
1163   int order_pos;
1164   bool something_changed = false;
1165   int i;
1166
1167   order_pos = cgraph_postorder (order);
1168   for (i = order_pos - 1; i >= 0; i--)
1169     {
1170       if (order[i]->local.local && cgraph_propagate_frequency (order[i]))
1171         {
1172           for (e = order[i]->callees; e; e = e->next_callee)
1173             if (e->callee->local.local && !e->callee->aux)
1174               {
1175                 something_changed = true;
1176                 e->callee->aux = (void *)1;
1177               }
1178         }
1179       order[i]->aux = NULL;
1180     }
1181
1182   while (something_changed)
1183     {
1184       something_changed = false;
1185       for (i = order_pos - 1; i >= 0; i--)
1186         {
1187           if (order[i]->aux && cgraph_propagate_frequency (order[i]))
1188             {
1189               for (e = order[i]->callees; e; e = e->next_callee)
1190                 if (e->callee->local.local && !e->callee->aux)
1191                   {
1192                     something_changed = true;
1193                     e->callee->aux = (void *)1;
1194                   }
1195             }
1196           order[i]->aux = NULL;
1197         }
1198     }
1199   free (order);
1200   return 0;
1201 }
1202
1203 static bool
1204 gate_ipa_profile (void)
1205 {
1206   return flag_ipa_profile;
1207 }
1208
1209 struct ipa_opt_pass_d pass_ipa_profile =
1210 {
1211  {
1212   IPA_PASS,
1213   "ipa-profile",                        /* name */
1214   gate_ipa_profile,                     /* gate */
1215   ipa_profile,                          /* execute */
1216   NULL,                                 /* sub */
1217   NULL,                                 /* next */
1218   0,                                    /* static_pass_number */
1219   TV_IPA_PROFILE,                       /* tv_id */
1220   0,                                    /* properties_required */
1221   0,                                    /* properties_provided */
1222   0,                                    /* properties_destroyed */
1223   0,                                    /* todo_flags_start */
1224   0                                     /* todo_flags_finish */
1225  },
1226  NULL,                                  /* generate_summary */
1227  NULL,                                  /* write_summary */
1228  NULL,                                  /* read_summary */
1229  NULL,                                  /* write_optimization_summary */
1230  NULL,                                  /* read_optimization_summary */
1231  NULL,                                  /* stmt_fixup */
1232  0,                                     /* TODOs */
1233  NULL,                                  /* function_transform */
1234  NULL                                   /* variable_transform */
1235 };