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                   if (!edge->caller->aux)
  74                     {
  75                       if (!edge->caller->callers)
  76                         edge->caller->aux = &last;
  77                       else
  78                         edge->caller->aux = edge->caller->callers;
  79                       stack[stack_size++] = node2;
  80                       node2 = edge->caller;
  81                       break;
  82                     }
  83                 }
  84               if (node2->aux == &last)
  85                 {
  86                   order[order_pos++] = node2;
  87                   if (stack_size)
  88                     node2 = stack[--stack_size];
  89                   else
  90                     node2 = NULL;
  91                 }
  92             }
  93         }
  94   free (stack);
  95   for (node = cgraph_nodes; node; node = node->next)
  96     node->aux = NULL;
  97   return order_pos;
  98 }
  99
 100 /* Look for all functions inlined to NODE and update their inlined_to pointers
 101    to INLINED_TO.  */
 102
 103 static void
 104 update_inlined_to_pointer (struct cgraph_node *node, struct cgraph_node *inlined_to)
 105 {
 106   struct cgraph_edge *e;
 107   for (e = node->callees; e; e = e->next_callee)
 108     if (e->callee->global.inlined_to)
 109       {
 110         e->callee->global.inlined_to = inlined_to;
 111         update_inlined_to_pointer (e->callee, inlined_to);
 112       }
 113 }
 114
 115 /* Perform reachability analysis and reclaim all unreachable nodes.
 116    If BEFORE_INLINING_P is true this function is called before inlining
 117    decisions has been made.  If BEFORE_INLINING_P is false this function also
 118    removes unneeded bodies of extern inline functions.  */
 119
 120 bool
 121 cgraph_remove_unreachable_nodes (bool before_inlining_p, FILE *file)
 122 {
 123   struct cgraph_node *first = (struct cgraph_node *) (void *) 1;
 124   struct cgraph_node *processed = (struct cgraph_node *) (void *) 2;
 125   struct cgraph_node *node, *next;
 126   bool changed = false;
 127
 128 #ifdef ENABLE_CHECKING
 129   verify_cgraph ();
 130 #endif
 131   if (file)
 132     fprintf (file, "\nReclaiming functions:");
 133 #ifdef ENABLE_CHECKING
 134   for (node = cgraph_nodes; node; node = node->next)
 135     gcc_assert (!node->aux);
 136 #endif
 137   for (node = cgraph_nodes; node; node = node->next)
 138     if (!cgraph_can_remove_if_no_direct_calls_p (node)
 139         && ((!DECL_EXTERNAL (node->decl))
 140             || !node->analyzed
 141             || before_inlining_p))
 142       {
 143         gcc_assert (!node->global.inlined_to);
 144         node->aux = first;
 145         first = node;
 146         node->reachable = true;
 147       }
 148     else
 149       {
 150         gcc_assert (!node->aux);
 151         node->reachable = false;
 152       }
 153
 154   /* Perform reachability analysis.  As a special case do not consider
 155      extern inline functions not inlined as live because we won't output
 156      them at all.  */
 157   while (first != (void *) 1)
 158     {
 159       struct cgraph_edge *e;
 160       node = first;
 161       first = (struct cgraph_node *) first->aux;
 162       node->aux = processed;
 163
 164       if (node->reachable)
 165         for (e = node->callees; e; e = e->next_callee)
 166           if (!e->callee->reachable
 167               && node->analyzed
 168               && (!e->inline_failed || !e->callee->analyzed
 169                   || (!DECL_EXTERNAL (e->callee->decl))
 170                   || before_inlining_p))
 171             {
 172               bool prev_reachable = e->callee->reachable;
 173               e->callee->reachable |= node->reachable;
 174               if (!e->callee->aux
 175                   || (e->callee->aux == processed
 176                       && prev_reachable != e->callee->reachable))
 177                 {
 178                   e->callee->aux = first;
 179                   first = e->callee;
 180                 }
 181             }
 182
 183       /* If any function in a comdat group is reachable, force
 184          all other functions in the same comdat group to be
 185          also reachable.  */
 186       if (node->same_comdat_group
 187           && node->reachable
 188           && !node->global.inlined_to)
 189         {
 190           for (next = node->same_comdat_group;
 191                next != node;
 192                next = next->same_comdat_group)
 193             if (!next->reachable)
 194               {
 195                 next->aux = first;
 196                 first = next;
 197                 next->reachable = true;
 198               }
 199         }
 200
 201       /* We can freely remove inline clones even if they are cloned, however if
 202          function is clone of real clone, we must keep it around in order to
 203          make materialize_clones produce function body with the changes
 204          applied.  */
 205       while (node->clone_of && !node->clone_of->aux && !gimple_has_body_p (node->decl))
 206         {
 207           bool noninline = node->clone_of->decl != node->decl;
 208           node = node->clone_of;
 209           if (noninline)
 210             {
 211               node->aux = first;
 212               first = node;
 213               break;
 214             }
 215         }
 216     }
 217
 218   /* Remove unreachable nodes.  Extern inline functions need special care;
 219      Unreachable extern inline functions shall be removed.
 220      Reachable extern inline functions we never inlined shall get their bodies
 221      eliminated.
 222      Reachable extern inline functions we sometimes inlined will be turned into
 223      unanalyzed nodes so they look like for true extern functions to the rest
 224      of code.  Body of such functions is released via remove_node once the
 225      inline clones are eliminated.  */
 226   for (node = cgraph_nodes; node; node = next)
 227     {
 228       next = node->next;
 229       if (node->aux && !node->reachable)
 230         {
 231           cgraph_node_remove_callees (node);
 232           node->analyzed = false;
 233           node->local.inlinable = false;
 234         }
 235       if (!node->aux)
 236         {
 237           node->global.inlined_to = NULL;
 238           if (file)
 239             fprintf (file, " %s", cgraph_node_name (node));
 240           if (!node->analyzed || !DECL_EXTERNAL (node->decl) || before_inlining_p)
 241             cgraph_remove_node (node);
 242           else
 243             {
 244               struct cgraph_edge *e;
 245
 246               /* See if there is reachable caller.  */
 247               for (e = node->callers; e; e = e->next_caller)
 248                 if (e->caller->aux)
 249                   break;
 250
 251               /* If so, we need to keep node in the callgraph.  */
 252               if (e || node->needed)
 253                 {
 254                   struct cgraph_node *clone;
 255
 256                   /* If there are still clones, we must keep body around.
 257                      Otherwise we can just remove the body but keep the clone.  */
 258                   for (clone = node->clones; clone;
 259                        clone = clone->next_sibling_clone)
 260                     if (clone->aux)
 261                       break;
 262                   if (!clone)
 263                     {
 264                       cgraph_release_function_body (node);
 265                       node->analyzed = false;
 266                       node->local.inlinable = false;
 267                     }
 268                   cgraph_node_remove_callees (node);
 269                   if (node->prev_sibling_clone)
 270                     node->prev_sibling_clone->next_sibling_clone = node->next_sibling_clone;
 271                   else if (node->clone_of)
 272                     node->clone_of->clones = node->next_sibling_clone;
 273                   if (node->next_sibling_clone)
 274                     node->next_sibling_clone->prev_sibling_clone = node->prev_sibling_clone;
 275                   node->clone_of = NULL;
 276                   node->next_sibling_clone = NULL;
 277                   node->prev_sibling_clone = NULL;
 278                 }
 279               else
 280                 cgraph_remove_node (node);
 281             }
 282           changed = true;
 283         }
 284     }
 285   for (node = cgraph_nodes; node; node = node->next)
 286     {
 287       /* Inline clones might be kept around so their materializing allows further
 288          cloning.  If the function the clone is inlined into is removed, we need
 289          to turn it into normal cone.  */
 290       if (node->global.inlined_to
 291           && !node->callers)
 292         {
 293           gcc_assert (node->clones);
 294           node->global.inlined_to = NULL;
 295           update_inlined_to_pointer (node, node);
 296         }
 297       node->aux = NULL;
 298     }
 299 #ifdef ENABLE_CHECKING
 300   verify_cgraph ();
 301 #endif
 302
 303   /* Reclaim alias pairs for functions that have disappeared from the
 304      call graph.  */
 305   remove_unreachable_alias_pairs ();
 306
 307   return changed;
 308 }
 309
 310 static bool
 311 cgraph_externally_visible_p (struct cgraph_node *node, bool whole_program)
 312 {
 313   if (!node->local.finalized)
 314     return false;
 315   if (!DECL_COMDAT (node->decl)
 316       && (!TREE_PUBLIC (node->decl) || DECL_EXTERNAL (node->decl)))
 317     return false;
 318   if (!whole_program)
 319     return true;
 320   if (DECL_PRESERVE_P (node->decl))
 321     return true;
 322   /* COMDAT functions must be shared only if they have address taken,
 323      otherwise we can produce our own private implementation with
 324      -fwhole-program.  */
 325   if (DECL_COMDAT (node->decl))
 326     {
 327       if (node->address_taken || !node->analyzed)
 328         return true;
 329       if (node->same_comdat_group)
 330         {
 331           struct cgraph_node *next;
 332
 333           /* If more than one function is in the same COMDAT group, it must
 334              be shared even if just one function in the comdat group has
 335              address taken.  */
 336           for (next = node->same_comdat_group;
 337                next != node;
 338                next = next->same_comdat_group)
 339             if (next->address_taken || !next->analyzed)
 340               return true;
 341         }
 342     }
 343   if (MAIN_NAME_P (DECL_NAME (node->decl)))
 344     return true;
 345   if (lookup_attribute ("externally_visible", DECL_ATTRIBUTES (node->decl)))
 346     return true;
 347   return false;
 348 }
 349
 350 /* Mark visibility of all functions.
 351
 352    A local function is one whose calls can occur only in the current
 353    compilation unit and all its calls are explicit, so we can change
 354    its calling convention.  We simply mark all static functions whose
 355    address is not taken as local.
 356
 357    We also change the TREE_PUBLIC flag of all declarations that are public
 358    in language point of view but we want to overwrite this default
 359    via visibilities for the backend point of view.  */
 360
 361 static unsigned int
 362 function_and_variable_visibility (bool whole_program)
 363 {
 364   struct cgraph_node *node;
 365   struct varpool_node *vnode;
 366
 367   for (node = cgraph_nodes; node; node = node->next)
 368     {
 369       /* C++ FE on lack of COMDAT support create local COMDAT functions
 370          (that ought to be shared but can not due to object format
 371          limitations).  It is neccesary to keep the flag to make rest of C++ FE
 372          happy.  Clear the flag here to avoid confusion in middle-end.  */
 373       if (DECL_COMDAT (node->decl) && !TREE_PUBLIC (node->decl))
 374         DECL_COMDAT (node->decl) = 0;
 375       /* For external decls stop tracking same_comdat_group, it doesn't matter
 376          what comdat group they are in when they won't be emitted in this TU,
 377          and simplifies later passes.  */
 378       if (node->same_comdat_group && DECL_EXTERNAL (node->decl))
 379         {
 380           struct cgraph_node *n = node, *next;
 381           do
 382             {
 383               /* If at least one of same comdat group functions is external,
 384                  all of them have to be, otherwise it is a front-end bug.  */
 385               gcc_assert (DECL_EXTERNAL (n->decl));
 386               next = n->same_comdat_group;
 387               n->same_comdat_group = NULL;
 388               n = next;
 389             }
 390           while (n != node);
 391         }
 392       gcc_assert ((!DECL_WEAK (node->decl) && !DECL_COMDAT (node->decl))
 393                   || TREE_PUBLIC (node->decl) || DECL_EXTERNAL (node->decl));
 394       if (cgraph_externally_visible_p (node, whole_program))
 395         {
 396           gcc_assert (!node->global.inlined_to);
 397           node->local.externally_visible = true;
 398         }
 399       else
 400         node->local.externally_visible = false;
 401       if (!node->local.externally_visible && node->analyzed
 402           && !DECL_EXTERNAL (node->decl))
 403         {
 404           gcc_assert (whole_program || !TREE_PUBLIC (node->decl));
 405           cgraph_make_decl_local (node->decl);
 406         }
 407       node->local.local = (cgraph_only_called_directly_p (node)
 408                            && node->analyzed
 409                            && !DECL_EXTERNAL (node->decl)
 410                            && !node->local.externally_visible);
 411     }
 412   for (vnode = varpool_nodes; vnode; vnode = vnode->next)
 413     {
 414       /* weak flag makes no sense on local variables.  */
 415       gcc_assert (!DECL_WEAK (vnode->decl)
 416                   || TREE_PUBLIC (vnode->decl) || DECL_EXTERNAL (vnode->decl));
 417       /* In several cases declarations can not be common:
 418
 419          - when declaration has initializer
 420          - when it is in weak
 421          - when it has specific section
 422          - when it resides in non-generic address space.
 423          - if declaration is local, it will get into .local common section
 424            so common flag is not needed.  Frontends still produce these in
 425            certain cases, such as for:
 426
 427              static int a __attribute__ ((common))
 428
 429          Canonicalize things here and clear the redundant flag.  */
 430       if (DECL_COMMON (vnode->decl)
 431           && (!(TREE_PUBLIC (vnode->decl) || DECL_EXTERNAL (vnode->decl))
 432               || (DECL_INITIAL (vnode->decl)
 433                   && DECL_INITIAL (vnode->decl) != error_mark_node)
 434               || DECL_WEAK (vnode->decl)
 435               || DECL_SECTION_NAME (vnode->decl) != NULL
 436               || ! (ADDR_SPACE_GENERIC_P
 437                     (TYPE_ADDR_SPACE (TREE_TYPE (vnode->decl))))))
 438         DECL_COMMON (vnode->decl) = 0;
 439     }
 440   for (vnode = varpool_nodes_queue; vnode; vnode = vnode->next_needed)
 441     {
 442       if (!vnode->finalized)
 443         continue;
 444       if (vnode->needed
 445           && (DECL_COMDAT (vnode->decl) || TREE_PUBLIC (vnode->decl))
 446           && (!whole_program
 447               /* We can privatize comdat readonly variables whose address is not taken,
 448                  but doing so is not going to bring us optimization oppurtunities until
 449                  we start reordering datastructures.  */
 450               || DECL_COMDAT (vnode->decl)
 451               || DECL_WEAK (vnode->decl)
 452               || lookup_attribute ("externally_visible",
 453                                    DECL_ATTRIBUTES (vnode->decl))))
 454         vnode->externally_visible = true;
 455       else
 456         vnode->externally_visible = false;
 457       if (!vnode->externally_visible)
 458         {
 459           gcc_assert (whole_program || !TREE_PUBLIC (vnode->decl));
 460           cgraph_make_decl_local (vnode->decl);
 461         }
 462      gcc_assert (TREE_STATIC (vnode->decl));
 463     }
 464
 465   if (dump_file)
 466     {
 467       fprintf (dump_file, "\nMarking local functions:");
 468       for (node = cgraph_nodes; node; node = node->next)
 469         if (node->local.local)
 470           fprintf (dump_file, " %s", cgraph_node_name (node));
 471       fprintf (dump_file, "\n\n");
 472       fprintf (dump_file, "\nMarking externally visible functions:");
 473       for (node = cgraph_nodes; node; node = node->next)
 474         if (node->local.externally_visible)
 475           fprintf (dump_file, " %s", cgraph_node_name (node));
 476       fprintf (dump_file, "\n\n");
 477       fprintf (dump_file, "\nMarking externally visible variables:");
 478       for (vnode = varpool_nodes_queue; vnode; vnode = vnode->next_needed)
 479         if (vnode->externally_visible)
 480           fprintf (dump_file, " %s", varpool_node_name (vnode));
 481       fprintf (dump_file, "\n\n");
 482     }
 483   cgraph_function_flags_ready = true;
 484   return 0;
 485 }
 486
 487 /* Local function pass handling visibilities.  This happens before LTO streaming
 488    so in particular -fwhole-program should be ignored at this level.  */
 489
 490 static unsigned int
 491 local_function_and_variable_visibility (void)
 492 {
 493   return function_and_variable_visibility (flag_whole_program && !flag_lto && !flag_whopr);
 494 }
 495
 496 struct simple_ipa_opt_pass pass_ipa_function_and_variable_visibility =
 497 {
 498  {
 499   SIMPLE_IPA_PASS,
 500   "visibility",                         /* name */
 501   NULL,                                 /* gate */
 502   local_function_and_variable_visibility,/* execute */
 503   NULL,                                 /* sub */
 504   NULL,                                 /* next */
 505   0,                                    /* static_pass_number */
 506   TV_CGRAPHOPT,                         /* tv_id */
 507   0,                                    /* properties_required */
 508   0,                                    /* properties_provided */
 509   0,                                    /* properties_destroyed */
 510   0,                                    /* todo_flags_start */
 511   TODO_remove_functions | TODO_dump_cgraph/* todo_flags_finish */
 512  }
 513 };
 514
 515 /* Do not re-run on ltrans stage.  */
 516
 517 static bool
 518 gate_whole_program_function_and_variable_visibility (void)
 519 {
 520   return !flag_ltrans;
 521 }
 522
 523 /* Bring functionss local at LTO time whith -fwhole-program.  */
 524
 525 static unsigned int
 526 whole_program_function_and_variable_visibility (void)
 527 {
 528   struct cgraph_node *node;
 529   struct varpool_node *vnode;
 530
 531   function_and_variable_visibility (flag_whole_program);
 532
 533   for (node = cgraph_nodes; node; node = node->next)
 534     if ((node->local.externally_visible && !DECL_COMDAT (node->decl))
 535         && node->local.finalized)
 536       cgraph_mark_needed_node (node);
 537   for (vnode = varpool_nodes_queue; vnode; vnode = vnode->next_needed)
 538     if (vnode->externally_visible && !DECL_COMDAT (vnode->decl))
 539       varpool_mark_needed_node (vnode);
 540   if (dump_file)
 541     {
 542       fprintf (dump_file, "\nNeeded variables:");
 543       for (vnode = varpool_nodes_queue; vnode; vnode = vnode->next_needed)
 544         if (vnode->needed)
 545           fprintf (dump_file, " %s", varpool_node_name (vnode));
 546       fprintf (dump_file, "\n\n");
 547     }
 548   return 0;
 549 }
 550
 551 struct ipa_opt_pass_d pass_ipa_whole_program_visibility =
 552 {
 553  {
 554   IPA_PASS,
 555   "whole-program",                      /* name */
 556   gate_whole_program_function_and_variable_visibility,/* gate */
 557   whole_program_function_and_variable_visibility,/* execute */
 558   NULL,                                 /* sub */
 559   NULL,                                 /* next */
 560   0,                                    /* static_pass_number */
 561   TV_CGRAPHOPT,                         /* tv_id */
 562   0,                                    /* properties_required */
 563   0,                                    /* properties_provided */
 564   0,                                    /* properties_destroyed */
 565   0,                                    /* todo_flags_start */
 566   TODO_dump_cgraph | TODO_remove_functions/* todo_flags_finish */
 567  },
 568  NULL,                                  /* generate_summary */
 569  NULL,                                  /* write_summary */
 570  NULL,                                  /* read_summary */
 571  NULL,                                  /* function_read_summary */
 572  NULL,                                  /* stmt_fixup */
 573  0,                                     /* TODOs */
 574  NULL,                                  /* function_transform */
 575  NULL,                                  /* variable_transform */
 576 };
 577
 578 /* Hash a cgraph node set element.  */
 579
 580 static hashval_t
 581 hash_cgraph_node_set_element (const void *p)
 582 {
 583   const_cgraph_node_set_element element = (const_cgraph_node_set_element) p;
 584   return htab_hash_pointer (element->node);
 585 }
 586
 587 /* Compare two cgraph node set elements.  */
 588
 589 static int
 590 eq_cgraph_node_set_element (const void *p1, const void *p2)
 591 {
 592   const_cgraph_node_set_element e1 = (const_cgraph_node_set_element) p1;
 593   const_cgraph_node_set_element e2 = (const_cgraph_node_set_element) p2;
 594
 595   return e1->node == e2->node;
 596 }
 597
 598 /* Create a new cgraph node set.  */
 599
 600 cgraph_node_set
 601 cgraph_node_set_new (void)
 602 {
 603   cgraph_node_set new_node_set;
 604
 605   new_node_set = GGC_NEW (struct cgraph_node_set_def);
 606   new_node_set->hashtab = htab_create_ggc (10,
 607                                            hash_cgraph_node_set_element,
 608                                            eq_cgraph_node_set_element,
 609                                            NULL);
 610   new_node_set->nodes = NULL;
 611   return new_node_set;
 612 }
 613
 614 /* Add cgraph_node NODE to cgraph_node_set SET.  */
 615
 616 void
 617 cgraph_node_set_add (cgraph_node_set set, struct cgraph_node *node)
 618 {
 619   void **slot;
 620   cgraph_node_set_element element;
 621   struct cgraph_node_set_element_def dummy;
 622
 623   dummy.node = node;
 624   slot = htab_find_slot (set->hashtab, &dummy, INSERT);
 625
 626   if (*slot != HTAB_EMPTY_ENTRY)
 627     {
 628       element = (cgraph_node_set_element) *slot;
 629       gcc_assert (node == element->node
 630                   && (VEC_index (cgraph_node_ptr, set->nodes, element->index)
 631                       == node));
 632       return;
 633     }
 634
 635   /* Insert node into hash table.  */
 636   element =
 637     (cgraph_node_set_element) GGC_NEW (struct cgraph_node_set_element_def);
 638   element->node = node;
 639   element->index = VEC_length (cgraph_node_ptr, set->nodes);
 640   *slot = element;
 641
 642   /* Insert into node vector.  */
 643   VEC_safe_push (cgraph_node_ptr, gc, set->nodes, node);
 644 }
 645
 646 /* Remove cgraph_node NODE from cgraph_node_set SET.  */
 647
 648 void
 649 cgraph_node_set_remove (cgraph_node_set set, struct cgraph_node *node)
 650 {
 651   void **slot, **last_slot;
 652   cgraph_node_set_element element, last_element;
 653   struct cgraph_node *last_node;
 654   struct cgraph_node_set_element_def dummy;
 655
 656   dummy.node = node;
 657   slot = htab_find_slot (set->hashtab, &dummy, NO_INSERT);
 658   if (slot == NULL)
 659     return;
 660
 661   element = (cgraph_node_set_element) *slot;
 662   gcc_assert (VEC_index (cgraph_node_ptr, set->nodes, element->index)
 663               == node);
 664
 665   /* Remove from vector. We do this by swapping node with the last element
 666      of the vector.  */
 667   last_node = VEC_pop (cgraph_node_ptr, set->nodes);
 668   if (last_node != node)
 669     {
 670       dummy.node = last_node;
 671       last_slot = htab_find_slot (set->hashtab, &dummy, NO_INSERT);
 672       last_element = (cgraph_node_set_element) *last_slot;
 673       gcc_assert (last_element);
 674
 675       /* Move the last element to the original spot of NODE.  */
 676       last_element->index = element->index;
 677       VEC_replace (cgraph_node_ptr, set->nodes, last_element->index,
 678                    last_node);
 679     }
 680
 681   /* Remove element from hash table.  */
 682   htab_clear_slot (set->hashtab, slot);
 683   ggc_free (element);
 684 }
 685
 686 /* Find NODE in SET and return an iterator to it if found.  A null iterator
 687    is returned if NODE is not in SET.  */
 688
 689 cgraph_node_set_iterator
 690 cgraph_node_set_find (cgraph_node_set set, struct cgraph_node *node)
 691 {
 692   void **slot;
 693   struct cgraph_node_set_element_def dummy;
 694   cgraph_node_set_element element;
 695   cgraph_node_set_iterator csi;
 696
 697   dummy.node = node;
 698   slot = htab_find_slot (set->hashtab, &dummy, NO_INSERT);
 699   if (slot == NULL)
 700     csi.index = (unsigned) ~0;
 701   else
 702     {
 703       element = (cgraph_node_set_element) *slot;
 704       gcc_assert (VEC_index (cgraph_node_ptr, set->nodes, element->index)
 705                   == node);
 706       csi.index = element->index;
 707     }
 708   csi.set = set;
 709
 710   return csi;
 711 }
 712
 713 /* Dump content of SET to file F.  */
 714
 715 void
 716 dump_cgraph_node_set (FILE *f, cgraph_node_set set)
 717 {
 718   cgraph_node_set_iterator iter;
 719
 720   for (iter = csi_start (set); !csi_end_p (iter); csi_next (&iter))
 721     {
 722       struct cgraph_node *node = csi_node (iter);
 723       dump_cgraph_node (f, node);
 724     }
 725 }
 726
 727 /* Dump content of SET to stderr.  */
 728
 729 void
 730 debug_cgraph_node_set (cgraph_node_set set)
 731 {
 732   dump_cgraph_node_set (stderr, set);
 733 }
 734