don't compare ARG_FRAME_POINTER_REGNUM and FRAME_POINTER_REGNUM with the preprocessor
[official-gcc.git] / gcc / ipa-devirt.c
blob09c3b5b045586ef42ded142369ddb8fb3030f1c2
1 /* Basic IPA utilities for type inheritance graph construction and
2 devirtualization.
3 Copyright (C) 2013-2015 Free Software Foundation, Inc.
4 Contributed by Jan Hubicka
6 This file is part of GCC.
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.
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.
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/>. */
22 /* Brief vocabulary:
23 ODR = One Definition Rule
24 In short, the ODR states that:
25 1 In any translation unit, a template, type, function, or object can
26 have no more than one definition. Some of these can have any number
27 of declarations. A definition provides an instance.
28 2 In the entire program, an object or non-inline function cannot have
29 more than one definition; if an object or function is used, it must
30 have exactly one definition. You can declare an object or function
31 that is never used, in which case you don't have to provide
32 a definition. In no event can there be more than one definition.
33 3 Some things, like types, templates, and extern inline functions, can
34 be defined in more than one translation unit. For a given entity,
35 each definition must be the same. Non-extern objects and functions
36 in different translation units are different entities, even if their
37 names and types are the same.
39 OTR = OBJ_TYPE_REF
40 This is the Gimple representation of type information of a polymorphic call.
41 It contains two parameters:
42 otr_type is a type of class whose method is called.
43 otr_token is the index into virtual table where address is taken.
45 BINFO
46 This is the type inheritance information attached to each tree
47 RECORD_TYPE by the C++ frontend. It provides information about base
48 types and virtual tables.
50 BINFO is linked to the RECORD_TYPE by TYPE_BINFO.
51 BINFO also links to its type by BINFO_TYPE and to the virtual table by
52 BINFO_VTABLE.
54 Base types of a given type are enumerated by BINFO_BASE_BINFO
55 vector. Members of this vectors are not BINFOs associated
56 with a base type. Rather they are new copies of BINFOs
57 (base BINFOs). Their virtual tables may differ from
58 virtual table of the base type. Also BINFO_OFFSET specifies
59 offset of the base within the type.
61 In the case of single inheritance, the virtual table is shared
62 and BINFO_VTABLE of base BINFO is NULL. In the case of multiple
63 inheritance the individual virtual tables are pointer to by
64 BINFO_VTABLE of base binfos (that differs of BINFO_VTABLE of
65 binfo associated to the base type).
67 BINFO lookup for a given base type and offset can be done by
68 get_binfo_at_offset. It returns proper BINFO whose virtual table
69 can be used for lookup of virtual methods associated with the
70 base type.
72 token
73 This is an index of virtual method in virtual table associated
74 to the type defining it. Token can be looked up from OBJ_TYPE_REF
75 or from DECL_VINDEX of a given virtual table.
77 polymorphic (indirect) call
78 This is callgraph representation of virtual method call. Every
79 polymorphic call contains otr_type and otr_token taken from
80 original OBJ_TYPE_REF at callgraph construction time.
82 What we do here:
84 build_type_inheritance_graph triggers a construction of the type inheritance
85 graph.
87 We reconstruct it based on types of methods we see in the unit.
88 This means that the graph is not complete. Types with no methods are not
89 inserted into the graph. Also types without virtual methods are not
90 represented at all, though it may be easy to add this.
92 The inheritance graph is represented as follows:
94 Vertices are structures odr_type. Every odr_type may correspond
95 to one or more tree type nodes that are equivalent by ODR rule.
96 (the multiple type nodes appear only with linktime optimization)
98 Edges are represented by odr_type->base and odr_type->derived_types.
99 At the moment we do not track offsets of types for multiple inheritance.
100 Adding this is easy.
102 possible_polymorphic_call_targets returns, given an parameters found in
103 indirect polymorphic edge all possible polymorphic call targets of the call.
105 pass_ipa_devirt performs simple speculative devirtualization.
108 #include "config.h"
109 #include "system.h"
110 #include "coretypes.h"
111 #include "tm.h"
112 #include "hash-set.h"
113 #include "machmode.h"
114 #include "hash-map.h"
115 #include "vec.h"
116 #include "double-int.h"
117 #include "input.h"
118 #include "alias.h"
119 #include "symtab.h"
120 #include "wide-int.h"
121 #include "inchash.h"
122 #include "tree.h"
123 #include "fold-const.h"
124 #include "print-tree.h"
125 #include "calls.h"
126 #include "predict.h"
127 #include "basic-block.h"
128 #include "is-a.h"
129 #include "plugin-api.h"
130 #include "hard-reg-set.h"
131 #include "function.h"
132 #include "ipa-ref.h"
133 #include "cgraph.h"
134 #include "hashtab.h"
135 #include "rtl.h"
136 #include "flags.h"
137 #include "statistics.h"
138 #include "real.h"
139 #include "fixed-value.h"
140 #include "insn-config.h"
141 #include "expmed.h"
142 #include "dojump.h"
143 #include "explow.h"
144 #include "emit-rtl.h"
145 #include "varasm.h"
146 #include "stmt.h"
147 #include "expr.h"
148 #include "tree-pass.h"
149 #include "target.h"
150 #include "hash-table.h"
151 #include "tree-pretty-print.h"
152 #include "ipa-utils.h"
153 #include "tree-ssa-alias.h"
154 #include "internal-fn.h"
155 #include "gimple-fold.h"
156 #include "gimple-expr.h"
157 #include "gimple.h"
158 #include "alloc-pool.h"
159 #include "symbol-summary.h"
160 #include "ipa-prop.h"
161 #include "ipa-inline.h"
162 #include "diagnostic.h"
163 #include "tree-dfa.h"
164 #include "demangle.h"
165 #include "dbgcnt.h"
166 #include "gimple-pretty-print.h"
167 #include "stor-layout.h"
168 #include "intl.h"
169 #include "streamer-hooks.h"
170 #include "lto-streamer.h"
172 /* Hash based set of pairs of types. */
173 typedef struct
175 tree first;
176 tree second;
177 } type_pair;
179 struct pair_traits : default_hashset_traits
181 static hashval_t
182 hash (type_pair p)
184 return TYPE_UID (p.first) ^ TYPE_UID (p.second);
186 static bool
187 is_empty (type_pair p)
189 return p.first == NULL;
191 static bool
192 is_deleted (type_pair p ATTRIBUTE_UNUSED)
194 return false;
196 static bool
197 equal (const type_pair &a, const type_pair &b)
199 return a.first==b.first && a.second == b.second;
201 static void
202 mark_empty (type_pair &e)
204 e.first = NULL;
208 static bool odr_types_equivalent_p (tree, tree, bool, bool *,
209 hash_set<type_pair,pair_traits> *);
211 static bool odr_violation_reported = false;
214 /* Pointer set of all call targets appearing in the cache. */
215 static hash_set<cgraph_node *> *cached_polymorphic_call_targets;
217 /* The node of type inheritance graph. For each type unique in
218 One Definition Rule (ODR) sense, we produce one node linking all
219 main variants of types equivalent to it, bases and derived types. */
221 struct GTY(()) odr_type_d
223 /* leader type. */
224 tree type;
225 /* All bases; built only for main variants of types. */
226 vec<odr_type> GTY((skip)) bases;
227 /* All derived types with virtual methods seen in unit;
228 built only for main variants of types. */
229 vec<odr_type> GTY((skip)) derived_types;
231 /* All equivalent types, if more than one. */
232 vec<tree, va_gc> *types;
233 /* Set of all equivalent types, if NON-NULL. */
234 hash_set<tree> * GTY((skip)) types_set;
236 /* Unique ID indexing the type in odr_types array. */
237 int id;
238 /* Is it in anonymous namespace? */
239 bool anonymous_namespace;
240 /* Do we know about all derivations of given type? */
241 bool all_derivations_known;
242 /* Did we report ODR violation here? */
243 bool odr_violated;
244 /* Set when virtual table without RTTI previaled table with. */
245 bool rtti_broken;
248 /* Return true if T is a type with linkage defined. */
250 bool
251 type_with_linkage_p (const_tree t)
253 /* Builtin types do not define linkage, their TYPE_CONTEXT is NULL. */
254 if (!TYPE_CONTEXT (t)
255 || !TYPE_NAME (t) || TREE_CODE (TYPE_NAME (t)) != TYPE_DECL)
256 return false;
258 return (RECORD_OR_UNION_TYPE_P (t)
259 || TREE_CODE (t) == ENUMERAL_TYPE);
262 /* Return true if T is in anonymous namespace.
263 This works only on those C++ types with linkage defined. */
265 bool
266 type_in_anonymous_namespace_p (const_tree t)
268 gcc_assert (type_with_linkage_p (t));
270 if (TYPE_STUB_DECL (t) && !TREE_PUBLIC (TYPE_STUB_DECL (t)))
272 if (DECL_ARTIFICIAL (TYPE_NAME (t)))
273 return true;
274 tree ctx = DECL_CONTEXT (TYPE_NAME (t));
275 while (ctx)
277 if (TREE_CODE (ctx) == NAMESPACE_DECL)
278 return !TREE_PUBLIC (ctx);
279 if (TREE_CODE (ctx) == BLOCK)
280 ctx = BLOCK_SUPERCONTEXT (ctx);
281 else
282 ctx = get_containing_scope (ctx);
285 return false;
288 /* Return true of T is type with One Definition Rule info attached.
289 It means that either it is anonymous type or it has assembler name
290 set. */
292 bool
293 odr_type_p (const_tree t)
295 if (type_with_linkage_p (t) && type_in_anonymous_namespace_p (t))
296 return true;
297 /* We do not have this information when not in LTO, but we do not need
298 to care, since it is used only for type merging. */
299 gcc_checking_assert (in_lto_p || flag_lto);
301 return (TYPE_NAME (t) && TREE_CODE (TYPE_NAME (t)) == TYPE_DECL
302 && (DECL_ASSEMBLER_NAME_SET_P (TYPE_NAME (t))));
305 /* Return TRUE if all derived types of T are known and thus
306 we may consider the walk of derived type complete.
308 This is typically true only for final anonymous namespace types and types
309 defined within functions (that may be COMDAT and thus shared across units,
310 but with the same set of derived types). */
312 bool
313 type_all_derivations_known_p (const_tree t)
315 if (TYPE_FINAL_P (t))
316 return true;
317 if (flag_ltrans)
318 return false;
319 /* Non-C++ types may have IDENTIFIER_NODE here, do not crash. */
320 if (!TYPE_NAME (t) || TREE_CODE (TYPE_NAME (t)) != TYPE_DECL)
321 return true;
322 if (type_in_anonymous_namespace_p (t))
323 return true;
324 return (decl_function_context (TYPE_NAME (t)) != NULL);
327 /* Return TRUE if type's constructors are all visible. */
329 static bool
330 type_all_ctors_visible_p (tree t)
332 return !flag_ltrans
333 && symtab->state >= CONSTRUCTION
334 /* We can not always use type_all_derivations_known_p.
335 For function local types we must assume case where
336 the function is COMDAT and shared in between units.
338 TODO: These cases are quite easy to get, but we need
339 to keep track of C++ privatizing via -Wno-weak
340 as well as the IPA privatizing. */
341 && type_in_anonymous_namespace_p (t);
344 /* Return TRUE if type may have instance. */
346 static bool
347 type_possibly_instantiated_p (tree t)
349 tree vtable;
350 varpool_node *vnode;
352 /* TODO: Add abstract types here. */
353 if (!type_all_ctors_visible_p (t))
354 return true;
356 vtable = BINFO_VTABLE (TYPE_BINFO (t));
357 if (TREE_CODE (vtable) == POINTER_PLUS_EXPR)
358 vtable = TREE_OPERAND (TREE_OPERAND (vtable, 0), 0);
359 vnode = varpool_node::get (vtable);
360 return vnode && vnode->definition;
363 /* Hash used to unify ODR types based on their mangled name and for anonymous
364 namespace types. */
366 struct odr_name_hasher
368 typedef odr_type_d *value_type;
369 typedef union tree_node *compare_type;
370 static inline hashval_t hash (const odr_type_d *);
371 static inline bool equal (const odr_type_d *, const tree_node *);
372 static inline void remove (odr_type_d *);
375 /* Has used to unify ODR types based on their associated virtual table.
376 This hash is needed to keep -fno-lto-odr-type-merging to work and contains
377 only polymorphic types. Types with mangled names are inserted to both. */
379 struct odr_vtable_hasher:odr_name_hasher
381 static inline hashval_t hash (const odr_type_d *);
382 static inline bool equal (const odr_type_d *, const tree_node *);
385 /* Return type that was declared with T's name so that T is an
386 qualified variant of it. */
388 static inline tree
389 main_odr_variant (const_tree t)
391 if (TYPE_NAME (t) && TREE_CODE (TYPE_NAME (t)) == TYPE_DECL)
392 return TREE_TYPE (TYPE_NAME (t));
393 /* Unnamed types and non-C++ produced types can be compared by variants. */
394 else
395 return TYPE_MAIN_VARIANT (t);
398 static bool
399 can_be_name_hashed_p (tree t)
401 return (!in_lto_p || odr_type_p (t));
404 /* Hash type by its ODR name. */
406 static hashval_t
407 hash_odr_name (const_tree t)
409 gcc_checking_assert (main_odr_variant (t) == t);
411 /* If not in LTO, all main variants are unique, so we can do
412 pointer hash. */
413 if (!in_lto_p)
414 return htab_hash_pointer (t);
416 /* Anonymous types are unique. */
417 if (type_with_linkage_p (t) && type_in_anonymous_namespace_p (t))
418 return htab_hash_pointer (t);
420 gcc_checking_assert (TYPE_NAME (t)
421 && DECL_ASSEMBLER_NAME_SET_P (TYPE_NAME (t)));
422 return IDENTIFIER_HASH_VALUE (DECL_ASSEMBLER_NAME (TYPE_NAME (t)));
425 /* Return the computed hashcode for ODR_TYPE. */
427 inline hashval_t
428 odr_name_hasher::hash (const odr_type_d *odr_type)
430 return hash_odr_name (odr_type->type);
433 static bool
434 can_be_vtable_hashed_p (tree t)
436 /* vtable hashing can distinguish only main variants. */
437 if (TYPE_MAIN_VARIANT (t) != t)
438 return false;
439 /* Anonymous namespace types are always handled by name hash. */
440 if (type_with_linkage_p (t) && type_in_anonymous_namespace_p (t))
441 return false;
442 return (TREE_CODE (t) == RECORD_TYPE
443 && TYPE_BINFO (t) && BINFO_VTABLE (TYPE_BINFO (t)));
446 /* Hash type by assembler name of its vtable. */
448 static hashval_t
449 hash_odr_vtable (const_tree t)
451 tree v = BINFO_VTABLE (TYPE_BINFO (TYPE_MAIN_VARIANT (t)));
452 inchash::hash hstate;
454 gcc_checking_assert (in_lto_p);
455 gcc_checking_assert (!type_in_anonymous_namespace_p (t));
456 gcc_checking_assert (TREE_CODE (t) == RECORD_TYPE
457 && TYPE_BINFO (t) && BINFO_VTABLE (TYPE_BINFO (t)));
458 gcc_checking_assert (main_odr_variant (t) == t);
460 if (TREE_CODE (v) == POINTER_PLUS_EXPR)
462 add_expr (TREE_OPERAND (v, 1), hstate);
463 v = TREE_OPERAND (TREE_OPERAND (v, 0), 0);
466 hstate.add_wide_int (IDENTIFIER_HASH_VALUE (DECL_ASSEMBLER_NAME (v)));
467 return hstate.end ();
470 /* Return the computed hashcode for ODR_TYPE. */
472 inline hashval_t
473 odr_vtable_hasher::hash (const odr_type_d *odr_type)
475 return hash_odr_vtable (odr_type->type);
478 /* For languages with One Definition Rule, work out if
479 types are the same based on their name.
481 This is non-trivial for LTO where minor differences in
482 the type representation may have prevented type merging
483 to merge two copies of otherwise equivalent type.
485 Until we start streaming mangled type names, this function works
486 only for polymorphic types.
488 When STRICT is true, we compare types by their names for purposes of
489 ODR violation warnings. When strict is false, we consider variants
490 equivalent, becuase it is all that matters for devirtualization machinery.
493 bool
494 types_same_for_odr (const_tree type1, const_tree type2, bool strict)
496 gcc_checking_assert (TYPE_P (type1) && TYPE_P (type2));
498 type1 = main_odr_variant (type1);
499 type2 = main_odr_variant (type2);
500 if (!strict)
502 type1 = TYPE_MAIN_VARIANT (type1);
503 type2 = TYPE_MAIN_VARIANT (type2);
506 if (type1 == type2)
507 return true;
509 if (!in_lto_p)
510 return false;
512 /* Check for anonymous namespaces. Those have !TREE_PUBLIC
513 on the corresponding TYPE_STUB_DECL. */
514 if ((type_with_linkage_p (type1) && type_in_anonymous_namespace_p (type1))
515 || (type_with_linkage_p (type2) && type_in_anonymous_namespace_p (type2)))
516 return false;
519 /* ODR name of the type is set in DECL_ASSEMBLER_NAME of its TYPE_NAME.
521 Ideally we should never need types without ODR names here. It can however
522 happen in two cases:
524 1) for builtin types that are not streamed but rebuilt in lto/lto-lang.c
525 Here testing for equivalence is safe, since their MAIN_VARIANTs are
526 unique.
527 2) for units streamed with -fno-lto-odr-type-merging. Here we can't
528 establish precise ODR equivalency, but for correctness we care only
529 about equivalency on complete polymorphic types. For these we can
530 compare assembler names of their virtual tables. */
531 if ((!TYPE_NAME (type1) || !DECL_ASSEMBLER_NAME_SET_P (TYPE_NAME (type1)))
532 || (!TYPE_NAME (type2) || !DECL_ASSEMBLER_NAME_SET_P (TYPE_NAME (type2))))
534 /* See if types are obviously different (i.e. different codes
535 or polymorphic wrt non-polymorphic). This is not strictly correct
536 for ODR violating programs, but we can't do better without streaming
537 ODR names. */
538 if (TREE_CODE (type1) != TREE_CODE (type2))
539 return false;
540 if (TREE_CODE (type1) == RECORD_TYPE
541 && (TYPE_BINFO (type1) == NULL_TREE)
542 != (TYPE_BINFO (type1) == NULL_TREE))
543 return false;
544 if (TREE_CODE (type1) == RECORD_TYPE && TYPE_BINFO (type1)
545 && (BINFO_VTABLE (TYPE_BINFO (type1)) == NULL_TREE)
546 != (BINFO_VTABLE (TYPE_BINFO (type2)) == NULL_TREE))
547 return false;
549 /* At the moment we have no way to establish ODR equivalence at LTO
550 other than comparing virtual table pointers of polymorphic types.
551 Eventually we should start saving mangled names in TYPE_NAME.
552 Then this condition will become non-trivial. */
554 if (TREE_CODE (type1) == RECORD_TYPE
555 && TYPE_BINFO (type1) && TYPE_BINFO (type2)
556 && BINFO_VTABLE (TYPE_BINFO (type1))
557 && BINFO_VTABLE (TYPE_BINFO (type2)))
559 tree v1 = BINFO_VTABLE (TYPE_BINFO (type1));
560 tree v2 = BINFO_VTABLE (TYPE_BINFO (type2));
561 gcc_assert (TREE_CODE (v1) == POINTER_PLUS_EXPR
562 && TREE_CODE (v2) == POINTER_PLUS_EXPR);
563 return (operand_equal_p (TREE_OPERAND (v1, 1),
564 TREE_OPERAND (v2, 1), 0)
565 && DECL_ASSEMBLER_NAME
566 (TREE_OPERAND (TREE_OPERAND (v1, 0), 0))
567 == DECL_ASSEMBLER_NAME
568 (TREE_OPERAND (TREE_OPERAND (v2, 0), 0)));
570 gcc_unreachable ();
572 return (DECL_ASSEMBLER_NAME (TYPE_NAME (type1))
573 == DECL_ASSEMBLER_NAME (TYPE_NAME (type2)));
576 /* Return true if we can decide on ODR equivalency.
578 In non-LTO it is always decide, in LTO however it depends in the type has
579 ODR info attached.
581 When STRICT is false, compare main variants. */
583 bool
584 types_odr_comparable (tree t1, tree t2, bool strict)
586 return (!in_lto_p
587 || (strict ? main_odr_variant (t1) == main_odr_variant (t2)
588 : TYPE_MAIN_VARIANT (t1) == TYPE_MAIN_VARIANT (t2))
589 || (odr_type_p (t1) && odr_type_p (t2))
590 || (TREE_CODE (t1) == RECORD_TYPE && TREE_CODE (t2) == RECORD_TYPE
591 && TYPE_BINFO (t1) && TYPE_BINFO (t2)
592 && polymorphic_type_binfo_p (TYPE_BINFO (t1))
593 && polymorphic_type_binfo_p (TYPE_BINFO (t2))));
596 /* Return true if T1 and T2 are ODR equivalent. If ODR equivalency is not
597 known, be conservative and return false. */
599 bool
600 types_must_be_same_for_odr (tree t1, tree t2)
602 if (types_odr_comparable (t1, t2))
603 return types_same_for_odr (t1, t2);
604 else
605 return TYPE_MAIN_VARIANT (t1) == TYPE_MAIN_VARIANT (t2);
608 /* If T is compound type, return type it is based on. */
610 static tree
611 compound_type_base (const_tree t)
613 if (TREE_CODE (t) == ARRAY_TYPE
614 || POINTER_TYPE_P (t)
615 || TREE_CODE (t) == COMPLEX_TYPE
616 || VECTOR_TYPE_P (t))
617 return TREE_TYPE (t);
618 if (TREE_CODE (t) == METHOD_TYPE)
619 return TYPE_METHOD_BASETYPE (t);
620 if (TREE_CODE (t) == OFFSET_TYPE)
621 return TYPE_OFFSET_BASETYPE (t);
622 return NULL_TREE;
625 /* Return true if T is either ODR type or compound type based from it.
626 If the function return true, we know that T is a type originating from C++
627 source even at link-time. */
629 bool
630 odr_or_derived_type_p (const_tree t)
634 if (odr_type_p (t))
635 return true;
636 /* Function type is a tricky one. Basically we can consider it
637 ODR derived if return type or any of the parameters is.
638 We need to check all parameters because LTO streaming merges
639 common types (such as void) and they are not considered ODR then. */
640 if (TREE_CODE (t) == FUNCTION_TYPE)
642 if (TYPE_METHOD_BASETYPE (t))
643 t = TYPE_METHOD_BASETYPE (t);
644 else
646 if (TREE_TYPE (t) && odr_or_derived_type_p (TREE_TYPE (t)))
647 return true;
648 for (t = TYPE_ARG_TYPES (t); t; t = TREE_CHAIN (t))
649 if (odr_or_derived_type_p (TREE_VALUE (t)))
650 return true;
651 return false;
654 else
655 t = compound_type_base (t);
657 while (t);
658 return t;
661 /* Compare types T1 and T2 and return true if they are
662 equivalent. */
664 inline bool
665 odr_name_hasher::equal (const odr_type_d *o1, const tree_node *t2)
667 tree t1 = o1->type;
669 gcc_checking_assert (main_odr_variant (t2) == t2);
670 gcc_checking_assert (main_odr_variant (t1) == t1);
671 if (t1 == t2)
672 return true;
673 if (!in_lto_p)
674 return false;
675 /* Check for anonymous namespaces. Those have !TREE_PUBLIC
676 on the corresponding TYPE_STUB_DECL. */
677 if ((type_with_linkage_p (t1) && type_in_anonymous_namespace_p (t1))
678 || (type_with_linkage_p (t2) && type_in_anonymous_namespace_p (t2)))
679 return false;
680 gcc_checking_assert (DECL_ASSEMBLER_NAME (TYPE_NAME (t1)));
681 gcc_checking_assert (DECL_ASSEMBLER_NAME (TYPE_NAME (t2)));
682 return (DECL_ASSEMBLER_NAME (TYPE_NAME (t1))
683 == DECL_ASSEMBLER_NAME (TYPE_NAME (t2)));
686 /* Compare types T1 and T2 and return true if they are
687 equivalent. */
689 inline bool
690 odr_vtable_hasher::equal (const odr_type_d *o1, const tree_node *t2)
692 tree t1 = o1->type;
694 gcc_checking_assert (main_odr_variant (t2) == t2);
695 gcc_checking_assert (main_odr_variant (t1) == t1);
696 gcc_checking_assert (in_lto_p);
697 t1 = TYPE_MAIN_VARIANT (t1);
698 t2 = TYPE_MAIN_VARIANT (t2);
699 if (t1 == t2)
700 return true;
701 tree v1 = BINFO_VTABLE (TYPE_BINFO (t1));
702 tree v2 = BINFO_VTABLE (TYPE_BINFO (t2));
703 return (operand_equal_p (TREE_OPERAND (v1, 1),
704 TREE_OPERAND (v2, 1), 0)
705 && DECL_ASSEMBLER_NAME
706 (TREE_OPERAND (TREE_OPERAND (v1, 0), 0))
707 == DECL_ASSEMBLER_NAME
708 (TREE_OPERAND (TREE_OPERAND (v2, 0), 0)));
711 /* Free ODR type V. */
713 inline void
714 odr_name_hasher::remove (odr_type_d *v)
716 v->bases.release ();
717 v->derived_types.release ();
718 if (v->types_set)
719 delete v->types_set;
720 ggc_free (v);
723 /* ODR type hash used to look up ODR type based on tree type node. */
725 typedef hash_table<odr_name_hasher> odr_hash_type;
726 static odr_hash_type *odr_hash;
727 typedef hash_table<odr_vtable_hasher> odr_vtable_hash_type;
728 static odr_vtable_hash_type *odr_vtable_hash;
730 /* ODR types are also stored into ODR_TYPE vector to allow consistent
731 walking. Bases appear before derived types. Vector is garbage collected
732 so we won't end up visiting empty types. */
734 static GTY(()) vec <odr_type, va_gc> *odr_types_ptr;
735 #define odr_types (*odr_types_ptr)
737 /* Set TYPE_BINFO of TYPE and its variants to BINFO. */
738 void
739 set_type_binfo (tree type, tree binfo)
741 for (; type; type = TYPE_NEXT_VARIANT (type))
742 if (COMPLETE_TYPE_P (type))
743 TYPE_BINFO (type) = binfo;
744 else
745 gcc_assert (!TYPE_BINFO (type));
748 /* Compare T2 and T2 based on name or structure. */
750 static bool
751 odr_subtypes_equivalent_p (tree t1, tree t2,
752 hash_set<type_pair,pair_traits> *visited)
755 /* This can happen in incomplete types that should be handled earlier. */
756 gcc_assert (t1 && t2);
758 t1 = main_odr_variant (t1);
759 t2 = main_odr_variant (t2);
760 if (t1 == t2)
761 return true;
763 /* Anonymous namespace types must match exactly. */
764 if ((type_with_linkage_p (t1) && type_in_anonymous_namespace_p (t1))
765 || (type_with_linkage_p (t2) && type_in_anonymous_namespace_p (t2)))
766 return false;
768 /* For ODR types be sure to compare their names.
769 To support -wno-odr-type-merging we allow one type to be non-ODR
770 and other ODR even though it is a violation. */
771 if (types_odr_comparable (t1, t2, true))
773 if (!types_same_for_odr (t1, t2, true))
774 return false;
775 /* Limit recursion: If subtypes are ODR types and we know
776 that they are same, be happy. */
777 if (!get_odr_type (t1, true)->odr_violated)
778 return true;
781 /* Component types, builtins and possibly violating ODR types
782 have to be compared structurally. */
783 if (TREE_CODE (t1) != TREE_CODE (t2))
784 return false;
785 if (AGGREGATE_TYPE_P (t1)
786 && (TYPE_NAME (t1) == NULL_TREE) != (TYPE_NAME (t2) == NULL_TREE))
787 return false;
789 type_pair pair={t1,t2};
790 if (TYPE_UID (t1) > TYPE_UID (t2))
792 pair.first = t2;
793 pair.second = t1;
795 if (visited->add (pair))
796 return true;
797 return odr_types_equivalent_p (t1, t2, false, NULL, visited);
800 /* Compare two virtual tables, PREVAILING and VTABLE and output ODR
801 violation warnings. */
803 void
804 compare_virtual_tables (varpool_node *prevailing, varpool_node *vtable)
806 int n1, n2;
808 if (DECL_VIRTUAL_P (prevailing->decl) != DECL_VIRTUAL_P (vtable->decl))
810 odr_violation_reported = true;
811 if (DECL_VIRTUAL_P (prevailing->decl))
813 varpool_node *tmp = prevailing;
814 prevailing = vtable;
815 vtable = tmp;
817 if (warning_at (DECL_SOURCE_LOCATION
818 (TYPE_NAME (DECL_CONTEXT (vtable->decl))),
819 OPT_Wodr,
820 "virtual table of type %qD violates one definition rule",
821 DECL_CONTEXT (vtable->decl)))
822 inform (DECL_SOURCE_LOCATION (prevailing->decl),
823 "variable of same assembler name as the virtual table is "
824 "defined in another translation unit");
825 return;
827 if (!prevailing->definition || !vtable->definition)
828 return;
830 /* If we do not stream ODR type info, do not bother to do useful compare. */
831 if (!TYPE_BINFO (DECL_CONTEXT (vtable->decl))
832 || !polymorphic_type_binfo_p (TYPE_BINFO (DECL_CONTEXT (vtable->decl))))
833 return;
835 odr_type class_type = get_odr_type (DECL_CONTEXT (vtable->decl), true);
837 if (class_type->odr_violated)
838 return;
840 for (n1 = 0, n2 = 0; true; n1++, n2++)
842 struct ipa_ref *ref1, *ref2;
843 bool end1, end2;
845 end1 = !prevailing->iterate_reference (n1, ref1);
846 end2 = !vtable->iterate_reference (n2, ref2);
848 /* !DECL_VIRTUAL_P means RTTI entry;
849 We warn when RTTI is lost because non-RTTI previals; we silently
850 accept the other case. */
851 while (!end2
852 && (end1
853 || (DECL_ASSEMBLER_NAME (ref1->referred->decl)
854 != DECL_ASSEMBLER_NAME (ref2->referred->decl)
855 && TREE_CODE (ref1->referred->decl) == FUNCTION_DECL))
856 && TREE_CODE (ref2->referred->decl) != FUNCTION_DECL)
858 if (!class_type->rtti_broken
859 && warning_at (DECL_SOURCE_LOCATION
860 (TYPE_NAME (DECL_CONTEXT (vtable->decl))),
861 OPT_Wodr,
862 "virtual table of type %qD contains RTTI "
863 "information",
864 DECL_CONTEXT (vtable->decl)))
866 inform (DECL_SOURCE_LOCATION
867 (TYPE_NAME (DECL_CONTEXT (prevailing->decl))),
868 "but is prevailed by one without from other translation "
869 "unit");
870 inform (DECL_SOURCE_LOCATION
871 (TYPE_NAME (DECL_CONTEXT (prevailing->decl))),
872 "RTTI will not work on this type");
873 class_type->rtti_broken = true;
875 n2++;
876 end2 = !vtable->iterate_reference (n2, ref2);
878 while (!end1
879 && (end2
880 || (DECL_ASSEMBLER_NAME (ref2->referred->decl)
881 != DECL_ASSEMBLER_NAME (ref1->referred->decl)
882 && TREE_CODE (ref2->referred->decl) == FUNCTION_DECL))
883 && TREE_CODE (ref1->referred->decl) != FUNCTION_DECL)
885 n1++;
886 end1 = !prevailing->iterate_reference (n1, ref1);
889 /* Finished? */
890 if (end1 && end2)
892 /* Extra paranoia; compare the sizes. We do not have information
893 about virtual inheritance offsets, so just be sure that these
894 match.
895 Do this as very last check so the not very informative error
896 is not output too often. */
897 if (DECL_SIZE (prevailing->decl) != DECL_SIZE (vtable->decl))
899 class_type->odr_violated = true;
900 if (warning_at (DECL_SOURCE_LOCATION
901 (TYPE_NAME (DECL_CONTEXT (vtable->decl))),
902 OPT_Wodr,
903 "virtual table of type %qD violates "
904 "one definition rule ",
905 DECL_CONTEXT (vtable->decl)))
907 inform (DECL_SOURCE_LOCATION
908 (TYPE_NAME (DECL_CONTEXT (prevailing->decl))),
909 "the conflicting type defined in another translation "
910 "unit has virtual table of different size");
913 return;
916 if (!end1 && !end2)
918 if (DECL_ASSEMBLER_NAME (ref1->referred->decl)
919 == DECL_ASSEMBLER_NAME (ref2->referred->decl))
920 continue;
922 class_type->odr_violated = true;
924 /* If the loops above stopped on non-virtual pointer, we have
925 mismatch in RTTI information mangling. */
926 if (TREE_CODE (ref1->referred->decl) != FUNCTION_DECL
927 && TREE_CODE (ref2->referred->decl) != FUNCTION_DECL)
929 if (warning_at (DECL_SOURCE_LOCATION
930 (TYPE_NAME (DECL_CONTEXT (vtable->decl))),
931 OPT_Wodr,
932 "virtual table of type %qD violates "
933 "one definition rule ",
934 DECL_CONTEXT (vtable->decl)))
936 inform (DECL_SOURCE_LOCATION
937 (TYPE_NAME (DECL_CONTEXT (prevailing->decl))),
938 "the conflicting type defined in another translation "
939 "unit with different RTTI information");
941 return;
943 /* At this point both REF1 and REF2 points either to virtual table
944 or virtual method. If one points to virtual table and other to
945 method we can complain the same way as if one table was shorter
946 than other pointing out the extra method. */
947 if (TREE_CODE (ref1->referred->decl)
948 != TREE_CODE (ref2->referred->decl))
950 if (TREE_CODE (ref1->referred->decl) == VAR_DECL)
951 end1 = true;
952 else if (TREE_CODE (ref2->referred->decl) == VAR_DECL)
953 end2 = true;
957 class_type->odr_violated = true;
959 /* Complain about size mismatch. Either we have too many virutal
960 functions or too many virtual table pointers. */
961 if (end1 || end2)
963 if (end1)
965 varpool_node *tmp = prevailing;
966 prevailing = vtable;
967 vtable = tmp;
968 ref1 = ref2;
970 if (warning_at (DECL_SOURCE_LOCATION
971 (TYPE_NAME (DECL_CONTEXT (vtable->decl))),
972 OPT_Wodr,
973 "virtual table of type %qD violates "
974 "one definition rule",
975 DECL_CONTEXT (vtable->decl)))
977 if (TREE_CODE (ref1->referring->decl) == FUNCTION_DECL)
979 inform (DECL_SOURCE_LOCATION
980 (TYPE_NAME (DECL_CONTEXT (prevailing->decl))),
981 "the conflicting type defined in another translation "
982 "unit");
983 inform (DECL_SOURCE_LOCATION
984 (TYPE_NAME (DECL_CONTEXT (ref1->referring->decl))),
985 "contains additional virtual method %qD",
986 ref1->referred->decl);
988 else
990 inform (DECL_SOURCE_LOCATION
991 (TYPE_NAME (DECL_CONTEXT (prevailing->decl))),
992 "the conflicting type defined in another translation "
993 "unit has virtual table table with more entries");
996 return;
999 /* And in the last case we have either mistmatch in between two virtual
1000 methods or two virtual table pointers. */
1001 if (warning_at (DECL_SOURCE_LOCATION
1002 (TYPE_NAME (DECL_CONTEXT (vtable->decl))), OPT_Wodr,
1003 "virtual table of type %qD violates "
1004 "one definition rule ",
1005 DECL_CONTEXT (vtable->decl)))
1007 if (TREE_CODE (ref1->referred->decl) == FUNCTION_DECL)
1009 inform (DECL_SOURCE_LOCATION
1010 (TYPE_NAME (DECL_CONTEXT (prevailing->decl))),
1011 "the conflicting type defined in another translation "
1012 "unit");
1013 gcc_assert (TREE_CODE (ref2->referred->decl)
1014 == FUNCTION_DECL);
1015 inform (DECL_SOURCE_LOCATION (ref1->referred->decl),
1016 "virtual method %qD", ref1->referred->decl);
1017 inform (DECL_SOURCE_LOCATION (ref2->referred->decl),
1018 "ought to match virtual method %qD but does not",
1019 ref2->referred->decl);
1021 else
1022 inform (DECL_SOURCE_LOCATION
1023 (TYPE_NAME (DECL_CONTEXT (prevailing->decl))),
1024 "the conflicting type defined in another translation "
1025 "unit has virtual table table with different contents");
1026 return;
1031 /* Output ODR violation warning about T1 and T2 with REASON.
1032 Display location of ST1 and ST2 if REASON speaks about field or
1033 method of the type.
1034 If WARN is false, do nothing. Set WARNED if warning was indeed
1035 output. */
1037 void
1038 warn_odr (tree t1, tree t2, tree st1, tree st2,
1039 bool warn, bool *warned, const char *reason)
1041 tree decl2 = TYPE_NAME (t2);
1042 if (warned)
1043 *warned = false;
1045 if (!warn || !TYPE_NAME(t1))
1046 return;
1048 /* ODR warnings are output druing LTO streaming; we must apply location
1049 cache for potential warnings to be output correctly. */
1050 if (lto_location_cache::current_cache)
1051 lto_location_cache::current_cache->apply_location_cache ();
1053 if (!warning_at (DECL_SOURCE_LOCATION (TYPE_NAME (t1)), OPT_Wodr,
1054 "type %qT violates one definition rule",
1055 t1))
1056 return;
1057 if (!st1 && !st2)
1059 /* For FIELD_DECL support also case where one of fields is
1060 NULL - this is used when the structures have mismatching number of
1061 elements. */
1062 else if (!st1 || TREE_CODE (st1) == FIELD_DECL)
1064 inform (DECL_SOURCE_LOCATION (decl2),
1065 "a different type is defined in another translation unit");
1066 if (!st1)
1068 st1 = st2;
1069 st2 = NULL;
1071 inform (DECL_SOURCE_LOCATION (st1),
1072 "the first difference of corresponding definitions is field %qD",
1073 st1);
1074 if (st2)
1075 decl2 = st2;
1077 else if (TREE_CODE (st1) == FUNCTION_DECL)
1079 inform (DECL_SOURCE_LOCATION (decl2),
1080 "a different type is defined in another translation unit");
1081 inform (DECL_SOURCE_LOCATION (st1),
1082 "the first difference of corresponding definitions is method %qD",
1083 st1);
1084 decl2 = st2;
1086 else
1087 return;
1088 inform (DECL_SOURCE_LOCATION (decl2), reason);
1090 if (warned)
1091 *warned = true;
1094 /* We already warned about ODR mismatch. T1 and T2 ought to be equivalent
1095 because they are used on same place in ODR matching types.
1096 They are not; inform the user. */
1098 void
1099 warn_types_mismatch (tree t1, tree t2)
1101 /* If types have names and they are different, it is most informative to
1102 output those. */
1103 if (TYPE_NAME (t1) && TYPE_NAME (t2)
1104 && DECL_ASSEMBLER_NAME_SET_P (TYPE_NAME (t1))
1105 && DECL_ASSEMBLER_NAME_SET_P (TYPE_NAME (t2))
1106 && DECL_ASSEMBLER_NAME (TYPE_NAME (t1))
1107 != DECL_ASSEMBLER_NAME (TYPE_NAME (t2)))
1109 char *name1 = xstrdup (cplus_demangle
1110 (IDENTIFIER_POINTER (DECL_ASSEMBLER_NAME (TYPE_NAME (t1))),
1111 DMGL_PARAMS | DMGL_ANSI | DMGL_TYPES));
1112 char *name2 = cplus_demangle
1113 (IDENTIFIER_POINTER (DECL_ASSEMBLER_NAME (TYPE_NAME (t2))),
1114 DMGL_PARAMS | DMGL_ANSI | DMGL_TYPES);
1115 if (name1 && name2 && strcmp (name1, name2))
1117 inform (DECL_SOURCE_LOCATION (TYPE_NAME (t1)),
1118 "type name %<%s%> should match type name %<%s%>",
1119 name1, name2);
1120 inform (DECL_SOURCE_LOCATION (TYPE_NAME (t2)),
1121 "the incompatible type is defined here");
1122 free (name1);
1123 return;
1125 free (name1);
1127 /* It is a quite common bug to reference anonymous namespace type in
1128 non-anonymous namespace class. */
1129 if ((type_with_linkage_p (t1) && type_in_anonymous_namespace_p (t1))
1130 || (type_with_linkage_p (t2) && type_in_anonymous_namespace_p (t2)))
1132 if (type_with_linkage_p (t1) && !type_in_anonymous_namespace_p (t1))
1134 tree tmp = t1;;
1135 t1 = t2;
1136 t2 = tmp;
1138 if (TYPE_NAME (t1) && TYPE_NAME (t2)
1139 && TREE_CODE (TYPE_NAME (t1)) == TYPE_DECL
1140 && TREE_CODE (TYPE_NAME (t2)) == TYPE_DECL)
1142 inform (DECL_SOURCE_LOCATION (TYPE_NAME (t1)),
1143 "type %qT defined in anonymous namespace can not match "
1144 "type %qT",
1145 t1, t2);
1146 inform (DECL_SOURCE_LOCATION (TYPE_NAME (t2)),
1147 "the incompatible type defined in anonymous namespace in "
1148 "another translation unit");
1150 else
1151 inform (UNKNOWN_LOCATION,
1152 "types in anonymous namespace does not match across "
1153 "translation unit boundary");
1154 return;
1156 /* A tricky case are component types. Often they appear the same in source
1157 code and the mismatch is dragged in by type they are build from.
1158 Look for those differences in subtypes and try to be informative. In other
1159 cases just output nothing because the source code is probably different
1160 and in this case we already output a all necessary info. */
1161 if (!TYPE_NAME (t1) || !TYPE_NAME (t2))
1163 if (TREE_CODE (t1) == TREE_CODE (t2))
1165 hash_set<type_pair,pair_traits> visited;
1166 if (TREE_CODE (t1) == ARRAY_TYPE
1167 && COMPLETE_TYPE_P (t1) && COMPLETE_TYPE_P (t2))
1169 tree i1 = TYPE_DOMAIN (t1);
1170 tree i2 = TYPE_DOMAIN (t2);
1172 if (i1 && i2
1173 && TYPE_MAX_VALUE (i1)
1174 && TYPE_MAX_VALUE (i2)
1175 && !operand_equal_p (TYPE_MAX_VALUE (i1),
1176 TYPE_MAX_VALUE (i2), 0))
1178 inform (UNKNOWN_LOCATION,
1179 "array types have different bounds");
1180 return;
1183 if ((POINTER_TYPE_P (t1) || TREE_CODE (t1) == ARRAY_TYPE)
1184 && !odr_subtypes_equivalent_p (TREE_TYPE (t1),
1185 TREE_TYPE (t2),
1186 &visited))
1187 warn_types_mismatch (TREE_TYPE (t1), TREE_TYPE (t2));
1188 else if (TREE_CODE (t1) == METHOD_TYPE
1189 || TREE_CODE (t1) == FUNCTION_TYPE)
1191 tree parms1 = NULL, parms2 = NULL;
1192 int count = 1;
1194 if (!odr_subtypes_equivalent_p (TREE_TYPE (t1), TREE_TYPE (t2),
1195 &visited))
1197 inform (UNKNOWN_LOCATION, "return value type mismatch");
1198 warn_types_mismatch (TREE_TYPE (t1), TREE_TYPE (t2));
1199 return;
1201 if (prototype_p (t1) && prototype_p (t2))
1202 for (parms1 = TYPE_ARG_TYPES (t1), parms2 = TYPE_ARG_TYPES (t2);
1203 parms1 && parms2;
1204 parms1 = TREE_CHAIN (parms1), parms2 = TREE_CHAIN (parms2),
1205 count++)
1207 if (!odr_subtypes_equivalent_p
1208 (TREE_VALUE (parms1), TREE_VALUE (parms2), &visited))
1210 if (count == 1 && TREE_CODE (t1) == METHOD_TYPE)
1211 inform (UNKNOWN_LOCATION,
1212 "implicit this pointer type mismatch");
1213 else
1214 inform (UNKNOWN_LOCATION,
1215 "type mismatch in parameter %i",
1216 count - (TREE_CODE (t1) == METHOD_TYPE));
1217 warn_types_mismatch (TREE_VALUE (parms1),
1218 TREE_VALUE (parms2));
1219 return;
1222 if (parms1 || parms2)
1224 inform (UNKNOWN_LOCATION,
1225 "types have different parameter counts");
1226 return;
1230 return;
1232 /* This should not happen but if it does, the warning would not be helpful.
1233 TODO: turn it into assert next stage1. */
1234 if (TYPE_NAME (t1) == TYPE_NAME (t2))
1235 return;
1236 /* In Firefox it is a common bug to have same types but in
1237 different namespaces. Be a bit more informative on
1238 this. */
1239 if (TYPE_CONTEXT (t1) && TYPE_CONTEXT (t2)
1240 && (((TREE_CODE (TYPE_CONTEXT (t1)) == NAMESPACE_DECL)
1241 != (TREE_CODE (TYPE_CONTEXT (t2)) == NAMESPACE_DECL))
1242 || (TREE_CODE (TYPE_CONTEXT (t1)) == NAMESPACE_DECL
1243 && (DECL_NAME (TYPE_CONTEXT (t1)) !=
1244 DECL_NAME (TYPE_CONTEXT (t2))))))
1245 inform (DECL_SOURCE_LOCATION (TYPE_NAME (t1)),
1246 "type %qT should match type %qT but is defined "
1247 "in different namespace ",
1248 t1, t2);
1249 else if (types_odr_comparable (t1, t2, true)
1250 && types_same_for_odr (t1, t2, true))
1251 inform (DECL_SOURCE_LOCATION (TYPE_NAME (t1)),
1252 "type %qT should match type %qT that itself violate "
1253 "one definition rule",
1254 t1, t2);
1255 else
1256 inform (DECL_SOURCE_LOCATION (TYPE_NAME (t1)),
1257 "type %qT should match type %qT",
1258 t1, t2);
1259 if (DECL_SOURCE_LOCATION (TYPE_NAME (t2)) > BUILTINS_LOCATION)
1260 inform (DECL_SOURCE_LOCATION (TYPE_NAME (t2)),
1261 "the incompatible type is defined here");
1264 /* Compare T1 and T2, report ODR violations if WARN is true and set
1265 WARNED to true if anything is reported. Return true if types match.
1266 If true is returned, the types are also compatible in the sense of
1267 gimple_canonical_types_compatible_p. */
1269 static bool
1270 odr_types_equivalent_p (tree t1, tree t2, bool warn, bool *warned,
1271 hash_set<type_pair,pair_traits> *visited)
1273 /* Check first for the obvious case of pointer identity. */
1274 if (t1 == t2)
1275 return true;
1276 gcc_assert (!type_with_linkage_p (t1) || !type_in_anonymous_namespace_p (t1));
1277 gcc_assert (!type_with_linkage_p (t2) || !type_in_anonymous_namespace_p (t2));
1279 /* Can't be the same type if the types don't have the same code. */
1280 if (TREE_CODE (t1) != TREE_CODE (t2))
1282 warn_odr (t1, t2, NULL, NULL, warn, warned,
1283 G_("a different type is defined in another translation unit"));
1284 return false;
1287 if (TYPE_QUALS (t1) != TYPE_QUALS (t2))
1289 warn_odr (t1, t2, NULL, NULL, warn, warned,
1290 G_("a type with different qualifiers is defined in another "
1291 "translation unit"));
1292 return false;
1295 if ((type_with_linkage_p (t1) && type_in_anonymous_namespace_p (t1))
1296 || (type_with_linkage_p (t2) && type_in_anonymous_namespace_p (t2)))
1298 /* We can not trip this when comparing ODR types, only when trying to
1299 match different ODR derivations from different declarations.
1300 So WARN should be always false. */
1301 gcc_assert (!warn);
1302 return false;
1305 if (comp_type_attributes (t1, t2) != 1)
1307 warn_odr (t1, t2, NULL, NULL, warn, warned,
1308 G_("a type with different attributes "
1309 "is defined in another translation unit"));
1310 return false;
1313 if (TREE_CODE (t1) == ENUMERAL_TYPE
1314 && TYPE_VALUES (t1) && TYPE_VALUES (t2))
1316 tree v1, v2;
1317 for (v1 = TYPE_VALUES (t1), v2 = TYPE_VALUES (t2);
1318 v1 && v2 ; v1 = TREE_CHAIN (v1), v2 = TREE_CHAIN (v2))
1320 if (TREE_PURPOSE (v1) != TREE_PURPOSE (v2))
1322 warn_odr (t1, t2, NULL, NULL, warn, warned,
1323 G_("an enum with different value name"
1324 " is defined in another translation unit"));
1325 return false;
1327 if (TREE_VALUE (v1) != TREE_VALUE (v2)
1328 && !operand_equal_p (DECL_INITIAL (TREE_VALUE (v1)),
1329 DECL_INITIAL (TREE_VALUE (v2)), 0))
1331 warn_odr (t1, t2, NULL, NULL, warn, warned,
1332 G_("an enum with different values is defined"
1333 " in another translation unit"));
1334 return false;
1337 if (v1 || v2)
1339 warn_odr (t1, t2, NULL, NULL, warn, warned,
1340 G_("an enum with mismatching number of values "
1341 "is defined in another translation unit"));
1342 return false;
1346 /* Non-aggregate types can be handled cheaply. */
1347 if (INTEGRAL_TYPE_P (t1)
1348 || SCALAR_FLOAT_TYPE_P (t1)
1349 || FIXED_POINT_TYPE_P (t1)
1350 || TREE_CODE (t1) == VECTOR_TYPE
1351 || TREE_CODE (t1) == COMPLEX_TYPE
1352 || TREE_CODE (t1) == OFFSET_TYPE
1353 || POINTER_TYPE_P (t1))
1355 if (TYPE_PRECISION (t1) != TYPE_PRECISION (t2))
1357 warn_odr (t1, t2, NULL, NULL, warn, warned,
1358 G_("a type with different precision is defined "
1359 "in another translation unit"));
1360 return false;
1362 if (TYPE_UNSIGNED (t1) != TYPE_UNSIGNED (t2))
1364 warn_odr (t1, t2, NULL, NULL, warn, warned,
1365 G_("a type with different signedness is defined "
1366 "in another translation unit"));
1367 return false;
1370 if (TREE_CODE (t1) == INTEGER_TYPE
1371 && TYPE_STRING_FLAG (t1) != TYPE_STRING_FLAG (t2))
1373 /* char WRT uint_8? */
1374 warn_odr (t1, t2, NULL, NULL, warn, warned,
1375 G_("a different type is defined in another "
1376 "translation unit"));
1377 return false;
1380 /* For canonical type comparisons we do not want to build SCCs
1381 so we cannot compare pointed-to types. But we can, for now,
1382 require the same pointed-to type kind and match what
1383 useless_type_conversion_p would do. */
1384 if (POINTER_TYPE_P (t1))
1386 if (TYPE_ADDR_SPACE (TREE_TYPE (t1))
1387 != TYPE_ADDR_SPACE (TREE_TYPE (t2)))
1389 warn_odr (t1, t2, NULL, NULL, warn, warned,
1390 G_("it is defined as a pointer in different address "
1391 "space in another translation unit"));
1392 return false;
1395 if (!odr_subtypes_equivalent_p (TREE_TYPE (t1), TREE_TYPE (t2), visited))
1397 warn_odr (t1, t2, NULL, NULL, warn, warned,
1398 G_("it is defined as a pointer to different type "
1399 "in another translation unit"));
1400 if (warn && warned)
1401 warn_types_mismatch (TREE_TYPE (t1), TREE_TYPE (t2));
1402 return false;
1406 if ((TREE_CODE (t1) == VECTOR_TYPE || TREE_CODE (t1) == COMPLEX_TYPE)
1407 && !odr_subtypes_equivalent_p (TREE_TYPE (t1), TREE_TYPE (t2), visited))
1409 /* Probably specific enough. */
1410 warn_odr (t1, t2, NULL, NULL, warn, warned,
1411 G_("a different type is defined "
1412 "in another translation unit"));
1413 if (warn && warned)
1414 warn_types_mismatch (TREE_TYPE (t1), TREE_TYPE (t2));
1415 return false;
1418 /* Do type-specific comparisons. */
1419 else switch (TREE_CODE (t1))
1421 case ARRAY_TYPE:
1423 /* Array types are the same if the element types are the same and
1424 the number of elements are the same. */
1425 if (!odr_subtypes_equivalent_p (TREE_TYPE (t1), TREE_TYPE (t2), visited))
1427 warn_odr (t1, t2, NULL, NULL, warn, warned,
1428 G_("a different type is defined in another "
1429 "translation unit"));
1430 if (warn && warned)
1431 warn_types_mismatch (TREE_TYPE (t1), TREE_TYPE (t2));
1433 gcc_assert (TYPE_STRING_FLAG (t1) == TYPE_STRING_FLAG (t2));
1434 gcc_assert (TYPE_NONALIASED_COMPONENT (t1)
1435 == TYPE_NONALIASED_COMPONENT (t2));
1437 tree i1 = TYPE_DOMAIN (t1);
1438 tree i2 = TYPE_DOMAIN (t2);
1440 /* For an incomplete external array, the type domain can be
1441 NULL_TREE. Check this condition also. */
1442 if (i1 == NULL_TREE || i2 == NULL_TREE)
1443 return true;
1445 tree min1 = TYPE_MIN_VALUE (i1);
1446 tree min2 = TYPE_MIN_VALUE (i2);
1447 tree max1 = TYPE_MAX_VALUE (i1);
1448 tree max2 = TYPE_MAX_VALUE (i2);
1450 /* In C++, minimums should be always 0. */
1451 gcc_assert (min1 == min2);
1452 if (!operand_equal_p (max1, max2, 0))
1454 warn_odr (t1, t2, NULL, NULL, warn, warned,
1455 G_("an array of different size is defined "
1456 "in another translation unit"));
1457 return false;
1460 break;
1462 case METHOD_TYPE:
1463 case FUNCTION_TYPE:
1464 /* Function types are the same if the return type and arguments types
1465 are the same. */
1466 if (!odr_subtypes_equivalent_p (TREE_TYPE (t1), TREE_TYPE (t2), visited))
1468 warn_odr (t1, t2, NULL, NULL, warn, warned,
1469 G_("has different return value "
1470 "in another translation unit"));
1471 if (warn && warned)
1472 warn_types_mismatch (TREE_TYPE (t1), TREE_TYPE (t2));
1473 return false;
1476 if (TYPE_ARG_TYPES (t1) == TYPE_ARG_TYPES (t2)
1477 || !prototype_p (t1) || !prototype_p (t2))
1478 return true;
1479 else
1481 tree parms1, parms2;
1483 for (parms1 = TYPE_ARG_TYPES (t1), parms2 = TYPE_ARG_TYPES (t2);
1484 parms1 && parms2;
1485 parms1 = TREE_CHAIN (parms1), parms2 = TREE_CHAIN (parms2))
1487 if (!odr_subtypes_equivalent_p
1488 (TREE_VALUE (parms1), TREE_VALUE (parms2), visited))
1490 warn_odr (t1, t2, NULL, NULL, warn, warned,
1491 G_("has different parameters in another "
1492 "translation unit"));
1493 if (warn && warned)
1494 warn_types_mismatch (TREE_VALUE (parms1),
1495 TREE_VALUE (parms2));
1496 return false;
1500 if (parms1 || parms2)
1502 warn_odr (t1, t2, NULL, NULL, warn, warned,
1503 G_("has different parameters "
1504 "in another translation unit"));
1505 return false;
1508 return true;
1511 case RECORD_TYPE:
1512 case UNION_TYPE:
1513 case QUAL_UNION_TYPE:
1515 tree f1, f2;
1517 /* For aggregate types, all the fields must be the same. */
1518 if (COMPLETE_TYPE_P (t1) && COMPLETE_TYPE_P (t2))
1520 if (TYPE_BINFO (t1) && TYPE_BINFO (t2)
1521 && polymorphic_type_binfo_p (TYPE_BINFO (t1))
1522 != polymorphic_type_binfo_p (TYPE_BINFO (t2)))
1524 if (polymorphic_type_binfo_p (TYPE_BINFO (t1)))
1525 warn_odr (t1, t2, NULL, NULL, warn, warned,
1526 G_("a type defined in another translation unit "
1527 "is not polymorphic"));
1528 else
1529 warn_odr (t1, t2, NULL, NULL, warn, warned,
1530 G_("a type defined in another translation unit "
1531 "is polymorphic"));
1532 return false;
1534 for (f1 = TYPE_FIELDS (t1), f2 = TYPE_FIELDS (t2);
1535 f1 || f2;
1536 f1 = TREE_CHAIN (f1), f2 = TREE_CHAIN (f2))
1538 /* Skip non-fields. */
1539 while (f1 && TREE_CODE (f1) != FIELD_DECL)
1540 f1 = TREE_CHAIN (f1);
1541 while (f2 && TREE_CODE (f2) != FIELD_DECL)
1542 f2 = TREE_CHAIN (f2);
1543 if (!f1 || !f2)
1544 break;
1545 if (DECL_VIRTUAL_P (f1) != DECL_VIRTUAL_P (f2))
1547 warn_odr (t1, t2, NULL, NULL, warn, warned,
1548 G_("a type with different virtual table pointers"
1549 " is defined in another translation unit"));
1550 return false;
1552 if (DECL_ARTIFICIAL (f1) != DECL_ARTIFICIAL (f2))
1554 warn_odr (t1, t2, NULL, NULL, warn, warned,
1555 G_("a type with different bases is defined "
1556 "in another translation unit"));
1557 return false;
1559 if (DECL_NAME (f1) != DECL_NAME (f2)
1560 && !DECL_ARTIFICIAL (f1))
1562 warn_odr (t1, t2, f1, f2, warn, warned,
1563 G_("a field with different name is defined "
1564 "in another translation unit"));
1565 return false;
1567 if (!odr_subtypes_equivalent_p (TREE_TYPE (f1),
1568 TREE_TYPE (f2), visited))
1570 /* Do not warn about artificial fields and just go into
1571 generic field mismatch warning. */
1572 if (DECL_ARTIFICIAL (f1))
1573 break;
1575 warn_odr (t1, t2, f1, f2, warn, warned,
1576 G_("a field of same name but different type "
1577 "is defined in another translation unit"));
1578 if (warn && warned)
1579 warn_types_mismatch (TREE_TYPE (f1), TREE_TYPE (f2));
1580 return false;
1582 if (!gimple_compare_field_offset (f1, f2))
1584 /* Do not warn about artificial fields and just go into
1585 generic field mismatch warning. */
1586 if (DECL_ARTIFICIAL (f1))
1587 break;
1588 warn_odr (t1, t2, f1, f2, warn, warned,
1589 G_("fields has different layout "
1590 "in another translation unit"));
1591 return false;
1593 gcc_assert (DECL_NONADDRESSABLE_P (f1)
1594 == DECL_NONADDRESSABLE_P (f2));
1597 /* If one aggregate has more fields than the other, they
1598 are not the same. */
1599 if (f1 || f2)
1601 if ((f1 && DECL_VIRTUAL_P (f1)) || (f2 && DECL_VIRTUAL_P (f2)))
1602 warn_odr (t1, t2, NULL, NULL, warn, warned,
1603 G_("a type with different virtual table pointers"
1604 " is defined in another translation unit"));
1605 else if ((f1 && DECL_ARTIFICIAL (f1))
1606 || (f2 && DECL_ARTIFICIAL (f2)))
1607 warn_odr (t1, t2, NULL, NULL, warn, warned,
1608 G_("a type with different bases is defined "
1609 "in another translation unit"));
1610 else
1611 warn_odr (t1, t2, f1, f2, warn, warned,
1612 G_("a type with different number of fields "
1613 "is defined in another translation unit"));
1615 return false;
1617 if ((TYPE_MAIN_VARIANT (t1) == t1 || TYPE_MAIN_VARIANT (t2) == t2)
1618 && COMPLETE_TYPE_P (TYPE_MAIN_VARIANT (t1))
1619 && COMPLETE_TYPE_P (TYPE_MAIN_VARIANT (t2))
1620 && odr_type_p (TYPE_MAIN_VARIANT (t1))
1621 && odr_type_p (TYPE_MAIN_VARIANT (t2))
1622 && (TYPE_METHODS (TYPE_MAIN_VARIANT (t1))
1623 != TYPE_METHODS (TYPE_MAIN_VARIANT (t2))))
1625 /* Currently free_lang_data sets TYPE_METHODS to error_mark_node
1626 if it is non-NULL so this loop will never realy execute. */
1627 if (TYPE_METHODS (TYPE_MAIN_VARIANT (t1)) != error_mark_node
1628 && TYPE_METHODS (TYPE_MAIN_VARIANT (t2)) != error_mark_node)
1629 for (f1 = TYPE_METHODS (TYPE_MAIN_VARIANT (t1)),
1630 f2 = TYPE_METHODS (TYPE_MAIN_VARIANT (t2));
1631 f1 && f2 ; f1 = DECL_CHAIN (f1), f2 = DECL_CHAIN (f2))
1633 if (DECL_ASSEMBLER_NAME (f1) != DECL_ASSEMBLER_NAME (f2))
1635 warn_odr (t1, t2, f1, f2, warn, warned,
1636 G_("a different method of same type "
1637 "is defined in another "
1638 "translation unit"));
1639 return false;
1641 if (DECL_VIRTUAL_P (f1) != DECL_VIRTUAL_P (f2))
1643 warn_odr (t1, t2, f1, f2, warn, warned,
1644 G_("s definition that differs by virtual "
1645 "keyword in another translation unit"));
1646 return false;
1648 if (DECL_VINDEX (f1) != DECL_VINDEX (f2))
1650 warn_odr (t1, t2, f1, f2, warn, warned,
1651 G_("virtual table layout differs "
1652 "in another translation unit"));
1653 return false;
1655 if (odr_subtypes_equivalent_p (TREE_TYPE (f1),
1656 TREE_TYPE (f2), visited))
1658 warn_odr (t1, t2, f1, f2, warn, warned,
1659 G_("method with incompatible type is "
1660 "defined in another translation unit"));
1661 return false;
1664 if ((f1 == NULL) != (f2 == NULL))
1666 warn_odr (t1, t2, NULL, NULL, warn, warned,
1667 G_("a type with different number of methods "
1668 "is defined in another translation unit"));
1669 return false;
1673 break;
1675 case VOID_TYPE:
1676 case NULLPTR_TYPE:
1677 break;
1679 default:
1680 debug_tree (t1);
1681 gcc_unreachable ();
1684 /* Those are better to come last as they are utterly uninformative. */
1685 if (TYPE_SIZE (t1) && TYPE_SIZE (t2)
1686 && !operand_equal_p (TYPE_SIZE (t1), TYPE_SIZE (t2), 0))
1688 warn_odr (t1, t2, NULL, NULL, warn, warned,
1689 G_("a type with different size "
1690 "is defined in another translation unit"));
1691 return false;
1693 if (COMPLETE_TYPE_P (t1) && COMPLETE_TYPE_P (t2)
1694 && TYPE_ALIGN (t1) != TYPE_ALIGN (t2))
1696 warn_odr (t1, t2, NULL, NULL, warn, warned,
1697 G_("a type with different alignment "
1698 "is defined in another translation unit"));
1699 return false;
1701 gcc_assert (!TYPE_SIZE_UNIT (t1) || !TYPE_SIZE_UNIT (t2)
1702 || operand_equal_p (TYPE_SIZE_UNIT (t1),
1703 TYPE_SIZE_UNIT (t2), 0));
1704 return true;
1707 /* Return true if TYPE1 and TYPE2 are equivalent for One Definition Rule. */
1709 bool
1710 odr_types_equivalent_p (tree type1, tree type2)
1712 hash_set<type_pair,pair_traits> visited;
1714 #ifdef ENABLE_CHECKING
1715 gcc_assert (odr_or_derived_type_p (type1) && odr_or_derived_type_p (type2));
1716 #endif
1717 return odr_types_equivalent_p (type1, type2, false, NULL,
1718 &visited);
1721 /* TYPE is equivalent to VAL by ODR, but its tree representation differs
1722 from VAL->type. This may happen in LTO where tree merging did not merge
1723 all variants of the same type or due to ODR violation.
1725 Analyze and report ODR violations and add type to duplicate list.
1726 If TYPE is more specified than VAL->type, prevail VAL->type. Also if
1727 this is first time we see definition of a class return true so the
1728 base types are analyzed. */
1730 static bool
1731 add_type_duplicate (odr_type val, tree type)
1733 bool build_bases = false;
1734 bool prevail = false;
1735 bool odr_must_violate = false;
1737 if (!val->types_set)
1738 val->types_set = new hash_set<tree>;
1740 /* Chose polymorphic type as leader (this happens only in case of ODR
1741 violations. */
1742 if ((TREE_CODE (type) == RECORD_TYPE && TYPE_BINFO (type)
1743 && polymorphic_type_binfo_p (TYPE_BINFO (type)))
1744 && (TREE_CODE (val->type) != RECORD_TYPE || !TYPE_BINFO (val->type)
1745 || !polymorphic_type_binfo_p (TYPE_BINFO (val->type))))
1747 prevail = true;
1748 build_bases = true;
1750 /* Always prefer complete type to be the leader. */
1751 else if (!COMPLETE_TYPE_P (val->type) && COMPLETE_TYPE_P (type))
1753 prevail = true;
1754 build_bases = TYPE_BINFO (type);
1756 else if (COMPLETE_TYPE_P (val->type) && !COMPLETE_TYPE_P (type))
1758 else if (TREE_CODE (val->type) == ENUMERAL_TYPE
1759 && TREE_CODE (type) == ENUMERAL_TYPE
1760 && !TYPE_VALUES (val->type) && TYPE_VALUES (type))
1761 prevail = true;
1762 else if (TREE_CODE (val->type) == RECORD_TYPE
1763 && TREE_CODE (type) == RECORD_TYPE
1764 && TYPE_BINFO (type) && !TYPE_BINFO (val->type))
1766 gcc_assert (!val->bases.length ());
1767 build_bases = true;
1768 prevail = true;
1771 if (prevail)
1773 tree tmp = type;
1775 type = val->type;
1776 val->type = tmp;
1779 val->types_set->add (type);
1781 /* If we now have a mangled name, be sure to record it to val->type
1782 so ODR hash can work. */
1784 if (can_be_name_hashed_p (type) && !can_be_name_hashed_p (val->type))
1785 SET_DECL_ASSEMBLER_NAME (TYPE_NAME (val->type),
1786 DECL_ASSEMBLER_NAME (TYPE_NAME (type)));
1788 bool merge = true;
1789 bool base_mismatch = false;
1790 unsigned int i;
1791 bool warned = false;
1792 hash_set<type_pair,pair_traits> visited;
1794 gcc_assert (in_lto_p);
1795 vec_safe_push (val->types, type);
1797 /* If both are class types, compare the bases. */
1798 if (COMPLETE_TYPE_P (type) && COMPLETE_TYPE_P (val->type)
1799 && TREE_CODE (val->type) == RECORD_TYPE
1800 && TREE_CODE (type) == RECORD_TYPE
1801 && TYPE_BINFO (val->type) && TYPE_BINFO (type))
1803 if (BINFO_N_BASE_BINFOS (TYPE_BINFO (type))
1804 != BINFO_N_BASE_BINFOS (TYPE_BINFO (val->type)))
1806 if (!flag_ltrans && !warned && !val->odr_violated)
1808 tree extra_base;
1809 warn_odr (type, val->type, NULL, NULL, !warned, &warned,
1810 "a type with the same name but different "
1811 "number of polymorphic bases is "
1812 "defined in another translation unit");
1813 if (warned)
1815 if (BINFO_N_BASE_BINFOS (TYPE_BINFO (type))
1816 > BINFO_N_BASE_BINFOS (TYPE_BINFO (val->type)))
1817 extra_base = BINFO_BASE_BINFO
1818 (TYPE_BINFO (type),
1819 BINFO_N_BASE_BINFOS (TYPE_BINFO (val->type)));
1820 else
1821 extra_base = BINFO_BASE_BINFO
1822 (TYPE_BINFO (val->type),
1823 BINFO_N_BASE_BINFOS (TYPE_BINFO (type)));
1824 tree extra_base_type = BINFO_TYPE (extra_base);
1825 inform (DECL_SOURCE_LOCATION (TYPE_NAME (extra_base_type)),
1826 "the extra base is defined here");
1829 base_mismatch = true;
1831 else
1832 for (i = 0; i < BINFO_N_BASE_BINFOS (TYPE_BINFO (type)); i++)
1834 tree base1 = BINFO_BASE_BINFO (TYPE_BINFO (type), i);
1835 tree base2 = BINFO_BASE_BINFO (TYPE_BINFO (val->type), i);
1836 tree type1 = BINFO_TYPE (base1);
1837 tree type2 = BINFO_TYPE (base2);
1839 if (types_odr_comparable (type1, type2))
1841 if (!types_same_for_odr (type1, type2))
1842 base_mismatch = true;
1844 else
1845 if (!odr_types_equivalent_p (type1, type2))
1846 base_mismatch = true;
1847 if (base_mismatch)
1849 if (!warned && !val->odr_violated)
1851 warn_odr (type, val->type, NULL, NULL,
1852 !warned, &warned,
1853 "a type with the same name but different base "
1854 "type is defined in another translation unit");
1855 if (warned)
1856 warn_types_mismatch (type1, type2);
1858 break;
1860 if (BINFO_OFFSET (base1) != BINFO_OFFSET (base2))
1862 base_mismatch = true;
1863 if (!warned && !val->odr_violated)
1864 warn_odr (type, val->type, NULL, NULL,
1865 !warned, &warned,
1866 "a type with the same name but different base "
1867 "layout is defined in another translation unit");
1868 break;
1870 /* One of bases is not of complete type. */
1871 if (!TYPE_BINFO (type1) != !TYPE_BINFO (type2))
1873 /* If we have a polymorphic type info specified for TYPE1
1874 but not for TYPE2 we possibly missed a base when recording
1875 VAL->type earlier.
1876 Be sure this does not happen. */
1877 if (TYPE_BINFO (type1)
1878 && polymorphic_type_binfo_p (TYPE_BINFO (type1))
1879 && !build_bases)
1880 odr_must_violate = true;
1881 break;
1883 /* One base is polymorphic and the other not.
1884 This ought to be diagnosed earlier, but do not ICE in the
1885 checking bellow. */
1886 else if (TYPE_BINFO (type1)
1887 && polymorphic_type_binfo_p (TYPE_BINFO (type1))
1888 != polymorphic_type_binfo_p (TYPE_BINFO (type2)))
1890 if (!warned && !val->odr_violated)
1891 warn_odr (type, val->type, NULL, NULL,
1892 !warned, &warned,
1893 "a base of the type is polymorphic only in one "
1894 "translation unit");
1895 base_mismatch = true;
1896 break;
1899 if (base_mismatch)
1901 merge = false;
1902 odr_violation_reported = true;
1903 val->odr_violated = true;
1905 if (symtab->dump_file)
1907 fprintf (symtab->dump_file, "ODR base violation\n");
1909 print_node (symtab->dump_file, "", val->type, 0);
1910 putc ('\n',symtab->dump_file);
1911 print_node (symtab->dump_file, "", type, 0);
1912 putc ('\n',symtab->dump_file);
1917 /* Next compare memory layout. */
1918 if (!odr_types_equivalent_p (val->type, type,
1919 !flag_ltrans && !val->odr_violated && !warned,
1920 &warned, &visited))
1922 merge = false;
1923 odr_violation_reported = true;
1924 val->odr_violated = true;
1925 if (symtab->dump_file)
1927 fprintf (symtab->dump_file, "ODR violation\n");
1929 print_node (symtab->dump_file, "", val->type, 0);
1930 putc ('\n',symtab->dump_file);
1931 print_node (symtab->dump_file, "", type, 0);
1932 putc ('\n',symtab->dump_file);
1935 gcc_assert (val->odr_violated || !odr_must_violate);
1936 /* Sanity check that all bases will be build same way again. */
1937 #ifdef ENABLE_CHECKING
1938 if (COMPLETE_TYPE_P (type) && COMPLETE_TYPE_P (val->type)
1939 && TREE_CODE (val->type) == RECORD_TYPE
1940 && TREE_CODE (type) == RECORD_TYPE
1941 && TYPE_BINFO (val->type) && TYPE_BINFO (type)
1942 && !val->odr_violated
1943 && !base_mismatch && val->bases.length ())
1945 unsigned int num_poly_bases = 0;
1946 unsigned int j;
1948 for (i = 0; i < BINFO_N_BASE_BINFOS (TYPE_BINFO (type)); i++)
1949 if (polymorphic_type_binfo_p (BINFO_BASE_BINFO
1950 (TYPE_BINFO (type), i)))
1951 num_poly_bases++;
1952 gcc_assert (num_poly_bases == val->bases.length ());
1953 for (j = 0, i = 0; i < BINFO_N_BASE_BINFOS (TYPE_BINFO (type));
1954 i++)
1955 if (polymorphic_type_binfo_p (BINFO_BASE_BINFO
1956 (TYPE_BINFO (type), i)))
1958 odr_type base = get_odr_type
1959 (BINFO_TYPE
1960 (BINFO_BASE_BINFO (TYPE_BINFO (type),
1961 i)),
1962 true);
1963 gcc_assert (val->bases[j] == base);
1964 j++;
1967 #endif
1970 /* Regularize things a little. During LTO same types may come with
1971 different BINFOs. Either because their virtual table was
1972 not merged by tree merging and only later at decl merging or
1973 because one type comes with external vtable, while other
1974 with internal. We want to merge equivalent binfos to conserve
1975 memory and streaming overhead.
1977 The external vtables are more harmful: they contain references
1978 to external declarations of methods that may be defined in the
1979 merged LTO unit. For this reason we absolutely need to remove
1980 them and replace by internal variants. Not doing so will lead
1981 to incomplete answers from possible_polymorphic_call_targets.
1983 FIXME: disable for now; because ODR types are now build during
1984 streaming in, the variants do not need to be linked to the type,
1985 yet. We need to do the merging in cleanup pass to be implemented
1986 soon. */
1987 if (!flag_ltrans && merge
1988 && 0
1989 && TREE_CODE (val->type) == RECORD_TYPE
1990 && TREE_CODE (type) == RECORD_TYPE
1991 && TYPE_BINFO (val->type) && TYPE_BINFO (type)
1992 && TYPE_MAIN_VARIANT (type) == type
1993 && TYPE_MAIN_VARIANT (val->type) == val->type
1994 && BINFO_VTABLE (TYPE_BINFO (val->type))
1995 && BINFO_VTABLE (TYPE_BINFO (type)))
1997 tree master_binfo = TYPE_BINFO (val->type);
1998 tree v1 = BINFO_VTABLE (master_binfo);
1999 tree v2 = BINFO_VTABLE (TYPE_BINFO (type));
2001 if (TREE_CODE (v1) == POINTER_PLUS_EXPR)
2003 gcc_assert (TREE_CODE (v2) == POINTER_PLUS_EXPR
2004 && operand_equal_p (TREE_OPERAND (v1, 1),
2005 TREE_OPERAND (v2, 1), 0));
2006 v1 = TREE_OPERAND (TREE_OPERAND (v1, 0), 0);
2007 v2 = TREE_OPERAND (TREE_OPERAND (v2, 0), 0);
2009 gcc_assert (DECL_ASSEMBLER_NAME (v1)
2010 == DECL_ASSEMBLER_NAME (v2));
2012 if (DECL_EXTERNAL (v1) && !DECL_EXTERNAL (v2))
2014 unsigned int i;
2016 set_type_binfo (val->type, TYPE_BINFO (type));
2017 for (i = 0; i < val->types->length (); i++)
2019 if (TYPE_BINFO ((*val->types)[i])
2020 == master_binfo)
2021 set_type_binfo ((*val->types)[i], TYPE_BINFO (type));
2023 BINFO_TYPE (TYPE_BINFO (type)) = val->type;
2025 else
2026 set_type_binfo (type, master_binfo);
2028 return build_bases;
2031 /* Get ODR type hash entry for TYPE. If INSERT is true, create
2032 possibly new entry. */
2034 odr_type
2035 get_odr_type (tree type, bool insert)
2037 odr_type_d **slot = NULL;
2038 odr_type_d **vtable_slot = NULL;
2039 odr_type val = NULL;
2040 hashval_t hash;
2041 bool build_bases = false;
2042 bool insert_to_odr_array = false;
2043 int base_id = -1;
2045 type = main_odr_variant (type);
2047 gcc_checking_assert (can_be_name_hashed_p (type)
2048 || can_be_vtable_hashed_p (type));
2050 /* Lookup entry, first try name hash, fallback to vtable hash. */
2051 if (can_be_name_hashed_p (type))
2053 hash = hash_odr_name (type);
2054 slot = odr_hash->find_slot_with_hash (type, hash,
2055 insert ? INSERT : NO_INSERT);
2057 if ((!slot || !*slot) && in_lto_p && can_be_vtable_hashed_p (type))
2059 hash = hash_odr_vtable (type);
2060 vtable_slot = odr_vtable_hash->find_slot_with_hash (type, hash,
2061 insert ? INSERT : NO_INSERT);
2064 if (!slot && !vtable_slot)
2065 return NULL;
2067 /* See if we already have entry for type. */
2068 if ((slot && *slot) || (vtable_slot && *vtable_slot))
2070 if (slot && *slot)
2072 val = *slot;
2073 #ifdef ENABLE_CHECKING
2074 if (in_lto_p && can_be_vtable_hashed_p (type))
2076 hash = hash_odr_vtable (type);
2077 vtable_slot = odr_vtable_hash->find_slot_with_hash (type, hash,
2078 NO_INSERT);
2079 gcc_assert (!vtable_slot || *vtable_slot == *slot);
2080 vtable_slot = NULL;
2082 #endif
2084 else if (*vtable_slot)
2085 val = *vtable_slot;
2087 if (val->type != type
2088 && (!val->types_set || !val->types_set->add (type)))
2090 gcc_assert (insert);
2091 /* We have type duplicate, but it may introduce vtable name or
2092 mangled name; be sure to keep hashes in sync. */
2093 if (in_lto_p && can_be_vtable_hashed_p (type)
2094 && (!vtable_slot || !*vtable_slot))
2096 if (!vtable_slot)
2098 hash = hash_odr_vtable (type);
2099 vtable_slot = odr_vtable_hash->find_slot_with_hash
2100 (type, hash, INSERT);
2101 gcc_checking_assert (!*vtable_slot || *vtable_slot == val);
2103 *vtable_slot = val;
2105 if (slot && !*slot)
2106 *slot = val;
2107 build_bases = add_type_duplicate (val, type);
2110 else
2112 val = ggc_cleared_alloc<odr_type_d> ();
2113 val->type = type;
2114 val->bases = vNULL;
2115 val->derived_types = vNULL;
2116 if (type_with_linkage_p (type))
2117 val->anonymous_namespace = type_in_anonymous_namespace_p (type);
2118 else
2119 val->anonymous_namespace = 0;
2120 build_bases = COMPLETE_TYPE_P (val->type);
2121 insert_to_odr_array = true;
2122 if (slot)
2123 *slot = val;
2124 if (vtable_slot)
2125 *vtable_slot = val;
2128 if (build_bases && TREE_CODE (type) == RECORD_TYPE && TYPE_BINFO (type)
2129 && type_with_linkage_p (type)
2130 && type == TYPE_MAIN_VARIANT (type))
2132 tree binfo = TYPE_BINFO (type);
2133 unsigned int i;
2135 gcc_assert (BINFO_TYPE (TYPE_BINFO (val->type)) == type);
2137 val->all_derivations_known = type_all_derivations_known_p (type);
2138 for (i = 0; i < BINFO_N_BASE_BINFOS (binfo); i++)
2139 /* For now record only polymorphic types. other are
2140 pointless for devirtualization and we can not precisely
2141 determine ODR equivalency of these during LTO. */
2142 if (polymorphic_type_binfo_p (BINFO_BASE_BINFO (binfo, i)))
2144 tree base_type= BINFO_TYPE (BINFO_BASE_BINFO (binfo, i));
2145 odr_type base = get_odr_type (base_type, true);
2146 gcc_assert (TYPE_MAIN_VARIANT (base_type) == base_type);
2147 base->derived_types.safe_push (val);
2148 val->bases.safe_push (base);
2149 if (base->id > base_id)
2150 base_id = base->id;
2153 /* Ensure that type always appears after bases. */
2154 if (insert_to_odr_array)
2156 if (odr_types_ptr)
2157 val->id = odr_types.length ();
2158 vec_safe_push (odr_types_ptr, val);
2160 else if (base_id > val->id)
2162 odr_types[val->id] = 0;
2163 /* Be sure we did not recorded any derived types; these may need
2164 renumbering too. */
2165 gcc_assert (val->derived_types.length() == 0);
2166 if (odr_types_ptr)
2167 val->id = odr_types.length ();
2168 vec_safe_push (odr_types_ptr, val);
2170 return val;
2173 /* Add TYPE od ODR type hash. */
2175 void
2176 register_odr_type (tree type)
2178 if (!odr_hash)
2180 odr_hash = new odr_hash_type (23);
2181 if (in_lto_p)
2182 odr_vtable_hash = new odr_vtable_hash_type (23);
2184 /* Arrange things to be nicer and insert main variants first.
2185 ??? fundamental prerecorded types do not have mangled names; this
2186 makes it possible that non-ODR type is main_odr_variant of ODR type.
2187 Things may get smoother if LTO FE set mangled name of those types same
2188 way as C++ FE does. */
2189 if (odr_type_p (main_odr_variant (TYPE_MAIN_VARIANT (type)))
2190 && odr_type_p (TYPE_MAIN_VARIANT (type)))
2191 get_odr_type (TYPE_MAIN_VARIANT (type), true);
2192 if (TYPE_MAIN_VARIANT (type) != type && odr_type_p (main_odr_variant (type)))
2193 get_odr_type (type, true);
2196 /* Return true if type is known to have no derivations. */
2198 bool
2199 type_known_to_have_no_derivations_p (tree t)
2201 return (type_all_derivations_known_p (t)
2202 && (TYPE_FINAL_P (t)
2203 || (odr_hash
2204 && !get_odr_type (t, true)->derived_types.length())));
2207 /* Dump ODR type T and all its derived types. INDENT specifies indentation for
2208 recursive printing. */
2210 static void
2211 dump_odr_type (FILE *f, odr_type t, int indent=0)
2213 unsigned int i;
2214 fprintf (f, "%*s type %i: ", indent * 2, "", t->id);
2215 print_generic_expr (f, t->type, TDF_SLIM);
2216 fprintf (f, "%s", t->anonymous_namespace ? " (anonymous namespace)":"");
2217 fprintf (f, "%s\n", t->all_derivations_known ? " (derivations known)":"");
2218 if (TYPE_NAME (t->type))
2220 /*fprintf (f, "%*s defined at: %s:%i\n", indent * 2, "",
2221 DECL_SOURCE_FILE (TYPE_NAME (t->type)),
2222 DECL_SOURCE_LINE (TYPE_NAME (t->type)));*/
2223 if (DECL_ASSEMBLER_NAME_SET_P (TYPE_NAME (t->type)))
2224 fprintf (f, "%*s mangled name: %s\n", indent * 2, "",
2225 IDENTIFIER_POINTER
2226 (DECL_ASSEMBLER_NAME (TYPE_NAME (t->type))));
2228 if (t->bases.length ())
2230 fprintf (f, "%*s base odr type ids: ", indent * 2, "");
2231 for (i = 0; i < t->bases.length (); i++)
2232 fprintf (f, " %i", t->bases[i]->id);
2233 fprintf (f, "\n");
2235 if (t->derived_types.length ())
2237 fprintf (f, "%*s derived types:\n", indent * 2, "");
2238 for (i = 0; i < t->derived_types.length (); i++)
2239 dump_odr_type (f, t->derived_types[i], indent + 1);
2241 fprintf (f, "\n");
2244 /* Dump the type inheritance graph. */
2246 static void
2247 dump_type_inheritance_graph (FILE *f)
2249 unsigned int i;
2250 if (!odr_types_ptr)
2251 return;
2252 fprintf (f, "\n\nType inheritance graph:\n");
2253 for (i = 0; i < odr_types.length (); i++)
2255 if (odr_types[i] && odr_types[i]->bases.length () == 0)
2256 dump_odr_type (f, odr_types[i]);
2258 for (i = 0; i < odr_types.length (); i++)
2260 if (odr_types[i] && odr_types[i]->types && odr_types[i]->types->length ())
2262 unsigned int j;
2263 fprintf (f, "Duplicate tree types for odr type %i\n", i);
2264 print_node (f, "", odr_types[i]->type, 0);
2265 for (j = 0; j < odr_types[i]->types->length (); j++)
2267 tree t;
2268 fprintf (f, "duplicate #%i\n", j);
2269 print_node (f, "", (*odr_types[i]->types)[j], 0);
2270 t = (*odr_types[i]->types)[j];
2271 while (TYPE_P (t) && TYPE_CONTEXT (t))
2273 t = TYPE_CONTEXT (t);
2274 print_node (f, "", t, 0);
2276 putc ('\n',f);
2282 /* Given method type T, return type of class it belongs to.
2283 Look up this pointer and get its type. */
2285 tree
2286 method_class_type (const_tree t)
2288 tree first_parm_type = TREE_VALUE (TYPE_ARG_TYPES (t));
2289 gcc_assert (TREE_CODE (t) == METHOD_TYPE);
2291 return TREE_TYPE (first_parm_type);
2294 /* Initialize IPA devirt and build inheritance tree graph. */
2296 void
2297 build_type_inheritance_graph (void)
2299 struct symtab_node *n;
2300 FILE *inheritance_dump_file;
2301 int flags;
2303 if (odr_hash)
2304 return;
2305 timevar_push (TV_IPA_INHERITANCE);
2306 inheritance_dump_file = dump_begin (TDI_inheritance, &flags);
2307 odr_hash = new odr_hash_type (23);
2308 if (in_lto_p)
2309 odr_vtable_hash = new odr_vtable_hash_type (23);
2311 /* We reconstruct the graph starting of types of all methods seen in the
2312 the unit. */
2313 FOR_EACH_SYMBOL (n)
2314 if (is_a <cgraph_node *> (n)
2315 && DECL_VIRTUAL_P (n->decl)
2316 && n->real_symbol_p ())
2317 get_odr_type (TYPE_MAIN_VARIANT (method_class_type (TREE_TYPE (n->decl))),
2318 true);
2320 /* Look also for virtual tables of types that do not define any methods.
2322 We need it in a case where class B has virtual base of class A
2323 re-defining its virtual method and there is class C with no virtual
2324 methods with B as virtual base.
2326 Here we output B's virtual method in two variant - for non-virtual
2327 and virtual inheritance. B's virtual table has non-virtual version,
2328 while C's has virtual.
2330 For this reason we need to know about C in order to include both
2331 variants of B. More correctly, record_target_from_binfo should
2332 add both variants of the method when walking B, but we have no
2333 link in between them.
2335 We rely on fact that either the method is exported and thus we
2336 assume it is called externally or C is in anonymous namespace and
2337 thus we will see the vtable. */
2339 else if (is_a <varpool_node *> (n)
2340 && DECL_VIRTUAL_P (n->decl)
2341 && TREE_CODE (DECL_CONTEXT (n->decl)) == RECORD_TYPE
2342 && TYPE_BINFO (DECL_CONTEXT (n->decl))
2343 && polymorphic_type_binfo_p (TYPE_BINFO (DECL_CONTEXT (n->decl))))
2344 get_odr_type (TYPE_MAIN_VARIANT (DECL_CONTEXT (n->decl)), true);
2345 if (inheritance_dump_file)
2347 dump_type_inheritance_graph (inheritance_dump_file);
2348 dump_end (TDI_inheritance, inheritance_dump_file);
2350 timevar_pop (TV_IPA_INHERITANCE);
2353 /* Return true if N has reference from live virtual table
2354 (and thus can be a destination of polymorphic call).
2355 Be conservatively correct when callgraph is not built or
2356 if the method may be referred externally. */
2358 static bool
2359 referenced_from_vtable_p (struct cgraph_node *node)
2361 int i;
2362 struct ipa_ref *ref;
2363 bool found = false;
2365 if (node->externally_visible
2366 || DECL_EXTERNAL (node->decl)
2367 || node->used_from_other_partition)
2368 return true;
2370 /* Keep this test constant time.
2371 It is unlikely this can happen except for the case where speculative
2372 devirtualization introduced many speculative edges to this node.
2373 In this case the target is very likely alive anyway. */
2374 if (node->ref_list.referring.length () > 100)
2375 return true;
2377 /* We need references built. */
2378 if (symtab->state <= CONSTRUCTION)
2379 return true;
2381 for (i = 0; node->iterate_referring (i, ref); i++)
2382 if ((ref->use == IPA_REF_ALIAS
2383 && referenced_from_vtable_p (dyn_cast<cgraph_node *> (ref->referring)))
2384 || (ref->use == IPA_REF_ADDR
2385 && TREE_CODE (ref->referring->decl) == VAR_DECL
2386 && DECL_VIRTUAL_P (ref->referring->decl)))
2388 found = true;
2389 break;
2391 return found;
2394 /* If TARGET has associated node, record it in the NODES array.
2395 CAN_REFER specify if program can refer to the target directly.
2396 if TARGET is unknown (NULL) or it can not be inserted (for example because
2397 its body was already removed and there is no way to refer to it), clear
2398 COMPLETEP. */
2400 static void
2401 maybe_record_node (vec <cgraph_node *> &nodes,
2402 tree target, hash_set<tree> *inserted,
2403 bool can_refer,
2404 bool *completep)
2406 struct cgraph_node *target_node, *alias_target;
2407 enum availability avail;
2409 /* cxa_pure_virtual and __builtin_unreachable do not need to be added into
2410 list of targets; the runtime effect of calling them is undefined.
2411 Only "real" virtual methods should be accounted. */
2412 if (target && TREE_CODE (TREE_TYPE (target)) != METHOD_TYPE)
2413 return;
2415 if (!can_refer)
2417 /* The only case when method of anonymous namespace becomes unreferable
2418 is when we completely optimized it out. */
2419 if (flag_ltrans
2420 || !target
2421 || !type_in_anonymous_namespace_p (DECL_CONTEXT (target)))
2422 *completep = false;
2423 return;
2426 if (!target)
2427 return;
2429 target_node = cgraph_node::get (target);
2431 /* Prefer alias target over aliases, so we do not get confused by
2432 fake duplicates. */
2433 if (target_node)
2435 alias_target = target_node->ultimate_alias_target (&avail);
2436 if (target_node != alias_target
2437 && avail >= AVAIL_AVAILABLE
2438 && target_node->get_availability ())
2439 target_node = alias_target;
2442 /* Method can only be called by polymorphic call if any
2443 of vtables referring to it are alive.
2445 While this holds for non-anonymous functions, too, there are
2446 cases where we want to keep them in the list; for example
2447 inline functions with -fno-weak are static, but we still
2448 may devirtualize them when instance comes from other unit.
2449 The same holds for LTO.
2451 Currently we ignore these functions in speculative devirtualization.
2452 ??? Maybe it would make sense to be more aggressive for LTO even
2453 elsewhere. */
2454 if (!flag_ltrans
2455 && type_in_anonymous_namespace_p (DECL_CONTEXT (target))
2456 && (!target_node
2457 || !referenced_from_vtable_p (target_node)))
2459 /* See if TARGET is useful function we can deal with. */
2460 else if (target_node != NULL
2461 && (TREE_PUBLIC (target)
2462 || DECL_EXTERNAL (target)
2463 || target_node->definition)
2464 && target_node->real_symbol_p ())
2466 gcc_assert (!target_node->global.inlined_to);
2467 gcc_assert (target_node->real_symbol_p ());
2468 if (!inserted->add (target))
2470 cached_polymorphic_call_targets->add (target_node);
2471 nodes.safe_push (target_node);
2474 else if (completep
2475 && (!type_in_anonymous_namespace_p
2476 (DECL_CONTEXT (target))
2477 || flag_ltrans))
2478 *completep = false;
2481 /* See if BINFO's type matches OUTER_TYPE. If so, look up
2482 BINFO of subtype of OTR_TYPE at OFFSET and in that BINFO find
2483 method in vtable and insert method to NODES array
2484 or BASES_TO_CONSIDER if this array is non-NULL.
2485 Otherwise recurse to base BINFOs.
2486 This matches what get_binfo_at_offset does, but with offset
2487 being unknown.
2489 TYPE_BINFOS is a stack of BINFOS of types with defined
2490 virtual table seen on way from class type to BINFO.
2492 MATCHED_VTABLES tracks virtual tables we already did lookup
2493 for virtual function in. INSERTED tracks nodes we already
2494 inserted.
2496 ANONYMOUS is true if BINFO is part of anonymous namespace.
2498 Clear COMPLETEP when we hit unreferable target.
2501 static void
2502 record_target_from_binfo (vec <cgraph_node *> &nodes,
2503 vec <tree> *bases_to_consider,
2504 tree binfo,
2505 tree otr_type,
2506 vec <tree> &type_binfos,
2507 HOST_WIDE_INT otr_token,
2508 tree outer_type,
2509 HOST_WIDE_INT offset,
2510 hash_set<tree> *inserted,
2511 hash_set<tree> *matched_vtables,
2512 bool anonymous,
2513 bool *completep)
2515 tree type = BINFO_TYPE (binfo);
2516 int i;
2517 tree base_binfo;
2520 if (BINFO_VTABLE (binfo))
2521 type_binfos.safe_push (binfo);
2522 if (types_same_for_odr (type, outer_type))
2524 int i;
2525 tree type_binfo = NULL;
2527 /* Look up BINFO with virtual table. For normal types it is always last
2528 binfo on stack. */
2529 for (i = type_binfos.length () - 1; i >= 0; i--)
2530 if (BINFO_OFFSET (type_binfos[i]) == BINFO_OFFSET (binfo))
2532 type_binfo = type_binfos[i];
2533 break;
2535 if (BINFO_VTABLE (binfo))
2536 type_binfos.pop ();
2537 /* If this is duplicated BINFO for base shared by virtual inheritance,
2538 we may not have its associated vtable. This is not a problem, since
2539 we will walk it on the other path. */
2540 if (!type_binfo)
2541 return;
2542 tree inner_binfo = get_binfo_at_offset (type_binfo,
2543 offset, otr_type);
2544 if (!inner_binfo)
2546 gcc_assert (odr_violation_reported);
2547 return;
2549 /* For types in anonymous namespace first check if the respective vtable
2550 is alive. If not, we know the type can't be called. */
2551 if (!flag_ltrans && anonymous)
2553 tree vtable = BINFO_VTABLE (inner_binfo);
2554 varpool_node *vnode;
2556 if (TREE_CODE (vtable) == POINTER_PLUS_EXPR)
2557 vtable = TREE_OPERAND (TREE_OPERAND (vtable, 0), 0);
2558 vnode = varpool_node::get (vtable);
2559 if (!vnode || !vnode->definition)
2560 return;
2562 gcc_assert (inner_binfo);
2563 if (bases_to_consider
2564 ? !matched_vtables->contains (BINFO_VTABLE (inner_binfo))
2565 : !matched_vtables->add (BINFO_VTABLE (inner_binfo)))
2567 bool can_refer;
2568 tree target = gimple_get_virt_method_for_binfo (otr_token,
2569 inner_binfo,
2570 &can_refer);
2571 if (!bases_to_consider)
2572 maybe_record_node (nodes, target, inserted, can_refer, completep);
2573 /* Destructors are never called via construction vtables. */
2574 else if (!target || !DECL_CXX_DESTRUCTOR_P (target))
2575 bases_to_consider->safe_push (target);
2577 return;
2580 /* Walk bases. */
2581 for (i = 0; BINFO_BASE_ITERATE (binfo, i, base_binfo); i++)
2582 /* Walking bases that have no virtual method is pointless exercise. */
2583 if (polymorphic_type_binfo_p (base_binfo))
2584 record_target_from_binfo (nodes, bases_to_consider, base_binfo, otr_type,
2585 type_binfos,
2586 otr_token, outer_type, offset, inserted,
2587 matched_vtables, anonymous, completep);
2588 if (BINFO_VTABLE (binfo))
2589 type_binfos.pop ();
2592 /* Look up virtual methods matching OTR_TYPE (with OFFSET and OTR_TOKEN)
2593 of TYPE, insert them to NODES, recurse into derived nodes.
2594 INSERTED is used to avoid duplicate insertions of methods into NODES.
2595 MATCHED_VTABLES are used to avoid duplicate walking vtables.
2596 Clear COMPLETEP if unreferable target is found.
2598 If CONSIDER_CONSTRUCTION is true, record to BASES_TO_CONSIDER
2599 all cases where BASE_SKIPPED is true (because the base is abstract
2600 class). */
2602 static void
2603 possible_polymorphic_call_targets_1 (vec <cgraph_node *> &nodes,
2604 hash_set<tree> *inserted,
2605 hash_set<tree> *matched_vtables,
2606 tree otr_type,
2607 odr_type type,
2608 HOST_WIDE_INT otr_token,
2609 tree outer_type,
2610 HOST_WIDE_INT offset,
2611 bool *completep,
2612 vec <tree> &bases_to_consider,
2613 bool consider_construction)
2615 tree binfo = TYPE_BINFO (type->type);
2616 unsigned int i;
2617 auto_vec <tree, 8> type_binfos;
2618 bool possibly_instantiated = type_possibly_instantiated_p (type->type);
2620 /* We may need to consider types w/o instances because of possible derived
2621 types using their methods either directly or via construction vtables.
2622 We are safe to skip them when all derivations are known, since we will
2623 handle them later.
2624 This is done by recording them to BASES_TO_CONSIDER array. */
2625 if (possibly_instantiated || consider_construction)
2627 record_target_from_binfo (nodes,
2628 (!possibly_instantiated
2629 && type_all_derivations_known_p (type->type))
2630 ? &bases_to_consider : NULL,
2631 binfo, otr_type, type_binfos, otr_token,
2632 outer_type, offset,
2633 inserted, matched_vtables,
2634 type->anonymous_namespace, completep);
2636 for (i = 0; i < type->derived_types.length (); i++)
2637 possible_polymorphic_call_targets_1 (nodes, inserted,
2638 matched_vtables,
2639 otr_type,
2640 type->derived_types[i],
2641 otr_token, outer_type, offset, completep,
2642 bases_to_consider, consider_construction);
2645 /* Cache of queries for polymorphic call targets.
2647 Enumerating all call targets may get expensive when there are many
2648 polymorphic calls in the program, so we memoize all the previous
2649 queries and avoid duplicated work. */
2651 struct polymorphic_call_target_d
2653 HOST_WIDE_INT otr_token;
2654 ipa_polymorphic_call_context context;
2655 odr_type type;
2656 vec <cgraph_node *> targets;
2657 tree decl_warning;
2658 int type_warning;
2659 bool complete;
2660 bool speculative;
2663 /* Polymorphic call target cache helpers. */
2665 struct polymorphic_call_target_hasher
2667 typedef polymorphic_call_target_d *value_type;
2668 typedef polymorphic_call_target_d *compare_type;
2669 static inline hashval_t hash (const polymorphic_call_target_d *);
2670 static inline bool equal (const polymorphic_call_target_d *,
2671 const polymorphic_call_target_d *);
2672 static inline void remove (polymorphic_call_target_d *);
2675 /* Return the computed hashcode for ODR_QUERY. */
2677 inline hashval_t
2678 polymorphic_call_target_hasher::hash (const polymorphic_call_target_d *odr_query)
2680 inchash::hash hstate (odr_query->otr_token);
2682 hstate.add_wide_int (odr_query->type->id);
2683 hstate.merge_hash (TYPE_UID (odr_query->context.outer_type));
2684 hstate.add_wide_int (odr_query->context.offset);
2686 if (odr_query->context.speculative_outer_type)
2688 hstate.merge_hash (TYPE_UID (odr_query->context.speculative_outer_type));
2689 hstate.add_wide_int (odr_query->context.speculative_offset);
2691 hstate.add_flag (odr_query->speculative);
2692 hstate.add_flag (odr_query->context.maybe_in_construction);
2693 hstate.add_flag (odr_query->context.maybe_derived_type);
2694 hstate.add_flag (odr_query->context.speculative_maybe_derived_type);
2695 hstate.commit_flag ();
2696 return hstate.end ();
2699 /* Compare cache entries T1 and T2. */
2701 inline bool
2702 polymorphic_call_target_hasher::equal (const polymorphic_call_target_d *t1,
2703 const polymorphic_call_target_d *t2)
2705 return (t1->type == t2->type && t1->otr_token == t2->otr_token
2706 && t1->speculative == t2->speculative
2707 && t1->context.offset == t2->context.offset
2708 && t1->context.speculative_offset == t2->context.speculative_offset
2709 && t1->context.outer_type == t2->context.outer_type
2710 && t1->context.speculative_outer_type == t2->context.speculative_outer_type
2711 && t1->context.maybe_in_construction
2712 == t2->context.maybe_in_construction
2713 && t1->context.maybe_derived_type == t2->context.maybe_derived_type
2714 && (t1->context.speculative_maybe_derived_type
2715 == t2->context.speculative_maybe_derived_type));
2718 /* Remove entry in polymorphic call target cache hash. */
2720 inline void
2721 polymorphic_call_target_hasher::remove (polymorphic_call_target_d *v)
2723 v->targets.release ();
2724 free (v);
2727 /* Polymorphic call target query cache. */
2729 typedef hash_table<polymorphic_call_target_hasher>
2730 polymorphic_call_target_hash_type;
2731 static polymorphic_call_target_hash_type *polymorphic_call_target_hash;
2733 /* Destroy polymorphic call target query cache. */
2735 static void
2736 free_polymorphic_call_targets_hash ()
2738 if (cached_polymorphic_call_targets)
2740 delete polymorphic_call_target_hash;
2741 polymorphic_call_target_hash = NULL;
2742 delete cached_polymorphic_call_targets;
2743 cached_polymorphic_call_targets = NULL;
2747 /* When virtual function is removed, we may need to flush the cache. */
2749 static void
2750 devirt_node_removal_hook (struct cgraph_node *n, void *d ATTRIBUTE_UNUSED)
2752 if (cached_polymorphic_call_targets
2753 && cached_polymorphic_call_targets->contains (n))
2754 free_polymorphic_call_targets_hash ();
2757 /* Look up base of BINFO that has virtual table VTABLE with OFFSET. */
2759 tree
2760 subbinfo_with_vtable_at_offset (tree binfo, unsigned HOST_WIDE_INT offset,
2761 tree vtable)
2763 tree v = BINFO_VTABLE (binfo);
2764 int i;
2765 tree base_binfo;
2766 unsigned HOST_WIDE_INT this_offset;
2768 if (v)
2770 if (!vtable_pointer_value_to_vtable (v, &v, &this_offset))
2771 gcc_unreachable ();
2773 if (offset == this_offset
2774 && DECL_ASSEMBLER_NAME (v) == DECL_ASSEMBLER_NAME (vtable))
2775 return binfo;
2778 for (i = 0; BINFO_BASE_ITERATE (binfo, i, base_binfo); i++)
2779 if (polymorphic_type_binfo_p (base_binfo))
2781 base_binfo = subbinfo_with_vtable_at_offset (base_binfo, offset, vtable);
2782 if (base_binfo)
2783 return base_binfo;
2785 return NULL;
2788 /* T is known constant value of virtual table pointer.
2789 Store virtual table to V and its offset to OFFSET.
2790 Return false if T does not look like virtual table reference. */
2792 bool
2793 vtable_pointer_value_to_vtable (const_tree t, tree *v,
2794 unsigned HOST_WIDE_INT *offset)
2796 /* We expect &MEM[(void *)&virtual_table + 16B].
2797 We obtain object's BINFO from the context of the virtual table.
2798 This one contains pointer to virtual table represented via
2799 POINTER_PLUS_EXPR. Verify that this pointer matches what
2800 we propagated through.
2802 In the case of virtual inheritance, the virtual tables may
2803 be nested, i.e. the offset may be different from 16 and we may
2804 need to dive into the type representation. */
2805 if (TREE_CODE (t) == ADDR_EXPR
2806 && TREE_CODE (TREE_OPERAND (t, 0)) == MEM_REF
2807 && TREE_CODE (TREE_OPERAND (TREE_OPERAND (t, 0), 0)) == ADDR_EXPR
2808 && TREE_CODE (TREE_OPERAND (TREE_OPERAND (t, 0), 1)) == INTEGER_CST
2809 && (TREE_CODE (TREE_OPERAND (TREE_OPERAND (TREE_OPERAND (t, 0), 0), 0))
2810 == VAR_DECL)
2811 && DECL_VIRTUAL_P (TREE_OPERAND (TREE_OPERAND
2812 (TREE_OPERAND (t, 0), 0), 0)))
2814 *v = TREE_OPERAND (TREE_OPERAND (TREE_OPERAND (t, 0), 0), 0);
2815 *offset = tree_to_uhwi (TREE_OPERAND (TREE_OPERAND (t, 0), 1));
2816 return true;
2819 /* Alternative representation, used by C++ frontend is POINTER_PLUS_EXPR.
2820 We need to handle it when T comes from static variable initializer or
2821 BINFO. */
2822 if (TREE_CODE (t) == POINTER_PLUS_EXPR)
2824 *offset = tree_to_uhwi (TREE_OPERAND (t, 1));
2825 t = TREE_OPERAND (t, 0);
2827 else
2828 *offset = 0;
2830 if (TREE_CODE (t) != ADDR_EXPR)
2831 return false;
2832 *v = TREE_OPERAND (t, 0);
2833 return true;
2836 /* T is known constant value of virtual table pointer. Return BINFO of the
2837 instance type. */
2839 tree
2840 vtable_pointer_value_to_binfo (const_tree t)
2842 tree vtable;
2843 unsigned HOST_WIDE_INT offset;
2845 if (!vtable_pointer_value_to_vtable (t, &vtable, &offset))
2846 return NULL_TREE;
2848 /* FIXME: for stores of construction vtables we return NULL,
2849 because we do not have BINFO for those. Eventually we should fix
2850 our representation to allow this case to be handled, too.
2851 In the case we see store of BINFO we however may assume
2852 that standard folding will be able to cope with it. */
2853 return subbinfo_with_vtable_at_offset (TYPE_BINFO (DECL_CONTEXT (vtable)),
2854 offset, vtable);
2857 /* Walk bases of OUTER_TYPE that contain OTR_TYPE at OFFSET.
2858 Look up their respective virtual methods for OTR_TOKEN and OTR_TYPE
2859 and insert them in NODES.
2861 MATCHED_VTABLES and INSERTED is used to avoid duplicated work. */
2863 static void
2864 record_targets_from_bases (tree otr_type,
2865 HOST_WIDE_INT otr_token,
2866 tree outer_type,
2867 HOST_WIDE_INT offset,
2868 vec <cgraph_node *> &nodes,
2869 hash_set<tree> *inserted,
2870 hash_set<tree> *matched_vtables,
2871 bool *completep)
2873 while (true)
2875 HOST_WIDE_INT pos, size;
2876 tree base_binfo;
2877 tree fld;
2879 if (types_same_for_odr (outer_type, otr_type))
2880 return;
2882 for (fld = TYPE_FIELDS (outer_type); fld; fld = DECL_CHAIN (fld))
2884 if (TREE_CODE (fld) != FIELD_DECL)
2885 continue;
2887 pos = int_bit_position (fld);
2888 size = tree_to_shwi (DECL_SIZE (fld));
2889 if (pos <= offset && (pos + size) > offset
2890 /* Do not get confused by zero sized bases. */
2891 && polymorphic_type_binfo_p (TYPE_BINFO (TREE_TYPE (fld))))
2892 break;
2894 /* Within a class type we should always find corresponding fields. */
2895 gcc_assert (fld && TREE_CODE (TREE_TYPE (fld)) == RECORD_TYPE);
2897 /* Nonbase types should have been stripped by outer_class_type. */
2898 gcc_assert (DECL_ARTIFICIAL (fld));
2900 outer_type = TREE_TYPE (fld);
2901 offset -= pos;
2903 base_binfo = get_binfo_at_offset (TYPE_BINFO (outer_type),
2904 offset, otr_type);
2905 if (!base_binfo)
2907 gcc_assert (odr_violation_reported);
2908 return;
2910 gcc_assert (base_binfo);
2911 if (!matched_vtables->add (BINFO_VTABLE (base_binfo)))
2913 bool can_refer;
2914 tree target = gimple_get_virt_method_for_binfo (otr_token,
2915 base_binfo,
2916 &can_refer);
2917 if (!target || ! DECL_CXX_DESTRUCTOR_P (target))
2918 maybe_record_node (nodes, target, inserted, can_refer, completep);
2919 matched_vtables->add (BINFO_VTABLE (base_binfo));
2924 /* When virtual table is removed, we may need to flush the cache. */
2926 static void
2927 devirt_variable_node_removal_hook (varpool_node *n,
2928 void *d ATTRIBUTE_UNUSED)
2930 if (cached_polymorphic_call_targets
2931 && DECL_VIRTUAL_P (n->decl)
2932 && type_in_anonymous_namespace_p (DECL_CONTEXT (n->decl)))
2933 free_polymorphic_call_targets_hash ();
2936 /* Record about how many calls would benefit from given type to be final. */
2938 struct odr_type_warn_count
2940 tree type;
2941 int count;
2942 gcov_type dyn_count;
2945 /* Record about how many calls would benefit from given method to be final. */
2947 struct decl_warn_count
2949 tree decl;
2950 int count;
2951 gcov_type dyn_count;
2954 /* Information about type and decl warnings. */
2956 struct final_warning_record
2958 gcov_type dyn_count;
2959 vec<odr_type_warn_count> type_warnings;
2960 hash_map<tree, decl_warn_count> decl_warnings;
2962 struct final_warning_record *final_warning_records;
2964 /* Return vector containing possible targets of polymorphic call of type
2965 OTR_TYPE calling method OTR_TOKEN within type of OTR_OUTER_TYPE and OFFSET.
2966 If INCLUDE_BASES is true, walk also base types of OUTER_TYPES containing
2967 OTR_TYPE and include their virtual method. This is useful for types
2968 possibly in construction or destruction where the virtual table may
2969 temporarily change to one of base types. INCLUDE_DERIVER_TYPES make
2970 us to walk the inheritance graph for all derivations.
2972 If COMPLETEP is non-NULL, store true if the list is complete.
2973 CACHE_TOKEN (if non-NULL) will get stored to an unique ID of entry
2974 in the target cache. If user needs to visit every target list
2975 just once, it can memoize them.
2977 If SPECULATIVE is set, the list will not contain targets that
2978 are not speculatively taken.
2980 Returned vector is placed into cache. It is NOT caller's responsibility
2981 to free it. The vector can be freed on cgraph_remove_node call if
2982 the particular node is a virtual function present in the cache. */
2984 vec <cgraph_node *>
2985 possible_polymorphic_call_targets (tree otr_type,
2986 HOST_WIDE_INT otr_token,
2987 ipa_polymorphic_call_context context,
2988 bool *completep,
2989 void **cache_token,
2990 bool speculative)
2992 static struct cgraph_node_hook_list *node_removal_hook_holder;
2993 vec <cgraph_node *> nodes = vNULL;
2994 auto_vec <tree, 8> bases_to_consider;
2995 odr_type type, outer_type;
2996 polymorphic_call_target_d key;
2997 polymorphic_call_target_d **slot;
2998 unsigned int i;
2999 tree binfo, target;
3000 bool complete;
3001 bool can_refer = false;
3002 bool skipped = false;
3004 otr_type = TYPE_MAIN_VARIANT (otr_type);
3006 /* If ODR is not initialized or the context is invalid, return empty
3007 incomplete list. */
3008 if (!odr_hash || context.invalid || !TYPE_BINFO (otr_type))
3010 if (completep)
3011 *completep = context.invalid;
3012 if (cache_token)
3013 *cache_token = NULL;
3014 return nodes;
3017 /* Do not bother to compute speculative info when user do not asks for it. */
3018 if (!speculative || !context.speculative_outer_type)
3019 context.clear_speculation ();
3021 type = get_odr_type (otr_type, true);
3023 /* Recording type variants would waste results cache. */
3024 gcc_assert (!context.outer_type
3025 || TYPE_MAIN_VARIANT (context.outer_type) == context.outer_type);
3027 /* Look up the outer class type we want to walk.
3028 If we fail to do so, the context is invalid. */
3029 if ((context.outer_type || context.speculative_outer_type)
3030 && !context.restrict_to_inner_class (otr_type))
3032 if (completep)
3033 *completep = true;
3034 if (cache_token)
3035 *cache_token = NULL;
3036 return nodes;
3038 gcc_assert (!context.invalid);
3040 /* Check that restrict_to_inner_class kept the main variant. */
3041 gcc_assert (!context.outer_type
3042 || TYPE_MAIN_VARIANT (context.outer_type) == context.outer_type);
3044 /* We canonicalize our query, so we do not need extra hashtable entries. */
3046 /* Without outer type, we have no use for offset. Just do the
3047 basic search from inner type. */
3048 if (!context.outer_type)
3049 context.clear_outer_type (otr_type);
3050 /* We need to update our hierarchy if the type does not exist. */
3051 outer_type = get_odr_type (context.outer_type, true);
3052 /* If the type is complete, there are no derivations. */
3053 if (TYPE_FINAL_P (outer_type->type))
3054 context.maybe_derived_type = false;
3056 /* Initialize query cache. */
3057 if (!cached_polymorphic_call_targets)
3059 cached_polymorphic_call_targets = new hash_set<cgraph_node *>;
3060 polymorphic_call_target_hash
3061 = new polymorphic_call_target_hash_type (23);
3062 if (!node_removal_hook_holder)
3064 node_removal_hook_holder =
3065 symtab->add_cgraph_removal_hook (&devirt_node_removal_hook, NULL);
3066 symtab->add_varpool_removal_hook (&devirt_variable_node_removal_hook,
3067 NULL);
3071 if (in_lto_p)
3073 if (context.outer_type != otr_type)
3074 context.outer_type
3075 = get_odr_type (context.outer_type, true)->type;
3076 if (context.speculative_outer_type)
3077 context.speculative_outer_type
3078 = get_odr_type (context.speculative_outer_type, true)->type;
3081 /* Look up cached answer. */
3082 key.type = type;
3083 key.otr_token = otr_token;
3084 key.speculative = speculative;
3085 key.context = context;
3086 slot = polymorphic_call_target_hash->find_slot (&key, INSERT);
3087 if (cache_token)
3088 *cache_token = (void *)*slot;
3089 if (*slot)
3091 if (completep)
3092 *completep = (*slot)->complete;
3093 if ((*slot)->type_warning && final_warning_records)
3095 final_warning_records->type_warnings[(*slot)->type_warning - 1].count++;
3096 final_warning_records->type_warnings[(*slot)->type_warning - 1].dyn_count
3097 += final_warning_records->dyn_count;
3099 if (!speculative && (*slot)->decl_warning && final_warning_records)
3101 struct decl_warn_count *c =
3102 final_warning_records->decl_warnings.get ((*slot)->decl_warning);
3103 c->count++;
3104 c->dyn_count += final_warning_records->dyn_count;
3106 return (*slot)->targets;
3109 complete = true;
3111 /* Do actual search. */
3112 timevar_push (TV_IPA_VIRTUAL_CALL);
3113 *slot = XCNEW (polymorphic_call_target_d);
3114 if (cache_token)
3115 *cache_token = (void *)*slot;
3116 (*slot)->type = type;
3117 (*slot)->otr_token = otr_token;
3118 (*slot)->context = context;
3119 (*slot)->speculative = speculative;
3121 hash_set<tree> inserted;
3122 hash_set<tree> matched_vtables;
3124 /* First insert targets we speculatively identified as likely. */
3125 if (context.speculative_outer_type)
3127 odr_type speculative_outer_type;
3128 bool speculation_complete = true;
3130 /* First insert target from type itself and check if it may have
3131 derived types. */
3132 speculative_outer_type = get_odr_type (context.speculative_outer_type, true);
3133 if (TYPE_FINAL_P (speculative_outer_type->type))
3134 context.speculative_maybe_derived_type = false;
3135 binfo = get_binfo_at_offset (TYPE_BINFO (speculative_outer_type->type),
3136 context.speculative_offset, otr_type);
3137 if (binfo)
3138 target = gimple_get_virt_method_for_binfo (otr_token, binfo,
3139 &can_refer);
3140 else
3141 target = NULL;
3143 /* In the case we get complete method, we don't need
3144 to walk derivations. */
3145 if (target && DECL_FINAL_P (target))
3146 context.speculative_maybe_derived_type = false;
3147 if (type_possibly_instantiated_p (speculative_outer_type->type))
3148 maybe_record_node (nodes, target, &inserted, can_refer, &speculation_complete);
3149 if (binfo)
3150 matched_vtables.add (BINFO_VTABLE (binfo));
3153 /* Next walk recursively all derived types. */
3154 if (context.speculative_maybe_derived_type)
3155 for (i = 0; i < speculative_outer_type->derived_types.length(); i++)
3156 possible_polymorphic_call_targets_1 (nodes, &inserted,
3157 &matched_vtables,
3158 otr_type,
3159 speculative_outer_type->derived_types[i],
3160 otr_token, speculative_outer_type->type,
3161 context.speculative_offset,
3162 &speculation_complete,
3163 bases_to_consider,
3164 false);
3167 if (!speculative || !nodes.length ())
3169 /* First see virtual method of type itself. */
3170 binfo = get_binfo_at_offset (TYPE_BINFO (outer_type->type),
3171 context.offset, otr_type);
3172 if (binfo)
3173 target = gimple_get_virt_method_for_binfo (otr_token, binfo,
3174 &can_refer);
3175 else
3177 gcc_assert (odr_violation_reported);
3178 target = NULL;
3181 /* Destructors are never called through construction virtual tables,
3182 because the type is always known. */
3183 if (target && DECL_CXX_DESTRUCTOR_P (target))
3184 context.maybe_in_construction = false;
3186 if (target)
3188 /* In the case we get complete method, we don't need
3189 to walk derivations. */
3190 if (DECL_FINAL_P (target))
3191 context.maybe_derived_type = false;
3194 /* If OUTER_TYPE is abstract, we know we are not seeing its instance. */
3195 if (type_possibly_instantiated_p (outer_type->type))
3196 maybe_record_node (nodes, target, &inserted, can_refer, &complete);
3197 else
3198 skipped = true;
3200 if (binfo)
3201 matched_vtables.add (BINFO_VTABLE (binfo));
3203 /* Next walk recursively all derived types. */
3204 if (context.maybe_derived_type)
3206 for (i = 0; i < outer_type->derived_types.length(); i++)
3207 possible_polymorphic_call_targets_1 (nodes, &inserted,
3208 &matched_vtables,
3209 otr_type,
3210 outer_type->derived_types[i],
3211 otr_token, outer_type->type,
3212 context.offset, &complete,
3213 bases_to_consider,
3214 context.maybe_in_construction);
3216 if (!outer_type->all_derivations_known)
3218 if (!speculative && final_warning_records)
3220 if (complete
3221 && nodes.length () == 1
3222 && warn_suggest_final_types
3223 && !outer_type->derived_types.length ())
3225 if (outer_type->id >= (int)final_warning_records->type_warnings.length ())
3226 final_warning_records->type_warnings.safe_grow_cleared
3227 (odr_types.length ());
3228 final_warning_records->type_warnings[outer_type->id].count++;
3229 final_warning_records->type_warnings[outer_type->id].dyn_count
3230 += final_warning_records->dyn_count;
3231 final_warning_records->type_warnings[outer_type->id].type
3232 = outer_type->type;
3233 (*slot)->type_warning = outer_type->id + 1;
3235 if (complete
3236 && warn_suggest_final_methods
3237 && nodes.length () == 1
3238 && types_same_for_odr (DECL_CONTEXT (nodes[0]->decl),
3239 outer_type->type))
3241 bool existed;
3242 struct decl_warn_count &c =
3243 final_warning_records->decl_warnings.get_or_insert
3244 (nodes[0]->decl, &existed);
3246 if (existed)
3248 c.count++;
3249 c.dyn_count += final_warning_records->dyn_count;
3251 else
3253 c.count = 1;
3254 c.dyn_count = final_warning_records->dyn_count;
3255 c.decl = nodes[0]->decl;
3257 (*slot)->decl_warning = nodes[0]->decl;
3260 complete = false;
3264 if (!speculative)
3266 /* Destructors are never called through construction virtual tables,
3267 because the type is always known. One of entries may be
3268 cxa_pure_virtual so look to at least two of them. */
3269 if (context.maybe_in_construction)
3270 for (i =0 ; i < MIN (nodes.length (), 2); i++)
3271 if (DECL_CXX_DESTRUCTOR_P (nodes[i]->decl))
3272 context.maybe_in_construction = false;
3273 if (context.maybe_in_construction)
3275 if (type != outer_type
3276 && (!skipped
3277 || (context.maybe_derived_type
3278 && !type_all_derivations_known_p (outer_type->type))))
3279 record_targets_from_bases (otr_type, otr_token, outer_type->type,
3280 context.offset, nodes, &inserted,
3281 &matched_vtables, &complete);
3282 if (skipped)
3283 maybe_record_node (nodes, target, &inserted, can_refer, &complete);
3284 for (i = 0; i < bases_to_consider.length(); i++)
3285 maybe_record_node (nodes, bases_to_consider[i], &inserted, can_refer, &complete);
3290 (*slot)->targets = nodes;
3291 (*slot)->complete = complete;
3292 if (completep)
3293 *completep = complete;
3295 timevar_pop (TV_IPA_VIRTUAL_CALL);
3296 return nodes;
3299 bool
3300 add_decl_warning (const tree &key ATTRIBUTE_UNUSED, const decl_warn_count &value,
3301 vec<const decl_warn_count*> *vec)
3303 vec->safe_push (&value);
3304 return true;
3307 /* Dump target list TARGETS into FILE. */
3309 static void
3310 dump_targets (FILE *f, vec <cgraph_node *> targets)
3312 unsigned int i;
3314 for (i = 0; i < targets.length (); i++)
3316 char *name = NULL;
3317 if (in_lto_p)
3318 name = cplus_demangle_v3 (targets[i]->asm_name (), 0);
3319 fprintf (f, " %s/%i", name ? name : targets[i]->name (), targets[i]->order);
3320 if (in_lto_p)
3321 free (name);
3322 if (!targets[i]->definition)
3323 fprintf (f, " (no definition%s)",
3324 DECL_DECLARED_INLINE_P (targets[i]->decl)
3325 ? " inline" : "");
3327 fprintf (f, "\n");
3330 /* Dump all possible targets of a polymorphic call. */
3332 void
3333 dump_possible_polymorphic_call_targets (FILE *f,
3334 tree otr_type,
3335 HOST_WIDE_INT otr_token,
3336 const ipa_polymorphic_call_context &ctx)
3338 vec <cgraph_node *> targets;
3339 bool final;
3340 odr_type type = get_odr_type (TYPE_MAIN_VARIANT (otr_type), false);
3341 unsigned int len;
3343 if (!type)
3344 return;
3345 targets = possible_polymorphic_call_targets (otr_type, otr_token,
3346 ctx,
3347 &final, NULL, false);
3348 fprintf (f, " Targets of polymorphic call of type %i:", type->id);
3349 print_generic_expr (f, type->type, TDF_SLIM);
3350 fprintf (f, " token %i\n", (int)otr_token);
3352 ctx.dump (f);
3354 fprintf (f, " %s%s%s%s\n ",
3355 final ? "This is a complete list." :
3356 "This is partial list; extra targets may be defined in other units.",
3357 ctx.maybe_in_construction ? " (base types included)" : "",
3358 ctx.maybe_derived_type ? " (derived types included)" : "",
3359 ctx.speculative_maybe_derived_type ? " (speculative derived types included)" : "");
3360 len = targets.length ();
3361 dump_targets (f, targets);
3363 targets = possible_polymorphic_call_targets (otr_type, otr_token,
3364 ctx,
3365 &final, NULL, true);
3366 if (targets.length () != len)
3368 fprintf (f, " Speculative targets:");
3369 dump_targets (f, targets);
3371 gcc_assert (targets.length () <= len);
3372 fprintf (f, "\n");
3376 /* Return true if N can be possibly target of a polymorphic call of
3377 OTR_TYPE/OTR_TOKEN. */
3379 bool
3380 possible_polymorphic_call_target_p (tree otr_type,
3381 HOST_WIDE_INT otr_token,
3382 const ipa_polymorphic_call_context &ctx,
3383 struct cgraph_node *n)
3385 vec <cgraph_node *> targets;
3386 unsigned int i;
3387 enum built_in_function fcode;
3388 bool final;
3390 if (TREE_CODE (TREE_TYPE (n->decl)) == FUNCTION_TYPE
3391 && ((fcode = DECL_FUNCTION_CODE (n->decl))
3392 == BUILT_IN_UNREACHABLE
3393 || fcode == BUILT_IN_TRAP))
3394 return true;
3396 if (!odr_hash)
3397 return true;
3398 targets = possible_polymorphic_call_targets (otr_type, otr_token, ctx, &final);
3399 for (i = 0; i < targets.length (); i++)
3400 if (n->semantically_equivalent_p (targets[i]))
3401 return true;
3403 /* At a moment we allow middle end to dig out new external declarations
3404 as a targets of polymorphic calls. */
3405 if (!final && !n->definition)
3406 return true;
3407 return false;
3412 /* Return true if N can be possibly target of a polymorphic call of
3413 OBJ_TYPE_REF expression REF in STMT. */
3415 bool
3416 possible_polymorphic_call_target_p (tree ref,
3417 gimple stmt,
3418 struct cgraph_node *n)
3420 ipa_polymorphic_call_context context (current_function_decl, ref, stmt);
3421 tree call_fn = gimple_call_fn (stmt);
3423 return possible_polymorphic_call_target_p (obj_type_ref_class (call_fn),
3424 tree_to_uhwi
3425 (OBJ_TYPE_REF_TOKEN (call_fn)),
3426 context,
3431 /* After callgraph construction new external nodes may appear.
3432 Add them into the graph. */
3434 void
3435 update_type_inheritance_graph (void)
3437 struct cgraph_node *n;
3439 if (!odr_hash)
3440 return;
3441 free_polymorphic_call_targets_hash ();
3442 timevar_push (TV_IPA_INHERITANCE);
3443 /* We reconstruct the graph starting from types of all methods seen in the
3444 the unit. */
3445 FOR_EACH_FUNCTION (n)
3446 if (DECL_VIRTUAL_P (n->decl)
3447 && !n->definition
3448 && n->real_symbol_p ())
3449 get_odr_type (method_class_type (TYPE_MAIN_VARIANT (TREE_TYPE (n->decl))),
3450 true);
3451 timevar_pop (TV_IPA_INHERITANCE);
3455 /* Return true if N looks like likely target of a polymorphic call.
3456 Rule out cxa_pure_virtual, noreturns, function declared cold and
3457 other obvious cases. */
3459 bool
3460 likely_target_p (struct cgraph_node *n)
3462 int flags;
3463 /* cxa_pure_virtual and similar things are not likely. */
3464 if (TREE_CODE (TREE_TYPE (n->decl)) != METHOD_TYPE)
3465 return false;
3466 flags = flags_from_decl_or_type (n->decl);
3467 if (flags & ECF_NORETURN)
3468 return false;
3469 if (lookup_attribute ("cold",
3470 DECL_ATTRIBUTES (n->decl)))
3471 return false;
3472 if (n->frequency < NODE_FREQUENCY_NORMAL)
3473 return false;
3474 /* If there are no live virtual tables referring the target,
3475 the only way the target can be called is an instance coming from other
3476 compilation unit; speculative devirtualization is built around an
3477 assumption that won't happen. */
3478 if (!referenced_from_vtable_p (n))
3479 return false;
3480 return true;
3483 /* Compare type warning records P1 and P2 and choose one with larger count;
3484 helper for qsort. */
3487 type_warning_cmp (const void *p1, const void *p2)
3489 const odr_type_warn_count *t1 = (const odr_type_warn_count *)p1;
3490 const odr_type_warn_count *t2 = (const odr_type_warn_count *)p2;
3492 if (t1->dyn_count < t2->dyn_count)
3493 return 1;
3494 if (t1->dyn_count > t2->dyn_count)
3495 return -1;
3496 return t2->count - t1->count;
3499 /* Compare decl warning records P1 and P2 and choose one with larger count;
3500 helper for qsort. */
3503 decl_warning_cmp (const void *p1, const void *p2)
3505 const decl_warn_count *t1 = *(const decl_warn_count * const *)p1;
3506 const decl_warn_count *t2 = *(const decl_warn_count * const *)p2;
3508 if (t1->dyn_count < t2->dyn_count)
3509 return 1;
3510 if (t1->dyn_count > t2->dyn_count)
3511 return -1;
3512 return t2->count - t1->count;
3516 /* Try to speculatively devirtualize call to OTR_TYPE with OTR_TOKEN with
3517 context CTX. */
3519 struct cgraph_node *
3520 try_speculative_devirtualization (tree otr_type, HOST_WIDE_INT otr_token,
3521 ipa_polymorphic_call_context ctx)
3523 vec <cgraph_node *>targets
3524 = possible_polymorphic_call_targets
3525 (otr_type, otr_token, ctx, NULL, NULL, true);
3526 unsigned int i;
3527 struct cgraph_node *likely_target = NULL;
3529 for (i = 0; i < targets.length (); i++)
3530 if (likely_target_p (targets[i]))
3532 if (likely_target)
3533 return NULL;
3534 likely_target = targets[i];
3536 if (!likely_target
3537 ||!likely_target->definition
3538 || DECL_EXTERNAL (likely_target->decl))
3539 return NULL;
3541 /* Don't use an implicitly-declared destructor (c++/58678). */
3542 struct cgraph_node *non_thunk_target
3543 = likely_target->function_symbol ();
3544 if (DECL_ARTIFICIAL (non_thunk_target->decl))
3545 return NULL;
3546 if (likely_target->get_availability () <= AVAIL_INTERPOSABLE
3547 && likely_target->can_be_discarded_p ())
3548 return NULL;
3549 return likely_target;
3552 /* The ipa-devirt pass.
3553 When polymorphic call has only one likely target in the unit,
3554 turn it into a speculative call. */
3556 static unsigned int
3557 ipa_devirt (void)
3559 struct cgraph_node *n;
3560 hash_set<void *> bad_call_targets;
3561 struct cgraph_edge *e;
3563 int npolymorphic = 0, nspeculated = 0, nconverted = 0, ncold = 0;
3564 int nmultiple = 0, noverwritable = 0, ndevirtualized = 0, nnotdefined = 0;
3565 int nwrong = 0, nok = 0, nexternal = 0, nartificial = 0;
3566 int ndropped = 0;
3568 if (!odr_types_ptr)
3569 return 0;
3571 if (dump_file)
3572 dump_type_inheritance_graph (dump_file);
3574 /* We can output -Wsuggest-final-methods and -Wsuggest-final-types warnings.
3575 This is implemented by setting up final_warning_records that are updated
3576 by get_polymorphic_call_targets.
3577 We need to clear cache in this case to trigger recomputation of all
3578 entries. */
3579 if (warn_suggest_final_methods || warn_suggest_final_types)
3581 final_warning_records = new (final_warning_record);
3582 final_warning_records->type_warnings = vNULL;
3583 final_warning_records->type_warnings.safe_grow_cleared (odr_types.length ());
3584 free_polymorphic_call_targets_hash ();
3587 FOR_EACH_DEFINED_FUNCTION (n)
3589 bool update = false;
3590 if (!opt_for_fn (n->decl, flag_devirtualize))
3591 continue;
3592 if (dump_file && n->indirect_calls)
3593 fprintf (dump_file, "\n\nProcesing function %s/%i\n",
3594 n->name (), n->order);
3595 for (e = n->indirect_calls; e; e = e->next_callee)
3596 if (e->indirect_info->polymorphic)
3598 struct cgraph_node *likely_target = NULL;
3599 void *cache_token;
3600 bool final;
3602 if (final_warning_records)
3603 final_warning_records->dyn_count = e->count;
3605 vec <cgraph_node *>targets
3606 = possible_polymorphic_call_targets
3607 (e, &final, &cache_token, true);
3608 unsigned int i;
3610 /* Trigger warnings by calculating non-speculative targets. */
3611 if (warn_suggest_final_methods || warn_suggest_final_types)
3612 possible_polymorphic_call_targets (e);
3614 if (dump_file)
3615 dump_possible_polymorphic_call_targets
3616 (dump_file, e);
3618 npolymorphic++;
3620 /* See if the call can be devirtualized by means of ipa-prop's
3621 polymorphic call context propagation. If not, we can just
3622 forget about this call being polymorphic and avoid some heavy
3623 lifting in remove_unreachable_nodes that will otherwise try to
3624 keep all possible targets alive until inlining and in the inliner
3625 itself.
3627 This may need to be revisited once we add further ways to use
3628 the may edges, but it is a resonable thing to do right now. */
3630 if ((e->indirect_info->param_index == -1
3631 || (!opt_for_fn (n->decl, flag_devirtualize_speculatively)
3632 && e->indirect_info->vptr_changed))
3633 && !flag_ltrans_devirtualize)
3635 e->indirect_info->polymorphic = false;
3636 ndropped++;
3637 if (dump_file)
3638 fprintf (dump_file, "Dropping polymorphic call info;"
3639 " it can not be used by ipa-prop\n");
3642 if (!opt_for_fn (n->decl, flag_devirtualize_speculatively))
3643 continue;
3645 if (!e->maybe_hot_p ())
3647 if (dump_file)
3648 fprintf (dump_file, "Call is cold\n\n");
3649 ncold++;
3650 continue;
3652 if (e->speculative)
3654 if (dump_file)
3655 fprintf (dump_file, "Call is already speculated\n\n");
3656 nspeculated++;
3658 /* When dumping see if we agree with speculation. */
3659 if (!dump_file)
3660 continue;
3662 if (bad_call_targets.contains (cache_token))
3664 if (dump_file)
3665 fprintf (dump_file, "Target list is known to be useless\n\n");
3666 nmultiple++;
3667 continue;
3669 for (i = 0; i < targets.length (); i++)
3670 if (likely_target_p (targets[i]))
3672 if (likely_target)
3674 likely_target = NULL;
3675 if (dump_file)
3676 fprintf (dump_file, "More than one likely target\n\n");
3677 nmultiple++;
3678 break;
3680 likely_target = targets[i];
3682 if (!likely_target)
3684 bad_call_targets.add (cache_token);
3685 continue;
3687 /* This is reached only when dumping; check if we agree or disagree
3688 with the speculation. */
3689 if (e->speculative)
3691 struct cgraph_edge *e2;
3692 struct ipa_ref *ref;
3693 e->speculative_call_info (e2, e, ref);
3694 if (e2->callee->ultimate_alias_target ()
3695 == likely_target->ultimate_alias_target ())
3697 fprintf (dump_file, "We agree with speculation\n\n");
3698 nok++;
3700 else
3702 fprintf (dump_file, "We disagree with speculation\n\n");
3703 nwrong++;
3705 continue;
3707 if (!likely_target->definition)
3709 if (dump_file)
3710 fprintf (dump_file, "Target is not a definition\n\n");
3711 nnotdefined++;
3712 continue;
3714 /* Do not introduce new references to external symbols. While we
3715 can handle these just well, it is common for programs to
3716 incorrectly with headers defining methods they are linked
3717 with. */
3718 if (DECL_EXTERNAL (likely_target->decl))
3720 if (dump_file)
3721 fprintf (dump_file, "Target is external\n\n");
3722 nexternal++;
3723 continue;
3725 /* Don't use an implicitly-declared destructor (c++/58678). */
3726 struct cgraph_node *non_thunk_target
3727 = likely_target->function_symbol ();
3728 if (DECL_ARTIFICIAL (non_thunk_target->decl))
3730 if (dump_file)
3731 fprintf (dump_file, "Target is artificial\n\n");
3732 nartificial++;
3733 continue;
3735 if (likely_target->get_availability () <= AVAIL_INTERPOSABLE
3736 && likely_target->can_be_discarded_p ())
3738 if (dump_file)
3739 fprintf (dump_file, "Target is overwritable\n\n");
3740 noverwritable++;
3741 continue;
3743 else if (dbg_cnt (devirt))
3745 if (dump_enabled_p ())
3747 location_t locus = gimple_location_safe (e->call_stmt);
3748 dump_printf_loc (MSG_OPTIMIZED_LOCATIONS, locus,
3749 "speculatively devirtualizing call in %s/%i to %s/%i\n",
3750 n->name (), n->order,
3751 likely_target->name (),
3752 likely_target->order);
3754 if (!likely_target->can_be_discarded_p ())
3756 cgraph_node *alias;
3757 alias = dyn_cast<cgraph_node *> (likely_target->noninterposable_alias ());
3758 if (alias)
3759 likely_target = alias;
3761 nconverted++;
3762 update = true;
3763 e->make_speculative
3764 (likely_target, e->count * 8 / 10, e->frequency * 8 / 10);
3767 if (update)
3768 inline_update_overall_summary (n);
3770 if (warn_suggest_final_methods || warn_suggest_final_types)
3772 if (warn_suggest_final_types)
3774 final_warning_records->type_warnings.qsort (type_warning_cmp);
3775 for (unsigned int i = 0;
3776 i < final_warning_records->type_warnings.length (); i++)
3777 if (final_warning_records->type_warnings[i].count)
3779 tree type = final_warning_records->type_warnings[i].type;
3780 int count = final_warning_records->type_warnings[i].count;
3781 long long dyn_count
3782 = final_warning_records->type_warnings[i].dyn_count;
3784 if (!dyn_count)
3785 warning_n (DECL_SOURCE_LOCATION (TYPE_NAME (type)),
3786 OPT_Wsuggest_final_types, count,
3787 "Declaring type %qD final "
3788 "would enable devirtualization of %i call",
3789 "Declaring type %qD final "
3790 "would enable devirtualization of %i calls",
3791 type,
3792 count);
3793 else
3794 warning_n (DECL_SOURCE_LOCATION (TYPE_NAME (type)),
3795 OPT_Wsuggest_final_types, count,
3796 "Declaring type %qD final "
3797 "would enable devirtualization of %i call "
3798 "executed %lli times",
3799 "Declaring type %qD final "
3800 "would enable devirtualization of %i calls "
3801 "executed %lli times",
3802 type,
3803 count,
3804 dyn_count);
3808 if (warn_suggest_final_methods)
3810 vec<const decl_warn_count*> decl_warnings_vec = vNULL;
3812 final_warning_records->decl_warnings.traverse
3813 <vec<const decl_warn_count *> *, add_decl_warning> (&decl_warnings_vec);
3814 decl_warnings_vec.qsort (decl_warning_cmp);
3815 for (unsigned int i = 0; i < decl_warnings_vec.length (); i++)
3817 tree decl = decl_warnings_vec[i]->decl;
3818 int count = decl_warnings_vec[i]->count;
3819 long long dyn_count = decl_warnings_vec[i]->dyn_count;
3821 if (!dyn_count)
3822 if (DECL_CXX_DESTRUCTOR_P (decl))
3823 warning_n (DECL_SOURCE_LOCATION (decl),
3824 OPT_Wsuggest_final_methods, count,
3825 "Declaring virtual destructor of %qD final "
3826 "would enable devirtualization of %i call",
3827 "Declaring virtual destructor of %qD final "
3828 "would enable devirtualization of %i calls",
3829 DECL_CONTEXT (decl), count);
3830 else
3831 warning_n (DECL_SOURCE_LOCATION (decl),
3832 OPT_Wsuggest_final_methods, count,
3833 "Declaring method %qD final "
3834 "would enable devirtualization of %i call",
3835 "Declaring method %qD final "
3836 "would enable devirtualization of %i calls",
3837 decl, count);
3838 else if (DECL_CXX_DESTRUCTOR_P (decl))
3839 warning_n (DECL_SOURCE_LOCATION (decl),
3840 OPT_Wsuggest_final_methods, count,
3841 "Declaring virtual destructor of %qD final "
3842 "would enable devirtualization of %i call "
3843 "executed %lli times",
3844 "Declaring virtual destructor of %qD final "
3845 "would enable devirtualization of %i calls "
3846 "executed %lli times",
3847 DECL_CONTEXT (decl), count, dyn_count);
3848 else
3849 warning_n (DECL_SOURCE_LOCATION (decl),
3850 OPT_Wsuggest_final_methods, count,
3851 "Declaring method %qD final "
3852 "would enable devirtualization of %i call "
3853 "executed %lli times",
3854 "Declaring method %qD final "
3855 "would enable devirtualization of %i calls "
3856 "executed %lli times",
3857 decl, count, dyn_count);
3861 delete (final_warning_records);
3862 final_warning_records = 0;
3865 if (dump_file)
3866 fprintf (dump_file,
3867 "%i polymorphic calls, %i devirtualized,"
3868 " %i speculatively devirtualized, %i cold\n"
3869 "%i have multiple targets, %i overwritable,"
3870 " %i already speculated (%i agree, %i disagree),"
3871 " %i external, %i not defined, %i artificial, %i infos dropped\n",
3872 npolymorphic, ndevirtualized, nconverted, ncold,
3873 nmultiple, noverwritable, nspeculated, nok, nwrong,
3874 nexternal, nnotdefined, nartificial, ndropped);
3875 return ndevirtualized || ndropped ? TODO_remove_functions : 0;
3878 namespace {
3880 const pass_data pass_data_ipa_devirt =
3882 IPA_PASS, /* type */
3883 "devirt", /* name */
3884 OPTGROUP_NONE, /* optinfo_flags */
3885 TV_IPA_DEVIRT, /* tv_id */
3886 0, /* properties_required */
3887 0, /* properties_provided */
3888 0, /* properties_destroyed */
3889 0, /* todo_flags_start */
3890 ( TODO_dump_symtab ), /* todo_flags_finish */
3893 class pass_ipa_devirt : public ipa_opt_pass_d
3895 public:
3896 pass_ipa_devirt (gcc::context *ctxt)
3897 : ipa_opt_pass_d (pass_data_ipa_devirt, ctxt,
3898 NULL, /* generate_summary */
3899 NULL, /* write_summary */
3900 NULL, /* read_summary */
3901 NULL, /* write_optimization_summary */
3902 NULL, /* read_optimization_summary */
3903 NULL, /* stmt_fixup */
3904 0, /* function_transform_todo_flags_start */
3905 NULL, /* function_transform */
3906 NULL) /* variable_transform */
3909 /* opt_pass methods: */
3910 virtual bool gate (function *)
3912 /* In LTO, always run the IPA passes and decide on function basis if the
3913 pass is enabled. */
3914 if (in_lto_p)
3915 return true;
3916 return (flag_devirtualize
3917 && (flag_devirtualize_speculatively
3918 || (warn_suggest_final_methods
3919 || warn_suggest_final_types))
3920 && optimize);
3923 virtual unsigned int execute (function *) { return ipa_devirt (); }
3925 }; // class pass_ipa_devirt
3927 } // anon namespace
3929 ipa_opt_pass_d *
3930 make_pass_ipa_devirt (gcc::context *ctxt)
3932 return new pass_ipa_devirt (ctxt);
3935 #include "gt-ipa-devirt.h"