2 Copyright 2009 Free Software Foundation, Inc.
3 Contributed by CodeSourcery, Inc.
5 This file is part of GCC.
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
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
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/>. */
23 #include "coretypes.h"
27 #include "ggc.h" /* lambda.h needs this */
28 #include "lambda.h" /* gcd */
30 #include "plugin-api.h"
31 #include "lto-streamer.h"
33 /* Vector to keep track of external variables we've seen so far. */
34 VEC(tree,gc) *lto_global_var_decls;
36 /* Symbol table entry. */
38 struct GTY(()) lto_symtab_entry_def
40 /* The symbol table entry key, an IDENTIFIER. */
42 /* The symbol table entry, a 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
51 struct lto_symtab_entry_def *next;
53 typedef struct lto_symtab_entry_def *lto_symtab_entry_t;
55 /* A poor man's symbol table. This hashes identifier to prevailing DECL
58 static GTY ((if_marked ("lto_symtab_entry_marked_p"),
59 param_is (struct lto_symtab_entry_def)))
60 htab_t lto_symtab_identifiers;
62 /* Return the hash value of an lto_symtab_entry_t object pointed to by P. */
65 lto_symtab_entry_hash (const void *p)
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));
72 /* Return non-zero if P1 and P2 points to lto_symtab_entry_def structs
73 corresponding to the same symbol. */
76 lto_symtab_entry_eq (const void *p1, const void *p2)
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);
85 /* Returns non-zero if P points to an lto_symtab_entry_def struct that needs
86 to be marked for GC. */
89 lto_symtab_entry_marked_p (const void *p)
91 const struct lto_symtab_entry_def *base =
92 (const struct lto_symtab_entry_def *) p;
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)));
99 /* Lazily initialize resolution hash tables. */
102 lto_symtab_maybe_init_hash_table (void)
104 if (lto_symtab_identifiers)
107 lto_symtab_identifiers =
108 htab_create_ggc (1021, lto_symtab_entry_hash,
109 lto_symtab_entry_eq, NULL);
112 static bool maybe_merge_incomplete_and_complete_type (tree, tree);
114 /* Try to merge an incomplete type INCOMPLETE with a complete type
115 COMPLETE of same kinds.
116 Return true if they were merged, false otherwise. */
119 merge_incomplete_and_complete_type (tree incomplete, tree complete)
121 /* For merging array types do some extra sanity checking. */
122 if (TREE_CODE (incomplete) == ARRAY_TYPE
123 && !maybe_merge_incomplete_and_complete_type (TREE_TYPE (incomplete),
124 TREE_TYPE (complete))
125 && !gimple_types_compatible_p (TREE_TYPE (incomplete),
126 TREE_TYPE (complete)))
129 /* ??? Ideally we would do this by means of a common canonical type, but
130 that's difficult as we do not have links from the canonical type
131 back to all its children. */
132 gimple_force_type_merge (incomplete, complete);
137 /* Try to merge a maybe complete / incomplete type pair TYPE1 and TYPE2.
138 Return true if they were merged, false otherwise. */
141 maybe_merge_incomplete_and_complete_type (tree type1, tree type2)
145 if (TREE_CODE (type1) != TREE_CODE (type2))
148 if (!COMPLETE_TYPE_P (type1) && COMPLETE_TYPE_P (type2))
149 res = merge_incomplete_and_complete_type (type1, type2);
150 else if (COMPLETE_TYPE_P (type1) && !COMPLETE_TYPE_P (type2))
151 res = merge_incomplete_and_complete_type (type2, type1);
153 /* Recurse on pointer targets. */
155 && POINTER_TYPE_P (type1)
156 && POINTER_TYPE_P (type2))
157 res = maybe_merge_incomplete_and_complete_type (TREE_TYPE (type1),
163 /* Check if OLD_DECL and NEW_DECL are compatible. */
166 lto_symtab_compatible (tree old_decl, tree new_decl)
168 tree old_type, new_type;
170 if (TREE_CODE (old_decl) != TREE_CODE (new_decl))
172 switch (TREE_CODE (new_decl))
175 gcc_assert (TREE_CODE (old_decl) == FUNCTION_DECL);
176 error_at (DECL_SOURCE_LOCATION (new_decl),
177 "function %qD redeclared as variable", new_decl);
178 inform (DECL_SOURCE_LOCATION (old_decl),
179 "previously declared here");
183 gcc_assert (TREE_CODE (old_decl) == VAR_DECL);
184 error_at (DECL_SOURCE_LOCATION (new_decl),
185 "variable %qD redeclared as function", new_decl);
186 inform (DECL_SOURCE_LOCATION (old_decl),
187 "previously declared here");
195 if (TREE_CODE (new_decl) == FUNCTION_DECL)
197 if (!gimple_types_compatible_p (TREE_TYPE (old_decl),
198 TREE_TYPE (new_decl)))
199 /* If we don't have a merged type yet...sigh. The linker
200 wouldn't complain if the types were mismatched, so we
201 probably shouldn't either. Just use the type from
202 whichever decl appears to be associated with the
203 definition. If for some odd reason neither decl is, the
210 /* Now we exclusively deal with VAR_DECLs. */
212 /* Handle external declarations with incomplete type or pointed-to
213 incomplete types by forcefully merging the types.
214 ??? In principle all types involved in the two decls should
215 be merged forcefully, for example without considering type or
217 old_type = TREE_TYPE (old_decl);
218 new_type = TREE_TYPE (new_decl);
220 if (DECL_EXTERNAL (old_decl) || DECL_EXTERNAL (new_decl))
221 maybe_merge_incomplete_and_complete_type (old_type, new_type);
222 else if (POINTER_TYPE_P (old_type)
223 && POINTER_TYPE_P (new_type))
224 maybe_merge_incomplete_and_complete_type (TREE_TYPE (old_type),
225 TREE_TYPE (new_type));
227 /* For array types we have to accept external declarations with
228 different sizes than the actual definition (164.gzip).
229 ??? We could emit a warning here. */
230 if (TREE_CODE (old_type) == TREE_CODE (new_type)
231 && TREE_CODE (old_type) == ARRAY_TYPE
232 && COMPLETE_TYPE_P (old_type)
233 && COMPLETE_TYPE_P (new_type)
234 && tree_int_cst_compare (TYPE_SIZE (old_type),
235 TYPE_SIZE (new_type)) != 0
236 && gimple_types_compatible_p (TREE_TYPE (old_type),
237 TREE_TYPE (new_type)))
239 /* If only one is external use the type of the non-external decl.
240 Else use the larger one and also adjust the decl size.
241 ??? Directional merging would allow us to simply pick the
242 larger one instead of rewriting it. */
243 if (DECL_EXTERNAL (old_decl) ^ DECL_EXTERNAL (new_decl))
245 if (DECL_EXTERNAL (old_decl))
246 TREE_TYPE (old_decl) = new_type;
247 else if (DECL_EXTERNAL (new_decl))
248 TREE_TYPE (new_decl) = old_type;
252 if (tree_int_cst_compare (TYPE_SIZE (old_type),
253 TYPE_SIZE (new_type)) < 0)
255 TREE_TYPE (old_decl) = new_type;
256 DECL_SIZE (old_decl) = DECL_SIZE (new_decl);
257 DECL_SIZE_UNIT (old_decl) = DECL_SIZE_UNIT (new_decl);
261 TREE_TYPE (new_decl) = old_type;
262 DECL_SIZE (new_decl) = DECL_SIZE (old_decl);
263 DECL_SIZE_UNIT (new_decl) = DECL_SIZE_UNIT (old_decl);
268 /* We can tolerate differences in type qualification, the
269 qualification of the prevailing definition will prevail. */
270 old_type = TYPE_MAIN_VARIANT (TREE_TYPE (old_decl));
271 new_type = TYPE_MAIN_VARIANT (TREE_TYPE (new_decl));
272 if (!gimple_types_compatible_p (old_type, new_type))
274 if (warning_at (DECL_SOURCE_LOCATION (new_decl), 0,
275 "type of %qD does not match original declaration",
277 inform (DECL_SOURCE_LOCATION (old_decl),
278 "previously declared here");
282 /* ??? We might want to emit a warning here if type qualification
283 differences were spotted. Do not do this unconditionally though. */
285 /* There is no point in comparing too many details of the decls here.
286 The type compatibility checks or the completing of types has properly
287 dealt with most issues. */
289 /* The following should all not invoke fatal errors as in non-LTO
290 mode the linker wouldn't complain either. Just emit warnings. */
292 /* Report a warning if user-specified alignments do not match. */
293 if ((DECL_USER_ALIGN (old_decl) && DECL_USER_ALIGN (new_decl))
294 && DECL_ALIGN (old_decl) != DECL_ALIGN (new_decl))
296 warning_at (DECL_SOURCE_LOCATION (new_decl), 0,
297 "alignment of %qD does not match original declaration",
299 inform (DECL_SOURCE_LOCATION (old_decl), "previously declared here");
306 /* Registers DECL with the LTO symbol table as having resolution RESOLUTION
307 and read from FILE_DATA. */
310 lto_symtab_register_decl (tree decl,
311 ld_plugin_symbol_resolution_t resolution,
312 struct lto_file_decl_data *file_data)
314 lto_symtab_entry_t new_entry;
317 /* Check that declarations reaching this function do not have
318 properties inconsistent with having external linkage. If any of
319 these asertions fail, then the object file reader has failed to
320 detect these cases and issue appropriate error messages. */
322 && TREE_PUBLIC (decl)
323 && (TREE_CODE (decl) == VAR_DECL
324 || TREE_CODE (decl) == FUNCTION_DECL)
325 && DECL_ASSEMBLER_NAME_SET_P (decl));
326 if (TREE_CODE (decl) == VAR_DECL)
327 gcc_assert (!(DECL_EXTERNAL (decl) && DECL_INITIAL (decl)));
328 if (TREE_CODE (decl) == FUNCTION_DECL)
329 gcc_assert (!DECL_ABSTRACT (decl));
331 new_entry = GGC_CNEW (struct lto_symtab_entry_def);
332 new_entry->id = DECL_ASSEMBLER_NAME (decl);
333 new_entry->decl = decl;
334 new_entry->resolution = resolution;
335 new_entry->file_data = file_data;
337 lto_symtab_maybe_init_hash_table ();
338 slot = htab_find_slot (lto_symtab_identifiers, new_entry, INSERT);
339 new_entry->next = (lto_symtab_entry_t) *slot;
343 /* Get the lto_symtab_entry_def struct associated with ID
346 static lto_symtab_entry_t
347 lto_symtab_get (tree id)
349 struct lto_symtab_entry_def temp;
352 lto_symtab_maybe_init_hash_table ();
354 slot = htab_find_slot (lto_symtab_identifiers, &temp, NO_INSERT);
355 return slot ? (lto_symtab_entry_t) *slot : NULL;
358 /* Get the linker resolution for DECL. */
360 enum ld_plugin_symbol_resolution
361 lto_symtab_get_resolution (tree decl)
363 lto_symtab_entry_t e;
365 gcc_assert (DECL_ASSEMBLER_NAME_SET_P (decl));
367 e = lto_symtab_get (DECL_ASSEMBLER_NAME (decl));
368 while (e && e->decl != decl)
373 return e->resolution;
376 /* Replace the cgraph node OLD_NODE with NEW_NODE in the cgraph, merging
377 all edges and removing the old node. */
380 lto_cgraph_replace_node (struct cgraph_node *old_node,
381 struct cgraph_node *new_node)
383 struct cgraph_edge *e, *next;
385 /* Merge node flags. */
386 if (old_node->needed)
387 cgraph_mark_needed_node (new_node);
388 if (old_node->reachable)
389 cgraph_mark_reachable_node (new_node);
390 if (old_node->address_taken)
391 cgraph_mark_address_taken_node (new_node);
393 /* Redirect all incoming edges. */
394 for (e = old_node->callers; e; e = next)
396 next = e->next_caller;
397 cgraph_redirect_edge_callee (e, new_node);
400 /* There are not supposed to be any outgoing edges from a node we
401 replace. Still this can happen for multiple instances of weak
403 ??? For now do what the old code did. Do not create edges for them. */
404 for (e = old_node->callees; e; e = next)
406 next = e->next_callee;
407 cgraph_remove_edge (e);
410 /* Finally remove the replaced node. */
411 cgraph_remove_node (old_node);
414 /* Merge two variable or function symbol table entries ENTRY1 and ENTRY2.
415 Return the prevailing one or NULL if a merge is not possible. */
417 static lto_symtab_entry_t
418 lto_symtab_merge (lto_symtab_entry_t entry1, lto_symtab_entry_t entry2)
420 tree old_decl = entry1->decl;
421 tree new_decl = entry2->decl;
422 ld_plugin_symbol_resolution_t old_resolution = entry1->resolution;
423 ld_plugin_symbol_resolution_t new_resolution = entry2->resolution;
424 struct cgraph_node *old_node = NULL;
425 struct cgraph_node *new_node = NULL;
427 /* Give ODR violation errors. */
428 if (new_resolution == LDPR_PREVAILING_DEF
429 || new_resolution == LDPR_PREVAILING_DEF_IRONLY)
431 if ((old_resolution == LDPR_PREVAILING_DEF
432 || old_resolution == LDPR_PREVAILING_DEF_IRONLY)
433 && (old_resolution != new_resolution || flag_no_common))
435 error_at (DECL_SOURCE_LOCATION (new_decl),
436 "%qD has already been defined", new_decl);
437 inform (DECL_SOURCE_LOCATION (old_decl),
438 "previously defined here");
443 /* The linker may ask us to combine two incompatible symbols. */
444 if (!lto_symtab_compatible (old_decl, new_decl))
447 if (TREE_CODE (old_decl) == FUNCTION_DECL)
448 old_node = cgraph_get_node (old_decl);
449 if (TREE_CODE (new_decl) == FUNCTION_DECL)
450 new_node = cgraph_get_node (new_decl);
452 /* Merge decl state in both directions, we may still end up using
454 TREE_ADDRESSABLE (old_decl) |= TREE_ADDRESSABLE (new_decl);
455 TREE_ADDRESSABLE (new_decl) |= TREE_ADDRESSABLE (old_decl);
457 gcc_assert (new_resolution != LDPR_UNKNOWN
458 && new_resolution != LDPR_UNDEF
459 && old_resolution != LDPR_UNKNOWN
460 && old_resolution != LDPR_UNDEF);
462 if (new_resolution == LDPR_PREVAILING_DEF
463 || new_resolution == LDPR_PREVAILING_DEF_IRONLY
464 || (!old_node && new_node))
466 gcc_assert ((!old_node && new_node)
467 || old_resolution == LDPR_PREEMPTED_IR
468 || old_resolution == LDPR_RESOLVED_IR
469 || (old_resolution == new_resolution && !flag_no_common));
471 lto_cgraph_replace_node (old_node, new_node);
472 /* Choose new_decl, entry2. */
476 if (new_resolution == LDPR_PREEMPTED_REG
477 || new_resolution == LDPR_RESOLVED_EXEC
478 || new_resolution == LDPR_RESOLVED_DYN)
479 gcc_assert (old_resolution == LDPR_PREEMPTED_REG
480 || old_resolution == LDPR_RESOLVED_EXEC
481 || old_resolution == LDPR_RESOLVED_DYN);
483 if (new_resolution == LDPR_PREEMPTED_IR
484 || new_resolution == LDPR_RESOLVED_IR)
485 gcc_assert (old_resolution == LDPR_PREVAILING_DEF
486 || old_resolution == LDPR_PREVAILING_DEF_IRONLY
487 || old_resolution == LDPR_PREEMPTED_IR
488 || old_resolution == LDPR_RESOLVED_IR);
491 lto_cgraph_replace_node (new_node, old_node);
493 /* Choose old_decl, entry1. */
497 /* Resolve the symbol with the candidates in the chain *SLOT and store
498 their resolutions. */
501 lto_symtab_resolve_symbols (void **slot)
503 lto_symtab_entry_t e = (lto_symtab_entry_t) *slot;
505 /* If the chain is already resolved there is nothing to do. */
506 if (e->resolution != LDPR_UNKNOWN)
509 /* This is a poor mans resolver. */
510 for (; e; e = e->next)
512 gcc_assert (e->resolution == LDPR_UNKNOWN);
513 if (DECL_EXTERNAL (e->decl)
514 || (TREE_CODE (e->decl) == FUNCTION_DECL
515 && !cgraph_get_node (e->decl)))
516 e->resolution = LDPR_RESOLVED_IR;
519 if (TREE_READONLY (e->decl))
520 e->resolution = LDPR_PREVAILING_DEF_IRONLY;
522 e->resolution = LDPR_PREVAILING_DEF;
527 /* Merge one symbol table chain to a (set of) prevailing decls. */
530 lto_symtab_merge_decls_2 (void **slot)
532 lto_symtab_entry_t e2, e1;
534 /* Nothing to do for a single entry. */
535 e1 = (lto_symtab_entry_t) *slot;
539 /* Try to merge each entry with each other entry. In case of a
540 single prevailing decl this is linear. */
542 for (; e1; e1 = e1->next)
543 for (e2 = e1->next; e2; e2 = e2->next)
545 lto_symtab_entry_t prevailing = lto_symtab_merge (e1, e2);
546 if (prevailing == e1)
548 lto_symtab_entry_t tmp = prevailing;
549 while (tmp->next != e2)
551 tmp->next = e2->next;
555 else if (prevailing == e2)
557 lto_symtab_entry_t tmp = (lto_symtab_entry_t) *slot;
565 while (tmp->next != e1)
567 tmp->next = e1->next;
576 /* Fixup the chain of prevailing variable decls *SLOT that are commonized
580 lto_symtab_fixup_var_decls (void **slot)
582 lto_symtab_entry_t e = (lto_symtab_entry_t) *slot;
583 tree size = bitsize_zero_node;
585 /* Find the largest prevailing decl and move it to the front of the chain.
586 This is the decl we will output as representative for the common
588 size = bitsize_zero_node;
589 if (e->resolution == LDPR_PREVAILING_DEF_IRONLY
590 || e->resolution == LDPR_PREVAILING_DEF)
591 size = DECL_SIZE (e->decl);
594 lto_symtab_entry_t next = e->next;
595 if ((next->resolution == LDPR_PREVAILING_DEF_IRONLY
596 || next->resolution == LDPR_PREVAILING_DEF)
597 && tree_int_cst_lt (size, DECL_SIZE (next->decl)))
599 size = DECL_SIZE (next->decl);
600 e->next = next->next;
601 next->next = (lto_symtab_entry_t) *slot;
608 /* Mark everything apart from the first var as written out. */
609 e = (lto_symtab_entry_t) *slot;
610 for (e = e->next; e; e = e->next)
611 TREE_ASM_WRITTEN (e->decl) = true;
614 /* Helper to process the decl chain for the symbol table entry *SLOT. */
617 lto_symtab_merge_decls_1 (void **slot, void *data ATTRIBUTE_UNUSED)
619 lto_symtab_entry_t e;
621 /* Compute the symbol resolutions. */
622 lto_symtab_resolve_symbols (slot);
624 /* Register and adjust types of the entries. */
625 for (e = (lto_symtab_entry_t) *slot; e; e = e->next)
626 TREE_TYPE (e->decl) = gimple_register_type (TREE_TYPE (e->decl));
628 /* Merge the chain to a (hopefully) single prevailing decl. */
629 lto_symtab_merge_decls_2 (slot);
631 /* ??? Ideally we should delay all diagnostics until this point to
634 /* All done for FUNCTION_DECLs. */
635 e = (lto_symtab_entry_t) *slot;
636 if (TREE_CODE (e->decl) == FUNCTION_DECL)
639 /* Fixup variables in case there are multiple prevailing ones. */
641 lto_symtab_fixup_var_decls (slot);
643 /* Insert all variable decls into the global variable decl vector. */
644 for (e = (lto_symtab_entry_t) *slot; e; e = e->next)
645 VEC_safe_push (tree, gc, lto_global_var_decls, e->decl);
650 /* Resolve and merge all symbol table chains to a prevailing decl. */
653 lto_symtab_merge_decls (void)
655 lto_symtab_maybe_init_hash_table ();
656 htab_traverse (lto_symtab_identifiers, lto_symtab_merge_decls_1, NULL);
660 /* Given the decl DECL, return the prevailing decl with the same name. */
663 lto_symtab_prevailing_decl (tree decl)
665 lto_symtab_entry_t ret;
667 /* Builtins and local symbols are their own prevailing decl. */
668 if (!TREE_PUBLIC (decl) || is_builtin_fn (decl))
671 /* DECL_ABSTRACTs are their own prevailng decl. */
672 if (TREE_CODE (decl) == FUNCTION_DECL && DECL_ABSTRACT (decl))
675 /* Ensure DECL_ASSEMBLER_NAME will not set assembler name. */
676 gcc_assert (DECL_ASSEMBLER_NAME_SET_P (decl));
678 /* Walk through the list of candidates and return the one we merged to. */
679 ret = lto_symtab_get (DECL_ASSEMBLER_NAME (decl));
683 /* If there is only one candidate return it. */
684 if (ret->next == NULL)
687 /* If there are multiple decls to choose from find the one we merged
688 with and return that. */
691 if (gimple_types_compatible_p (TREE_TYPE (decl), TREE_TYPE (ret->decl)))
700 /* Remove any storage used to store resolution of DECL. */
703 lto_symtab_clear_resolution (tree decl)
705 struct lto_symtab_entry_def temp;
706 lto_symtab_entry_t head;
709 if (!TREE_PUBLIC (decl))
712 /* LTO FIXME: There should be no DECL_ABSTRACT in the middle end. */
713 if (TREE_CODE (decl) == FUNCTION_DECL && DECL_ABSTRACT (decl))
716 gcc_assert (DECL_ASSEMBLER_NAME_SET_P (decl));
718 lto_symtab_maybe_init_hash_table ();
719 temp.id = DECL_ASSEMBLER_NAME (decl);
720 slot = htab_find_slot (lto_symtab_identifiers, &temp, NO_INSERT);
724 head = (lto_symtab_entry_t) *slot;
725 if (head->decl == decl)
733 htab_remove_elt (lto_symtab_identifiers, &temp);
737 lto_symtab_entry_t e;
738 while (head->next && head->next->decl != decl)
743 head->next = e->next;
749 #include "gt-lto-symtab.h"