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