OSDN Git Service

76d8f724bcb6ada3904a1f332908a714561268e9
[pf3gnuchains/gcc-fork.git] / gcc / varpool.c
1 /* Callgraph handling code.
2    Copyright (C) 2003, 2004, 2005, 2006, 2007, 2008, 2010
3    Free Software Foundation, Inc.
4    Contributed by Jan Hubicka
5
6 This file is part of GCC.
7
8 GCC is free software; you can redistribute it and/or modify it under
9 the terms of the GNU General Public License as published by the Free
10 Software Foundation; either version 3, or (at your option) any later
11 version.
12
13 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
14 WARRANTY; without even the implied warranty of MERCHANTABILITY or
15 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
16 for more details.
17
18 You should have received a copy of the GNU General Public License
19 along with GCC; see the file COPYING3.  If not see
20 <http://www.gnu.org/licenses/>.  */
21
22 #include "config.h"
23 #include "system.h"
24 #include "coretypes.h"
25 #include "tm.h"
26 #include "tree.h"
27 #include "cgraph.h"
28 #include "langhooks.h"
29 #include "diagnostic.h"
30 #include "hashtab.h"
31 #include "ggc.h"
32 #include "timevar.h"
33 #include "debug.h"
34 #include "target.h"
35 #include "output.h"
36 #include "gimple.h"
37 #include "tree-flow.h"
38 #include "flags.h"
39
40 /*  This file contains basic routines manipulating variable pool.
41
42     Varpool acts as interface in between the front-end and middle-end
43     and drives the decision process on what variables and when are
44     going to be compiled.
45
46     The varpool nodes are allocated lazily for declarations
47     either by frontend or at callgraph construction time.
48     All variables supposed to be output into final file needs to be
49     explicitly marked by frontend via VARPOOL_FINALIZE_DECL function.  */
50
51 /* Hash table used to convert declarations into nodes.  */
52 static GTY((param_is (struct varpool_node))) htab_t varpool_hash;
53
54 /* The linked list of cgraph varpool nodes.
55    Linked via node->next pointer.  */
56 struct varpool_node *varpool_nodes;
57
58 /* Queue of cgraph nodes scheduled to be lowered and output.
59    The queue is maintained via mark_needed_node, linked via node->next_needed
60    pointer.
61
62    LAST_NEEDED_NODE points to the end of queue, so it can be
63    maintained in forward order.  GTY is needed to make it friendly to
64    PCH.
65
66    During compilation we construct the queue of needed variables
67    twice: first time it is during cgraph construction, second time it is at the
68    end of compilation in VARPOOL_REMOVE_UNREFERENCED_DECLS so we can avoid
69    optimized out variables being output.
70
71    Each variable is thus first analyzed and then later possibly output.
72    FIRST_UNANALYZED_NODE points to first node in queue that was not analyzed
73    yet and is moved via VARPOOL_ANALYZE_PENDING_DECLS.  */
74
75 struct varpool_node *varpool_nodes_queue;
76 static GTY(()) struct varpool_node *varpool_last_needed_node;
77 static GTY(()) struct varpool_node *varpool_first_unanalyzed_node;
78
79 /* Lists all assembled variables to be sent to debugger output later on.  */
80 static GTY(()) struct varpool_node *varpool_assembled_nodes_queue;
81
82 /* Return name of the node used in debug output.  */
83 const char *
84 varpool_node_name (struct varpool_node *node)
85 {
86   return lang_hooks.decl_printable_name (node->decl, 2);
87 }
88
89 /* Returns a hash code for P.  */
90 static hashval_t
91 hash_varpool_node (const void *p)
92 {
93   const struct varpool_node *n = (const struct varpool_node *) p;
94   return (hashval_t) DECL_UID (n->decl);
95 }
96
97 /* Returns nonzero if P1 and P2 are equal.  */
98 static int
99 eq_varpool_node (const void *p1, const void *p2)
100 {
101   const struct varpool_node *n1 =
102     (const struct varpool_node *) p1;
103   const struct varpool_node *n2 =
104     (const struct varpool_node *) p2;
105   return DECL_UID (n1->decl) == DECL_UID (n2->decl);
106 }
107
108 /* Return varpool node assigned to DECL without creating new one.  */
109 struct varpool_node *
110 varpool_get_node (tree decl)
111 {
112   struct varpool_node key, **slot;
113
114   gcc_assert (DECL_P (decl) && TREE_CODE (decl) != FUNCTION_DECL);
115
116   if (!varpool_hash)
117     return NULL;
118   key.decl = decl;
119   slot = (struct varpool_node **)
120     htab_find_slot (varpool_hash, &key, INSERT);
121   return *slot;
122 }
123
124 /* Return varpool node assigned to DECL.  Create new one when needed.  */
125 struct varpool_node *
126 varpool_node (tree decl)
127 {
128   struct varpool_node key, *node, **slot;
129
130   gcc_assert (DECL_P (decl) && TREE_CODE (decl) != FUNCTION_DECL);
131
132   if (!varpool_hash)
133     varpool_hash = htab_create_ggc (10, hash_varpool_node,
134                                            eq_varpool_node, NULL);
135   key.decl = decl;
136   slot = (struct varpool_node **)
137     htab_find_slot (varpool_hash, &key, INSERT);
138   if (*slot)
139     return *slot;
140   node = GGC_CNEW (struct varpool_node);
141   node->decl = decl;
142   node->order = cgraph_order++;
143   node->next = varpool_nodes;
144   if (varpool_nodes)
145     varpool_nodes->prev = node;
146   varpool_nodes = node;
147   *slot = node;
148   return node;
149 }
150
151 /* Remove node from the varpool.  */
152 void
153 varpool_remove_node (struct varpool_node *node)
154 {
155   void **slot;
156   slot = htab_find_slot (varpool_hash, node, NO_INSERT);
157   gcc_assert (*slot == node);
158   htab_clear_slot (varpool_hash, slot);
159   gcc_assert (!varpool_assembled_nodes_queue);
160   if (!node->alias)
161     while (node->extra_name)
162       varpool_remove_node (node->extra_name);
163   if (node->next)
164     node->next->prev = node->prev;
165   if (node->prev)
166     node->prev->next = node->next;
167   else
168     {
169       if (node->alias)
170         {
171           gcc_assert (node->extra_name->extra_name == node);
172           node->extra_name->extra_name = node->next;
173         }
174       else
175         {
176           gcc_assert (varpool_nodes == node);
177           varpool_nodes = node->next;
178         }
179     }
180   if (varpool_first_unanalyzed_node == node)
181     varpool_first_unanalyzed_node = node->next_needed;
182   if (node->next_needed)
183     node->next_needed->prev_needed = node->prev_needed;
184   else if (node->prev_needed)
185     {
186       gcc_assert (varpool_last_needed_node);
187       varpool_last_needed_node = node->prev_needed;
188     }
189   if (node->prev_needed)
190     node->prev_needed->next_needed = node->next_needed;
191   else if (node->next_needed)
192     {
193       gcc_assert (varpool_nodes_queue == node);
194       varpool_nodes_queue = node->next_needed;
195     }
196   if (DECL_INITIAL (node->decl))
197     DECL_INITIAL (node->decl) = error_mark_node;
198   ggc_free (node);
199 }
200
201 /* Dump given cgraph node.  */
202 void
203 dump_varpool_node (FILE *f, struct varpool_node *node)
204 {
205   fprintf (f, "%s:", varpool_node_name (node));
206   fprintf (f, " availability:%s",
207            cgraph_function_flags_ready
208            ? cgraph_availability_names[cgraph_variable_initializer_availability (node)]
209            : "not-ready");
210   if (DECL_ASSEMBLER_NAME_SET_P (node->decl))
211     fprintf (f, " (asm: %s)", IDENTIFIER_POINTER (DECL_ASSEMBLER_NAME (node->decl)));
212   if (DECL_INITIAL (node->decl))
213     fprintf (f, " initialized");
214   if (TREE_ASM_WRITTEN (node->decl))
215     fprintf (f, " (asm written)");
216   if (node->needed)
217     fprintf (f, " needed");
218   if (node->analyzed)
219     fprintf (f, " analyzed");
220   if (node->finalized)
221     fprintf (f, " finalized");
222   if (node->output)
223     fprintf (f, " output");
224   if (node->externally_visible)
225     fprintf (f, " externally_visible");
226   if (node->in_other_partition)
227     fprintf (f, " in_other_partition");
228   else if (node->used_from_other_partition)
229     fprintf (f, " used_from_other_partition");
230   fprintf (f, "\n");
231 }
232
233 /* Dump the variable pool.  */
234 void
235 dump_varpool (FILE *f)
236 {
237   struct varpool_node *node;
238
239   fprintf (f, "variable pool:\n\n");
240   for (node = varpool_nodes; node; node = node->next)
241     dump_varpool_node (f, node);
242 }
243
244 /* Dump the variable pool to stderr.  */
245
246 void
247 debug_varpool (void)
248 {
249   dump_varpool (stderr);
250 }
251
252 /* Given an assembler name, lookup node.  */
253 struct varpool_node *
254 varpool_node_for_asm (tree asmname)
255 {
256   struct varpool_node *node;
257
258   for (node = varpool_nodes; node ; node = node->next)
259     if (decl_assembler_name_equal (node->decl, asmname))
260       return node;
261
262   return NULL;
263 }
264
265 /* Helper function for finalization code - add node into lists so it will
266    be analyzed and compiled.  */
267 static void
268 varpool_enqueue_needed_node (struct varpool_node *node)
269 {
270   if (varpool_last_needed_node)
271     {
272       varpool_last_needed_node->next_needed = node;
273       node->prev_needed = varpool_last_needed_node;
274     }
275   varpool_last_needed_node = node;
276   node->next_needed = NULL;
277   if (!varpool_nodes_queue)
278     varpool_nodes_queue = node;
279   if (!varpool_first_unanalyzed_node)
280     varpool_first_unanalyzed_node = node;
281   notice_global_symbol (node->decl);
282 }
283
284 /* Notify finalize_compilation_unit that given node is reachable
285    or needed.  */
286 void
287 varpool_mark_needed_node (struct varpool_node *node)
288 {
289   if (node->alias && node->extra_name)
290     node = node->extra_name;
291   if (!node->needed && node->finalized
292       && !TREE_ASM_WRITTEN (node->decl))
293     varpool_enqueue_needed_node (node);
294   node->needed = 1;
295 }
296
297 /* Reset the queue of needed nodes.  */
298 static void
299 varpool_reset_queue (void)
300 {
301   varpool_last_needed_node = NULL;
302   varpool_nodes_queue = NULL;
303   varpool_first_unanalyzed_node = NULL;
304 }
305
306 /* Determine if variable DECL is needed.  That is, visible to something
307    either outside this translation unit, something magic in the system
308    configury */
309 bool
310 decide_is_variable_needed (struct varpool_node *node, tree decl)
311 {
312   if (node->used_from_other_partition)
313     return true;
314   /* If the user told us it is used, then it must be so.  */
315   if ((node->externally_visible && !DECL_COMDAT (decl))
316       || node->force_output)
317     return true;
318
319   /* ??? If the assembler name is set by hand, it is possible to assemble
320      the name later after finalizing the function and the fact is noticed
321      in assemble_name then.  This is arguably a bug.  */
322   if (DECL_ASSEMBLER_NAME_SET_P (decl)
323       && TREE_SYMBOL_REFERENCED (DECL_ASSEMBLER_NAME (decl)))
324     return true;
325
326   /* Externally visible variables must be output.  The exception is
327      COMDAT variables that must be output only when they are needed.  */
328   if (TREE_PUBLIC (decl)
329       && !flag_whole_program
330       && !flag_lto
331       && !flag_whopr
332       && !DECL_COMDAT (decl)
333       && !DECL_EXTERNAL (decl))
334     return true;
335
336   /* When emulating tls, we actually see references to the control
337      variable, rather than the user-level variable.  */
338   if (!targetm.have_tls
339       && TREE_CODE (decl) == VAR_DECL
340       && DECL_THREAD_LOCAL_P (decl))
341     {
342       tree control = emutls_decl (decl);
343       if (decide_is_variable_needed (varpool_node (control), control))
344         return true;
345     }
346
347   /* When not reordering top level variables, we have to assume that
348      we are going to keep everything.  */
349   if (flag_toplevel_reorder)
350     return false;
351
352   /* We want to emit COMDAT variables only when absolutely necessary.  */
353   if (DECL_COMDAT (decl))
354     return false;
355   return true;
356 }
357
358 /* Mark DECL as finalized.  By finalizing the declaration, frontend instruct the
359    middle end to output the variable to asm file, if needed or externally
360    visible.  */
361 void
362 varpool_finalize_decl (tree decl)
363 {
364   struct varpool_node *node = varpool_node (decl);
365
366   /* The first declaration of a variable that comes through this function
367      decides whether it is global (in C, has external linkage)
368      or local (in C, has internal linkage).  So do nothing more
369      if this function has already run.  */
370   if (node->finalized)
371     {
372       if (cgraph_global_info_ready)
373         varpool_assemble_pending_decls ();
374       return;
375     }
376   if (node->needed)
377     varpool_enqueue_needed_node (node);
378   node->finalized = true;
379
380   if (decide_is_variable_needed (node, decl))
381     varpool_mark_needed_node (node);
382   /* Since we reclaim unreachable nodes at the end of every language
383      level unit, we need to be conservative about possible entry points
384      there.  */
385   else if (TREE_PUBLIC (decl) && !DECL_COMDAT (decl) && !DECL_EXTERNAL (decl))
386     varpool_mark_needed_node (node);
387   if (cgraph_global_info_ready)
388     varpool_assemble_pending_decls ();
389 }
390
391 /* Return variable availability.  See cgraph.h for description of individual
392    return values.  */
393 enum availability
394 cgraph_variable_initializer_availability (struct varpool_node *node)
395 {
396   gcc_assert (cgraph_function_flags_ready);
397   if (!node->finalized)
398     return AVAIL_NOT_AVAILABLE;
399   if (!TREE_PUBLIC (node->decl))
400     return AVAIL_AVAILABLE;
401   /* If the variable can be overwritten, return OVERWRITABLE.  Takes
402      care of at least two notable extensions - the COMDAT variables
403      used to share template instantiations in C++.  */
404   if (!(*targetm.binds_local_p) (node->decl) && !DECL_COMDAT (node->decl))
405     return AVAIL_OVERWRITABLE;
406   return AVAIL_AVAILABLE;
407 }
408
409 /* Walk the decls we marked as necessary and see if they reference new
410    variables or functions and add them into the worklists.  */
411 bool
412 varpool_analyze_pending_decls (void)
413 {
414   bool changed = false;
415
416   timevar_push (TV_VARPOOL);
417   while (varpool_first_unanalyzed_node)
418     {
419       tree decl = varpool_first_unanalyzed_node->decl;
420       bool analyzed = varpool_first_unanalyzed_node->analyzed;
421
422       varpool_first_unanalyzed_node->analyzed = true;
423
424       varpool_first_unanalyzed_node = varpool_first_unanalyzed_node->next_needed;
425
426       /* When reading back varpool at LTO time, we re-construct the queue in order
427          to have "needed" list right by inserting all needed nodes into varpool.
428          We however don't want to re-analyze already analyzed nodes.  */
429       if (!analyzed)
430         {
431           gcc_assert (!in_lto_p || cgraph_function_flags_ready);
432           /* Compute the alignment early so function body expanders are
433              already informed about increased alignment.  */
434           align_variable (decl, 0);
435         }
436       if (DECL_INITIAL (decl))
437         record_references_in_initializer (decl, analyzed);
438       changed = true;
439     }
440   timevar_pop (TV_VARPOOL);
441   return changed;
442 }
443
444 /* Output one variable, if necessary.  Return whether we output it.  */
445 bool
446 varpool_assemble_decl (struct varpool_node *node)
447 {
448   tree decl = node->decl;
449
450   if (!TREE_ASM_WRITTEN (decl)
451       && !node->alias
452       && !node->in_other_partition
453       && !DECL_EXTERNAL (decl)
454       && (TREE_CODE (decl) != VAR_DECL || !DECL_HAS_VALUE_EXPR_P (decl)))
455     {
456       assemble_variable (decl, 0, 1, 0);
457       if (TREE_ASM_WRITTEN (decl))
458         {
459           struct varpool_node *alias;
460
461           node->next_needed = varpool_assembled_nodes_queue;
462           node->prev_needed = NULL;
463           if (varpool_assembled_nodes_queue)
464             varpool_assembled_nodes_queue->prev_needed = node;
465           varpool_assembled_nodes_queue = node;
466           node->finalized = 1;
467
468           /* Also emit any extra name aliases.  */
469           for (alias = node->extra_name; alias; alias = alias->next)
470             {
471               /* Update linkage fields in case they've changed.  */
472               DECL_WEAK (alias->decl) = DECL_WEAK (decl);
473               TREE_PUBLIC (alias->decl) = TREE_PUBLIC (decl);
474               DECL_VISIBILITY (alias->decl) = DECL_VISIBILITY (decl);
475               assemble_alias (alias->decl, DECL_ASSEMBLER_NAME (decl));
476             }
477
478           return true;
479         }
480     }
481
482   return false;
483 }
484
485 /* Optimization of function bodies might've rendered some variables as
486    unnecessary so we want to avoid these from being compiled.
487
488    This is done by pruning the queue and keeping only the variables that
489    really appear needed (ie they are either externally visible or referenced
490    by compiled function). Re-doing the reachability analysis on variables
491    brings back the remaining variables referenced by these.  */
492 void
493 varpool_remove_unreferenced_decls (void)
494 {
495   struct varpool_node *next, *node = varpool_nodes_queue;
496
497   varpool_reset_queue ();
498
499   if (errorcount || sorrycount)
500     return;
501
502   while (node)
503     {
504       tree decl = node->decl;
505       next = node->next_needed;
506       node->needed = 0;
507
508       if (node->finalized
509           && (decide_is_variable_needed (node, decl)
510               /* ??? Cgraph does not yet rule the world with an iron hand,
511                  and does not control the emission of debug information.
512                  After a variable has its DECL_RTL set, we must assume that
513                  it may be referenced by the debug information, and we can
514                  no longer elide it.  */
515               || DECL_RTL_SET_P (decl)))
516         varpool_mark_needed_node (node);
517
518       node = next;
519     }
520   /* Make sure we mark alias targets as used targets.  */
521   finish_aliases_1 ();
522   varpool_analyze_pending_decls ();
523 }
524
525 /* Output all variables enqueued to be assembled.  */
526 bool
527 varpool_assemble_pending_decls (void)
528 {
529   bool changed = false;
530
531   if (errorcount || sorrycount)
532     return false;
533
534   timevar_push (TV_VAROUT);
535   /* EH might mark decls as needed during expansion.  This should be safe since
536      we don't create references to new function, but it should not be used
537      elsewhere.  */
538   varpool_analyze_pending_decls ();
539
540   while (varpool_nodes_queue)
541     {
542       struct varpool_node *node = varpool_nodes_queue;
543
544       varpool_nodes_queue = varpool_nodes_queue->next_needed;
545       if (varpool_assemble_decl (node))
546         changed = true;
547       else
548         {
549           node->prev_needed = NULL;
550           node->next_needed = NULL;
551         }
552     }
553   /* varpool_nodes_queue is now empty, clear the pointer to the last element
554      in the queue.  */
555   varpool_last_needed_node = NULL;
556   timevar_pop (TV_VAROUT);
557   return changed;
558 }
559
560 /* Remove all elements from the queue so we can re-use it for debug output.  */
561 void
562 varpool_empty_needed_queue (void)
563 {
564   /* EH might mark decls as needed during expansion.  This should be safe since
565      we don't create references to new function, but it should not be used
566      elsewhere.  */
567   varpool_analyze_pending_decls ();
568
569   while (varpool_nodes_queue)
570     {
571       struct varpool_node *node = varpool_nodes_queue;
572       varpool_nodes_queue = varpool_nodes_queue->next_needed;
573       node->next_needed = NULL;
574       node->prev_needed = NULL;
575     }
576   /* varpool_nodes_queue is now empty, clear the pointer to the last element
577      in the queue.  */
578   varpool_last_needed_node = NULL;
579 }
580
581 /* Create a new global variable of type TYPE.  */
582 tree
583 add_new_static_var (tree type)
584 {
585   tree new_decl;
586   struct varpool_node *new_node;
587
588   new_decl = create_tmp_var (type, NULL);
589   DECL_NAME (new_decl) = create_tmp_var_name (NULL);
590   TREE_READONLY (new_decl) = 0;
591   TREE_STATIC (new_decl) = 1;
592   TREE_USED (new_decl) = 1;
593   DECL_CONTEXT (new_decl) = NULL_TREE;
594   DECL_ABSTRACT (new_decl) = 0;
595   lang_hooks.dup_lang_specific_decl (new_decl);
596   create_var_ann (new_decl);
597   new_node = varpool_node (new_decl);
598   varpool_mark_needed_node (new_node);
599   add_referenced_var (new_decl);
600   varpool_finalize_decl (new_decl);
601
602   return new_node->decl;
603 }
604
605 /* Attempt to mark ALIAS as an alias to DECL.  Return TRUE if successful.
606    Extra name aliases are output whenever DECL is output.  */
607
608 bool
609 varpool_extra_name_alias (tree alias, tree decl)
610 {
611   struct varpool_node key, *alias_node, *decl_node, **slot;
612
613 #ifndef ASM_OUTPUT_DEF
614   /* If aliases aren't supported by the assembler, fail.  */
615   return false;
616 #endif
617
618   gcc_assert (TREE_CODE (decl) == VAR_DECL);
619   gcc_assert (TREE_CODE (alias) == VAR_DECL);
620   /* Make sure the hash table has been created.  */
621   decl_node = varpool_node (decl);
622
623   key.decl = alias;
624
625   slot = (struct varpool_node **) htab_find_slot (varpool_hash, &key, INSERT);
626
627   /* If the varpool_node has been already created, fail.  */
628   if (*slot)
629     return false;
630
631   alias_node = GGC_CNEW (struct varpool_node);
632   alias_node->decl = alias;
633   alias_node->alias = 1;
634   alias_node->extra_name = decl_node;
635   alias_node->next = decl_node->extra_name;
636   if (decl_node->extra_name)
637     decl_node->extra_name->prev = alias_node;
638   decl_node->extra_name = alias_node;
639   *slot = alias_node;
640   return true;
641 }
642
643 #include "gt-varpool.h"