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