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                   cgraph_node_remove_callees (node);
 275                   if (node->prev_sibling_clone)
 276                     node->prev_sibling_clone->next_sibling_clone = node->next_sibling_clone;
 277                   else if (node->clone_of)
 278                     node->clone_of->clones = node->next_sibling_clone;
 279                   if (node->next_sibling_clone)
 280                     node->next_sibling_clone->prev_sibling_clone = node->prev_sibling_clone;
 281                   node->clone_of = NULL;
 282                   node->next_sibling_clone = NULL;
 283                   node->prev_sibling_clone = NULL;
 284                 }
 285               else
 286                 cgraph_remove_node (node);
 287             }
 288           changed = true;
 289         }
 290     }
 291   for (node = cgraph_nodes; node; node = node->next)
 292     {
 293       /* Inline clones might be kept around so their materializing allows further
 294          cloning.  If the function the clone is inlined into is removed, we need
 295          to turn it into normal cone.  */
 296       if (node->global.inlined_to
 297           && !node->callers)
 298         {
 299           gcc_assert (node->clones);
 300           node->global.inlined_to = NULL;
 301           update_inlined_to_pointer (node, node);
 302         }
 303       node->aux = NULL;
 304     }
 305 #ifdef ENABLE_CHECKING
 306   verify_cgraph ();
 307 #endif
 308
 309   /* Reclaim alias pairs for functions that have disappeared from the
 310      call graph.  */
 311   remove_unreachable_alias_pairs ();
 312
 313   return changed;
 314 }
 315
 316 static bool
 317 cgraph_externally_visible_p (struct cgraph_node *node, bool whole_program)
 318 {
 319   if (!node->local.finalized)
 320     return false;
 321   if (!DECL_COMDAT (node->decl)
 322       && (!TREE_PUBLIC (node->decl) || DECL_EXTERNAL (node->decl)))
 323     return false;
 324   if (!whole_program)
 325     return true;
 326   if (DECL_PRESERVE_P (node->decl))
 327     return true;
 328   /* COMDAT functions must be shared only if they have address taken,
 329      otherwise we can produce our own private implementation with
 330      -fwhole-program.  */
 331   if (DECL_COMDAT (node->decl))
 332     {
 333       if (node->address_taken || !node->analyzed)
 334         return true;
 335       if (node->same_comdat_group)
 336         {
 337           struct cgraph_node *next;
 338
 339           /* If more than one function is in the same COMDAT group, it must
 340              be shared even if just one function in the comdat group has
 341              address taken.  */
 342           for (next = node->same_comdat_group;
 343                next != node;
 344                next = next->same_comdat_group)
 345             if (next->address_taken || !next->analyzed)
 346               return true;
 347         }
 348     }
 349   if (MAIN_NAME_P (DECL_NAME (node->decl)))
 350     return true;
 351   if (lookup_attribute ("externally_visible", DECL_ATTRIBUTES (node->decl)))
 352     return true;
 353   return false;
 354 }
 355
 356 /* Mark visibility of all functions.
 357
 358    A local function is one whose calls can occur only in the current
 359    compilation unit and all its calls are explicit, so we can change
 360    its calling convention.  We simply mark all static functions whose
 361    address is not taken as local.
 362
 363    We also change the TREE_PUBLIC flag of all declarations that are public
 364    in language point of view but we want to overwrite this default
 365    via visibilities for the backend point of view.  */
 366
 367 static unsigned int
 368 function_and_variable_visibility (bool whole_program)
 369 {
 370   struct cgraph_node *node;
 371   struct varpool_node *vnode;
 372
 373   for (node = cgraph_nodes; node; node = node->next)
 374     {
 375       /* C++ FE on lack of COMDAT support create local COMDAT functions
 376          (that ought to be shared but can not due to object format
 377          limitations).  It is neccesary to keep the flag to make rest of C++ FE
 378          happy.  Clear the flag here to avoid confusion in middle-end.  */
 379       if (DECL_COMDAT (node->decl) && !TREE_PUBLIC (node->decl))
 380         DECL_COMDAT (node->decl) = 0;
 381       /* For external decls stop tracking same_comdat_group, it doesn't matter
 382          what comdat group they are in when they won't be emitted in this TU,
 383          and simplifies later passes.  */
 384       if (node->same_comdat_group && DECL_EXTERNAL (node->decl))
 385         {
 386           struct cgraph_node *n = node, *next;
 387           do
 388             {
 389               /* If at least one of same comdat group functions is external,
 390                  all of them have to be, otherwise it is a front-end bug.  */
 391               gcc_assert (DECL_EXTERNAL (n->decl));
 392               next = n->same_comdat_group;
 393               n->same_comdat_group = NULL;
 394               n = next;
 395             }
 396           while (n != node);
 397         }
 398       gcc_assert ((!DECL_WEAK (node->decl) && !DECL_COMDAT (node->decl))
 399                   || TREE_PUBLIC (node->decl) || DECL_EXTERNAL (node->decl));
 400       if (cgraph_externally_visible_p (node, whole_program))
 401         {
 402           gcc_assert (!node->global.inlined_to);
 403           node->local.externally_visible = true;
 404         }
 405       else
 406         node->local.externally_visible = false;
 407       if (!node->local.externally_visible && node->analyzed
 408           && !DECL_EXTERNAL (node->decl))
 409         {
 410           gcc_assert (whole_program || !TREE_PUBLIC (node->decl));
 411           cgraph_make_decl_local (node->decl);
 412         }
 413       node->local.local = (cgraph_only_called_directly_p (node)
 414                            && node->analyzed
 415                            && !DECL_EXTERNAL (node->decl)
 416                            && !node->local.externally_visible);
 417     }
 418   for (vnode = varpool_nodes; vnode; vnode = vnode->next)
 419     {
 420       /* weak flag makes no sense on local variables.  */
 421       gcc_assert (!DECL_WEAK (vnode->decl)
 422                   || TREE_PUBLIC (vnode->decl) || DECL_EXTERNAL (vnode->decl));
 423       /* In several cases declarations can not be common:
 424
 425          - when declaration has initializer
 426          - when it is in weak
 427          - when it has specific section
 428          - when it resides in non-generic address space.
 429          - if declaration is local, it will get into .local common section
 430            so common flag is not needed.  Frontends still produce these in
 431            certain cases, such as for:
 432
 433              static int a __attribute__ ((common))
 434
 435          Canonicalize things here and clear the redundant flag.  */
 436       if (DECL_COMMON (vnode->decl)
 437           && (!(TREE_PUBLIC (vnode->decl) || DECL_EXTERNAL (vnode->decl))
 438               || (DECL_INITIAL (vnode->decl)
 439                   && DECL_INITIAL (vnode->decl) != error_mark_node)
 440               || DECL_WEAK (vnode->decl)
 441               || DECL_SECTION_NAME (vnode->decl) != NULL
 442               || ! (ADDR_SPACE_GENERIC_P
 443                     (TYPE_ADDR_SPACE (TREE_TYPE (vnode->decl))))))
 444         DECL_COMMON (vnode->decl) = 0;
 445     }
 446   for (vnode = varpool_nodes_queue; vnode; vnode = vnode->next_needed)
 447     {
 448       if (!vnode->finalized)
 449         continue;
 450       if (vnode->needed
 451           && (DECL_COMDAT (vnode->decl) || TREE_PUBLIC (vnode->decl))
 452           && (!whole_program
 453               /* We can privatize comdat readonly variables whose address is not taken,
 454                  but doing so is not going to bring us optimization oppurtunities until
 455                  we start reordering datastructures.  */
 456               || DECL_COMDAT (vnode->decl)
 457               || DECL_WEAK (vnode->decl)
 458               || lookup_attribute ("externally_visible",
 459                                    DECL_ATTRIBUTES (vnode->decl))))
 460         vnode->externally_visible = true;
 461       else
 462         vnode->externally_visible = false;
 463       if (!vnode->externally_visible)
 464         {
 465           gcc_assert (whole_program || !TREE_PUBLIC (vnode->decl));
 466           cgraph_make_decl_local (vnode->decl);
 467         }
 468      gcc_assert (TREE_STATIC (vnode->decl));
 469     }
 470
 471   if (dump_file)
 472     {
 473       fprintf (dump_file, "\nMarking local functions:");
 474       for (node = cgraph_nodes; node; node = node->next)
 475         if (node->local.local)
 476           fprintf (dump_file, " %s", cgraph_node_name (node));
 477       fprintf (dump_file, "\n\n");
 478       fprintf (dump_file, "\nMarking externally visible functions:");
 479       for (node = cgraph_nodes; node; node = node->next)
 480         if (node->local.externally_visible)
 481           fprintf (dump_file, " %s", cgraph_node_name (node));
 482       fprintf (dump_file, "\n\n");
 483       fprintf (dump_file, "\nMarking externally visible variables:");
 484       for (vnode = varpool_nodes_queue; vnode; vnode = vnode->next_needed)
 485         if (vnode->externally_visible)
 486           fprintf (dump_file, " %s", varpool_node_name (vnode));
 487       fprintf (dump_file, "\n\n");
 488     }
 489   cgraph_function_flags_ready = true;
 490   return 0;
 491 }
 492
 493 /* Local function pass handling visibilities.  This happens before LTO streaming
 494    so in particular -fwhole-program should be ignored at this level.  */
 495
 496 static unsigned int
 497 local_function_and_variable_visibility (void)
 498 {
 499   return function_and_variable_visibility (flag_whole_program && !flag_lto && !flag_whopr);
 500 }
 501
 502 struct simple_ipa_opt_pass pass_ipa_function_and_variable_visibility =
 503 {
 504  {
 505   SIMPLE_IPA_PASS,
 506   "visibility",                         /* name */
 507   NULL,                                 /* gate */
 508   local_function_and_variable_visibility,/* execute */
 509   NULL,                                 /* sub */
 510   NULL,                                 /* next */
 511   0,                                    /* static_pass_number */
 512   TV_CGRAPHOPT,                         /* tv_id */
 513   0,                                    /* properties_required */
 514   0,                                    /* properties_provided */
 515   0,                                    /* properties_destroyed */
 516   0,                                    /* todo_flags_start */
 517   TODO_remove_functions | TODO_dump_cgraph/* todo_flags_finish */
 518  }
 519 };
 520
 521 /* Do not re-run on ltrans stage.  */
 522
 523 static bool
 524 gate_whole_program_function_and_variable_visibility (void)
 525 {
 526   return !flag_ltrans;
 527 }
 528
 529 /* Bring functionss local at LTO time whith -fwhole-program.  */
 530
 531 static unsigned int
 532 whole_program_function_and_variable_visibility (void)
 533 {
 534   struct cgraph_node *node;
 535   struct varpool_node *vnode;
 536
 537   function_and_variable_visibility (flag_whole_program);
 538
 539   for (node = cgraph_nodes; node; node = node->next)
 540     if ((node->local.externally_visible && !DECL_COMDAT (node->decl))
 541         && node->local.finalized)
 542       cgraph_mark_needed_node (node);
 543   for (vnode = varpool_nodes_queue; vnode; vnode = vnode->next_needed)
 544     if (vnode->externally_visible && !DECL_COMDAT (vnode->decl))
 545       varpool_mark_needed_node (vnode);
 546   if (dump_file)
 547     {
 548       fprintf (dump_file, "\nNeeded variables:");
 549       for (vnode = varpool_nodes_queue; vnode; vnode = vnode->next_needed)
 550         if (vnode->needed)
 551           fprintf (dump_file, " %s", varpool_node_name (vnode));
 552       fprintf (dump_file, "\n\n");
 553     }
 554   return 0;
 555 }
 556
 557 struct ipa_opt_pass_d pass_ipa_whole_program_visibility =
 558 {
 559  {
 560   IPA_PASS,
 561   "whole-program",                      /* name */
 562   gate_whole_program_function_and_variable_visibility,/* gate */
 563   whole_program_function_and_variable_visibility,/* execute */
 564   NULL,                                 /* sub */
 565   NULL,                                 /* next */
 566   0,                                    /* static_pass_number */
 567   TV_CGRAPHOPT,                         /* tv_id */
 568   0,                                    /* properties_required */
 569   0,                                    /* properties_provided */
 570   0,                                    /* properties_destroyed */
 571   0,                                    /* todo_flags_start */
 572   TODO_dump_cgraph | TODO_remove_functions/* todo_flags_finish */
 573  },
 574  NULL,                                  /* generate_summary */
 575  NULL,                                  /* write_summary */
 576  NULL,                                  /* read_summary */
 577  NULL,                                  /* function_read_summary */
 578  NULL,                                  /* stmt_fixup */
 579  0,                                     /* TODOs */
 580  NULL,                                  /* function_transform */
 581  NULL,                                  /* variable_transform */
 582 };
 583
 584 /* Hash a cgraph node set element.  */
 585
 586 static hashval_t
 587 hash_cgraph_node_set_element (const void *p)
 588 {
 589   const_cgraph_node_set_element element = (const_cgraph_node_set_element) p;
 590   return htab_hash_pointer (element->node);
 591 }
 592
 593 /* Compare two cgraph node set elements.  */
 594
 595 static int
 596 eq_cgraph_node_set_element (const void *p1, const void *p2)
 597 {
 598   const_cgraph_node_set_element e1 = (const_cgraph_node_set_element) p1;
 599   const_cgraph_node_set_element e2 = (const_cgraph_node_set_element) p2;
 600
 601   return e1->node == e2->node;
 602 }
 603
 604 /* Create a new cgraph node set.  */
 605
 606 cgraph_node_set
 607 cgraph_node_set_new (void)
 608 {
 609   cgraph_node_set new_node_set;
 610
 611   new_node_set = GGC_NEW (struct cgraph_node_set_def);
 612   new_node_set->hashtab = htab_create_ggc (10,
 613                                            hash_cgraph_node_set_element,
 614                                            eq_cgraph_node_set_element,
 615                                            NULL);
 616   new_node_set->nodes = NULL;
 617   return new_node_set;
 618 }
 619
 620 /* Add cgraph_node NODE to cgraph_node_set SET.  */
 621
 622 void
 623 cgraph_node_set_add (cgraph_node_set set, struct cgraph_node *node)
 624 {
 625   void **slot;
 626   cgraph_node_set_element element;
 627   struct cgraph_node_set_element_def dummy;
 628
 629   dummy.node = node;
 630   slot = htab_find_slot (set->hashtab, &dummy, INSERT);
 631
 632   if (*slot != HTAB_EMPTY_ENTRY)
 633     {
 634       element = (cgraph_node_set_element) *slot;
 635       gcc_assert (node == element->node
 636                   && (VEC_index (cgraph_node_ptr, set->nodes, element->index)
 637                       == node));
 638       return;
 639     }
 640
 641   /* Insert node into hash table.  */
 642   element =
 643     (cgraph_node_set_element) GGC_NEW (struct cgraph_node_set_element_def);
 644   element->node = node;
 645   element->index = VEC_length (cgraph_node_ptr, set->nodes);
 646   *slot = element;
 647
 648   /* Insert into node vector.  */
 649   VEC_safe_push (cgraph_node_ptr, gc, set->nodes, node);
 650 }
 651
 652 /* Remove cgraph_node NODE from cgraph_node_set SET.  */
 653
 654 void
 655 cgraph_node_set_remove (cgraph_node_set set, struct cgraph_node *node)
 656 {
 657   void **slot, **last_slot;
 658   cgraph_node_set_element element, last_element;
 659   struct cgraph_node *last_node;
 660   struct cgraph_node_set_element_def dummy;
 661
 662   dummy.node = node;
 663   slot = htab_find_slot (set->hashtab, &dummy, NO_INSERT);
 664   if (slot == NULL)
 665     return;
 666
 667   element = (cgraph_node_set_element) *slot;
 668   gcc_assert (VEC_index (cgraph_node_ptr, set->nodes, element->index)
 669               == node);
 670
 671   /* Remove from vector. We do this by swapping node with the last element
 672      of the vector.  */
 673   last_node = VEC_pop (cgraph_node_ptr, set->nodes);
 674   if (last_node != node)
 675     {
 676       dummy.node = last_node;
 677       last_slot = htab_find_slot (set->hashtab, &dummy, NO_INSERT);
 678       last_element = (cgraph_node_set_element) *last_slot;
 679       gcc_assert (last_element);
 680
 681       /* Move the last element to the original spot of NODE.  */
 682       last_element->index = element->index;
 683       VEC_replace (cgraph_node_ptr, set->nodes, last_element->index,
 684                    last_node);
 685     }
 686
 687   /* Remove element from hash table.  */
 688   htab_clear_slot (set->hashtab, slot);
 689   ggc_free (element);
 690 }
 691
 692 /* Find NODE in SET and return an iterator to it if found.  A null iterator
 693    is returned if NODE is not in SET.  */
 694
 695 cgraph_node_set_iterator
 696 cgraph_node_set_find (cgraph_node_set set, struct cgraph_node *node)
 697 {
 698   void **slot;
 699   struct cgraph_node_set_element_def dummy;
 700   cgraph_node_set_element element;
 701   cgraph_node_set_iterator csi;
 702
 703   dummy.node = node;
 704   slot = htab_find_slot (set->hashtab, &dummy, NO_INSERT);
 705   if (slot == NULL)
 706     csi.index = (unsigned) ~0;
 707   else
 708     {
 709       element = (cgraph_node_set_element) *slot;
 710       gcc_assert (VEC_index (cgraph_node_ptr, set->nodes, element->index)
 711                   == node);
 712       csi.index = element->index;
 713     }
 714   csi.set = set;
 715
 716   return csi;
 717 }
 718
 719 /* Dump content of SET to file F.  */
 720
 721 void
 722 dump_cgraph_node_set (FILE *f, cgraph_node_set set)
 723 {
 724   cgraph_node_set_iterator iter;
 725
 726   for (iter = csi_start (set); !csi_end_p (iter); csi_next (&iter))
 727     {
 728       struct cgraph_node *node = csi_node (iter);
 729       dump_cgraph_node (f, node);
 730     }
 731 }
 732
 733 /* Dump content of SET to stderr.  */
 734
 735 void
 736 debug_cgraph_node_set (cgraph_node_set set)
 737 {
 738   dump_cgraph_node_set (stderr, set);
 739 }
 740