OSDN Git Service

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