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