gcc/ipa.c

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