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