OSDN Git Service

8295357cc0e50c06d478f170ddcb12e622621427
[pf3gnuchains/gcc-fork.git] / 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/* todo_flags_finish */
541  }
542 };
543
544 /* Do not re-run on ltrans stage.  */
545
546 static bool
547 gate_whole_program_function_and_variable_visibility (void)
548 {
549   return !flag_ltrans;
550 }
551
552 /* Bring functionss local at LTO time whith -fwhole-program.  */
553
554 static unsigned int
555 whole_program_function_and_variable_visibility (void)
556 {
557   struct cgraph_node *node;
558   struct varpool_node *vnode;
559
560   function_and_variable_visibility (flag_whole_program);
561
562   for (node = cgraph_nodes; node; node = node->next)
563     if ((node->local.externally_visible && !DECL_COMDAT (node->decl))
564         && node->local.finalized)
565       cgraph_mark_needed_node (node);
566   for (vnode = varpool_nodes_queue; vnode; vnode = vnode->next_needed)
567     if (vnode->externally_visible && !DECL_COMDAT (vnode->decl))
568       varpool_mark_needed_node (vnode);
569   if (dump_file)
570     {
571       fprintf (dump_file, "\nNeeded variables:");
572       for (vnode = varpool_nodes_queue; vnode; vnode = vnode->next_needed)
573         if (vnode->needed)
574           fprintf (dump_file, " %s", varpool_node_name (vnode));
575       fprintf (dump_file, "\n\n");
576     }
577   return 0;
578 }
579
580 struct ipa_opt_pass_d pass_ipa_whole_program_visibility =
581 {
582  {
583   IPA_PASS,
584   "whole-program",                      /* name */
585   gate_whole_program_function_and_variable_visibility,/* gate */
586   whole_program_function_and_variable_visibility,/* execute */
587   NULL,                                 /* sub */
588   NULL,                                 /* next */
589   0,                                    /* static_pass_number */
590   TV_CGRAPHOPT,                         /* tv_id */
591   0,                                    /* properties_required */
592   0,                                    /* properties_provided */
593   0,                                    /* properties_destroyed */
594   0,                                    /* todo_flags_start */
595   TODO_dump_cgraph | TODO_remove_functions/* todo_flags_finish */
596  },
597  NULL,                                  /* generate_summary */
598  NULL,                                  /* write_summary */
599  NULL,                                  /* read_summary */
600  NULL,                                  /* write_optimization_summary */
601  NULL,                                  /* read_optimization_summary */
602  NULL,                                  /* stmt_fixup */
603  0,                                     /* TODOs */
604  NULL,                                  /* function_transform */
605  NULL,                                  /* variable_transform */
606 };
607
608 /* Hash a cgraph node set element.  */
609
610 static hashval_t
611 hash_cgraph_node_set_element (const void *p)
612 {
613   const_cgraph_node_set_element element = (const_cgraph_node_set_element) p;
614   return htab_hash_pointer (element->node);
615 }
616
617 /* Compare two cgraph node set elements.  */
618
619 static int
620 eq_cgraph_node_set_element (const void *p1, const void *p2)
621 {
622   const_cgraph_node_set_element e1 = (const_cgraph_node_set_element) p1;
623   const_cgraph_node_set_element e2 = (const_cgraph_node_set_element) p2;
624
625   return e1->node == e2->node;
626 }
627
628 /* Create a new cgraph node set.  */
629
630 cgraph_node_set
631 cgraph_node_set_new (void)
632 {
633   cgraph_node_set new_node_set;
634
635   new_node_set = GGC_NEW (struct cgraph_node_set_def);
636   new_node_set->hashtab = htab_create_ggc (10,
637                                            hash_cgraph_node_set_element,
638                                            eq_cgraph_node_set_element,
639                                            NULL);
640   new_node_set->nodes = NULL;
641   return new_node_set;
642 }
643
644 /* Add cgraph_node NODE to cgraph_node_set SET.  */
645
646 void
647 cgraph_node_set_add (cgraph_node_set set, struct cgraph_node *node)
648 {
649   void **slot;
650   cgraph_node_set_element element;
651   struct cgraph_node_set_element_def dummy;
652
653   dummy.node = node;
654   slot = htab_find_slot (set->hashtab, &dummy, INSERT);
655
656   if (*slot != HTAB_EMPTY_ENTRY)
657     {
658       element = (cgraph_node_set_element) *slot;
659       gcc_assert (node == element->node
660                   && (VEC_index (cgraph_node_ptr, set->nodes, element->index)
661                       == node));
662       return;
663     }
664
665   /* Insert node into hash table.  */
666   element =
667     (cgraph_node_set_element) GGC_NEW (struct cgraph_node_set_element_def);
668   element->node = node;
669   element->index = VEC_length (cgraph_node_ptr, set->nodes);
670   *slot = element;
671
672   /* Insert into node vector.  */
673   VEC_safe_push (cgraph_node_ptr, gc, set->nodes, node);
674 }
675
676 /* Remove cgraph_node NODE from cgraph_node_set SET.  */
677
678 void
679 cgraph_node_set_remove (cgraph_node_set set, struct cgraph_node *node)
680 {
681   void **slot, **last_slot;
682   cgraph_node_set_element element, last_element;
683   struct cgraph_node *last_node;
684   struct cgraph_node_set_element_def dummy;
685
686   dummy.node = node;
687   slot = htab_find_slot (set->hashtab, &dummy, NO_INSERT);
688   if (slot == NULL)
689     return;
690
691   element = (cgraph_node_set_element) *slot;
692   gcc_assert (VEC_index (cgraph_node_ptr, set->nodes, element->index)
693               == node);
694
695   /* Remove from vector. We do this by swapping node with the last element
696      of the vector.  */
697   last_node = VEC_pop (cgraph_node_ptr, set->nodes);
698   if (last_node != node)
699     {
700       dummy.node = last_node;
701       last_slot = htab_find_slot (set->hashtab, &dummy, NO_INSERT);
702       last_element = (cgraph_node_set_element) *last_slot;
703       gcc_assert (last_element);
704
705       /* Move the last element to the original spot of NODE.  */
706       last_element->index = element->index;
707       VEC_replace (cgraph_node_ptr, set->nodes, last_element->index,
708                    last_node);
709     }
710
711   /* Remove element from hash table.  */
712   htab_clear_slot (set->hashtab, slot);
713   ggc_free (element);
714 }
715
716 /* Find NODE in SET and return an iterator to it if found.  A null iterator
717    is returned if NODE is not in SET.  */
718
719 cgraph_node_set_iterator
720 cgraph_node_set_find (cgraph_node_set set, struct cgraph_node *node)
721 {
722   void **slot;
723   struct cgraph_node_set_element_def dummy;
724   cgraph_node_set_element element;
725   cgraph_node_set_iterator csi;
726
727   dummy.node = node;
728   slot = htab_find_slot (set->hashtab, &dummy, NO_INSERT);
729   if (slot == NULL)
730     csi.index = (unsigned) ~0;
731   else
732     {
733       element = (cgraph_node_set_element) *slot;
734       gcc_assert (VEC_index (cgraph_node_ptr, set->nodes, element->index)
735                   == node);
736       csi.index = element->index;
737     }
738   csi.set = set;
739
740   return csi;
741 }
742
743 /* Dump content of SET to file F.  */
744
745 void
746 dump_cgraph_node_set (FILE *f, cgraph_node_set set)
747 {
748   cgraph_node_set_iterator iter;
749
750   for (iter = csi_start (set); !csi_end_p (iter); csi_next (&iter))
751     {
752       struct cgraph_node *node = csi_node (iter);
753       dump_cgraph_node (f, node);
754     }
755 }
756
757 /* Dump content of SET to stderr.  */
758
759 void
760 debug_cgraph_node_set (cgraph_node_set set)
761 {
762   dump_cgraph_node_set (stderr, set);
763 }
764