OSDN Git Service

* cgraph.c (cgraph_release_function_body): Update use of
[pf3gnuchains/gcc-fork.git] / gcc / ipa.c
1 /* Basic IPA optimizations and utilities.
2    Copyright (C) 2003, 2004, 2005, 2007, 2008 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       while (node->clone_of && !node->clone_of->aux && !gimple_has_body_p (node->decl))
183         {
184           node = node->clone_of;
185           node->aux = first;
186           first = node;
187         }
188     }
189
190   /* Remove unreachable nodes.  Extern inline functions need special care;
191      Unreachable extern inline functions shall be removed.
192      Reachable extern inline functions we never inlined shall get their bodies
193      eliminated.
194      Reachable extern inline functions we sometimes inlined will be turned into
195      unanalyzed nodes so they look like for true extern functions to the rest
196      of code.  Body of such functions is released via remove_node once the
197      inline clones are eliminated.  */
198   for (node = cgraph_nodes; node; node = next)
199     {
200       next = node->next;
201       if (node->aux && !node->reachable)
202         {
203           cgraph_node_remove_callees (node);
204           node->analyzed = false;
205           node->local.inlinable = false;
206         }
207       if (!node->aux)
208         {
209           node->global.inlined_to = NULL;
210           if (file)
211             fprintf (file, " %s", cgraph_node_name (node));
212           if (!node->analyzed || !DECL_EXTERNAL (node->decl) || before_inlining_p)
213             cgraph_remove_node (node);
214           else
215             {
216               struct cgraph_edge *e;
217
218               /* See if there is reachable caller.  */
219               for (e = node->callers; e; e = e->next_caller)
220                 if (e->caller->aux)
221                   break;
222
223               /* If so, we need to keep node in the callgraph.  */
224               if (e || node->needed)
225                 {
226                   struct cgraph_node *clone;
227
228                   /* If there are still clones, we must keep body around.
229                      Otherwise we can just remove the body but keep the clone.  */
230                   for (clone = node->clones; clone;
231                        clone = clone->next_sibling_clone)
232                     if (clone->aux)
233                       break;
234                   if (!clone)
235                     {
236                       cgraph_release_function_body (node);
237                       cgraph_node_remove_callees (node);
238                       node->analyzed = false;
239                       node->local.inlinable = false;
240                     }
241                   if (node->prev_sibling_clone)
242                     node->prev_sibling_clone->next_sibling_clone = node->next_sibling_clone;
243                   else if (node->clone_of)
244                     node->clone_of->clones = node->next_sibling_clone;
245                   if (node->next_sibling_clone)
246                     node->next_sibling_clone->prev_sibling_clone = node->prev_sibling_clone;
247                 }
248               else
249                 cgraph_remove_node (node);
250             }
251           changed = true;
252         }
253     }
254   for (node = cgraph_nodes; node; node = node->next)
255     {
256       /* Inline clones might be kept around so their materializing allows further
257          cloning.  If the function the clone is inlined into is removed, we need
258          to turn it into normal cone.  */
259       if (node->global.inlined_to
260           && !node->callers)
261         {
262           gcc_assert (node->clones);
263           node->global.inlined_to = NULL;
264           update_inlined_to_pointer (node, node);
265         }
266       node->aux = NULL;
267     }
268 #ifdef ENABLE_CHECKING
269   verify_cgraph ();
270 #endif
271
272   /* Reclaim alias pairs for functions that have disappeared from the
273      call graph.  */
274   remove_unreachable_alias_pairs ();
275
276   return changed;
277 }
278
279 static bool
280 cgraph_externally_visible_p (struct cgraph_node *node, bool whole_program)
281 {
282   if (!node->local.finalized)
283     return false;
284   if (!DECL_COMDAT (node->decl)
285       && (!TREE_PUBLIC (node->decl) || DECL_EXTERNAL (node->decl)))
286     return false;
287   if (!whole_program)
288     return true;
289   /* COMDAT functions must be shared only if they have address taken,
290      otherwise we can produce our own private implementation with
291      -fwhole-program.  */
292   if (DECL_COMDAT (node->decl) && (node->address_taken || !node->analyzed))
293     return true;
294   if (MAIN_NAME_P (DECL_NAME (node->decl)))
295     return true;
296   if (lookup_attribute ("externally_visible", DECL_ATTRIBUTES (node->decl)))
297     return true;
298   return false;
299 }
300
301 /* Mark visibility of all functions.
302
303    A local function is one whose calls can occur only in the current
304    compilation unit and all its calls are explicit, so we can change
305    its calling convention.  We simply mark all static functions whose
306    address is not taken as local.
307
308    We also change the TREE_PUBLIC flag of all declarations that are public
309    in language point of view but we want to overwrite this default
310    via visibilities for the backend point of view.  */
311
312 static unsigned int
313 function_and_variable_visibility (bool whole_program)
314 {
315   struct cgraph_node *node;
316   struct varpool_node *vnode;
317
318   for (node = cgraph_nodes; node; node = node->next)
319     {
320       /* C++ FE on lack of COMDAT support create local COMDAT functions
321          (that ought to be shared but can not due to object format
322          limitations).  It is neccesary to keep the flag to make rest of C++ FE
323          happy.  Clear the flag here to avoid confusion in middle-end.  */
324       if (DECL_COMDAT (node->decl) && !TREE_PUBLIC (node->decl))
325         DECL_COMDAT (node->decl) = 0;
326       gcc_assert ((!DECL_WEAK (node->decl) && !DECL_COMDAT (node->decl))
327                   || TREE_PUBLIC (node->decl) || DECL_EXTERNAL (node->decl));
328       if (cgraph_externally_visible_p (node, whole_program))
329         {
330           gcc_assert (!node->global.inlined_to);
331           node->local.externally_visible = true;
332         }
333       else
334         node->local.externally_visible = false;
335       if (!node->local.externally_visible && node->analyzed
336           && !DECL_EXTERNAL (node->decl))
337         {
338           gcc_assert (whole_program || !TREE_PUBLIC (node->decl));
339           TREE_PUBLIC (node->decl) = 0;
340           DECL_COMDAT (node->decl) = 0;
341           DECL_WEAK (node->decl) = 0;
342         }
343       node->local.local = (cgraph_only_called_directly_p (node)
344                            && node->analyzed
345                            && !DECL_EXTERNAL (node->decl)
346                            && !node->local.externally_visible);
347     }
348   for (vnode = varpool_nodes_queue; vnode; vnode = vnode->next_needed)
349     {
350       if (!vnode->finalized)
351         continue;
352       gcc_assert ((!DECL_WEAK (vnode->decl) && !DECL_COMMON (vnode->decl))
353                   || TREE_PUBLIC (vnode->decl) || DECL_EXTERNAL (vnode->decl));
354       if (vnode->needed
355           && (DECL_COMDAT (vnode->decl) || TREE_PUBLIC (vnode->decl))
356           && (!whole_program
357               /* We can privatize comdat readonly variables whose address is not taken,
358                  but doing so is not going to bring us optimization oppurtunities until
359                  we start reordering datastructures.  */
360               || DECL_COMDAT (vnode->decl)
361               || DECL_WEAK (vnode->decl)
362               || lookup_attribute ("externally_visible",
363                                    DECL_ATTRIBUTES (vnode->decl))))
364         vnode->externally_visible = true;
365       else
366         vnode->externally_visible = false;
367       if (!vnode->externally_visible)
368         {
369           gcc_assert (whole_program || !TREE_PUBLIC (vnode->decl));
370           TREE_PUBLIC (vnode->decl) = 0;
371           DECL_COMMON (vnode->decl) = 0;
372         }
373      gcc_assert (TREE_STATIC (vnode->decl));
374     }
375
376   if (dump_file)
377     {
378       fprintf (dump_file, "\nMarking local functions:");
379       for (node = cgraph_nodes; node; node = node->next)
380         if (node->local.local)
381           fprintf (dump_file, " %s", cgraph_node_name (node));
382       fprintf (dump_file, "\n\n");
383       fprintf (dump_file, "\nMarking externally visible functions:");
384       for (node = cgraph_nodes; node; node = node->next)
385         if (node->local.externally_visible)
386           fprintf (dump_file, " %s", cgraph_node_name (node));
387       fprintf (dump_file, "\n\n");
388       fprintf (dump_file, "\nMarking externally visible variables:");
389       for (vnode = varpool_nodes_queue; vnode; vnode = vnode->next_needed)
390         if (vnode->externally_visible)
391           fprintf (dump_file, " %s", varpool_node_name (vnode));
392       fprintf (dump_file, "\n\n");
393     }
394   cgraph_function_flags_ready = true;
395   return 0;
396 }
397
398 /* Local function pass handling visibilities.  This happens before LTO streaming
399    so in particular -fwhole-program should be ignored at this level.  */
400
401 static unsigned int
402 local_function_and_variable_visibility (void)
403 {
404   return function_and_variable_visibility (flag_whole_program && !flag_lto && !flag_whopr);
405 }
406
407 struct simple_ipa_opt_pass pass_ipa_function_and_variable_visibility = 
408 {
409  {
410   SIMPLE_IPA_PASS,
411   "visibility",                         /* name */
412   NULL,                                 /* gate */
413   local_function_and_variable_visibility,/* execute */
414   NULL,                                 /* sub */
415   NULL,                                 /* next */
416   0,                                    /* static_pass_number */
417   TV_CGRAPHOPT,                         /* tv_id */
418   0,                                    /* properties_required */
419   0,                                    /* properties_provided */
420   0,                                    /* properties_destroyed */
421   0,                                    /* todo_flags_start */
422   TODO_remove_functions | TODO_dump_cgraph/* todo_flags_finish */
423  }
424 };
425
426 /* Do not re-run on ltrans stage.  */
427
428 static bool
429 gate_whole_program_function_and_variable_visibility (void)
430 {
431   return !flag_ltrans;
432 }
433
434 /* Bring functionss local at LTO time whith -fwhole-program.  */
435
436 static unsigned int
437 whole_program_function_and_variable_visibility (void)
438 {
439   struct cgraph_node *node;
440   struct varpool_node *vnode;
441
442   function_and_variable_visibility (flag_whole_program);
443
444   for (node = cgraph_nodes; node; node = node->next)
445     if ((node->local.externally_visible && !DECL_COMDAT (node->decl))
446         && node->local.finalized)
447       cgraph_mark_needed_node (node);
448   for (vnode = varpool_nodes_queue; vnode; vnode = vnode->next_needed)
449     if (vnode->externally_visible && !DECL_COMDAT (vnode->decl))
450       varpool_mark_needed_node (vnode);
451   if (dump_file)
452     {
453       fprintf (dump_file, "\nNeeded variables:");
454       for (vnode = varpool_nodes_queue; vnode; vnode = vnode->next_needed)
455         if (vnode->needed)
456           fprintf (dump_file, " %s", varpool_node_name (vnode));
457       fprintf (dump_file, "\n\n");
458     }
459   return 0;
460 }
461
462 struct ipa_opt_pass_d pass_ipa_whole_program_visibility =
463 {
464  {
465   IPA_PASS,
466   "whole-program",                      /* name */
467   gate_whole_program_function_and_variable_visibility,/* gate */
468   whole_program_function_and_variable_visibility,/* execute */
469   NULL,                                 /* sub */
470   NULL,                                 /* next */
471   0,                                    /* static_pass_number */
472   TV_CGRAPHOPT,                         /* tv_id */
473   0,                                    /* properties_required */
474   0,                                    /* properties_provided */
475   0,                                    /* properties_destroyed */
476   0,                                    /* todo_flags_start */
477   TODO_dump_cgraph | TODO_remove_functions/* todo_flags_finish */
478  },
479  NULL,                                  /* generate_summary */
480  NULL,                                  /* write_summary */
481  NULL,                                  /* read_summary */
482  NULL,                                  /* function_read_summary */
483  NULL,                                  /* stmt_fixup */
484  0,                                     /* TODOs */
485  NULL,                                  /* function_transform */
486  NULL,                                  /* variable_transform */
487 };
488
489 /* Hash a cgraph node set element.  */
490
491 static hashval_t
492 hash_cgraph_node_set_element (const void *p)
493 {
494   const_cgraph_node_set_element element = (const_cgraph_node_set_element) p;
495   return htab_hash_pointer (element->node);
496 }
497
498 /* Compare two cgraph node set elements.  */
499
500 static int
501 eq_cgraph_node_set_element (const void *p1, const void *p2)
502 {
503   const_cgraph_node_set_element e1 = (const_cgraph_node_set_element) p1;
504   const_cgraph_node_set_element e2 = (const_cgraph_node_set_element) p2;
505
506   return e1->node == e2->node;
507 }
508
509 /* Create a new cgraph node set.  */
510
511 cgraph_node_set
512 cgraph_node_set_new (void)
513 {
514   cgraph_node_set new_node_set;
515
516   new_node_set = GGC_NEW (struct cgraph_node_set_def);
517   new_node_set->hashtab = htab_create_ggc (10,
518                                            hash_cgraph_node_set_element,
519                                            eq_cgraph_node_set_element,
520                                            NULL);
521   new_node_set->nodes = NULL;
522   return new_node_set;
523 }
524
525 /* Add cgraph_node NODE to cgraph_node_set SET.  */
526
527 void
528 cgraph_node_set_add (cgraph_node_set set, struct cgraph_node *node)
529 {
530   void **slot;
531   cgraph_node_set_element element;
532   struct cgraph_node_set_element_def dummy;
533
534   dummy.node = node;
535   slot = htab_find_slot (set->hashtab, &dummy, INSERT);
536
537   if (*slot != HTAB_EMPTY_ENTRY)
538     {
539       element = (cgraph_node_set_element) *slot;
540       gcc_assert (node == element->node
541                   && (VEC_index (cgraph_node_ptr, set->nodes, element->index)
542                       == node));
543       return;
544     }
545
546   /* Insert node into hash table.  */
547   element =
548     (cgraph_node_set_element) GGC_NEW (struct cgraph_node_set_element_def);
549   element->node = node;
550   element->index = VEC_length (cgraph_node_ptr, set->nodes);
551   *slot = element;
552
553   /* Insert into node vector.  */
554   VEC_safe_push (cgraph_node_ptr, gc, set->nodes, node);
555 }
556
557 /* Remove cgraph_node NODE from cgraph_node_set SET.  */
558
559 void
560 cgraph_node_set_remove (cgraph_node_set set, struct cgraph_node *node)
561 {
562   void **slot, **last_slot;
563   cgraph_node_set_element element, last_element;
564   struct cgraph_node *last_node;
565   struct cgraph_node_set_element_def dummy;
566
567   dummy.node = node;
568   slot = htab_find_slot (set->hashtab, &dummy, NO_INSERT);
569   if (slot == NULL)
570     return;
571
572   element = (cgraph_node_set_element) *slot;
573   gcc_assert (VEC_index (cgraph_node_ptr, set->nodes, element->index)
574               == node);
575
576   /* Remove from vector. We do this by swapping node with the last element
577      of the vector.  */
578   last_node = VEC_pop (cgraph_node_ptr, set->nodes);
579   if (last_node != node)
580     {
581       dummy.node = last_node;
582       last_slot = htab_find_slot (set->hashtab, &dummy, NO_INSERT);
583       last_element = (cgraph_node_set_element) *last_slot;
584       gcc_assert (last_element);
585
586       /* Move the last element to the original spot of NODE.  */
587       last_element->index = element->index;
588       VEC_replace (cgraph_node_ptr, set->nodes, last_element->index,
589                    last_node);
590     }
591   
592   /* Remove element from hash table.  */
593   htab_clear_slot (set->hashtab, slot);
594   ggc_free (element);
595 }
596
597 /* Find NODE in SET and return an iterator to it if found.  A null iterator
598    is returned if NODE is not in SET.  */
599
600 cgraph_node_set_iterator
601 cgraph_node_set_find (cgraph_node_set set, struct cgraph_node *node)
602 {
603   void **slot;
604   struct cgraph_node_set_element_def dummy;
605   cgraph_node_set_element element;
606   cgraph_node_set_iterator csi;
607
608   dummy.node = node;
609   slot = htab_find_slot (set->hashtab, &dummy, NO_INSERT);
610   if (slot == NULL)
611     csi.index = (unsigned) ~0;
612   else
613     {
614       element = (cgraph_node_set_element) *slot;
615       gcc_assert (VEC_index (cgraph_node_ptr, set->nodes, element->index)
616                   == node);
617       csi.index = element->index;
618     }
619   csi.set = set;
620
621   return csi;
622 }
623
624 /* Dump content of SET to file F.  */
625
626 void
627 dump_cgraph_node_set (FILE *f, cgraph_node_set set)
628 {
629   cgraph_node_set_iterator iter;
630
631   for (iter = csi_start (set); !csi_end_p (iter); csi_next (&iter))
632     {
633       struct cgraph_node *node = csi_node (iter);
634       dump_cgraph_node (f, node);
635     }
636 }
637
638 /* Dump content of SET to stderr.  */
639
640 void
641 debug_cgraph_node_set (cgraph_node_set set)
642 {
643   dump_cgraph_node_set (stderr, set);
644 }
645