OSDN Git Service

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