OSDN Git Service

2009-10-05 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_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 /* Returns true iff the union of ATTRIBUTES_1 and ATTRIBUTES_2 can be
113    applied to DECL.  */
114 static bool
115 lto_compatible_attributes_p (tree decl ATTRIBUTE_UNUSED, 
116                              tree attributes_1, 
117                              tree attributes_2)
118 {
119 #if 0
120   /* ??? For now, assume two attribute sets are compatible only if they
121      are both empty.  */
122   return !attributes_1 && !attributes_2;
123 #else
124   /* FIXME.  For the moment, live dangerously, and assume the user knows
125      what he's doing. I don't think the linker would distinguish these cases.  */
126   return true || (!attributes_1 && !attributes_2);
127 #endif
128 }
129
130 /* Helper for lto_symtab_compatible. Return TRUE if DECL is an external
131    variable declaration of an aggregate type. */
132
133 static bool
134 external_aggregate_decl_p (tree decl)
135 {
136   return (TREE_CODE (decl) == VAR_DECL
137           && DECL_EXTERNAL (decl)
138           && AGGREGATE_TYPE_P (TREE_TYPE (decl)));
139 }
140
141 static bool maybe_merge_incomplete_and_complete_type (tree, tree);
142
143 /* Try to merge an incomplete type INCOMPLETE with a complete type
144    COMPLETE of same kinds.
145    Return true if they were merged, false otherwise.  */
146
147 static bool
148 merge_incomplete_and_complete_type (tree incomplete, tree complete)
149 {
150   /* For merging array types do some extra sanity checking.  */
151   if (TREE_CODE (incomplete) == ARRAY_TYPE
152       && !maybe_merge_incomplete_and_complete_type (TREE_TYPE (incomplete),
153                                                     TREE_TYPE (complete))
154       && !gimple_types_compatible_p (TREE_TYPE (incomplete),
155                                      TREE_TYPE (complete)))
156     return false;
157
158   /* ??? Ideally we would do this by means of a common canonical type, but
159      that's difficult as we do not have links from the canonical type
160      back to all its children.  */
161   gimple_force_type_merge (incomplete, complete);
162
163   return true;
164 }
165
166 /* Try to merge a maybe complete / incomplete type pair TYPE1 and TYPE2.
167    Return true if they were merged, false otherwise.  */
168
169 static bool
170 maybe_merge_incomplete_and_complete_type (tree type1, tree type2)
171 {
172   bool res = false;
173
174   if (TREE_CODE (type1) != TREE_CODE (type2))
175     return false;
176
177   if (!COMPLETE_TYPE_P (type1) && COMPLETE_TYPE_P (type2))
178     res = merge_incomplete_and_complete_type (type1, type2);
179   else if (COMPLETE_TYPE_P (type1) && !COMPLETE_TYPE_P (type2))
180     res = merge_incomplete_and_complete_type (type2, type1);
181
182   /* Recurse on pointer targets.  */
183   if (!res
184       && POINTER_TYPE_P (type1)
185       && POINTER_TYPE_P (type2))
186     res = maybe_merge_incomplete_and_complete_type (TREE_TYPE (type1),
187                                                     TREE_TYPE (type2));
188
189   return res;
190 }
191
192 /* Check if OLD_DECL and NEW_DECL are compatible. */
193
194 static bool
195 lto_symtab_compatible (tree old_decl, tree new_decl)
196 {
197   tree merged_type = NULL_TREE;
198
199   if (TREE_CODE (old_decl) != TREE_CODE (new_decl))
200     {
201       switch (TREE_CODE (new_decl))
202         {
203         case VAR_DECL:
204           gcc_assert (TREE_CODE (old_decl) == FUNCTION_DECL);
205           error_at (DECL_SOURCE_LOCATION (new_decl),
206                     "function %qD redeclared as variable", new_decl);
207           inform (DECL_SOURCE_LOCATION (old_decl),
208                   "previously declared here");
209           return false;
210
211         case FUNCTION_DECL:
212           gcc_assert (TREE_CODE (old_decl) == VAR_DECL);
213           error_at (DECL_SOURCE_LOCATION (new_decl),
214                     "variable %qD redeclared as function", new_decl);
215           inform (DECL_SOURCE_LOCATION (old_decl),
216                   "previously declared here");
217           return false;
218
219         default:
220           gcc_unreachable ();
221         }
222     }
223
224   /* Handle external declarations with incomplete type or pointed-to
225      incomplete types by forcefully merging the types.
226      ???  In principle all types involved in the two decls should
227      be merged forcefully, for example without considering type or
228      field names.  */
229   if (TREE_CODE (old_decl) == VAR_DECL)
230     {
231       tree old_type = TREE_TYPE (old_decl);
232       tree new_type = TREE_TYPE (new_decl);
233
234       if (DECL_EXTERNAL (old_decl) || DECL_EXTERNAL (new_decl))
235         maybe_merge_incomplete_and_complete_type (old_type, new_type);
236       else if (POINTER_TYPE_P (old_type)
237                && POINTER_TYPE_P (new_type))
238         maybe_merge_incomplete_and_complete_type (TREE_TYPE (old_type),
239                                                   TREE_TYPE (new_type));
240
241       /* For array types we have to accept external declarations with
242          different sizes than the actual definition (164.gzip).
243          ???  We could emit a warning here.  */
244       if (TREE_CODE (old_type) == TREE_CODE (new_type)
245           && TREE_CODE (old_type) == ARRAY_TYPE
246           && COMPLETE_TYPE_P (old_type)
247           && COMPLETE_TYPE_P (new_type)
248           && tree_int_cst_compare (TYPE_SIZE (old_type),
249                                    TYPE_SIZE (new_type)) != 0
250           && gimple_types_compatible_p (TREE_TYPE (old_type),
251                                         TREE_TYPE (new_type)))
252         {
253           /* If only one is external use the type of the non-external decl.
254              Else use the larger one and also adjust the decl size.
255              ???  Directional merging would allow us to simply pick the
256              larger one instead of rewriting it.  */
257           if (DECL_EXTERNAL (old_decl) ^ DECL_EXTERNAL (new_decl))
258             {
259               if (DECL_EXTERNAL (old_decl))
260                 TREE_TYPE (old_decl) = new_type;
261               else if (DECL_EXTERNAL (new_decl))
262                 TREE_TYPE (new_decl) = old_type;
263             }
264           else
265             {
266               if (tree_int_cst_compare (TYPE_SIZE (old_type),
267                                         TYPE_SIZE (new_type)) < 0)
268                 {
269                   TREE_TYPE (old_decl) = new_type;
270                   DECL_SIZE (old_decl) = DECL_SIZE (new_decl);
271                   DECL_SIZE_UNIT (old_decl) = DECL_SIZE_UNIT (new_decl);
272                 }
273               else
274                 {
275                   TREE_TYPE (new_decl) = old_type;
276                   DECL_SIZE (new_decl) = DECL_SIZE (old_decl);
277                   DECL_SIZE_UNIT (new_decl) = DECL_SIZE_UNIT (old_decl);
278                 }
279             }
280         }
281     }
282
283   if (!gimple_types_compatible_p (TREE_TYPE (old_decl), TREE_TYPE (new_decl)))
284     {
285       if (TREE_CODE (new_decl) == FUNCTION_DECL)
286         {
287           if (!merged_type
288               /* We want either of the types to have argument types,
289                  but not both.  */
290               && ((TYPE_ARG_TYPES (TREE_TYPE (old_decl)) != NULL)
291                   ^ (TYPE_ARG_TYPES (TREE_TYPE (new_decl)) != NULL)))
292             {
293               /* The situation here is that (in C) somebody was smart
294                  enough to use proper declarations in a header file, but
295                  the actual definition of the function uses
296                  non-ANSI-style argument lists.  Or we have a situation
297                  where declarations weren't used anywhere and we're
298                  merging the actual definition with a use.  One of the
299                  decls will then have a complete function type, whereas
300                  the other will only have a result type.  Assume that
301                  the more complete type is the right one and don't
302                  complain.  */
303               if (TYPE_ARG_TYPES (TREE_TYPE (old_decl)))
304                 {
305                   merged_type = TREE_TYPE (old_decl);
306                 }
307               else
308                 {
309                   merged_type = TREE_TYPE (new_decl);
310                 }
311             }
312
313           /* If we don't have a merged type yet...sigh.  The linker
314              wouldn't complain if the types were mismatched, so we
315              probably shouldn't either.  Just use the type from
316              whichever decl appears to be associated with the
317              definition.  If for some odd reason neither decl is, the
318              older one wins.  */
319           if (!merged_type)
320             {
321               if (!DECL_EXTERNAL (new_decl))
322                 {
323                   merged_type = TREE_TYPE (new_decl);
324                 }
325               else
326                 {
327                   merged_type = TREE_TYPE (old_decl);
328                 }
329             }
330         }
331
332       if (!merged_type)
333         {
334           if (warning_at (DECL_SOURCE_LOCATION (new_decl), 0,
335                           "type of %qD does not match original declaration",
336                           new_decl))
337             inform (DECL_SOURCE_LOCATION (old_decl),
338                     "previously declared here");
339           return false;
340         }
341     }
342
343   if (DECL_UNSIGNED (old_decl) != DECL_UNSIGNED (new_decl))
344     {
345       error_at (DECL_SOURCE_LOCATION (new_decl),
346                 "signedness of %qD does not match original declaration",
347                 new_decl);
348       inform (DECL_SOURCE_LOCATION (old_decl), "previously declared here");
349       return false;
350     }
351
352   if (!tree_int_cst_equal (DECL_SIZE (old_decl),
353                            DECL_SIZE (new_decl))
354       || !tree_int_cst_equal (DECL_SIZE_UNIT (old_decl),
355                               DECL_SIZE_UNIT (new_decl)))
356     {
357       /* Permit cases where we are declaring aggregates and at least one
358          of the decls is external and one of the decls has a size whereas
359          the other one does not.  This is perfectly legal in C:
360
361          struct s;
362          extern struct s x;
363
364          void*
365          f (void)
366          {
367            return &x;
368          }
369
370          There is no way a compiler can tell the size of x.  So we cannot
371          assume that external aggreates have complete types.  */
372
373       if (!((TREE_CODE (TREE_TYPE (old_decl))
374              == TREE_CODE (TREE_TYPE (new_decl)))
375             && ((external_aggregate_decl_p (old_decl)
376                  && DECL_SIZE (old_decl) == NULL_TREE)
377                 || (external_aggregate_decl_p (new_decl)
378                     && DECL_SIZE (new_decl) == NULL_TREE))))
379         {
380           error_at (DECL_SOURCE_LOCATION (new_decl),
381                     "size of %qD does not match original declaration",
382                     new_decl);
383           inform (DECL_SOURCE_LOCATION (old_decl),
384                   "previously declared here");
385           return false;
386         }
387     }
388
389   /* Report an error if user-specified alignments do not match.  */
390   if ((DECL_USER_ALIGN (old_decl) && DECL_USER_ALIGN (new_decl))
391       && DECL_ALIGN (old_decl) != DECL_ALIGN (new_decl))
392     {
393       error_at (DECL_SOURCE_LOCATION (new_decl),
394                 "alignment of %qD does not match original declaration",
395                 new_decl);
396       inform (DECL_SOURCE_LOCATION (old_decl), "previously declared here");
397       return false;
398     }
399
400   /* Do not compare the modes of the decls.  The type compatibility
401      checks or the completing of types has properly dealt with all issues.  */
402
403   if (!lto_compatible_attributes_p (old_decl,
404                                     DECL_ATTRIBUTES (old_decl),
405                                     DECL_ATTRIBUTES (new_decl)))
406     {
407       error_at (DECL_SOURCE_LOCATION (new_decl),
408                 "attributes applied to %qD are incompatible with original "
409                 "declaration", new_decl);
410       inform (DECL_SOURCE_LOCATION (old_decl), "previously declared here");
411       return false;
412     }
413
414   /* We do not require matches for:
415
416      - DECL_NAME
417
418        Only the name used in object files matters.
419
420      - DECL_CONTEXT  
421
422        An entity might be declared in a C++ namespace in one file and
423        with a C identifier in another file.  
424
425      - TREE_PRIVATE, TREE_PROTECTED
426
427        Access control is the problem of the front end that created the
428        object file.  
429        
430      Therefore, at this point we have decided to merge the declarations.  */
431   return true;
432 }
433
434 /* Registers DECL with the LTO symbol table as having resolution RESOLUTION
435    and read from FILE_DATA. */
436
437 void
438 lto_symtab_register_decl (tree decl,
439                           ld_plugin_symbol_resolution_t resolution,
440                           struct lto_file_decl_data *file_data)
441 {
442   lto_symtab_entry_t new_entry;
443   void **slot;
444
445   /* Check that declarations reaching this function do not have
446      properties inconsistent with having external linkage.  If any of
447      these asertions fail, then the object file reader has failed to
448      detect these cases and issue appropriate error messages.  */
449   gcc_assert (decl
450               && TREE_PUBLIC (decl)
451               && (TREE_CODE (decl) == VAR_DECL
452                   || TREE_CODE (decl) == FUNCTION_DECL)
453               && DECL_ASSEMBLER_NAME_SET_P (decl));
454   if (TREE_CODE (decl) == VAR_DECL)
455     gcc_assert (!(DECL_EXTERNAL (decl) && DECL_INITIAL (decl)));
456   if (TREE_CODE (decl) == FUNCTION_DECL)
457     gcc_assert (!DECL_ABSTRACT (decl));
458
459   new_entry = GGC_CNEW (struct lto_symtab_entry_def);
460   new_entry->id = DECL_ASSEMBLER_NAME (decl);
461   new_entry->decl = decl;
462   new_entry->resolution = resolution;
463   new_entry->file_data = file_data;
464   
465   lto_symtab_maybe_init_hash_table ();
466   slot = htab_find_slot (lto_symtab_identifiers, new_entry, INSERT);
467   new_entry->next = (lto_symtab_entry_t) *slot;
468   *slot = new_entry;
469 }
470
471 /* Get the lto_symtab_entry_def struct associated with ID
472    if there is one.  */
473
474 static lto_symtab_entry_t
475 lto_symtab_get (tree id)
476 {
477   struct lto_symtab_entry_def temp;
478   void **slot;
479
480   lto_symtab_maybe_init_hash_table ();
481   temp.id = id;
482   slot = htab_find_slot (lto_symtab_identifiers, &temp, NO_INSERT);
483   return slot ? (lto_symtab_entry_t) *slot : NULL;
484 }
485
486 /* Get the linker resolution for DECL.  */
487
488 enum ld_plugin_symbol_resolution
489 lto_symtab_get_resolution (tree decl)
490 {
491   lto_symtab_entry_t e;
492
493   gcc_assert (DECL_ASSEMBLER_NAME_SET_P (decl));
494
495   e = lto_symtab_get (DECL_ASSEMBLER_NAME (decl));
496   while (e && e->decl != decl)
497     e = e->next;
498   if (!e)
499     return LDPR_UNKNOWN;
500
501   return e->resolution;
502 }
503
504 /* Replace the cgraph node OLD_NODE with NEW_NODE in the cgraph, merging
505    all edges and removing the old node.  */
506
507 static void
508 lto_cgraph_replace_node (struct cgraph_node *old_node,
509                          struct cgraph_node *new_node)
510 {
511   struct cgraph_edge *e, *next;
512
513   /* Merge node flags.  */
514   if (old_node->needed)
515     cgraph_mark_needed_node (new_node);
516   if (old_node->reachable)
517     cgraph_mark_reachable_node (new_node);
518   if (old_node->address_taken)
519     cgraph_mark_address_taken_node (new_node);
520
521   /* Redirect all incoming edges.  */
522   for (e = old_node->callers; e; e = next)
523     {
524       next = e->next_caller;
525       cgraph_redirect_edge_callee (e, new_node);
526     }
527
528   /* There are not supposed to be any outgoing edges from a node we
529      replace.  Still this can happen for multiple instances of weak
530      functions.
531      ???  For now do what the old code did.  Do not create edges for them.  */
532   for (e = old_node->callees; e; e = next)
533     {
534       next = e->next_callee;
535       cgraph_remove_edge (e);
536     }
537
538   /* Finally remove the replaced node.  */
539   cgraph_remove_node (old_node);
540 }
541
542 /* Merge two variable or function symbol table entries ENTRY1 and ENTRY2.
543    Return the prevailing one or NULL if a merge is not possible.  */
544
545 static lto_symtab_entry_t
546 lto_symtab_merge (lto_symtab_entry_t entry1, lto_symtab_entry_t entry2)
547 {
548   tree old_decl = entry1->decl;
549   tree new_decl = entry2->decl;
550   ld_plugin_symbol_resolution_t old_resolution = entry1->resolution;
551   ld_plugin_symbol_resolution_t new_resolution = entry2->resolution;
552   struct cgraph_node *old_node = NULL;
553   struct cgraph_node *new_node = NULL;
554
555   /* Give ODR violation errors.  */
556   if (new_resolution == LDPR_PREVAILING_DEF
557       || new_resolution == LDPR_PREVAILING_DEF_IRONLY)
558     {
559       if ((old_resolution == LDPR_PREVAILING_DEF
560            || old_resolution == LDPR_PREVAILING_DEF_IRONLY)
561           && (old_resolution != new_resolution || flag_no_common))
562         {
563           error_at (DECL_SOURCE_LOCATION (new_decl),
564                     "%qD has already been defined", new_decl);
565           inform (DECL_SOURCE_LOCATION (old_decl),
566                   "previously defined here");
567           return NULL;
568         }
569     }
570
571   /* The linker may ask us to combine two incompatible symbols.  */
572   if (!lto_symtab_compatible (old_decl, new_decl))
573     return NULL;
574
575   if (TREE_CODE (old_decl) == FUNCTION_DECL)
576     old_node = cgraph_get_node (old_decl);
577   if (TREE_CODE (new_decl) == FUNCTION_DECL)
578     new_node = cgraph_get_node (new_decl);
579
580   /* Merge decl state in both directions, we may still end up using
581      the new decl.  */
582   TREE_ADDRESSABLE (old_decl) |= TREE_ADDRESSABLE (new_decl);
583   TREE_ADDRESSABLE (new_decl) |= TREE_ADDRESSABLE (old_decl);
584
585   gcc_assert (new_resolution != LDPR_UNKNOWN
586               && new_resolution != LDPR_UNDEF
587               && old_resolution != LDPR_UNKNOWN
588               && old_resolution != LDPR_UNDEF);
589
590   if (new_resolution == LDPR_PREVAILING_DEF
591       || new_resolution == LDPR_PREVAILING_DEF_IRONLY
592       || (!old_node && new_node))
593     {
594       gcc_assert ((!old_node && new_node)
595                   || old_resolution == LDPR_PREEMPTED_IR
596                   || old_resolution ==  LDPR_RESOLVED_IR
597                   || (old_resolution == new_resolution && !flag_no_common));
598       if (old_node)
599         lto_cgraph_replace_node (old_node, new_node);
600       /* Choose new_decl, entry2.  */
601       return entry2;
602     }
603
604   if (new_resolution == LDPR_PREEMPTED_REG
605       || new_resolution == LDPR_RESOLVED_EXEC
606       || new_resolution == LDPR_RESOLVED_DYN)
607     gcc_assert (old_resolution == LDPR_PREEMPTED_REG
608                 || old_resolution == LDPR_RESOLVED_EXEC
609                 || old_resolution == LDPR_RESOLVED_DYN);
610
611   if (new_resolution == LDPR_PREEMPTED_IR
612       || new_resolution == LDPR_RESOLVED_IR)
613     gcc_assert (old_resolution == LDPR_PREVAILING_DEF
614                 || old_resolution == LDPR_PREVAILING_DEF_IRONLY
615                 || old_resolution == LDPR_PREEMPTED_IR
616                 || old_resolution == LDPR_RESOLVED_IR);
617
618   if (new_node)
619     lto_cgraph_replace_node (new_node, old_node);
620
621   /* Choose old_decl, entry1.  */
622   return entry1;
623 }
624
625 /* Resolve the symbol with the candidates in the chain *SLOT and store
626    their resolutions.  */
627
628 static void
629 lto_symtab_resolve_symbols (void **slot)
630 {
631   lto_symtab_entry_t e = (lto_symtab_entry_t) *slot;
632
633   /* If the chain is already resolved there is nothing to do.  */
634   if (e->resolution != LDPR_UNKNOWN)
635     return;
636
637   /* This is a poor mans resolver.  */
638   for (; e; e = e->next)
639     {
640       gcc_assert (e->resolution == LDPR_UNKNOWN);
641       if (DECL_EXTERNAL (e->decl)
642           || (TREE_CODE (e->decl) == FUNCTION_DECL
643               && !cgraph_get_node (e->decl)))
644         e->resolution = LDPR_RESOLVED_IR;
645       else
646         {
647           if (TREE_READONLY (e->decl))
648             e->resolution = LDPR_PREVAILING_DEF_IRONLY;
649           else
650             e->resolution = LDPR_PREVAILING_DEF;
651         }
652     }
653 }
654
655 /* Merge one symbol table chain to a (set of) prevailing decls.  */
656
657 static void
658 lto_symtab_merge_decls_2 (void **slot)
659 {
660   lto_symtab_entry_t e2, e1;
661
662   /* Nothing to do for a single entry.  */
663   e1 = (lto_symtab_entry_t) *slot;
664   if (!e1->next)
665     return;
666
667   /* Try to merge each entry with each other entry.  In case of a
668      single prevailing decl this is linear.  */
669 restart:
670   for (; e1; e1 = e1->next)
671     for (e2 = e1->next; e2; e2 = e2->next)
672       {
673         lto_symtab_entry_t prevailing = lto_symtab_merge (e1, e2);
674         if (prevailing == e1)
675           {
676             lto_symtab_entry_t tmp = prevailing;
677             while (tmp->next != e2)
678               tmp = tmp->next;
679             tmp->next = e2->next;
680             e2->next = NULL;
681             e2 = tmp;
682           }
683         else if (prevailing == e2)
684           {
685             lto_symtab_entry_t tmp = (lto_symtab_entry_t) *slot;
686             if (tmp == e1)
687               {
688                 *slot = e1->next;
689                 tmp = e1->next;
690               }
691             else
692               {
693                 while (tmp->next != e1)
694                   tmp = tmp->next;
695                 tmp->next = e1->next;
696               }
697             e1->next = NULL;
698             e1 = tmp;
699             goto restart;
700           }
701       }
702 }
703
704 /* Fixup the chain of prevailing variable decls *SLOT that are commonized
705    during link-time.  */
706
707 static void
708 lto_symtab_fixup_var_decls (void **slot)
709 {
710   lto_symtab_entry_t e = (lto_symtab_entry_t) *slot;
711   tree size = bitsize_zero_node;
712
713   /* Find the largest prevailing decl and move it to the front of the chain.
714      This is the decl we will output as representative for the common
715      section.  */
716   size = bitsize_zero_node;
717   if (e->resolution == LDPR_PREVAILING_DEF_IRONLY
718       || e->resolution == LDPR_PREVAILING_DEF)
719     size = DECL_SIZE (e->decl);
720   for (; e->next;)
721     {
722       lto_symtab_entry_t next = e->next;
723       if ((next->resolution == LDPR_PREVAILING_DEF_IRONLY
724            || next->resolution == LDPR_PREVAILING_DEF)
725           && tree_int_cst_lt (size, DECL_SIZE (next->decl)))
726         {
727           size = DECL_SIZE (next->decl);
728           e->next = next->next;
729           next->next = (lto_symtab_entry_t) *slot;
730           *slot = next;
731         }
732       else
733         e = next;
734     }
735
736   /* Mark everything apart from the first var as written out.  */
737   e = (lto_symtab_entry_t) *slot;
738   for (e = e->next; e; e = e->next)
739     TREE_ASM_WRITTEN (e->decl) = true;
740 }
741
742 /* Helper to process the decl chain for the symbol table entry *SLOT.  */
743
744 static int
745 lto_symtab_merge_decls_1 (void **slot, void *data ATTRIBUTE_UNUSED)
746 {
747   lto_symtab_entry_t e;
748
749   /* Compute the symbol resolutions.  */
750   lto_symtab_resolve_symbols (slot);
751
752   /* Register and adjust types of the entries.  */
753   for (e = (lto_symtab_entry_t) *slot; e; e = e->next)
754     TREE_TYPE (e->decl) = gimple_register_type (TREE_TYPE (e->decl));
755
756   /* Merge the chain to a (hopefully) single prevailing decl.  */
757   lto_symtab_merge_decls_2 (slot);
758
759   /* ???  Ideally we should delay all diagnostics until this point to
760      avoid duplicates.  */
761
762   /* All done for FUNCTION_DECLs.  */
763   e = (lto_symtab_entry_t) *slot;
764   if (TREE_CODE (e->decl) == FUNCTION_DECL)
765     return 1;
766
767   /* Fixup variables in case there are multiple prevailing ones.  */
768   if (e->next)
769     lto_symtab_fixup_var_decls (slot);
770
771   /* Insert all variable decls into the global variable decl vector.  */
772   for (e = (lto_symtab_entry_t) *slot; e; e = e->next)
773     VEC_safe_push (tree, gc, lto_global_var_decls, e->decl);
774
775   return 1;
776 }
777
778 /* Resolve and merge all symbol table chains to a prevailing decl.  */
779
780 void
781 lto_symtab_merge_decls (void)
782 {
783   lto_symtab_maybe_init_hash_table ();
784   htab_traverse (lto_symtab_identifiers, lto_symtab_merge_decls_1, NULL);
785 }
786
787
788 /* Given the decl DECL, return the prevailing decl with the same name. */
789
790 tree
791 lto_symtab_prevailing_decl (tree decl)
792 {
793   lto_symtab_entry_t ret;
794
795   /* Builtins and local symbols are their own prevailing decl.  */
796   if (!TREE_PUBLIC (decl) || is_builtin_fn (decl))
797     return decl;
798
799   /* DECL_ABSTRACTs are their own prevailng decl.  */
800   if (TREE_CODE (decl) == FUNCTION_DECL && DECL_ABSTRACT (decl))
801     return decl;
802
803   /* Ensure DECL_ASSEMBLER_NAME will not set assembler name.  */
804   gcc_assert (DECL_ASSEMBLER_NAME_SET_P (decl));
805
806   /* Walk through the list of candidates and return the one we merged to.  */
807   ret = lto_symtab_get (DECL_ASSEMBLER_NAME (decl));
808   if (!ret)
809     return NULL_TREE;
810
811   /* If there is only one candidate return it.  */
812   if (ret->next == NULL)
813     return ret->decl;
814
815   /* If there are multiple decls to choose from find the one we merged
816      with and return that.  */
817   while (ret)
818     {
819       if (gimple_types_compatible_p (TREE_TYPE (decl), TREE_TYPE (ret->decl)))
820         return ret->decl;
821
822       ret = ret->next;
823     }
824
825   gcc_unreachable ();
826 }
827
828 /* Remove any storage used to store resolution of DECL.  */
829
830 void
831 lto_symtab_clear_resolution (tree decl)
832 {
833   struct lto_symtab_entry_def temp;
834   lto_symtab_entry_t head;
835   void **slot;
836
837   if (!TREE_PUBLIC (decl))
838     return;
839
840   /* LTO FIXME: There should be no DECL_ABSTRACT in the middle end. */
841   if (TREE_CODE (decl) == FUNCTION_DECL && DECL_ABSTRACT (decl))
842     return;
843
844   gcc_assert (DECL_ASSEMBLER_NAME_SET_P (decl));
845
846   lto_symtab_maybe_init_hash_table ();
847   temp.id = DECL_ASSEMBLER_NAME (decl);
848   slot = htab_find_slot (lto_symtab_identifiers, &temp, NO_INSERT);
849   if (!*slot)
850     return;
851
852   head = (lto_symtab_entry_t) *slot;
853   if (head->decl == decl)
854     {
855       if (head->next)
856         {
857           *slot = head->next;
858           head->next = NULL;
859         }
860       else
861         htab_remove_elt (lto_symtab_identifiers, &temp);
862     }
863   else
864     {
865       lto_symtab_entry_t e;
866       while (head->next && head->next->decl != decl)
867         head = head->next;
868       if (head->next)
869         {
870           e = head->next;
871           head->next = e->next;
872           e->next = NULL;
873         }
874     }
875 }
876
877 #include "gt-lto-symtab.h"