OSDN Git Service

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