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