OSDN Git Service

2009-10-22 Richard Guenther <rguenther@suse.de>
[pf3gnuchains/gcc-fork.git] / gcc / lto-symtab.c
1 /* LTO symbol table.
2    Copyright 2009 Free Software Foundation, Inc.
3    Contributed by CodeSourcery, 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 "toplev.h"
25 #include "tree.h"
26 #include "gimple.h"
27 #include "ggc.h"        /* lambda.h needs this */
28 #include "lambda.h"     /* gcd */
29 #include "hashtab.h"
30 #include "plugin-api.h"
31 #include "lto-streamer.h"
32
33 /* Vector to keep track of external variables we've seen so far.  */
34 VEC(tree,gc) *lto_global_var_decls;
35
36 /* Symbol table entry.  */
37
38 struct GTY(()) lto_symtab_entry_def
39 {
40   /* The symbol table entry key, an IDENTIFIER.  */
41   tree id;
42   /* The symbol table entry, a DECL.  */
43   tree decl;
44   /* LTO file-data and symbol resolution for this decl.  */
45   struct lto_file_decl_data * GTY((skip (""))) file_data;
46   enum ld_plugin_symbol_resolution resolution;
47   /* Pointer to the next entry with the same key.  Before decl merging
48      this links all symbols from the different TUs.  After decl merging
49      this links merged but incompatible decls, thus all prevailing ones
50      remaining.  */
51   struct lto_symtab_entry_def *next;
52 };
53 typedef struct lto_symtab_entry_def *lto_symtab_entry_t;
54
55 /* A poor man's symbol table. This hashes identifier to prevailing DECL
56    if there is one. */
57
58 static GTY ((if_marked ("lto_symtab_entry_marked_p"),
59              param_is (struct lto_symtab_entry_def)))
60   htab_t lto_symtab_identifiers;
61
62 /* Return the hash value of an lto_symtab_entry_t object pointed to by P.  */
63
64 static hashval_t
65 lto_symtab_entry_hash (const void *p)
66 {
67   const struct lto_symtab_entry_def *base =
68     (const struct lto_symtab_entry_def *) p;
69   return htab_hash_string (IDENTIFIER_POINTER (base->id));
70 }
71
72 /* Return non-zero if P1 and P2 points to lto_symtab_entry_def structs
73    corresponding to the same symbol.  */
74
75 static int
76 lto_symtab_entry_eq (const void *p1, const void *p2)
77 {
78   const struct lto_symtab_entry_def *base1 =
79      (const struct lto_symtab_entry_def *) p1;
80   const struct lto_symtab_entry_def *base2 =
81      (const struct lto_symtab_entry_def *) p2;
82   return (base1->id == base2->id);
83 }
84
85 /* Returns non-zero if P points to an lto_symtab_entry_def struct that needs
86    to be marked for GC.  */ 
87
88 static int
89 lto_symtab_entry_marked_p (const void *p)
90 {
91   const struct lto_symtab_entry_def *base =
92      (const struct lto_symtab_entry_def *) p;
93
94   /* Keep this only if the decl or the chain is marked.  */
95   return (ggc_marked_p (base->decl)
96           || (base->next && ggc_marked_p (base->next)));
97 }
98
99 /* Lazily initialize resolution hash tables.  */
100
101 static void
102 lto_symtab_maybe_init_hash_table (void)
103 {
104   if (lto_symtab_identifiers)
105     return;
106
107   lto_symtab_identifiers =
108     htab_create_ggc (1021, lto_symtab_entry_hash,
109                      lto_symtab_entry_eq, NULL);
110 }
111
112 /* Registers DECL with the LTO symbol table as having resolution RESOLUTION
113    and read from FILE_DATA. */
114
115 void
116 lto_symtab_register_decl (tree decl,
117                           ld_plugin_symbol_resolution_t resolution,
118                           struct lto_file_decl_data *file_data)
119 {
120   lto_symtab_entry_t new_entry;
121   void **slot;
122
123   /* Check that declarations reaching this function do not have
124      properties inconsistent with having external linkage.  If any of
125      these asertions fail, then the object file reader has failed to
126      detect these cases and issue appropriate error messages.  */
127   gcc_assert (decl
128               && TREE_PUBLIC (decl)
129               && (TREE_CODE (decl) == VAR_DECL
130                   || TREE_CODE (decl) == FUNCTION_DECL)
131               && DECL_ASSEMBLER_NAME_SET_P (decl));
132   if (TREE_CODE (decl) == VAR_DECL
133       && DECL_INITIAL (decl))
134     gcc_assert (!DECL_EXTERNAL (decl)
135                 || (TREE_STATIC (decl) && TREE_READONLY (decl)));
136   if (TREE_CODE (decl) == FUNCTION_DECL)
137     gcc_assert (!DECL_ABSTRACT (decl));
138
139   new_entry = GGC_CNEW (struct lto_symtab_entry_def);
140   new_entry->id = DECL_ASSEMBLER_NAME (decl);
141   new_entry->decl = decl;
142   new_entry->resolution = resolution;
143   new_entry->file_data = file_data;
144
145   lto_symtab_maybe_init_hash_table ();
146   slot = htab_find_slot (lto_symtab_identifiers, new_entry, INSERT);
147   new_entry->next = (lto_symtab_entry_t) *slot;
148   *slot = new_entry;
149 }
150
151 /* Get the lto_symtab_entry_def struct associated with ID
152    if there is one.  */
153
154 static lto_symtab_entry_t
155 lto_symtab_get (tree id)
156 {
157   struct lto_symtab_entry_def temp;
158   void **slot;
159
160   lto_symtab_maybe_init_hash_table ();
161   temp.id = id;
162   slot = htab_find_slot (lto_symtab_identifiers, &temp, NO_INSERT);
163   return slot ? (lto_symtab_entry_t) *slot : NULL;
164 }
165
166 /* Get the linker resolution for DECL.  */
167
168 enum ld_plugin_symbol_resolution
169 lto_symtab_get_resolution (tree decl)
170 {
171   lto_symtab_entry_t e;
172
173   gcc_assert (DECL_ASSEMBLER_NAME_SET_P (decl));
174
175   e = lto_symtab_get (DECL_ASSEMBLER_NAME (decl));
176   while (e && e->decl != decl)
177     e = e->next;
178   if (!e)
179     return LDPR_UNKNOWN;
180
181   return e->resolution;
182 }
183
184
185 /* Replace the cgraph node NODE with PREVAILING_NODE in the cgraph, merging
186    all edges and removing the old node.  */
187
188 static void
189 lto_cgraph_replace_node (struct cgraph_node *node,
190                          struct cgraph_node *prevailing_node)
191 {
192   struct cgraph_edge *e, *next;
193
194   /* Merge node flags.  */
195   if (node->needed)
196     cgraph_mark_needed_node (prevailing_node);
197   if (node->reachable)
198     cgraph_mark_reachable_node (prevailing_node);
199   if (node->address_taken)
200     {
201       gcc_assert (!prevailing_node->global.inlined_to);
202       cgraph_mark_address_taken_node (prevailing_node);
203     }
204
205   /* Redirect all incoming edges.  */
206   for (e = node->callers; e; e = next)
207     {
208       next = e->next_caller;
209       cgraph_redirect_edge_callee (e, prevailing_node);
210     }
211
212   /* There are not supposed to be any outgoing edges from a node we
213      replace.  Still this can happen for multiple instances of weak
214      functions.  */
215   for (e = node->callees; e; e = next)
216     {
217       next = e->next_callee;
218       cgraph_remove_edge (e);
219     }
220
221   /* Finally remove the replaced node.  */
222   cgraph_remove_node (node);
223 }
224
225 /* Merge two variable or function symbol table entries PREVAILING and ENTRY.
226    Return false if the symbols are not fully compatible and a diagnostic
227    should be emitted.  */
228
229 static bool
230 lto_symtab_merge (lto_symtab_entry_t prevailing, lto_symtab_entry_t entry)
231 {
232   tree prevailing_decl = prevailing->decl;
233   tree decl = entry->decl;
234   tree prevailing_type, type;
235   struct cgraph_node *node;
236
237   /* Merge decl state in both directions, we may still end up using
238      the new decl.  */
239   TREE_ADDRESSABLE (prevailing_decl) |= TREE_ADDRESSABLE (decl);
240   TREE_ADDRESSABLE (decl) |= TREE_ADDRESSABLE (prevailing_decl);
241
242   /* Replace a cgraph node of entry with the prevailing one.  */
243   if (TREE_CODE (decl) == FUNCTION_DECL
244       && (node = cgraph_get_node (decl)) != NULL)
245     lto_cgraph_replace_node (node, cgraph_get_node (prevailing_decl));
246
247   /* The linker may ask us to combine two incompatible symbols.
248      Detect this case and notify the caller of required diagnostics.  */
249
250   if (TREE_CODE (decl) == FUNCTION_DECL)
251     {
252       if (TREE_TYPE (prevailing_decl) != TREE_TYPE (decl))
253         /* If we don't have a merged type yet...sigh.  The linker
254            wouldn't complain if the types were mismatched, so we
255            probably shouldn't either.  Just use the type from
256            whichever decl appears to be associated with the
257            definition.  If for some odd reason neither decl is, the
258            older one wins.  */
259         (void) 0;
260
261       return true;
262     }
263
264   /* Now we exclusively deal with VAR_DECLs.  */
265
266   /* Sharing a global symbol is a strong hint that two types are
267      compatible.  We could use this information to complete
268      incomplete pointed-to types more aggressively here, ignoring
269      mismatches in both field and tag names.  It's difficult though
270      to guarantee that this does not have side-effects on merging
271      more compatible types from other translation units though.  */
272
273   /* We can tolerate differences in type qualification, the
274      qualification of the prevailing definition will prevail.
275      ???  In principle we might want to only warn for structurally
276      incompatible types here, but unless we have protective measures
277      for TBAA in place that would hide useful information.  */
278   prevailing_type = TYPE_MAIN_VARIANT (TREE_TYPE (prevailing_decl));
279   type = TYPE_MAIN_VARIANT (TREE_TYPE (decl));
280
281   /* We have to register and fetch canonical types here as the global
282      fixup process didn't yet run.  */
283   prevailing_type = gimple_register_type (prevailing_type);
284   type = gimple_register_type (type);
285   if (prevailing_type != type)
286     {
287       if (COMPLETE_TYPE_P (type))
288         return false;
289
290       /* If type is incomplete then avoid warnings in the cases
291          that TBAA handles just fine.  */
292
293       if (TREE_CODE (prevailing_type) != TREE_CODE (type))
294         return false;
295
296       if (TREE_CODE (prevailing_type) == ARRAY_TYPE)
297         {
298           tree tem1 = TREE_TYPE (prevailing_type);
299           tree tem2 = TREE_TYPE (type);
300           while (TREE_CODE (tem1) == ARRAY_TYPE
301                  && TREE_CODE (tem2) == ARRAY_TYPE)
302             {
303               tem1 = TREE_TYPE (tem1);
304               tem2 = TREE_TYPE (tem2);
305             }
306
307           if (TREE_CODE (tem1) != TREE_CODE (tem2))
308             return false;
309
310           if (gimple_register_type (tem1) != gimple_register_type (tem2))
311             return false;
312         }
313
314       /* Fallthru.  Compatible enough.  */
315     }
316
317   /* ???  We might want to emit a warning here if type qualification
318      differences were spotted.  Do not do this unconditionally though.  */
319
320   /* There is no point in comparing too many details of the decls here.
321      The type compatibility checks or the completing of types has properly
322      dealt with most issues.  */
323
324   /* The following should all not invoke fatal errors as in non-LTO
325      mode the linker wouldn't complain either.  Just emit warnings.  */
326
327   /* Report a warning if user-specified alignments do not match.  */
328   if ((DECL_USER_ALIGN (prevailing_decl) && DECL_USER_ALIGN (decl))
329       && DECL_ALIGN (prevailing_decl) < DECL_ALIGN (decl))
330     return false;
331
332   return true;
333 }
334
335 /* Return true if the symtab entry E can be replaced by another symtab
336    entry.  */
337
338 static bool
339 lto_symtab_resolve_replaceable_p (lto_symtab_entry_t e)
340 {
341   if (DECL_EXTERNAL (e->decl)
342       || DECL_COMDAT (e->decl)
343       || DECL_WEAK (e->decl))
344     return true;
345
346   if (TREE_CODE (e->decl) == VAR_DECL)
347     return (DECL_COMMON (e->decl)
348             || (!flag_no_common && !DECL_INITIAL (e->decl)));
349
350   return false;
351 }
352
353 /* Return true if the symtab entry E can be the prevailing one.  */
354
355 static bool
356 lto_symtab_resolve_can_prevail_p (lto_symtab_entry_t e)
357 {
358   struct cgraph_node *node;
359
360   if (!TREE_STATIC (e->decl))
361     return false;
362
363   /* For functions we need a non-discarded body.  */
364   if (TREE_CODE (e->decl) == FUNCTION_DECL)
365     return ((node = cgraph_get_node (e->decl))
366             && node->analyzed);
367
368   /* A variable should have a size.  */
369   else if (TREE_CODE (e->decl) == VAR_DECL)
370     return (DECL_SIZE (e->decl) != NULL_TREE
371             /* The C++ frontend retains TREE_STATIC on the declaration
372                of foo_ in struct Foo { static Foo *foo_; }; but it is
373                not a definition.  g++.dg/lto/20090315_0.C.  */
374             && !DECL_EXTERNAL (e->decl));
375
376   gcc_unreachable ();
377 }
378
379 /* Resolve the symbol with the candidates in the chain *SLOT and store
380    their resolutions.  */
381
382 static void
383 lto_symtab_resolve_symbols (void **slot)
384 {
385   lto_symtab_entry_t e = (lto_symtab_entry_t) *slot;
386   lto_symtab_entry_t prevailing = NULL;
387
388   /* If the chain is already resolved there is nothing to do.  */
389   if (e->resolution != LDPR_UNKNOWN)
390     return;
391
392   /* Find the single non-replaceable prevailing symbol and
393      diagnose ODR violations.  */
394   for (; e; e = e->next)
395     {
396       if (!lto_symtab_resolve_can_prevail_p (e))
397         {
398           e->resolution = LDPR_RESOLVED_IR;
399           continue;
400         }
401
402       /* Set a default resolution - the final prevailing one will get
403          adjusted later.  */
404       e->resolution = LDPR_PREEMPTED_IR;
405       if (!lto_symtab_resolve_replaceable_p (e))
406         {
407           if (prevailing)
408             {
409               error_at (DECL_SOURCE_LOCATION (e->decl),
410                         "%qD has already been defined", e->decl);
411               inform (DECL_SOURCE_LOCATION (prevailing->decl),
412                       "previously defined here");
413             }
414           prevailing = e;
415         }
416     }
417   if (prevailing)
418     goto found;
419
420   /* Do a second round choosing one from the replaceable prevailing decls.  */
421   for (e = (lto_symtab_entry_t) *slot; e; e = e->next)
422     {
423       if (e->resolution != LDPR_PREEMPTED_IR)
424         continue;
425
426       /* Choose the first function that can prevail as prevailing.  */
427       if (TREE_CODE (e->decl) == FUNCTION_DECL)
428         {
429           prevailing = e;
430           break;
431         }
432
433       /* From variables that can prevail choose the largest one.  */
434       if (!prevailing
435           || tree_int_cst_lt (DECL_SIZE (prevailing->decl),
436                               DECL_SIZE (e->decl)))
437         prevailing = e;
438     }
439
440   if (!prevailing)
441     return;
442
443 found:
444   if (TREE_CODE (prevailing->decl) == VAR_DECL
445       && TREE_READONLY (prevailing->decl))
446     prevailing->resolution = LDPR_PREVAILING_DEF_IRONLY;
447   else
448     prevailing->resolution = LDPR_PREVAILING_DEF;
449 }
450
451 /* Merge all decls in the symbol table chain to the prevailing decl and
452    issue diagnostics about type mismatches.  */
453
454 static void
455 lto_symtab_merge_decls_2 (void **slot)
456 {
457   lto_symtab_entry_t prevailing, e;
458   VEC(tree, heap) *mismatches = NULL;
459   unsigned i;
460   tree decl;
461   bool diagnosed_p = false;
462
463   /* Nothing to do for a single entry.  */
464   prevailing = (lto_symtab_entry_t) *slot;
465   if (!prevailing->next)
466     return;
467
468   /* Try to merge each entry with the prevailing one.  */
469   for (e = prevailing->next; e; e = e->next)
470     {
471       if (!lto_symtab_merge (prevailing, e))
472         VEC_safe_push (tree, heap, mismatches, e->decl);
473     }
474   if (VEC_empty (tree, mismatches))
475     return;
476
477   /* Diagnose all mismatched re-declarations.  */
478   for (i = 0; VEC_iterate (tree, mismatches, i, decl); ++i)
479     {
480       if (TREE_TYPE (prevailing->decl) != TREE_TYPE (decl))
481         diagnosed_p |= warning_at (DECL_SOURCE_LOCATION (decl), 0,
482                                    "type of %qD does not match original "
483                                    "declaration", decl);
484
485       else if ((DECL_USER_ALIGN (prevailing->decl) && DECL_USER_ALIGN (decl))
486                && DECL_ALIGN (prevailing->decl) < DECL_ALIGN (decl))
487         {
488           diagnosed_p |= warning_at (DECL_SOURCE_LOCATION (decl), 0,
489                                      "alignment of %qD is bigger than "
490                                      "original declaration", decl);
491         }
492     }
493   if (diagnosed_p)
494     inform (DECL_SOURCE_LOCATION (prevailing->decl),
495             "previously declared here");
496
497   VEC_free (tree, heap, mismatches);
498 }
499
500 /* Helper to process the decl chain for the symbol table entry *SLOT.  */
501
502 static int
503 lto_symtab_merge_decls_1 (void **slot, void *data ATTRIBUTE_UNUSED)
504 {
505   lto_symtab_entry_t e, prevailing;
506   bool diagnosed_p = false;
507
508   /* Compute the symbol resolutions.  This is a no-op when using the
509      linker plugin.  */
510   lto_symtab_resolve_symbols (slot);
511
512   /* Find the prevailing decl.  */
513   for (prevailing = (lto_symtab_entry_t) *slot;
514        prevailing
515        && prevailing->resolution != LDPR_PREVAILING_DEF_IRONLY
516        && prevailing->resolution != LDPR_PREVAILING_DEF;
517        prevailing = prevailing->next)
518     ;
519
520   /* Assert it's the only one.  */
521   if (prevailing)
522     for (e = prevailing->next; e; e = e->next)
523       gcc_assert (e->resolution != LDPR_PREVAILING_DEF_IRONLY
524                   && e->resolution != LDPR_PREVAILING_DEF);
525
526   /* If there's not a prevailing symbol yet it's an external reference.
527      Happens a lot during ltrans.  Choose the first symbol with a
528      cgraph or a varpool node.  */
529   if (!prevailing)
530     {
531       prevailing = (lto_symtab_entry_t) *slot;
532       /* For functions choose one with a cgraph node.  */
533       if (TREE_CODE (prevailing->decl) == FUNCTION_DECL)
534         while (!cgraph_get_node (prevailing->decl)
535                && prevailing->next)
536           prevailing = prevailing->next;
537       /* We do not stream varpool nodes, so the first decl has to
538          be good enough for now.
539          ???  For QOI choose a variable with readonly initializer
540          if there is one.  This matches C++
541          struct Foo { static const int i = 1; }; without a real
542          definition.  */
543       if (TREE_CODE (prevailing->decl) == VAR_DECL)
544         while (!(TREE_READONLY (prevailing->decl)
545                  && DECL_INITIAL (prevailing->decl))
546                && prevailing->next)
547           prevailing = prevailing->next;
548     }
549
550   /* Move it first in the list.  */
551   if ((lto_symtab_entry_t) *slot != prevailing)
552     {
553       for (e = (lto_symtab_entry_t) *slot; e->next != prevailing; e = e->next)
554         ;
555       e->next = prevailing->next;
556       prevailing->next = (lto_symtab_entry_t) *slot;
557       *slot = (void *) prevailing;
558     }
559
560   /* Record the prevailing variable.  */
561   if (TREE_CODE (prevailing->decl) == VAR_DECL)
562     VEC_safe_push (tree, gc, lto_global_var_decls, prevailing->decl);
563
564   /* Diagnose mismatched objects.  */
565   for (e = prevailing->next; e; e = e->next)
566     {
567       if (TREE_CODE (prevailing->decl) == TREE_CODE (e->decl))
568         continue;
569
570       switch (TREE_CODE (prevailing->decl))
571         {
572         case VAR_DECL:
573           gcc_assert (TREE_CODE (e->decl) == FUNCTION_DECL);
574           error_at (DECL_SOURCE_LOCATION (e->decl),
575                     "variable %qD redeclared as function", prevailing->decl);
576           break;
577
578         case FUNCTION_DECL:
579           gcc_assert (TREE_CODE (e->decl) == VAR_DECL);
580           error_at (DECL_SOURCE_LOCATION (e->decl),
581                     "function %qD redeclared as variable", prevailing->decl);
582           break;
583
584         default:
585           gcc_unreachable ();
586         }
587
588       diagnosed_p = true;
589     }
590   if (diagnosed_p)
591       inform (DECL_SOURCE_LOCATION (prevailing->decl),
592               "previously declared here");
593
594   /* Register and adjust types of the entries.  */
595   for (e = (lto_symtab_entry_t) *slot; e; e = e->next)
596     TREE_TYPE (e->decl) = gimple_register_type (TREE_TYPE (e->decl));
597
598   /* Merge the chain to the single prevailing decl and diagnose
599      mismatches.  */
600   lto_symtab_merge_decls_2 (slot);
601
602   /* Drop all but the prevailing decl from the symtab.  */
603   prevailing->next = NULL;
604
605   return 1;
606 }
607
608 /* Resolve and merge all symbol table chains to a prevailing decl.  */
609
610 void
611 lto_symtab_merge_decls (void)
612 {
613   lto_symtab_maybe_init_hash_table ();
614   htab_traverse (lto_symtab_identifiers, lto_symtab_merge_decls_1, NULL);
615 }
616
617
618 /* Given the decl DECL, return the prevailing decl with the same name. */
619
620 tree
621 lto_symtab_prevailing_decl (tree decl)
622 {
623   lto_symtab_entry_t ret;
624
625   /* Builtins and local symbols are their own prevailing decl.  */
626   if (!TREE_PUBLIC (decl) || is_builtin_fn (decl))
627     return decl;
628
629   /* DECL_ABSTRACTs are their own prevailng decl.  */
630   if (TREE_CODE (decl) == FUNCTION_DECL && DECL_ABSTRACT (decl))
631     return decl;
632
633   /* Ensure DECL_ASSEMBLER_NAME will not set assembler name.  */
634   gcc_assert (DECL_ASSEMBLER_NAME_SET_P (decl));
635
636   /* Walk through the list of candidates and return the one we merged to.  */
637   ret = lto_symtab_get (DECL_ASSEMBLER_NAME (decl));
638   if (!ret)
639     return NULL_TREE;
640
641   return ret->decl;
642 }
643
644 #include "gt-lto-symtab.h"