1 /* Basic IPA utilities for type inheritance graph construction and
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
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
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/>. */
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.
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.
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
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
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.
84 build_type_inheritance_graph triggers a construction of the type inheritance
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.
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.
110 #include "coretypes.h"
112 #include "hash-set.h"
113 #include "machmode.h"
114 #include "hash-map.h"
116 #include "double-int.h"
120 #include "wide-int.h"
123 #include "fold-const.h"
124 #include "print-tree.h"
127 #include "basic-block.h"
129 #include "plugin-api.h"
130 #include "hard-reg-set.h"
131 #include "function.h"
137 #include "statistics.h"
139 #include "fixed-value.h"
140 #include "insn-config.h"
144 #include "emit-rtl.h"
148 #include "tree-pass.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"
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"
166 #include "gimple-pretty-print.h"
167 #include "stor-layout.h"
170 /* Hash based set of pairs of types. */
177 struct pair_traits : default_hashset_traits
182 return TYPE_UID (p.first) ^ TYPE_UID (p.second);
185 is_empty (type_pair p)
187 return p.first == NULL;
190 is_deleted (type_pair p ATTRIBUTE_UNUSED)
195 equal (const type_pair &a, const type_pair &b)
197 return a.first==b.first && a.second == b.second;
200 mark_empty (type_pair &e)
206 static bool odr_types_equivalent_p (tree, tree, bool, bool *,
207 hash_set<type_pair,pair_traits> *);
209 static bool odr_violation_reported = false;
212 /* Pointer set of all call targets appearing in the cache. */
213 static hash_set<cgraph_node *> *cached_polymorphic_call_targets;
215 /* The node of type inheritance graph. For each type unique in
216 One Definition Rule (ODR) sense, we produce one node linking all
217 main variants of types equivalent to it, bases and derived types. */
219 struct GTY(()) odr_type_d
223 /* All bases; built only for main variants of types. */
224 vec<odr_type> GTY((skip)) bases;
225 /* All derived types with virtual methods seen in unit;
226 built only for main variants of types. */
227 vec<odr_type> GTY((skip)) derived_types;
229 /* All equivalent types, if more than one. */
230 vec<tree, va_gc> *types;
231 /* Set of all equivalent types, if NON-NULL. */
232 hash_set<tree> * GTY((skip)) types_set;
234 /* Unique ID indexing the type in odr_types array. */
236 /* Is it in anonymous namespace? */
237 bool anonymous_namespace;
238 /* Do we know about all derivations of given type? */
239 bool all_derivations_known;
240 /* Did we report ODR violation here? */
244 /* Return TRUE if all derived types of T are known and thus
245 we may consider the walk of derived type complete.
247 This is typically true only for final anonymous namespace types and types
248 defined within functions (that may be COMDAT and thus shared across units,
249 but with the same set of derived types). */
252 type_all_derivations_known_p (const_tree t)
254 if (TYPE_FINAL_P (t))
258 /* Non-C++ types may have IDENTIFIER_NODE here, do not crash. */
259 if (!TYPE_NAME (t) || TREE_CODE (TYPE_NAME (t)) != TYPE_DECL)
261 if (type_in_anonymous_namespace_p (t))
263 return (decl_function_context (TYPE_NAME (t)) != NULL);
266 /* Return TRUE if type's constructors are all visible. */
269 type_all_ctors_visible_p (tree t)
272 && symtab->state >= CONSTRUCTION
273 /* We can not always use type_all_derivations_known_p.
274 For function local types we must assume case where
275 the function is COMDAT and shared in between units.
277 TODO: These cases are quite easy to get, but we need
278 to keep track of C++ privatizing via -Wno-weak
279 as well as the IPA privatizing. */
280 && type_in_anonymous_namespace_p (t);
283 /* Return TRUE if type may have instance. */
286 type_possibly_instantiated_p (tree t)
291 /* TODO: Add abstract types here. */
292 if (!type_all_ctors_visible_p (t))
295 vtable = BINFO_VTABLE (TYPE_BINFO (t));
296 if (TREE_CODE (vtable) == POINTER_PLUS_EXPR)
297 vtable = TREE_OPERAND (TREE_OPERAND (vtable, 0), 0);
298 vnode = varpool_node::get (vtable);
299 return vnode && vnode->definition;
302 /* Hash used to unify ODR types based on their mangled name and for anonymous
305 struct odr_name_hasher
307 typedef odr_type_d value_type;
308 typedef union tree_node compare_type;
309 static inline hashval_t hash (const value_type *);
310 static inline bool equal (const value_type *, const compare_type *);
311 static inline void remove (value_type *);
314 /* Has used to unify ODR types based on their associated virtual table.
315 This hash is needed to keep -fno-lto-odr-type-merging to work and contains
316 only polymorphic types. Types with mangled names are inserted to both. */
318 struct odr_vtable_hasher:odr_name_hasher
320 static inline hashval_t hash (const value_type *);
321 static inline bool equal (const value_type *, const compare_type *);
324 /* Return type that was declared with T's name so that T is an
325 qualified variant of it. */
328 main_odr_variant (const_tree t)
330 if (TYPE_NAME (t) && TREE_CODE (TYPE_NAME (t)) == TYPE_DECL)
331 return TREE_TYPE (TYPE_NAME (t));
332 /* Unnamed types and non-C++ produced types can be compared by variants. */
334 return TYPE_MAIN_VARIANT (t);
338 can_be_name_hashed_p (tree t)
340 return (!in_lto_p || type_in_anonymous_namespace_p (t)
341 || (TYPE_NAME (t) && DECL_ASSEMBLER_NAME_SET_P (TYPE_NAME (t))));
344 /* Hash type by its ODR name. */
347 hash_odr_name (const_tree t)
349 gcc_checking_assert (main_odr_variant (t) == t);
351 /* If not in LTO, all main variants are unique, so we can do
354 return htab_hash_pointer (t);
356 /* Anonymous types are unique. */
357 if (type_in_anonymous_namespace_p (t))
358 return htab_hash_pointer (t);
360 gcc_checking_assert (TYPE_NAME (t)
361 && DECL_ASSEMBLER_NAME_SET_P (TYPE_NAME (t)));
362 return IDENTIFIER_HASH_VALUE (DECL_ASSEMBLER_NAME (TYPE_NAME (t)));
365 /* Return the computed hashcode for ODR_TYPE. */
368 odr_name_hasher::hash (const value_type *odr_type)
370 return hash_odr_name (odr_type->type);
374 can_be_vtable_hashed_p (tree t)
376 /* vtable hashing can distinguish only main variants. */
377 if (TYPE_MAIN_VARIANT (t) != t)
379 /* Anonymous namespace types are always handled by name hash. */
380 if (type_in_anonymous_namespace_p (t))
382 return (TREE_CODE (t) == RECORD_TYPE
383 && TYPE_BINFO (t) && BINFO_VTABLE (TYPE_BINFO (t)));
386 /* Hash type by assembler name of its vtable. */
389 hash_odr_vtable (const_tree t)
391 tree v = BINFO_VTABLE (TYPE_BINFO (TYPE_MAIN_VARIANT (t)));
392 inchash::hash hstate;
394 gcc_checking_assert (in_lto_p);
395 gcc_checking_assert (!type_in_anonymous_namespace_p (t));
396 gcc_checking_assert (TREE_CODE (t) == RECORD_TYPE
397 && TYPE_BINFO (t) && BINFO_VTABLE (TYPE_BINFO (t)));
398 gcc_checking_assert (main_odr_variant (t) == t);
400 if (TREE_CODE (v) == POINTER_PLUS_EXPR)
402 add_expr (TREE_OPERAND (v, 1), hstate);
403 v = TREE_OPERAND (TREE_OPERAND (v, 0), 0);
406 hstate.add_wide_int (IDENTIFIER_HASH_VALUE (DECL_ASSEMBLER_NAME (v)));
407 return hstate.end ();
410 /* Return the computed hashcode for ODR_TYPE. */
413 odr_vtable_hasher::hash (const value_type *odr_type)
415 return hash_odr_vtable (odr_type->type);
418 /* For languages with One Definition Rule, work out if
419 types are the same based on their name.
421 This is non-trivial for LTO where minor differences in
422 the type representation may have prevented type merging
423 to merge two copies of otherwise equivalent type.
425 Until we start streaming mangled type names, this function works
426 only for polymorphic types.
428 When STRICT is true, we compare types by their names for purposes of
429 ODR violation warnings. When strict is false, we consider variants
430 equivalent, becuase it is all that matters for devirtualization machinery.
434 types_same_for_odr (const_tree type1, const_tree type2, bool strict)
436 gcc_checking_assert (TYPE_P (type1) && TYPE_P (type2));
438 type1 = main_odr_variant (type1);
439 type2 = main_odr_variant (type2);
442 type1 = TYPE_MAIN_VARIANT (type1);
443 type2 = TYPE_MAIN_VARIANT (type2);
452 /* Check for anonymous namespaces. Those have !TREE_PUBLIC
453 on the corresponding TYPE_STUB_DECL. */
454 if (type_in_anonymous_namespace_p (type1)
455 || type_in_anonymous_namespace_p (type2))
459 /* ODR name of the type is set in DECL_ASSEMBLER_NAME of its TYPE_NAME.
461 Ideally we should never need types without ODR names here. It can however
464 1) for builtin types that are not streamed but rebuilt in lto/lto-lang.c
465 Here testing for equivalence is safe, since their MAIN_VARIANTs are
467 2) for units streamed with -fno-lto-odr-type-merging. Here we can't
468 establish precise ODR equivalency, but for correctness we care only
469 about equivalency on complete polymorphic types. For these we can
470 compare assembler names of their virtual tables. */
471 if ((!TYPE_NAME (type1) || !DECL_ASSEMBLER_NAME_SET_P (TYPE_NAME (type1)))
472 || (!TYPE_NAME (type2) || !DECL_ASSEMBLER_NAME_SET_P (TYPE_NAME (type2))))
474 /* See if types are obviously different (i.e. different codes
475 or polymorphic wrt non-polymorphic). This is not strictly correct
476 for ODR violating programs, but we can't do better without streaming
478 if (TREE_CODE (type1) != TREE_CODE (type2))
480 if (TREE_CODE (type1) == RECORD_TYPE
481 && (TYPE_BINFO (type1) == NULL_TREE)
482 != (TYPE_BINFO (type1) == NULL_TREE))
484 if (TREE_CODE (type1) == RECORD_TYPE && TYPE_BINFO (type1)
485 && (BINFO_VTABLE (TYPE_BINFO (type1)) == NULL_TREE)
486 != (BINFO_VTABLE (TYPE_BINFO (type2)) == NULL_TREE))
489 /* At the moment we have no way to establish ODR equivalence at LTO
490 other than comparing virtual table pointers of polymorphic types.
491 Eventually we should start saving mangled names in TYPE_NAME.
492 Then this condition will become non-trivial. */
494 if (TREE_CODE (type1) == RECORD_TYPE
495 && TYPE_BINFO (type1) && TYPE_BINFO (type2)
496 && BINFO_VTABLE (TYPE_BINFO (type1))
497 && BINFO_VTABLE (TYPE_BINFO (type2)))
499 tree v1 = BINFO_VTABLE (TYPE_BINFO (type1));
500 tree v2 = BINFO_VTABLE (TYPE_BINFO (type2));
501 gcc_assert (TREE_CODE (v1) == POINTER_PLUS_EXPR
502 && TREE_CODE (v2) == POINTER_PLUS_EXPR);
503 return (operand_equal_p (TREE_OPERAND (v1, 1),
504 TREE_OPERAND (v2, 1), 0)
505 && DECL_ASSEMBLER_NAME
506 (TREE_OPERAND (TREE_OPERAND (v1, 0), 0))
507 == DECL_ASSEMBLER_NAME
508 (TREE_OPERAND (TREE_OPERAND (v2, 0), 0)));
512 return (DECL_ASSEMBLER_NAME (TYPE_NAME (type1))
513 == DECL_ASSEMBLER_NAME (TYPE_NAME (type2)));
516 /* Return true if we can decide on ODR equivalency.
518 In non-LTO it is always decide, in LTO however it depends in the type has
521 When STRICT is false, compare main variants. */
524 types_odr_comparable (tree t1, tree t2, bool strict)
527 || (strict ? main_odr_variant (t1) == main_odr_variant (t2)
528 : TYPE_MAIN_VARIANT (t1) == TYPE_MAIN_VARIANT (t2))
529 || (odr_type_p (t1) && odr_type_p (t2))
530 || (TREE_CODE (t1) == RECORD_TYPE && TREE_CODE (t2) == RECORD_TYPE
531 && TYPE_BINFO (t1) && TYPE_BINFO (t2)
532 && polymorphic_type_binfo_p (TYPE_BINFO (t1))
533 && polymorphic_type_binfo_p (TYPE_BINFO (t2))));
536 /* Return true if T1 and T2 are ODR equivalent. If ODR equivalency is not
537 known, be conservative and return false. */
540 types_must_be_same_for_odr (tree t1, tree t2)
542 if (types_odr_comparable (t1, t2))
543 return types_same_for_odr (t1, t2);
545 return TYPE_MAIN_VARIANT (t1) == TYPE_MAIN_VARIANT (t2);
548 /* Compare types T1 and T2 and return true if they are
552 odr_name_hasher::equal (const value_type *o1, const compare_type *t2)
556 gcc_checking_assert (main_odr_variant (t2) == t2);
557 gcc_checking_assert (main_odr_variant (t1) == t1);
562 /* Check for anonymous namespaces. Those have !TREE_PUBLIC
563 on the corresponding TYPE_STUB_DECL. */
564 if (type_in_anonymous_namespace_p (t1)
565 || type_in_anonymous_namespace_p (t2))
567 gcc_checking_assert (DECL_ASSEMBLER_NAME (TYPE_NAME (t1)));
568 gcc_checking_assert (DECL_ASSEMBLER_NAME (TYPE_NAME (t2)));
569 return (DECL_ASSEMBLER_NAME (TYPE_NAME (t1))
570 == DECL_ASSEMBLER_NAME (TYPE_NAME (t2)));
573 /* Compare types T1 and T2 and return true if they are
577 odr_vtable_hasher::equal (const value_type *o1, const compare_type *t2)
581 gcc_checking_assert (main_odr_variant (t2) == t2);
582 gcc_checking_assert (main_odr_variant (t1) == t1);
583 gcc_checking_assert (in_lto_p);
584 t1 = TYPE_MAIN_VARIANT (t1);
585 t2 = TYPE_MAIN_VARIANT (t2);
588 tree v1 = BINFO_VTABLE (TYPE_BINFO (t1));
589 tree v2 = BINFO_VTABLE (TYPE_BINFO (t2));
590 return (operand_equal_p (TREE_OPERAND (v1, 1),
591 TREE_OPERAND (v2, 1), 0)
592 && DECL_ASSEMBLER_NAME
593 (TREE_OPERAND (TREE_OPERAND (v1, 0), 0))
594 == DECL_ASSEMBLER_NAME
595 (TREE_OPERAND (TREE_OPERAND (v2, 0), 0)));
598 /* Free ODR type V. */
601 odr_name_hasher::remove (value_type *v)
604 v->derived_types.release ();
610 /* ODR type hash used to look up ODR type based on tree type node. */
612 typedef hash_table<odr_name_hasher> odr_hash_type;
613 static odr_hash_type *odr_hash;
614 typedef hash_table<odr_vtable_hasher> odr_vtable_hash_type;
615 static odr_vtable_hash_type *odr_vtable_hash;
617 /* ODR types are also stored into ODR_TYPE vector to allow consistent
618 walking. Bases appear before derived types. Vector is garbage collected
619 so we won't end up visiting empty types. */
621 static GTY(()) vec <odr_type, va_gc> *odr_types_ptr;
622 #define odr_types (*odr_types_ptr)
624 /* Set TYPE_BINFO of TYPE and its variants to BINFO. */
626 set_type_binfo (tree type, tree binfo)
628 for (; type; type = TYPE_NEXT_VARIANT (type))
629 if (COMPLETE_TYPE_P (type))
630 TYPE_BINFO (type) = binfo;
632 gcc_assert (!TYPE_BINFO (type));
635 /* Compare T2 and T2 based on name or structure. */
638 odr_subtypes_equivalent_p (tree t1, tree t2,
639 hash_set<type_pair,pair_traits> *visited)
643 /* This can happen in incomplete types that should be handled earlier. */
644 gcc_assert (t1 && t2);
646 t1 = main_odr_variant (t1);
647 t2 = main_odr_variant (t2);
651 /* Anonymous namespace types must match exactly. */
652 an1 = type_in_anonymous_namespace_p (t1);
653 an2 = type_in_anonymous_namespace_p (t2);
654 if (an1 != an2 || an1)
657 /* For ODR types be sure to compare their names.
658 To support -wno-odr-type-merging we allow one type to be non-ODR
659 and other ODR even though it is a violation. */
660 if (types_odr_comparable (t1, t2, true))
662 if (!types_same_for_odr (t1, t2, true))
664 /* Limit recursion: If subtypes are ODR types and we know
665 that they are same, be happy. */
666 if (!get_odr_type (t1, true)->odr_violated)
670 /* Component types, builtins and possibly violating ODR types
671 have to be compared structurally. */
672 if (TREE_CODE (t1) != TREE_CODE (t2))
674 if ((TYPE_NAME (t1) == NULL_TREE) != (TYPE_NAME (t2) == NULL_TREE))
676 if (TYPE_NAME (t1) && DECL_NAME (TYPE_NAME (t1)) != DECL_NAME (TYPE_NAME (t2)))
679 type_pair pair={t1,t2};
680 if (TYPE_UID (t1) > TYPE_UID (t2))
685 if (visited->add (pair))
687 return odr_types_equivalent_p (t1, t2, false, NULL, visited);
690 /* Compare two virtual tables, PREVAILING and VTABLE and output ODR
691 violation warnings. */
694 compare_virtual_tables (varpool_node *prevailing, varpool_node *vtable)
697 if (DECL_VIRTUAL_P (prevailing->decl) != DECL_VIRTUAL_P (vtable->decl))
699 odr_violation_reported = true;
700 if (DECL_VIRTUAL_P (prevailing->decl))
702 varpool_node *tmp = prevailing;
706 if (warning_at (DECL_SOURCE_LOCATION
707 (TYPE_NAME (DECL_CONTEXT (vtable->decl))),
709 "virtual table of type %qD violates one definition rule",
710 DECL_CONTEXT (vtable->decl)))
711 inform (DECL_SOURCE_LOCATION (prevailing->decl),
712 "variable of same assembler name as the virtual table is "
713 "defined in another translation unit");
716 if (!prevailing->definition || !vtable->definition)
718 for (n1 = 0, n2 = 0; true; n1++, n2++)
720 struct ipa_ref *ref1, *ref2;
723 end1 = !prevailing->iterate_reference (n1, ref1);
724 end2 = !vtable->iterate_reference (n2, ref2);
726 /* !DECL_VIRTUAL_P means RTTI entry;
727 We warn when RTTI is lost because non-RTTI previals; we silently
728 accept the other case. */
731 || (DECL_ASSEMBLER_NAME (ref1->referred->decl)
732 != DECL_ASSEMBLER_NAME (ref2->referred->decl)
733 && DECL_VIRTUAL_P (ref1->referred->decl)))
734 && !DECL_VIRTUAL_P (ref2->referred->decl))
736 if (warning_at (DECL_SOURCE_LOCATION
737 (TYPE_NAME (DECL_CONTEXT (vtable->decl))), 0,
738 "virtual table of type %qD contains RTTI information",
739 DECL_CONTEXT (vtable->decl)))
741 inform (DECL_SOURCE_LOCATION
742 (TYPE_NAME (DECL_CONTEXT (prevailing->decl))),
743 "but is prevailed by one without from other translation "
745 inform (DECL_SOURCE_LOCATION
746 (TYPE_NAME (DECL_CONTEXT (prevailing->decl))),
747 "RTTI will not work on this type");
750 end2 = !vtable->iterate_reference (n2, ref2);
754 || (DECL_ASSEMBLER_NAME (ref2->referred->decl)
755 != DECL_ASSEMBLER_NAME (ref1->referred->decl)
756 && DECL_VIRTUAL_P (ref2->referred->decl)))
757 && !DECL_VIRTUAL_P (ref1->referred->decl))
760 end1 = !vtable->iterate_reference (n1, ref1);
766 /* Extra paranoia; compare the sizes. We do not have information
767 about virtual inheritance offsets, so just be sure that these
769 Do this as very last check so the not very informative error
770 is not output too often. */
771 if (DECL_SIZE (prevailing->decl) != DECL_SIZE (vtable->decl))
773 if (warning_at (DECL_SOURCE_LOCATION
774 (TYPE_NAME (DECL_CONTEXT (vtable->decl))), 0,
775 "virtual table of type %qD violates "
776 "one definition rule ",
777 DECL_CONTEXT (vtable->decl)))
779 inform (DECL_SOURCE_LOCATION
780 (TYPE_NAME (DECL_CONTEXT (prevailing->decl))),
781 "the conflicting type defined in another translation "
782 "unit has virtual table of different size");
790 if (DECL_ASSEMBLER_NAME (ref1->referred->decl)
791 == DECL_ASSEMBLER_NAME (ref2->referred->decl))
794 /* If the loops above stopped on non-virtual pointer, we have
795 mismatch in RTTI information mangling. */
796 if (!DECL_VIRTUAL_P (ref1->referred->decl)
797 && !DECL_VIRTUAL_P (ref2->referred->decl))
799 if (warning_at (DECL_SOURCE_LOCATION
800 (TYPE_NAME (DECL_CONTEXT (vtable->decl))), 0,
801 "virtual table of type %qD violates "
802 "one definition rule ",
803 DECL_CONTEXT (vtable->decl)))
805 inform (DECL_SOURCE_LOCATION
806 (TYPE_NAME (DECL_CONTEXT (prevailing->decl))),
807 "the conflicting type defined in another translation "
808 "unit with different RTTI information");
812 /* At this point both REF1 and REF2 points either to virtual table
813 or virtual method. If one points to virtual table and other to
814 method we can complain the same way as if one table was shorter
815 than other pointing out the extra method. */
816 gcc_assert (DECL_VIRTUAL_P (ref1->referred->decl)
817 && (TREE_CODE (ref1->referred->decl) == FUNCTION_DECL
818 || TREE_CODE (ref1->referred->decl) == VAR_DECL));
819 gcc_assert (DECL_VIRTUAL_P (ref2->referred->decl)
820 && (TREE_CODE (ref2->referred->decl) == FUNCTION_DECL
821 || TREE_CODE (ref2->referred->decl) == VAR_DECL));
822 if (TREE_CODE (ref1->referred->decl)
823 != TREE_CODE (ref2->referred->decl))
825 if (TREE_CODE (ref1->referred->decl) == VAR_DECL)
827 else if (TREE_CODE (ref2->referred->decl) == VAR_DECL)
832 /* Complain about size mismatch. Either we have too many virutal
833 functions or too many virtual table pointers. */
838 varpool_node *tmp = prevailing;
843 if (warning_at (DECL_SOURCE_LOCATION
844 (TYPE_NAME (DECL_CONTEXT (vtable->decl))), 0,
845 "virtual table of type %qD violates "
846 "one definition rule",
847 DECL_CONTEXT (vtable->decl)))
849 if (TREE_CODE (ref1->referring->decl) == FUNCTION_DECL)
851 inform (DECL_SOURCE_LOCATION
852 (TYPE_NAME (DECL_CONTEXT (prevailing->decl))),
853 "the conflicting type defined in another translation "
855 inform (DECL_SOURCE_LOCATION
856 (TYPE_NAME (DECL_CONTEXT (ref1->referring->decl))),
857 "contains additional virtual method %qD",
858 ref1->referred->decl);
862 inform (DECL_SOURCE_LOCATION
863 (TYPE_NAME (DECL_CONTEXT (prevailing->decl))),
864 "the conflicting type defined in another translation "
865 "unit has virtual table table with more entries");
871 /* And in the last case we have either mistmatch in between two virtual
872 methods or two virtual table pointers. */
873 if (warning_at (DECL_SOURCE_LOCATION
874 (TYPE_NAME (DECL_CONTEXT (vtable->decl))), 0,
875 "virtual table of type %qD violates "
876 "one definition rule ",
877 DECL_CONTEXT (vtable->decl)))
879 if (TREE_CODE (ref1->referred->decl) == FUNCTION_DECL)
881 inform (DECL_SOURCE_LOCATION
882 (TYPE_NAME (DECL_CONTEXT (prevailing->decl))),
883 "the conflicting type defined in another translation "
885 gcc_assert (TREE_CODE (ref2->referred->decl)
887 inform (DECL_SOURCE_LOCATION (ref1->referred->decl),
888 "virtual method %qD", ref1->referred->decl);
889 inform (DECL_SOURCE_LOCATION (ref2->referred->decl),
890 "ought to match virtual method %qD but does not",
891 ref2->referred->decl);
894 inform (DECL_SOURCE_LOCATION
895 (TYPE_NAME (DECL_CONTEXT (prevailing->decl))),
896 "the conflicting type defined in another translation "
897 "unit has virtual table table with different contents");
903 /* Output ODR violation warning about T1 and T2 with REASON.
904 Display location of ST1 and ST2 if REASON speaks about field or
906 If WARN is false, do nothing. Set WARNED if warning was indeed
910 warn_odr (tree t1, tree t2, tree st1, tree st2,
911 bool warn, bool *warned, const char *reason)
913 tree decl2 = TYPE_NAME (t2);
919 if (!warning_at (DECL_SOURCE_LOCATION (TYPE_NAME (t1)), OPT_Wodr,
920 "type %qT violates one definition rule",
925 /* For FIELD_DECL support also case where one of fields is
926 NULL - this is used when the structures have mismatching number of
928 else if (!st1 || TREE_CODE (st1) == FIELD_DECL)
930 inform (DECL_SOURCE_LOCATION (decl2),
931 "a different type is defined in another translation unit");
937 inform (DECL_SOURCE_LOCATION (st1),
938 "the first difference of corresponding definitions is field %qD",
943 else if (TREE_CODE (st1) == FUNCTION_DECL)
945 inform (DECL_SOURCE_LOCATION (decl2),
946 "a different type is defined in another translation unit");
947 inform (DECL_SOURCE_LOCATION (st1),
948 "the first difference of corresponding definitions is method %qD",
954 inform (DECL_SOURCE_LOCATION (decl2), reason);
960 /* We already warned about ODR mismatch. T1 and T2 ought to be equivalent
961 because they are used on same place in ODR matching types.
962 They are not; inform the user. */
965 warn_types_mismatch (tree t1, tree t2)
967 if (!TYPE_NAME (t1) || !TYPE_NAME (t2))
969 /* In Firefox it is a common bug to have same types but in
970 different namespaces. Be a bit more informative on
972 if (TYPE_CONTEXT (t1) && TYPE_CONTEXT (t2)
973 && (((TREE_CODE (TYPE_CONTEXT (t1)) == NAMESPACE_DECL)
974 != (TREE_CODE (TYPE_CONTEXT (t2)) == NAMESPACE_DECL))
975 || (TREE_CODE (TYPE_CONTEXT (t1)) == NAMESPACE_DECL
976 && (DECL_NAME (TYPE_CONTEXT (t1)) !=
977 DECL_NAME (TYPE_CONTEXT (t2))))))
978 inform (DECL_SOURCE_LOCATION (TYPE_NAME (t1)),
979 "type %qT should match type %qT but is defined "
980 "in different namespace ",
983 inform (DECL_SOURCE_LOCATION (TYPE_NAME (t1)),
984 "type %qT should match type %qT",
986 inform (DECL_SOURCE_LOCATION (TYPE_NAME (t2)),
987 "the incompatible type is defined here");
990 /* Compare T1 and T2, report ODR violations if WARN is true and set
991 WARNED to true if anything is reported. Return true if types match.
992 If true is returned, the types are also compatible in the sense of
993 gimple_canonical_types_compatible_p. */
996 odr_types_equivalent_p (tree t1, tree t2, bool warn, bool *warned,
997 hash_set<type_pair,pair_traits> *visited)
999 /* Check first for the obvious case of pointer identity. */
1002 gcc_assert (!type_in_anonymous_namespace_p (t1));
1003 gcc_assert (!type_in_anonymous_namespace_p (t2));
1005 /* Can't be the same type if the types don't have the same code. */
1006 if (TREE_CODE (t1) != TREE_CODE (t2))
1008 warn_odr (t1, t2, NULL, NULL, warn, warned,
1009 G_("a different type is defined in another translation unit"));
1013 if (TYPE_QUALS (t1) != TYPE_QUALS (t2))
1015 warn_odr (t1, t2, NULL, NULL, warn, warned,
1016 G_("a type with different qualifiers is defined in another "
1017 "translation unit"));
1021 if (comp_type_attributes (t1, t2) != 1)
1023 warn_odr (t1, t2, NULL, NULL, warn, warned,
1024 G_("a type with attributes "
1025 "is defined in another translation unit"));
1029 if (TREE_CODE (t1) == ENUMERAL_TYPE
1030 && TYPE_VALUES (t1) && TYPE_VALUES (t2))
1033 for (v1 = TYPE_VALUES (t1), v2 = TYPE_VALUES (t2);
1034 v1 && v2 ; v1 = TREE_CHAIN (v1), v2 = TREE_CHAIN (v2))
1036 if (TREE_PURPOSE (v1) != TREE_PURPOSE (v2))
1038 warn_odr (t1, t2, NULL, NULL, warn, warned,
1039 G_("an enum with different value name"
1040 " is defined in another translation unit"));
1043 if (TREE_VALUE (v1) != TREE_VALUE (v2)
1044 && !operand_equal_p (DECL_INITIAL (TREE_VALUE (v1)),
1045 DECL_INITIAL (TREE_VALUE (v2)), 0))
1047 warn_odr (t1, t2, NULL, NULL, warn, warned,
1048 G_("an enum with different values is defined"
1049 " in another translation unit"));
1055 warn_odr (t1, t2, NULL, NULL, warn, warned,
1056 G_("an enum with mismatching number of values "
1057 "is defined in another translation unit"));
1062 /* Non-aggregate types can be handled cheaply. */
1063 if (INTEGRAL_TYPE_P (t1)
1064 || SCALAR_FLOAT_TYPE_P (t1)
1065 || FIXED_POINT_TYPE_P (t1)
1066 || TREE_CODE (t1) == VECTOR_TYPE
1067 || TREE_CODE (t1) == COMPLEX_TYPE
1068 || TREE_CODE (t1) == OFFSET_TYPE
1069 || POINTER_TYPE_P (t1))
1071 if (TYPE_PRECISION (t1) != TYPE_PRECISION (t2))
1073 warn_odr (t1, t2, NULL, NULL, warn, warned,
1074 G_("a type with different precision is defined "
1075 "in another translation unit"));
1078 if (TYPE_UNSIGNED (t1) != TYPE_UNSIGNED (t2))
1080 warn_odr (t1, t2, NULL, NULL, warn, warned,
1081 G_("a type with different signedness is defined "
1082 "in another translation unit"));
1086 if (TREE_CODE (t1) == INTEGER_TYPE
1087 && TYPE_STRING_FLAG (t1) != TYPE_STRING_FLAG (t2))
1089 /* char WRT uint_8? */
1090 warn_odr (t1, t2, NULL, NULL, warn, warned,
1091 G_("a different type is defined in another "
1092 "translation unit"));
1096 /* For canonical type comparisons we do not want to build SCCs
1097 so we cannot compare pointed-to types. But we can, for now,
1098 require the same pointed-to type kind and match what
1099 useless_type_conversion_p would do. */
1100 if (POINTER_TYPE_P (t1))
1102 if (TYPE_ADDR_SPACE (TREE_TYPE (t1))
1103 != TYPE_ADDR_SPACE (TREE_TYPE (t2)))
1105 warn_odr (t1, t2, NULL, NULL, warn, warned,
1106 G_("it is defined as a pointer in different address "
1107 "space in another translation unit"));
1111 if (!odr_subtypes_equivalent_p (TREE_TYPE (t1), TREE_TYPE (t2), visited))
1113 warn_odr (t1, t2, NULL, NULL, warn, warned,
1114 G_("it is defined as a pointer to different type "
1115 "in another translation unit"));
1117 warn_types_mismatch (TREE_TYPE (t1), TREE_TYPE (t2));
1122 if ((TREE_CODE (t1) == VECTOR_TYPE || TREE_CODE (t1) == COMPLEX_TYPE)
1123 && !odr_subtypes_equivalent_p (TREE_TYPE (t1), TREE_TYPE (t2), visited))
1125 /* Probably specific enough. */
1126 warn_odr (t1, t2, NULL, NULL, warn, warned,
1127 G_("a different type is defined "
1128 "in another translation unit"));
1130 warn_types_mismatch (TREE_TYPE (t1), TREE_TYPE (t2));
1134 /* Do type-specific comparisons. */
1135 else switch (TREE_CODE (t1))
1139 /* Array types are the same if the element types are the same and
1140 the number of elements are the same. */
1141 if (!odr_subtypes_equivalent_p (TREE_TYPE (t1), TREE_TYPE (t2), visited))
1143 warn_odr (t1, t2, NULL, NULL, warn, warned,
1144 G_("a different type is defined in another "
1145 "translation unit"));
1147 warn_types_mismatch (TREE_TYPE (t1), TREE_TYPE (t2));
1149 gcc_assert (TYPE_STRING_FLAG (t1) == TYPE_STRING_FLAG (t2));
1150 gcc_assert (TYPE_NONALIASED_COMPONENT (t1)
1151 == TYPE_NONALIASED_COMPONENT (t2));
1153 tree i1 = TYPE_DOMAIN (t1);
1154 tree i2 = TYPE_DOMAIN (t2);
1156 /* For an incomplete external array, the type domain can be
1157 NULL_TREE. Check this condition also. */
1158 if (i1 == NULL_TREE || i2 == NULL_TREE)
1161 tree min1 = TYPE_MIN_VALUE (i1);
1162 tree min2 = TYPE_MIN_VALUE (i2);
1163 tree max1 = TYPE_MAX_VALUE (i1);
1164 tree max2 = TYPE_MAX_VALUE (i2);
1166 /* In C++, minimums should be always 0. */
1167 gcc_assert (min1 == min2);
1168 if (!operand_equal_p (max1, max2, 0))
1170 warn_odr (t1, t2, NULL, NULL, warn, warned,
1171 G_("an array of different size is defined "
1172 "in another translation unit"));
1180 /* Function types are the same if the return type and arguments types
1182 if (!odr_subtypes_equivalent_p (TREE_TYPE (t1), TREE_TYPE (t2), visited))
1184 warn_odr (t1, t2, NULL, NULL, warn, warned,
1185 G_("has different return value "
1186 "in another translation unit"));
1188 warn_types_mismatch (TREE_TYPE (t1), TREE_TYPE (t2));
1192 if (TYPE_ARG_TYPES (t1) == TYPE_ARG_TYPES (t2))
1196 tree parms1, parms2;
1198 for (parms1 = TYPE_ARG_TYPES (t1), parms2 = TYPE_ARG_TYPES (t2);
1200 parms1 = TREE_CHAIN (parms1), parms2 = TREE_CHAIN (parms2))
1202 if (!odr_subtypes_equivalent_p
1203 (TREE_VALUE (parms1), TREE_VALUE (parms2), visited))
1205 warn_odr (t1, t2, NULL, NULL, warn, warned,
1206 G_("has different parameters in another "
1207 "translation unit"));
1209 warn_types_mismatch (TREE_VALUE (parms1),
1210 TREE_VALUE (parms2));
1215 if (parms1 || parms2)
1217 warn_odr (t1, t2, NULL, NULL, warn, warned,
1218 G_("has different parameters "
1219 "in another translation unit"));
1228 case QUAL_UNION_TYPE:
1232 /* For aggregate types, all the fields must be the same. */
1233 if (COMPLETE_TYPE_P (t1) && COMPLETE_TYPE_P (t2))
1235 for (f1 = TYPE_FIELDS (t1), f2 = TYPE_FIELDS (t2);
1237 f1 = TREE_CHAIN (f1), f2 = TREE_CHAIN (f2))
1239 /* Skip non-fields. */
1240 while (f1 && TREE_CODE (f1) != FIELD_DECL)
1241 f1 = TREE_CHAIN (f1);
1242 while (f2 && TREE_CODE (f2) != FIELD_DECL)
1243 f2 = TREE_CHAIN (f2);
1246 if (DECL_VIRTUAL_P (f1) != DECL_VIRTUAL_P (f2))
1248 warn_odr (t1, t2, NULL, NULL, warn, warned,
1249 G_("a type with different virtual table pointers"
1250 " is defined in another translation unit"));
1253 if (DECL_ARTIFICIAL (f1) != DECL_ARTIFICIAL (f2))
1255 warn_odr (t1, t2, NULL, NULL, warn, warned,
1256 G_("a type with different bases is defined "
1257 "in another translation unit"));
1260 if (DECL_NAME (f1) != DECL_NAME (f2)
1261 && !DECL_ARTIFICIAL (f1))
1263 warn_odr (t1, t2, f1, f2, warn, warned,
1264 G_("a field with different name is defined "
1265 "in another translation unit"));
1268 if (!odr_subtypes_equivalent_p (TREE_TYPE (f1),
1269 TREE_TYPE (f2), visited))
1271 /* Do not warn about artificial fields and just go into
1272 generic field mismatch warning. */
1273 if (DECL_ARTIFICIAL (f1))
1276 warn_odr (t1, t2, f1, f2, warn, warned,
1277 G_("a field of same name but different type "
1278 "is defined in another translation unit"));
1280 warn_types_mismatch (TREE_TYPE (f1), TREE_TYPE (f2));
1283 if (!gimple_compare_field_offset (f1, f2))
1285 /* Do not warn about artificial fields and just go into
1286 generic field mismatch warning. */
1287 if (DECL_ARTIFICIAL (f1))
1289 warn_odr (t1, t2, f1, f2, warn, warned,
1290 G_("fields has different layout "
1291 "in another translation unit"));
1294 gcc_assert (DECL_NONADDRESSABLE_P (f1)
1295 == DECL_NONADDRESSABLE_P (f2));
1298 /* If one aggregate has more fields than the other, they
1299 are not the same. */
1302 if ((f1 && DECL_VIRTUAL_P (f1)) || (f2 && DECL_VIRTUAL_P (f2)))
1303 warn_odr (t1, t2, NULL, NULL, warn, warned,
1304 G_("a type with different virtual table pointers"
1305 " is defined in another translation unit"));
1306 if ((f1 && DECL_ARTIFICIAL (f1))
1307 || (f2 && DECL_ARTIFICIAL (f2)))
1308 warn_odr (t1, t2, NULL, NULL, warn, warned,
1309 G_("a type with different bases is defined "
1310 "in another translation unit"));
1312 warn_odr (t1, t2, f1, f2, warn, warned,
1313 G_("a type with different number of fields "
1314 "is defined in another translation unit"));
1318 if ((TYPE_MAIN_VARIANT (t1) == t1 || TYPE_MAIN_VARIANT (t2) == t2)
1319 && (TYPE_METHODS (TYPE_MAIN_VARIANT (t1))
1320 != TYPE_METHODS (TYPE_MAIN_VARIANT (t2))))
1322 for (f1 = TYPE_METHODS (TYPE_MAIN_VARIANT (t1)),
1323 f2 = TYPE_METHODS (TYPE_MAIN_VARIANT (t2));
1324 f1 && f2 ; f1 = DECL_CHAIN (f1), f2 = DECL_CHAIN (f2))
1326 if (DECL_ASSEMBLER_NAME (f1) != DECL_ASSEMBLER_NAME (f2))
1328 warn_odr (t1, t2, f1, f2, warn, warned,
1329 G_("a different method of same type "
1330 "is defined in another translation unit"));
1333 if (DECL_VIRTUAL_P (f1) != DECL_VIRTUAL_P (f2))
1335 warn_odr (t1, t2, f1, f2, warn, warned,
1336 G_("s definition that differs by virtual "
1337 "keyword in another translation unit"));
1340 if (DECL_VINDEX (f1) != DECL_VINDEX (f2))
1342 warn_odr (t1, t2, f1, f2, warn, warned,
1343 G_("virtual table layout differs in another "
1344 "translation unit"));
1347 if (odr_subtypes_equivalent_p (TREE_TYPE (f1), TREE_TYPE (f2), visited))
1349 warn_odr (t1, t2, f1, f2, warn, warned,
1350 G_("method with incompatible type is defined "
1351 "in another translation unit"));
1357 warn_odr (t1, t2, NULL, NULL, warn, warned,
1358 G_("a type with different number of methods "
1359 "is defined in another translation unit"));
1374 /* Those are better to come last as they are utterly uninformative. */
1375 if (TYPE_SIZE (t1) && TYPE_SIZE (t2)
1376 && !operand_equal_p (TYPE_SIZE (t1), TYPE_SIZE (t2), 0))
1378 warn_odr (t1, t2, NULL, NULL, warn, warned,
1379 G_("a type with different size "
1380 "is defined in another translation unit"));
1383 if (COMPLETE_TYPE_P (t1) && COMPLETE_TYPE_P (t2)
1384 && TYPE_ALIGN (t1) != TYPE_ALIGN (t2))
1386 warn_odr (t1, t2, NULL, NULL, warn, warned,
1387 G_("a type with different alignment "
1388 "is defined in another translation unit"));
1391 gcc_assert (!TYPE_SIZE_UNIT (t1) || !TYPE_SIZE_UNIT (t2)
1392 || operand_equal_p (TYPE_SIZE_UNIT (t1),
1393 TYPE_SIZE_UNIT (t2), 0));
1397 /* TYPE is equivalent to VAL by ODR, but its tree representation differs
1398 from VAL->type. This may happen in LTO where tree merging did not merge
1399 all variants of the same type or due to ODR violation.
1401 Analyze and report ODR violations and add type to duplicate list.
1402 If TYPE is more specified than VAL->type, prevail VAL->type. Also if
1403 this is first time we see definition of a class return true so the
1404 base types are analyzed. */
1407 add_type_duplicate (odr_type val, tree type)
1409 bool build_bases = false;
1410 bool prevail = false;
1412 if (!val->types_set)
1413 val->types_set = new hash_set<tree>;
1415 /* Always prefer complete type to be the leader. */
1417 if (!COMPLETE_TYPE_P (val->type) && COMPLETE_TYPE_P (type))
1420 build_bases = TYPE_BINFO (type);
1422 else if (COMPLETE_TYPE_P (val->type) && !COMPLETE_TYPE_P (type))
1424 else if (TREE_CODE (val->type) == ENUMERAL_TYPE
1425 && TREE_CODE (type) == ENUMERAL_TYPE
1426 && !TYPE_VALUES (val->type) && TYPE_VALUES (type))
1428 else if (TREE_CODE (val->type) == RECORD_TYPE
1429 && TREE_CODE (type) == RECORD_TYPE
1430 && TYPE_BINFO (type) && !TYPE_BINFO (val->type))
1432 gcc_assert (!val->bases.length ());
1445 val->types_set->add (type);
1447 /* If we now have a mangled name, be sure to record it to val->type
1448 so ODR hash can work. */
1450 if (can_be_name_hashed_p (type) && !can_be_name_hashed_p (val->type))
1451 SET_DECL_ASSEMBLER_NAME (TYPE_NAME (val->type),
1452 DECL_ASSEMBLER_NAME (TYPE_NAME (type)));
1455 bool base_mismatch = false;
1457 bool warned = false;
1458 hash_set<type_pair,pair_traits> visited;
1460 gcc_assert (in_lto_p);
1461 vec_safe_push (val->types, type);
1463 /* First we compare memory layout. */
1464 if (!odr_types_equivalent_p (val->type, type,
1465 !flag_ltrans && !val->odr_violated,
1469 odr_violation_reported = true;
1470 val->odr_violated = true;
1471 if (symtab->dump_file)
1473 fprintf (symtab->dump_file, "ODR violation\n");
1475 print_node (symtab->dump_file, "", val->type, 0);
1476 putc ('\n',symtab->dump_file);
1477 print_node (symtab->dump_file, "", type, 0);
1478 putc ('\n',symtab->dump_file);
1482 /* Next sanity check that bases are the same. If not, we will end
1483 up producing wrong answers. */
1484 if (COMPLETE_TYPE_P (type) && COMPLETE_TYPE_P (val->type)
1485 && TREE_CODE (val->type) == RECORD_TYPE
1486 && TREE_CODE (type) == RECORD_TYPE
1487 && TYPE_BINFO (val->type) && TYPE_BINFO (type))
1489 if (BINFO_N_BASE_BINFOS (TYPE_BINFO (type))
1490 != BINFO_N_BASE_BINFOS (TYPE_BINFO (val->type)))
1492 if (!warned && !val->odr_violated)
1495 warn_odr (type, val->type, NULL, NULL, !warned, &warned,
1496 "a type with the same name but different "
1497 "number of polymorphic bases is "
1498 "defined in another translation unit");
1499 if (BINFO_N_BASE_BINFOS (TYPE_BINFO (type))
1500 > BINFO_N_BASE_BINFOS (TYPE_BINFO (val->type)))
1501 extra_base = BINFO_BASE_BINFO
1503 BINFO_N_BASE_BINFOS (TYPE_BINFO (val->type)));
1505 extra_base = BINFO_BASE_BINFO
1506 (TYPE_BINFO (val->type),
1507 BINFO_N_BASE_BINFOS (TYPE_BINFO (type)));
1508 tree extra_base_type = BINFO_TYPE (extra_base);
1509 inform (DECL_SOURCE_LOCATION (TYPE_NAME (extra_base_type)),
1510 "the extra base is defined here");
1512 base_mismatch = true;
1515 for (i = 0; i < BINFO_N_BASE_BINFOS (TYPE_BINFO (type)); i++)
1517 tree base1 = BINFO_BASE_BINFO (TYPE_BINFO (type), i);
1518 tree base2 = BINFO_BASE_BINFO (TYPE_BINFO (val->type), i);
1519 tree type1 = BINFO_TYPE (base1);
1520 tree type2 = BINFO_TYPE (base2);
1522 if (types_odr_comparable (type1, type2))
1524 if (!types_same_for_odr (type1, type2))
1525 base_mismatch = true;
1529 hash_set<type_pair,pair_traits> visited;
1530 if (!odr_types_equivalent_p (type1, type2, false, NULL,
1532 base_mismatch = true;
1536 if (!warned && !val->odr_violated)
1538 warn_odr (type, val->type, NULL, NULL,
1540 "a type with the same name but different base "
1541 "type is defined in another translation unit");
1543 warn_types_mismatch (type1, type2);
1547 if (BINFO_OFFSET (base1) != BINFO_OFFSET (base2))
1549 base_mismatch = true;
1550 if (!warned && !val->odr_violated)
1551 warn_odr (type, val->type, NULL, NULL,
1553 "a type with the same name but different base "
1554 "layout is defined in another translation unit");
1557 /* One of bases is not of complete type. */
1558 if (!TYPE_BINFO (type1) != !TYPE_BINFO (type2))
1560 /* If we have a polymorphic type info specified for TYPE1
1561 but not for TYPE2 we possibly missed a base when recording
1563 Be sure this does not happen. */
1564 gcc_assert (TYPE_BINFO (type2)
1565 || !polymorphic_type_binfo_p (TYPE_BINFO (type1))
1569 /* One base is polymorphic and the other not.
1570 This ought to be diagnosed earlier, but do not ICE in the
1572 else if (TYPE_BINFO (type1)
1573 && polymorphic_type_binfo_p (TYPE_BINFO (type1))
1574 != polymorphic_type_binfo_p (TYPE_BINFO (type2)))
1576 gcc_assert (val->odr_violated);
1577 base_mismatch = true;
1581 #ifdef ENABLE_CHECKING
1582 /* Sanity check that all bases will be build same way again. */
1583 if (!base_mismatch && val->bases.length ())
1585 unsigned int num_poly_bases = 0;
1588 for (i = 0; i < BINFO_N_BASE_BINFOS (TYPE_BINFO (type)); i++)
1589 if (polymorphic_type_binfo_p (BINFO_BASE_BINFO
1590 (TYPE_BINFO (type), i)))
1592 gcc_assert (num_poly_bases == val->bases.length ());
1593 for (j = 0, i = 0; i < BINFO_N_BASE_BINFOS (TYPE_BINFO (type));
1595 if (polymorphic_type_binfo_p (BINFO_BASE_BINFO
1596 (TYPE_BINFO (type), i)))
1598 odr_type base = get_odr_type
1600 (BINFO_BASE_BINFO (TYPE_BINFO (type),
1603 gcc_assert (val->bases[j] == base);
1611 odr_violation_reported = true;
1612 val->odr_violated = true;
1614 if (symtab->dump_file)
1616 fprintf (symtab->dump_file, "ODR base violation\n");
1618 print_node (symtab->dump_file, "", val->type, 0);
1619 putc ('\n',symtab->dump_file);
1620 print_node (symtab->dump_file, "", type, 0);
1621 putc ('\n',symtab->dump_file);
1626 /* Regularize things a little. During LTO same types may come with
1627 different BINFOs. Either because their virtual table was
1628 not merged by tree merging and only later at decl merging or
1629 because one type comes with external vtable, while other
1630 with internal. We want to merge equivalent binfos to conserve
1631 memory and streaming overhead.
1633 The external vtables are more harmful: they contain references
1634 to external declarations of methods that may be defined in the
1635 merged LTO unit. For this reason we absolutely need to remove
1636 them and replace by internal variants. Not doing so will lead
1637 to incomplete answers from possible_polymorphic_call_targets.
1639 FIXME: disable for now; because ODR types are now build during
1640 streaming in, the variants do not need to be linked to the type,
1641 yet. We need to do the merging in cleanup pass to be implemented
1643 if (!flag_ltrans && merge
1645 && TREE_CODE (val->type) == RECORD_TYPE
1646 && TREE_CODE (type) == RECORD_TYPE
1647 && TYPE_BINFO (val->type) && TYPE_BINFO (type)
1648 && TYPE_MAIN_VARIANT (type) == type
1649 && TYPE_MAIN_VARIANT (val->type) == val->type
1650 && BINFO_VTABLE (TYPE_BINFO (val->type))
1651 && BINFO_VTABLE (TYPE_BINFO (type)))
1653 tree master_binfo = TYPE_BINFO (val->type);
1654 tree v1 = BINFO_VTABLE (master_binfo);
1655 tree v2 = BINFO_VTABLE (TYPE_BINFO (type));
1657 if (TREE_CODE (v1) == POINTER_PLUS_EXPR)
1659 gcc_assert (TREE_CODE (v2) == POINTER_PLUS_EXPR
1660 && operand_equal_p (TREE_OPERAND (v1, 1),
1661 TREE_OPERAND (v2, 1), 0));
1662 v1 = TREE_OPERAND (TREE_OPERAND (v1, 0), 0);
1663 v2 = TREE_OPERAND (TREE_OPERAND (v2, 0), 0);
1665 gcc_assert (DECL_ASSEMBLER_NAME (v1)
1666 == DECL_ASSEMBLER_NAME (v2));
1668 if (DECL_EXTERNAL (v1) && !DECL_EXTERNAL (v2))
1672 set_type_binfo (val->type, TYPE_BINFO (type));
1673 for (i = 0; i < val->types->length (); i++)
1675 if (TYPE_BINFO ((*val->types)[i])
1677 set_type_binfo ((*val->types)[i], TYPE_BINFO (type));
1679 BINFO_TYPE (TYPE_BINFO (type)) = val->type;
1682 set_type_binfo (type, master_binfo);
1687 /* Get ODR type hash entry for TYPE. If INSERT is true, create
1688 possibly new entry. */
1691 get_odr_type (tree type, bool insert)
1693 odr_type_d **slot = NULL;
1694 odr_type_d **vtable_slot = NULL;
1695 odr_type val = NULL;
1697 bool build_bases = false;
1698 bool insert_to_odr_array = false;
1701 type = main_odr_variant (type);
1703 gcc_checking_assert (can_be_name_hashed_p (type)
1704 || can_be_vtable_hashed_p (type));
1706 /* Lookup entry, first try name hash, fallback to vtable hash. */
1707 if (can_be_name_hashed_p (type))
1709 hash = hash_odr_name (type);
1710 slot = odr_hash->find_slot_with_hash (type, hash,
1711 insert ? INSERT : NO_INSERT);
1713 if ((!slot || !*slot) && in_lto_p && can_be_vtable_hashed_p (type))
1715 hash = hash_odr_vtable (type);
1716 vtable_slot = odr_vtable_hash->find_slot_with_hash (type, hash,
1717 insert ? INSERT : NO_INSERT);
1720 if (!slot && !vtable_slot)
1723 /* See if we already have entry for type. */
1724 if ((slot && *slot) || (vtable_slot && *vtable_slot))
1729 #ifdef ENABLE_CHECKING
1730 if (in_lto_p && can_be_vtable_hashed_p (type))
1732 hash = hash_odr_vtable (type);
1733 vtable_slot = odr_vtable_hash->find_slot_with_hash (type, hash,
1735 gcc_assert (!vtable_slot || *vtable_slot == *slot);
1740 else if (*vtable_slot)
1743 if (val->type != type
1744 && (!val->types_set || !val->types_set->add (type)))
1746 gcc_assert (insert);
1747 /* We have type duplicate, but it may introduce vtable name or
1748 mangled name; be sure to keep hashes in sync. */
1749 if (in_lto_p && can_be_vtable_hashed_p (type)
1750 && (!vtable_slot || !*vtable_slot))
1754 hash = hash_odr_vtable (type);
1755 vtable_slot = odr_vtable_hash->find_slot_with_hash
1756 (type, hash, INSERT);
1757 gcc_checking_assert (!*vtable_slot || *vtable_slot == val);
1763 build_bases = add_type_duplicate (val, type);
1768 val = ggc_cleared_alloc<odr_type_d> ();
1771 val->derived_types = vNULL;
1772 val->anonymous_namespace = type_in_anonymous_namespace_p (type);
1773 build_bases = COMPLETE_TYPE_P (val->type);
1774 insert_to_odr_array = true;
1781 if (build_bases && TREE_CODE (type) == RECORD_TYPE && TYPE_BINFO (type)
1782 && type == TYPE_MAIN_VARIANT (type))
1784 tree binfo = TYPE_BINFO (type);
1787 gcc_assert (BINFO_TYPE (TYPE_BINFO (val->type)) = type);
1789 val->all_derivations_known = type_all_derivations_known_p (type);
1790 for (i = 0; i < BINFO_N_BASE_BINFOS (binfo); i++)
1791 /* For now record only polymorphic types. other are
1792 pointless for devirtualization and we can not precisely
1793 determine ODR equivalency of these during LTO. */
1794 if (polymorphic_type_binfo_p (BINFO_BASE_BINFO (binfo, i)))
1796 odr_type base = get_odr_type (BINFO_TYPE (BINFO_BASE_BINFO (binfo,
1799 gcc_assert (TYPE_MAIN_VARIANT (base->type) == base->type);
1800 base->derived_types.safe_push (val);
1801 val->bases.safe_push (base);
1802 if (base->id > base_id)
1806 /* Ensure that type always appears after bases. */
1807 if (insert_to_odr_array)
1810 val->id = odr_types.length ();
1811 vec_safe_push (odr_types_ptr, val);
1813 else if (base_id > val->id)
1815 odr_types[val->id] = 0;
1816 /* Be sure we did not recorded any derived types; these may need
1818 gcc_assert (val->derived_types.length() == 0);
1820 val->id = odr_types.length ();
1821 vec_safe_push (odr_types_ptr, val);
1826 /* Add TYPE od ODR type hash. */
1829 register_odr_type (tree type)
1833 odr_hash = new odr_hash_type (23);
1835 odr_vtable_hash = new odr_vtable_hash_type (23);
1837 /* Arrange things to be nicer and insert main variants first. */
1838 if (odr_type_p (TYPE_MAIN_VARIANT (type)))
1839 get_odr_type (TYPE_MAIN_VARIANT (type), true);
1840 if (TYPE_MAIN_VARIANT (type) != type)
1841 get_odr_type (type, true);
1844 /* Return true if type is known to have no derivations. */
1847 type_known_to_have_no_deriavations_p (tree t)
1849 return (type_all_derivations_known_p (t)
1850 && (TYPE_FINAL_P (t)
1852 && !get_odr_type (t, true)->derived_types.length())));
1855 /* Dump ODR type T and all its derived types. INDENT specifies indentation for
1856 recursive printing. */
1859 dump_odr_type (FILE *f, odr_type t, int indent=0)
1862 fprintf (f, "%*s type %i: ", indent * 2, "", t->id);
1863 print_generic_expr (f, t->type, TDF_SLIM);
1864 fprintf (f, "%s", t->anonymous_namespace ? " (anonymous namespace)":"");
1865 fprintf (f, "%s\n", t->all_derivations_known ? " (derivations known)":"");
1866 if (TYPE_NAME (t->type))
1868 fprintf (f, "%*s defined at: %s:%i\n", indent * 2, "",
1869 DECL_SOURCE_FILE (TYPE_NAME (t->type)),
1870 DECL_SOURCE_LINE (TYPE_NAME (t->type)));
1871 if (DECL_ASSEMBLER_NAME_SET_P (TYPE_NAME (t->type)))
1872 fprintf (f, "%*s mangled name: %s\n", indent * 2, "",
1874 (DECL_ASSEMBLER_NAME (TYPE_NAME (t->type))));
1876 if (t->bases.length ())
1878 fprintf (f, "%*s base odr type ids: ", indent * 2, "");
1879 for (i = 0; i < t->bases.length (); i++)
1880 fprintf (f, " %i", t->bases[i]->id);
1883 if (t->derived_types.length ())
1885 fprintf (f, "%*s derived types:\n", indent * 2, "");
1886 for (i = 0; i < t->derived_types.length (); i++)
1887 dump_odr_type (f, t->derived_types[i], indent + 1);
1892 /* Dump the type inheritance graph. */
1895 dump_type_inheritance_graph (FILE *f)
1900 fprintf (f, "\n\nType inheritance graph:\n");
1901 for (i = 0; i < odr_types.length (); i++)
1903 if (odr_types[i] && odr_types[i]->bases.length () == 0)
1904 dump_odr_type (f, odr_types[i]);
1906 for (i = 0; i < odr_types.length (); i++)
1908 if (odr_types[i] && odr_types[i]->types && odr_types[i]->types->length ())
1911 fprintf (f, "Duplicate tree types for odr type %i\n", i);
1912 print_node (f, "", odr_types[i]->type, 0);
1913 for (j = 0; j < odr_types[i]->types->length (); j++)
1916 fprintf (f, "duplicate #%i\n", j);
1917 print_node (f, "", (*odr_types[i]->types)[j], 0);
1918 t = (*odr_types[i]->types)[j];
1919 while (TYPE_P (t) && TYPE_CONTEXT (t))
1921 t = TYPE_CONTEXT (t);
1922 print_node (f, "", t, 0);
1930 /* Given method type T, return type of class it belongs to.
1931 Look up this pointer and get its type. */
1934 method_class_type (const_tree t)
1936 tree first_parm_type = TREE_VALUE (TYPE_ARG_TYPES (t));
1937 gcc_assert (TREE_CODE (t) == METHOD_TYPE);
1939 return TREE_TYPE (first_parm_type);
1942 /* Initialize IPA devirt and build inheritance tree graph. */
1945 build_type_inheritance_graph (void)
1947 struct symtab_node *n;
1948 FILE *inheritance_dump_file;
1953 timevar_push (TV_IPA_INHERITANCE);
1954 inheritance_dump_file = dump_begin (TDI_inheritance, &flags);
1955 odr_hash = new odr_hash_type (23);
1957 odr_vtable_hash = new odr_vtable_hash_type (23);
1959 /* We reconstruct the graph starting of types of all methods seen in the
1962 if (is_a <cgraph_node *> (n)
1963 && DECL_VIRTUAL_P (n->decl)
1964 && n->real_symbol_p ())
1965 get_odr_type (TYPE_MAIN_VARIANT (method_class_type (TREE_TYPE (n->decl))),
1968 /* Look also for virtual tables of types that do not define any methods.
1970 We need it in a case where class B has virtual base of class A
1971 re-defining its virtual method and there is class C with no virtual
1972 methods with B as virtual base.
1974 Here we output B's virtual method in two variant - for non-virtual
1975 and virtual inheritance. B's virtual table has non-virtual version,
1976 while C's has virtual.
1978 For this reason we need to know about C in order to include both
1979 variants of B. More correctly, record_target_from_binfo should
1980 add both variants of the method when walking B, but we have no
1981 link in between them.
1983 We rely on fact that either the method is exported and thus we
1984 assume it is called externally or C is in anonymous namespace and
1985 thus we will see the vtable. */
1987 else if (is_a <varpool_node *> (n)
1988 && DECL_VIRTUAL_P (n->decl)
1989 && TREE_CODE (DECL_CONTEXT (n->decl)) == RECORD_TYPE
1990 && TYPE_BINFO (DECL_CONTEXT (n->decl))
1991 && polymorphic_type_binfo_p (TYPE_BINFO (DECL_CONTEXT (n->decl))))
1992 get_odr_type (TYPE_MAIN_VARIANT (DECL_CONTEXT (n->decl)), true);
1993 if (inheritance_dump_file)
1995 dump_type_inheritance_graph (inheritance_dump_file);
1996 dump_end (TDI_inheritance, inheritance_dump_file);
1998 timevar_pop (TV_IPA_INHERITANCE);
2001 /* Return true if N has reference from live virtual table
2002 (and thus can be a destination of polymorphic call).
2003 Be conservatively correct when callgraph is not built or
2004 if the method may be referred externally. */
2007 referenced_from_vtable_p (struct cgraph_node *node)
2010 struct ipa_ref *ref;
2013 if (node->externally_visible
2014 || DECL_EXTERNAL (node->decl)
2015 || node->used_from_other_partition)
2018 /* Keep this test constant time.
2019 It is unlikely this can happen except for the case where speculative
2020 devirtualization introduced many speculative edges to this node.
2021 In this case the target is very likely alive anyway. */
2022 if (node->ref_list.referring.length () > 100)
2025 /* We need references built. */
2026 if (symtab->state <= CONSTRUCTION)
2029 for (i = 0; node->iterate_referring (i, ref); i++)
2030 if ((ref->use == IPA_REF_ALIAS
2031 && referenced_from_vtable_p (dyn_cast<cgraph_node *> (ref->referring)))
2032 || (ref->use == IPA_REF_ADDR
2033 && TREE_CODE (ref->referring->decl) == VAR_DECL
2034 && DECL_VIRTUAL_P (ref->referring->decl)))
2042 /* If TARGET has associated node, record it in the NODES array.
2043 CAN_REFER specify if program can refer to the target directly.
2044 if TARGET is unknown (NULL) or it can not be inserted (for example because
2045 its body was already removed and there is no way to refer to it), clear
2049 maybe_record_node (vec <cgraph_node *> &nodes,
2050 tree target, hash_set<tree> *inserted,
2054 struct cgraph_node *target_node, *alias_target;
2055 enum availability avail;
2057 /* cxa_pure_virtual and __builtin_unreachable do not need to be added into
2058 list of targets; the runtime effect of calling them is undefined.
2059 Only "real" virtual methods should be accounted. */
2060 if (target && TREE_CODE (TREE_TYPE (target)) != METHOD_TYPE)
2065 /* The only case when method of anonymous namespace becomes unreferable
2066 is when we completely optimized it out. */
2069 || !type_in_anonymous_namespace_p (DECL_CONTEXT (target)))
2077 target_node = cgraph_node::get (target);
2079 /* Prefer alias target over aliases, so we do not get confused by
2083 alias_target = target_node->ultimate_alias_target (&avail);
2084 if (target_node != alias_target
2085 && avail >= AVAIL_AVAILABLE
2086 && target_node->get_availability ())
2087 target_node = alias_target;
2090 /* Method can only be called by polymorphic call if any
2091 of vtables referring to it are alive.
2093 While this holds for non-anonymous functions, too, there are
2094 cases where we want to keep them in the list; for example
2095 inline functions with -fno-weak are static, but we still
2096 may devirtualize them when instance comes from other unit.
2097 The same holds for LTO.
2099 Currently we ignore these functions in speculative devirtualization.
2100 ??? Maybe it would make sense to be more aggressive for LTO even
2103 && type_in_anonymous_namespace_p (DECL_CONTEXT (target))
2105 || !referenced_from_vtable_p (target_node)))
2107 /* See if TARGET is useful function we can deal with. */
2108 else if (target_node != NULL
2109 && (TREE_PUBLIC (target)
2110 || DECL_EXTERNAL (target)
2111 || target_node->definition)
2112 && target_node->real_symbol_p ())
2114 gcc_assert (!target_node->global.inlined_to);
2115 gcc_assert (target_node->real_symbol_p ());
2116 if (!inserted->add (target))
2118 cached_polymorphic_call_targets->add (target_node);
2119 nodes.safe_push (target_node);
2123 && (!type_in_anonymous_namespace_p
2124 (DECL_CONTEXT (target))
2129 /* See if BINFO's type matches OUTER_TYPE. If so, look up
2130 BINFO of subtype of OTR_TYPE at OFFSET and in that BINFO find
2131 method in vtable and insert method to NODES array
2132 or BASES_TO_CONSIDER if this array is non-NULL.
2133 Otherwise recurse to base BINFOs.
2134 This matches what get_binfo_at_offset does, but with offset
2137 TYPE_BINFOS is a stack of BINFOS of types with defined
2138 virtual table seen on way from class type to BINFO.
2140 MATCHED_VTABLES tracks virtual tables we already did lookup
2141 for virtual function in. INSERTED tracks nodes we already
2144 ANONYMOUS is true if BINFO is part of anonymous namespace.
2146 Clear COMPLETEP when we hit unreferable target.
2150 record_target_from_binfo (vec <cgraph_node *> &nodes,
2151 vec <tree> *bases_to_consider,
2154 vec <tree> &type_binfos,
2155 HOST_WIDE_INT otr_token,
2157 HOST_WIDE_INT offset,
2158 hash_set<tree> *inserted,
2159 hash_set<tree> *matched_vtables,
2163 tree type = BINFO_TYPE (binfo);
2168 if (BINFO_VTABLE (binfo))
2169 type_binfos.safe_push (binfo);
2170 if (types_same_for_odr (type, outer_type))
2173 tree type_binfo = NULL;
2175 /* Look up BINFO with virtual table. For normal types it is always last
2177 for (i = type_binfos.length () - 1; i >= 0; i--)
2178 if (BINFO_OFFSET (type_binfos[i]) == BINFO_OFFSET (binfo))
2180 type_binfo = type_binfos[i];
2183 if (BINFO_VTABLE (binfo))
2185 /* If this is duplicated BINFO for base shared by virtual inheritance,
2186 we may not have its associated vtable. This is not a problem, since
2187 we will walk it on the other path. */
2190 tree inner_binfo = get_binfo_at_offset (type_binfo,
2194 gcc_assert (odr_violation_reported);
2197 /* For types in anonymous namespace first check if the respective vtable
2198 is alive. If not, we know the type can't be called. */
2199 if (!flag_ltrans && anonymous)
2201 tree vtable = BINFO_VTABLE (inner_binfo);
2202 varpool_node *vnode;
2204 if (TREE_CODE (vtable) == POINTER_PLUS_EXPR)
2205 vtable = TREE_OPERAND (TREE_OPERAND (vtable, 0), 0);
2206 vnode = varpool_node::get (vtable);
2207 if (!vnode || !vnode->definition)
2210 gcc_assert (inner_binfo);
2211 if (bases_to_consider
2212 ? !matched_vtables->contains (BINFO_VTABLE (inner_binfo))
2213 : !matched_vtables->add (BINFO_VTABLE (inner_binfo)))
2216 tree target = gimple_get_virt_method_for_binfo (otr_token,
2219 if (!bases_to_consider)
2220 maybe_record_node (nodes, target, inserted, can_refer, completep);
2221 /* Destructors are never called via construction vtables. */
2222 else if (!target || !DECL_CXX_DESTRUCTOR_P (target))
2223 bases_to_consider->safe_push (target);
2229 for (i = 0; BINFO_BASE_ITERATE (binfo, i, base_binfo); i++)
2230 /* Walking bases that have no virtual method is pointless exercise. */
2231 if (polymorphic_type_binfo_p (base_binfo))
2232 record_target_from_binfo (nodes, bases_to_consider, base_binfo, otr_type,
2234 otr_token, outer_type, offset, inserted,
2235 matched_vtables, anonymous, completep);
2236 if (BINFO_VTABLE (binfo))
2240 /* Look up virtual methods matching OTR_TYPE (with OFFSET and OTR_TOKEN)
2241 of TYPE, insert them to NODES, recurse into derived nodes.
2242 INSERTED is used to avoid duplicate insertions of methods into NODES.
2243 MATCHED_VTABLES are used to avoid duplicate walking vtables.
2244 Clear COMPLETEP if unreferable target is found.
2246 If CONSIDER_CONSTRUCTION is true, record to BASES_TO_CONSIDER
2247 all cases where BASE_SKIPPED is true (because the base is abstract
2251 possible_polymorphic_call_targets_1 (vec <cgraph_node *> &nodes,
2252 hash_set<tree> *inserted,
2253 hash_set<tree> *matched_vtables,
2256 HOST_WIDE_INT otr_token,
2258 HOST_WIDE_INT offset,
2260 vec <tree> &bases_to_consider,
2261 bool consider_construction)
2263 tree binfo = TYPE_BINFO (type->type);
2265 auto_vec <tree, 8> type_binfos;
2266 bool possibly_instantiated = type_possibly_instantiated_p (type->type);
2268 /* We may need to consider types w/o instances because of possible derived
2269 types using their methods either directly or via construction vtables.
2270 We are safe to skip them when all derivations are known, since we will
2272 This is done by recording them to BASES_TO_CONSIDER array. */
2273 if (possibly_instantiated || consider_construction)
2275 record_target_from_binfo (nodes,
2276 (!possibly_instantiated
2277 && type_all_derivations_known_p (type->type))
2278 ? &bases_to_consider : NULL,
2279 binfo, otr_type, type_binfos, otr_token,
2281 inserted, matched_vtables,
2282 type->anonymous_namespace, completep);
2284 for (i = 0; i < type->derived_types.length (); i++)
2285 possible_polymorphic_call_targets_1 (nodes, inserted,
2288 type->derived_types[i],
2289 otr_token, outer_type, offset, completep,
2290 bases_to_consider, consider_construction);
2293 /* Cache of queries for polymorphic call targets.
2295 Enumerating all call targets may get expensive when there are many
2296 polymorphic calls in the program, so we memoize all the previous
2297 queries and avoid duplicated work. */
2299 struct polymorphic_call_target_d
2301 HOST_WIDE_INT otr_token;
2302 ipa_polymorphic_call_context context;
2304 vec <cgraph_node *> targets;
2311 /* Polymorphic call target cache helpers. */
2313 struct polymorphic_call_target_hasher
2315 typedef polymorphic_call_target_d value_type;
2316 typedef polymorphic_call_target_d compare_type;
2317 static inline hashval_t hash (const value_type *);
2318 static inline bool equal (const value_type *, const compare_type *);
2319 static inline void remove (value_type *);
2322 /* Return the computed hashcode for ODR_QUERY. */
2325 polymorphic_call_target_hasher::hash (const value_type *odr_query)
2327 inchash::hash hstate (odr_query->otr_token);
2329 hstate.add_wide_int (odr_query->type->id);
2330 hstate.merge_hash (TYPE_UID (odr_query->context.outer_type));
2331 hstate.add_wide_int (odr_query->context.offset);
2333 if (odr_query->context.speculative_outer_type)
2335 hstate.merge_hash (TYPE_UID (odr_query->context.speculative_outer_type));
2336 hstate.add_wide_int (odr_query->context.speculative_offset);
2338 hstate.add_flag (odr_query->speculative);
2339 hstate.add_flag (odr_query->context.maybe_in_construction);
2340 hstate.add_flag (odr_query->context.maybe_derived_type);
2341 hstate.add_flag (odr_query->context.speculative_maybe_derived_type);
2342 hstate.commit_flag ();
2343 return hstate.end ();
2346 /* Compare cache entries T1 and T2. */
2349 polymorphic_call_target_hasher::equal (const value_type *t1,
2350 const compare_type *t2)
2352 return (t1->type == t2->type && t1->otr_token == t2->otr_token
2353 && t1->speculative == t2->speculative
2354 && t1->context.offset == t2->context.offset
2355 && t1->context.speculative_offset == t2->context.speculative_offset
2356 && t1->context.outer_type == t2->context.outer_type
2357 && t1->context.speculative_outer_type == t2->context.speculative_outer_type
2358 && t1->context.maybe_in_construction
2359 == t2->context.maybe_in_construction
2360 && t1->context.maybe_derived_type == t2->context.maybe_derived_type
2361 && (t1->context.speculative_maybe_derived_type
2362 == t2->context.speculative_maybe_derived_type));
2365 /* Remove entry in polymorphic call target cache hash. */
2368 polymorphic_call_target_hasher::remove (value_type *v)
2370 v->targets.release ();
2374 /* Polymorphic call target query cache. */
2376 typedef hash_table<polymorphic_call_target_hasher>
2377 polymorphic_call_target_hash_type;
2378 static polymorphic_call_target_hash_type *polymorphic_call_target_hash;
2380 /* Destroy polymorphic call target query cache. */
2383 free_polymorphic_call_targets_hash ()
2385 if (cached_polymorphic_call_targets)
2387 delete polymorphic_call_target_hash;
2388 polymorphic_call_target_hash = NULL;
2389 delete cached_polymorphic_call_targets;
2390 cached_polymorphic_call_targets = NULL;
2394 /* When virtual function is removed, we may need to flush the cache. */
2397 devirt_node_removal_hook (struct cgraph_node *n, void *d ATTRIBUTE_UNUSED)
2399 if (cached_polymorphic_call_targets
2400 && cached_polymorphic_call_targets->contains (n))
2401 free_polymorphic_call_targets_hash ();
2404 /* Look up base of BINFO that has virtual table VTABLE with OFFSET. */
2407 subbinfo_with_vtable_at_offset (tree binfo, unsigned HOST_WIDE_INT offset,
2410 tree v = BINFO_VTABLE (binfo);
2413 unsigned HOST_WIDE_INT this_offset;
2417 if (!vtable_pointer_value_to_vtable (v, &v, &this_offset))
2420 if (offset == this_offset
2421 && DECL_ASSEMBLER_NAME (v) == DECL_ASSEMBLER_NAME (vtable))
2425 for (i = 0; BINFO_BASE_ITERATE (binfo, i, base_binfo); i++)
2426 if (polymorphic_type_binfo_p (base_binfo))
2428 base_binfo = subbinfo_with_vtable_at_offset (base_binfo, offset, vtable);
2435 /* T is known constant value of virtual table pointer.
2436 Store virtual table to V and its offset to OFFSET.
2437 Return false if T does not look like virtual table reference. */
2440 vtable_pointer_value_to_vtable (const_tree t, tree *v,
2441 unsigned HOST_WIDE_INT *offset)
2443 /* We expect &MEM[(void *)&virtual_table + 16B].
2444 We obtain object's BINFO from the context of the virtual table.
2445 This one contains pointer to virtual table represented via
2446 POINTER_PLUS_EXPR. Verify that this pointer matches what
2447 we propagated through.
2449 In the case of virtual inheritance, the virtual tables may
2450 be nested, i.e. the offset may be different from 16 and we may
2451 need to dive into the type representation. */
2452 if (TREE_CODE (t) == ADDR_EXPR
2453 && TREE_CODE (TREE_OPERAND (t, 0)) == MEM_REF
2454 && TREE_CODE (TREE_OPERAND (TREE_OPERAND (t, 0), 0)) == ADDR_EXPR
2455 && TREE_CODE (TREE_OPERAND (TREE_OPERAND (t, 0), 1)) == INTEGER_CST
2456 && (TREE_CODE (TREE_OPERAND (TREE_OPERAND (TREE_OPERAND (t, 0), 0), 0))
2458 && DECL_VIRTUAL_P (TREE_OPERAND (TREE_OPERAND
2459 (TREE_OPERAND (t, 0), 0), 0)))
2461 *v = TREE_OPERAND (TREE_OPERAND (TREE_OPERAND (t, 0), 0), 0);
2462 *offset = tree_to_uhwi (TREE_OPERAND (TREE_OPERAND (t, 0), 1));
2466 /* Alternative representation, used by C++ frontend is POINTER_PLUS_EXPR.
2467 We need to handle it when T comes from static variable initializer or
2469 if (TREE_CODE (t) == POINTER_PLUS_EXPR)
2471 *offset = tree_to_uhwi (TREE_OPERAND (t, 1));
2472 t = TREE_OPERAND (t, 0);
2477 if (TREE_CODE (t) != ADDR_EXPR)
2479 *v = TREE_OPERAND (t, 0);
2483 /* T is known constant value of virtual table pointer. Return BINFO of the
2487 vtable_pointer_value_to_binfo (const_tree t)
2490 unsigned HOST_WIDE_INT offset;
2492 if (!vtable_pointer_value_to_vtable (t, &vtable, &offset))
2495 /* FIXME: for stores of construction vtables we return NULL,
2496 because we do not have BINFO for those. Eventually we should fix
2497 our representation to allow this case to be handled, too.
2498 In the case we see store of BINFO we however may assume
2499 that standard folding will be able to cope with it. */
2500 return subbinfo_with_vtable_at_offset (TYPE_BINFO (DECL_CONTEXT (vtable)),
2504 /* Walk bases of OUTER_TYPE that contain OTR_TYPE at OFFSET.
2505 Look up their respective virtual methods for OTR_TOKEN and OTR_TYPE
2506 and insert them in NODES.
2508 MATCHED_VTABLES and INSERTED is used to avoid duplicated work. */
2511 record_targets_from_bases (tree otr_type,
2512 HOST_WIDE_INT otr_token,
2514 HOST_WIDE_INT offset,
2515 vec <cgraph_node *> &nodes,
2516 hash_set<tree> *inserted,
2517 hash_set<tree> *matched_vtables,
2522 HOST_WIDE_INT pos, size;
2526 if (types_same_for_odr (outer_type, otr_type))
2529 for (fld = TYPE_FIELDS (outer_type); fld; fld = DECL_CHAIN (fld))
2531 if (TREE_CODE (fld) != FIELD_DECL)
2534 pos = int_bit_position (fld);
2535 size = tree_to_shwi (DECL_SIZE (fld));
2536 if (pos <= offset && (pos + size) > offset
2537 /* Do not get confused by zero sized bases. */
2538 && polymorphic_type_binfo_p (TYPE_BINFO (TREE_TYPE (fld))))
2541 /* Within a class type we should always find corresponding fields. */
2542 gcc_assert (fld && TREE_CODE (TREE_TYPE (fld)) == RECORD_TYPE);
2544 /* Nonbase types should have been stripped by outer_class_type. */
2545 gcc_assert (DECL_ARTIFICIAL (fld));
2547 outer_type = TREE_TYPE (fld);
2550 base_binfo = get_binfo_at_offset (TYPE_BINFO (outer_type),
2554 gcc_assert (odr_violation_reported);
2557 gcc_assert (base_binfo);
2558 if (!matched_vtables->add (BINFO_VTABLE (base_binfo)))
2561 tree target = gimple_get_virt_method_for_binfo (otr_token,
2564 if (!target || ! DECL_CXX_DESTRUCTOR_P (target))
2565 maybe_record_node (nodes, target, inserted, can_refer, completep);
2566 matched_vtables->add (BINFO_VTABLE (base_binfo));
2571 /* When virtual table is removed, we may need to flush the cache. */
2574 devirt_variable_node_removal_hook (varpool_node *n,
2575 void *d ATTRIBUTE_UNUSED)
2577 if (cached_polymorphic_call_targets
2578 && DECL_VIRTUAL_P (n->decl)
2579 && type_in_anonymous_namespace_p (DECL_CONTEXT (n->decl)))
2580 free_polymorphic_call_targets_hash ();
2583 /* Record about how many calls would benefit from given type to be final. */
2585 struct odr_type_warn_count
2589 gcov_type dyn_count;
2592 /* Record about how many calls would benefit from given method to be final. */
2594 struct decl_warn_count
2598 gcov_type dyn_count;
2601 /* Information about type and decl warnings. */
2603 struct final_warning_record
2605 gcov_type dyn_count;
2606 vec<odr_type_warn_count> type_warnings;
2607 hash_map<tree, decl_warn_count> decl_warnings;
2609 struct final_warning_record *final_warning_records;
2611 /* Return vector containing possible targets of polymorphic call of type
2612 OTR_TYPE calling method OTR_TOKEN within type of OTR_OUTER_TYPE and OFFSET.
2613 If INCLUDE_BASES is true, walk also base types of OUTER_TYPES containing
2614 OTR_TYPE and include their virtual method. This is useful for types
2615 possibly in construction or destruction where the virtual table may
2616 temporarily change to one of base types. INCLUDE_DERIVER_TYPES make
2617 us to walk the inheritance graph for all derivations.
2619 If COMPLETEP is non-NULL, store true if the list is complete.
2620 CACHE_TOKEN (if non-NULL) will get stored to an unique ID of entry
2621 in the target cache. If user needs to visit every target list
2622 just once, it can memoize them.
2624 If SPECULATIVE is set, the list will not contain targets that
2625 are not speculatively taken.
2627 Returned vector is placed into cache. It is NOT caller's responsibility
2628 to free it. The vector can be freed on cgraph_remove_node call if
2629 the particular node is a virtual function present in the cache. */
2632 possible_polymorphic_call_targets (tree otr_type,
2633 HOST_WIDE_INT otr_token,
2634 ipa_polymorphic_call_context context,
2639 static struct cgraph_node_hook_list *node_removal_hook_holder;
2640 vec <cgraph_node *> nodes = vNULL;
2641 auto_vec <tree, 8> bases_to_consider;
2642 odr_type type, outer_type;
2643 polymorphic_call_target_d key;
2644 polymorphic_call_target_d **slot;
2648 bool can_refer = false;
2649 bool skipped = false;
2651 otr_type = TYPE_MAIN_VARIANT (otr_type);
2653 /* If ODR is not initialized or the context is invalid, return empty
2655 if (!odr_hash || context.invalid || !TYPE_BINFO (otr_type))
2658 *completep = context.invalid;
2660 *cache_token = NULL;
2664 /* Do not bother to compute speculative info when user do not asks for it. */
2665 if (!speculative || !context.speculative_outer_type)
2666 context.clear_speculation ();
2668 type = get_odr_type (otr_type, true);
2670 /* Recording type variants would waste results cache. */
2671 gcc_assert (!context.outer_type
2672 || TYPE_MAIN_VARIANT (context.outer_type) == context.outer_type);
2674 /* Look up the outer class type we want to walk.
2675 If we fail to do so, the context is invalid. */
2676 if ((context.outer_type || context.speculative_outer_type)
2677 && !context.restrict_to_inner_class (otr_type))
2682 *cache_token = NULL;
2685 gcc_assert (!context.invalid);
2687 /* Check that restrict_to_inner_class kept the main variant. */
2688 gcc_assert (!context.outer_type
2689 || TYPE_MAIN_VARIANT (context.outer_type) == context.outer_type);
2691 /* We canonicalize our query, so we do not need extra hashtable entries. */
2693 /* Without outer type, we have no use for offset. Just do the
2694 basic search from inner type. */
2695 if (!context.outer_type)
2696 context.clear_outer_type (otr_type);
2697 /* We need to update our hierarchy if the type does not exist. */
2698 outer_type = get_odr_type (context.outer_type, true);
2699 /* If the type is complete, there are no derivations. */
2700 if (TYPE_FINAL_P (outer_type->type))
2701 context.maybe_derived_type = false;
2703 /* Initialize query cache. */
2704 if (!cached_polymorphic_call_targets)
2706 cached_polymorphic_call_targets = new hash_set<cgraph_node *>;
2707 polymorphic_call_target_hash
2708 = new polymorphic_call_target_hash_type (23);
2709 if (!node_removal_hook_holder)
2711 node_removal_hook_holder =
2712 symtab->add_cgraph_removal_hook (&devirt_node_removal_hook, NULL);
2713 symtab->add_varpool_removal_hook (&devirt_variable_node_removal_hook,
2720 if (context.outer_type != otr_type)
2722 = get_odr_type (context.outer_type, true)->type;
2723 if (context.speculative_outer_type)
2724 context.speculative_outer_type
2725 = get_odr_type (context.speculative_outer_type, true)->type;
2728 /* Look up cached answer. */
2730 key.otr_token = otr_token;
2731 key.speculative = speculative;
2732 key.context = context;
2733 slot = polymorphic_call_target_hash->find_slot (&key, INSERT);
2735 *cache_token = (void *)*slot;
2739 *completep = (*slot)->complete;
2740 if ((*slot)->type_warning && final_warning_records)
2742 final_warning_records->type_warnings[(*slot)->type_warning - 1].count++;
2743 final_warning_records->type_warnings[(*slot)->type_warning - 1].dyn_count
2744 += final_warning_records->dyn_count;
2746 if (!speculative && (*slot)->decl_warning && final_warning_records)
2748 struct decl_warn_count *c =
2749 final_warning_records->decl_warnings.get ((*slot)->decl_warning);
2751 c->dyn_count += final_warning_records->dyn_count;
2753 return (*slot)->targets;
2758 /* Do actual search. */
2759 timevar_push (TV_IPA_VIRTUAL_CALL);
2760 *slot = XCNEW (polymorphic_call_target_d);
2762 *cache_token = (void *)*slot;
2763 (*slot)->type = type;
2764 (*slot)->otr_token = otr_token;
2765 (*slot)->context = context;
2766 (*slot)->speculative = speculative;
2768 hash_set<tree> inserted;
2769 hash_set<tree> matched_vtables;
2771 /* First insert targets we speculatively identified as likely. */
2772 if (context.speculative_outer_type)
2774 odr_type speculative_outer_type;
2775 bool speculation_complete = true;
2777 /* First insert target from type itself and check if it may have
2779 speculative_outer_type = get_odr_type (context.speculative_outer_type, true);
2780 if (TYPE_FINAL_P (speculative_outer_type->type))
2781 context.speculative_maybe_derived_type = false;
2782 binfo = get_binfo_at_offset (TYPE_BINFO (speculative_outer_type->type),
2783 context.speculative_offset, otr_type);
2785 target = gimple_get_virt_method_for_binfo (otr_token, binfo,
2790 /* In the case we get complete method, we don't need
2791 to walk derivations. */
2792 if (target && DECL_FINAL_P (target))
2793 context.speculative_maybe_derived_type = false;
2794 if (type_possibly_instantiated_p (speculative_outer_type->type))
2795 maybe_record_node (nodes, target, &inserted, can_refer, &speculation_complete);
2797 matched_vtables.add (BINFO_VTABLE (binfo));
2800 /* Next walk recursively all derived types. */
2801 if (context.speculative_maybe_derived_type)
2802 for (i = 0; i < speculative_outer_type->derived_types.length(); i++)
2803 possible_polymorphic_call_targets_1 (nodes, &inserted,
2806 speculative_outer_type->derived_types[i],
2807 otr_token, speculative_outer_type->type,
2808 context.speculative_offset,
2809 &speculation_complete,
2814 if (!speculative || !nodes.length ())
2816 /* First see virtual method of type itself. */
2817 binfo = get_binfo_at_offset (TYPE_BINFO (outer_type->type),
2818 context.offset, otr_type);
2820 target = gimple_get_virt_method_for_binfo (otr_token, binfo,
2824 gcc_assert (odr_violation_reported);
2828 /* Destructors are never called through construction virtual tables,
2829 because the type is always known. */
2830 if (target && DECL_CXX_DESTRUCTOR_P (target))
2831 context.maybe_in_construction = false;
2835 /* In the case we get complete method, we don't need
2836 to walk derivations. */
2837 if (DECL_FINAL_P (target))
2838 context.maybe_derived_type = false;
2841 /* If OUTER_TYPE is abstract, we know we are not seeing its instance. */
2842 if (type_possibly_instantiated_p (outer_type->type))
2843 maybe_record_node (nodes, target, &inserted, can_refer, &complete);
2848 matched_vtables.add (BINFO_VTABLE (binfo));
2850 /* Next walk recursively all derived types. */
2851 if (context.maybe_derived_type)
2853 for (i = 0; i < outer_type->derived_types.length(); i++)
2854 possible_polymorphic_call_targets_1 (nodes, &inserted,
2857 outer_type->derived_types[i],
2858 otr_token, outer_type->type,
2859 context.offset, &complete,
2861 context.maybe_in_construction);
2863 if (!outer_type->all_derivations_known)
2865 if (!speculative && final_warning_records)
2868 && nodes.length () == 1
2869 && warn_suggest_final_types
2870 && !outer_type->derived_types.length ())
2872 if (outer_type->id >= (int)final_warning_records->type_warnings.length ())
2873 final_warning_records->type_warnings.safe_grow_cleared
2874 (odr_types.length ());
2875 final_warning_records->type_warnings[outer_type->id].count++;
2876 final_warning_records->type_warnings[outer_type->id].dyn_count
2877 += final_warning_records->dyn_count;
2878 final_warning_records->type_warnings[outer_type->id].type
2880 (*slot)->type_warning = outer_type->id + 1;
2883 && warn_suggest_final_methods
2884 && nodes.length () == 1
2885 && types_same_for_odr (DECL_CONTEXT (nodes[0]->decl),
2889 struct decl_warn_count &c =
2890 final_warning_records->decl_warnings.get_or_insert
2891 (nodes[0]->decl, &existed);
2896 c.dyn_count += final_warning_records->dyn_count;
2901 c.dyn_count = final_warning_records->dyn_count;
2902 c.decl = nodes[0]->decl;
2904 (*slot)->decl_warning = nodes[0]->decl;
2913 /* Destructors are never called through construction virtual tables,
2914 because the type is always known. One of entries may be
2915 cxa_pure_virtual so look to at least two of them. */
2916 if (context.maybe_in_construction)
2917 for (i =0 ; i < MIN (nodes.length (), 2); i++)
2918 if (DECL_CXX_DESTRUCTOR_P (nodes[i]->decl))
2919 context.maybe_in_construction = false;
2920 if (context.maybe_in_construction)
2922 if (type != outer_type
2924 || (context.maybe_derived_type
2925 && !type_all_derivations_known_p (outer_type->type))))
2926 record_targets_from_bases (otr_type, otr_token, outer_type->type,
2927 context.offset, nodes, &inserted,
2928 &matched_vtables, &complete);
2930 maybe_record_node (nodes, target, &inserted, can_refer, &complete);
2931 for (i = 0; i < bases_to_consider.length(); i++)
2932 maybe_record_node (nodes, bases_to_consider[i], &inserted, can_refer, &complete);
2937 (*slot)->targets = nodes;
2938 (*slot)->complete = complete;
2940 *completep = complete;
2942 timevar_pop (TV_IPA_VIRTUAL_CALL);
2947 add_decl_warning (const tree &key ATTRIBUTE_UNUSED, const decl_warn_count &value,
2948 vec<const decl_warn_count*> *vec)
2950 vec->safe_push (&value);
2954 /* Dump target list TARGETS into FILE. */
2957 dump_targets (FILE *f, vec <cgraph_node *> targets)
2961 for (i = 0; i < targets.length (); i++)
2965 name = cplus_demangle_v3 (targets[i]->asm_name (), 0);
2966 fprintf (f, " %s/%i", name ? name : targets[i]->name (), targets[i]->order);
2969 if (!targets[i]->definition)
2970 fprintf (f, " (no definition%s)",
2971 DECL_DECLARED_INLINE_P (targets[i]->decl)
2977 /* Dump all possible targets of a polymorphic call. */
2980 dump_possible_polymorphic_call_targets (FILE *f,
2982 HOST_WIDE_INT otr_token,
2983 const ipa_polymorphic_call_context &ctx)
2985 vec <cgraph_node *> targets;
2987 odr_type type = get_odr_type (TYPE_MAIN_VARIANT (otr_type), false);
2992 targets = possible_polymorphic_call_targets (otr_type, otr_token,
2994 &final, NULL, false);
2995 fprintf (f, " Targets of polymorphic call of type %i:", type->id);
2996 print_generic_expr (f, type->type, TDF_SLIM);
2997 fprintf (f, " token %i\n", (int)otr_token);
3001 fprintf (f, " %s%s%s%s\n ",
3002 final ? "This is a complete list." :
3003 "This is partial list; extra targets may be defined in other units.",
3004 ctx.maybe_in_construction ? " (base types included)" : "",
3005 ctx.maybe_derived_type ? " (derived types included)" : "",
3006 ctx.speculative_maybe_derived_type ? " (speculative derived types included)" : "");
3007 len = targets.length ();
3008 dump_targets (f, targets);
3010 targets = possible_polymorphic_call_targets (otr_type, otr_token,
3012 &final, NULL, true);
3013 if (targets.length () != len)
3015 fprintf (f, " Speculative targets:");
3016 dump_targets (f, targets);
3018 gcc_assert (targets.length () <= len);
3023 /* Return true if N can be possibly target of a polymorphic call of
3024 OTR_TYPE/OTR_TOKEN. */
3027 possible_polymorphic_call_target_p (tree otr_type,
3028 HOST_WIDE_INT otr_token,
3029 const ipa_polymorphic_call_context &ctx,
3030 struct cgraph_node *n)
3032 vec <cgraph_node *> targets;
3034 enum built_in_function fcode;
3037 if (TREE_CODE (TREE_TYPE (n->decl)) == FUNCTION_TYPE
3038 && ((fcode = DECL_FUNCTION_CODE (n->decl))
3039 == BUILT_IN_UNREACHABLE
3040 || fcode == BUILT_IN_TRAP))
3045 targets = possible_polymorphic_call_targets (otr_type, otr_token, ctx, &final);
3046 for (i = 0; i < targets.length (); i++)
3047 if (n->semantically_equivalent_p (targets[i]))
3050 /* At a moment we allow middle end to dig out new external declarations
3051 as a targets of polymorphic calls. */
3052 if (!final && !n->definition)
3059 /* Return true if N can be possibly target of a polymorphic call of
3060 OBJ_TYPE_REF expression REF in STMT. */
3063 possible_polymorphic_call_target_p (tree ref,
3065 struct cgraph_node *n)
3067 ipa_polymorphic_call_context context (current_function_decl, ref, stmt);
3068 tree call_fn = gimple_call_fn (stmt);
3070 return possible_polymorphic_call_target_p (obj_type_ref_class (call_fn),
3072 (OBJ_TYPE_REF_TOKEN (call_fn)),
3078 /* After callgraph construction new external nodes may appear.
3079 Add them into the graph. */
3082 update_type_inheritance_graph (void)
3084 struct cgraph_node *n;
3088 free_polymorphic_call_targets_hash ();
3089 timevar_push (TV_IPA_INHERITANCE);
3090 /* We reconstruct the graph starting from types of all methods seen in the
3092 FOR_EACH_FUNCTION (n)
3093 if (DECL_VIRTUAL_P (n->decl)
3095 && n->real_symbol_p ())
3096 get_odr_type (method_class_type (TYPE_MAIN_VARIANT (TREE_TYPE (n->decl))),
3098 timevar_pop (TV_IPA_INHERITANCE);
3102 /* Return true if N looks like likely target of a polymorphic call.
3103 Rule out cxa_pure_virtual, noreturns, function declared cold and
3104 other obvious cases. */
3107 likely_target_p (struct cgraph_node *n)
3110 /* cxa_pure_virtual and similar things are not likely. */
3111 if (TREE_CODE (TREE_TYPE (n->decl)) != METHOD_TYPE)
3113 flags = flags_from_decl_or_type (n->decl);
3114 if (flags & ECF_NORETURN)
3116 if (lookup_attribute ("cold",
3117 DECL_ATTRIBUTES (n->decl)))
3119 if (n->frequency < NODE_FREQUENCY_NORMAL)
3121 /* If there are no live virtual tables referring the target,
3122 the only way the target can be called is an instance coming from other
3123 compilation unit; speculative devirtualization is built around an
3124 assumption that won't happen. */
3125 if (!referenced_from_vtable_p (n))
3130 /* Compare type warning records P1 and P2 and choose one with larger count;
3131 helper for qsort. */
3134 type_warning_cmp (const void *p1, const void *p2)
3136 const odr_type_warn_count *t1 = (const odr_type_warn_count *)p1;
3137 const odr_type_warn_count *t2 = (const odr_type_warn_count *)p2;
3139 if (t1->dyn_count < t2->dyn_count)
3141 if (t1->dyn_count > t2->dyn_count)
3143 return t2->count - t1->count;
3146 /* Compare decl warning records P1 and P2 and choose one with larger count;
3147 helper for qsort. */
3150 decl_warning_cmp (const void *p1, const void *p2)
3152 const decl_warn_count *t1 = *(const decl_warn_count * const *)p1;
3153 const decl_warn_count *t2 = *(const decl_warn_count * const *)p2;
3155 if (t1->dyn_count < t2->dyn_count)
3157 if (t1->dyn_count > t2->dyn_count)
3159 return t2->count - t1->count;
3163 /* Try to speculatively devirtualize call to OTR_TYPE with OTR_TOKEN with
3166 struct cgraph_node *
3167 try_speculative_devirtualization (tree otr_type, HOST_WIDE_INT otr_token,
3168 ipa_polymorphic_call_context ctx)
3170 vec <cgraph_node *>targets
3171 = possible_polymorphic_call_targets
3172 (otr_type, otr_token, ctx, NULL, NULL, true);
3174 struct cgraph_node *likely_target = NULL;
3176 for (i = 0; i < targets.length (); i++)
3177 if (likely_target_p (targets[i]))
3181 likely_target = targets[i];
3184 ||!likely_target->definition
3185 || DECL_EXTERNAL (likely_target->decl))
3188 /* Don't use an implicitly-declared destructor (c++/58678). */
3189 struct cgraph_node *non_thunk_target
3190 = likely_target->function_symbol ();
3191 if (DECL_ARTIFICIAL (non_thunk_target->decl))
3193 if (likely_target->get_availability () <= AVAIL_INTERPOSABLE
3194 && likely_target->can_be_discarded_p ())
3196 return likely_target;
3199 /* The ipa-devirt pass.
3200 When polymorphic call has only one likely target in the unit,
3201 turn it into a speculative call. */
3206 struct cgraph_node *n;
3207 hash_set<void *> bad_call_targets;
3208 struct cgraph_edge *e;
3210 int npolymorphic = 0, nspeculated = 0, nconverted = 0, ncold = 0;
3211 int nmultiple = 0, noverwritable = 0, ndevirtualized = 0, nnotdefined = 0;
3212 int nwrong = 0, nok = 0, nexternal = 0, nartificial = 0;
3219 dump_type_inheritance_graph (dump_file);
3221 /* We can output -Wsuggest-final-methods and -Wsuggest-final-types warnings.
3222 This is implemented by setting up final_warning_records that are updated
3223 by get_polymorphic_call_targets.
3224 We need to clear cache in this case to trigger recomputation of all
3226 if (warn_suggest_final_methods || warn_suggest_final_types)
3228 final_warning_records = new (final_warning_record);
3229 final_warning_records->type_warnings = vNULL;
3230 final_warning_records->type_warnings.safe_grow_cleared (odr_types.length ());
3231 free_polymorphic_call_targets_hash ();
3234 FOR_EACH_DEFINED_FUNCTION (n)
3236 bool update = false;
3237 if (!opt_for_fn (n->decl, flag_devirtualize))
3239 if (dump_file && n->indirect_calls)
3240 fprintf (dump_file, "\n\nProcesing function %s/%i\n",
3241 n->name (), n->order);
3242 for (e = n->indirect_calls; e; e = e->next_callee)
3243 if (e->indirect_info->polymorphic)
3245 struct cgraph_node *likely_target = NULL;
3249 if (final_warning_records)
3250 final_warning_records->dyn_count = e->count;
3252 vec <cgraph_node *>targets
3253 = possible_polymorphic_call_targets
3254 (e, &final, &cache_token, true);
3257 /* Trigger warnings by calculating non-speculative targets. */
3258 if (warn_suggest_final_methods || warn_suggest_final_types)
3259 possible_polymorphic_call_targets (e);
3262 dump_possible_polymorphic_call_targets
3267 /* See if the call can be devirtualized by means of ipa-prop's
3268 polymorphic call context propagation. If not, we can just
3269 forget about this call being polymorphic and avoid some heavy
3270 lifting in remove_unreachable_nodes that will otherwise try to
3271 keep all possible targets alive until inlining and in the inliner
3274 This may need to be revisited once we add further ways to use
3275 the may edges, but it is a resonable thing to do right now. */
3277 if ((e->indirect_info->param_index == -1
3278 || (!opt_for_fn (n->decl, flag_devirtualize_speculatively)
3279 && e->indirect_info->vptr_changed))
3280 && !flag_ltrans_devirtualize)
3282 e->indirect_info->polymorphic = false;
3285 fprintf (dump_file, "Dropping polymorphic call info;"
3286 " it can not be used by ipa-prop\n");
3289 if (!opt_for_fn (n->decl, flag_devirtualize_speculatively))
3292 if (!e->maybe_hot_p ())
3295 fprintf (dump_file, "Call is cold\n\n");
3302 fprintf (dump_file, "Call is already speculated\n\n");
3305 /* When dumping see if we agree with speculation. */
3309 if (bad_call_targets.contains (cache_token))
3312 fprintf (dump_file, "Target list is known to be useless\n\n");
3316 for (i = 0; i < targets.length (); i++)
3317 if (likely_target_p (targets[i]))
3321 likely_target = NULL;
3323 fprintf (dump_file, "More than one likely target\n\n");
3327 likely_target = targets[i];
3331 bad_call_targets.add (cache_token);
3334 /* This is reached only when dumping; check if we agree or disagree
3335 with the speculation. */
3338 struct cgraph_edge *e2;
3339 struct ipa_ref *ref;
3340 e->speculative_call_info (e2, e, ref);
3341 if (e2->callee->ultimate_alias_target ()
3342 == likely_target->ultimate_alias_target ())
3344 fprintf (dump_file, "We agree with speculation\n\n");
3349 fprintf (dump_file, "We disagree with speculation\n\n");
3354 if (!likely_target->definition)
3357 fprintf (dump_file, "Target is not a definition\n\n");
3361 /* Do not introduce new references to external symbols. While we
3362 can handle these just well, it is common for programs to
3363 incorrectly with headers defining methods they are linked
3365 if (DECL_EXTERNAL (likely_target->decl))
3368 fprintf (dump_file, "Target is external\n\n");
3372 /* Don't use an implicitly-declared destructor (c++/58678). */
3373 struct cgraph_node *non_thunk_target
3374 = likely_target->function_symbol ();
3375 if (DECL_ARTIFICIAL (non_thunk_target->decl))
3378 fprintf (dump_file, "Target is artificial\n\n");
3382 if (likely_target->get_availability () <= AVAIL_INTERPOSABLE
3383 && likely_target->can_be_discarded_p ())
3386 fprintf (dump_file, "Target is overwritable\n\n");
3390 else if (dbg_cnt (devirt))
3392 if (dump_enabled_p ())
3394 location_t locus = gimple_location_safe (e->call_stmt);
3395 dump_printf_loc (MSG_OPTIMIZED_LOCATIONS, locus,
3396 "speculatively devirtualizing call in %s/%i to %s/%i\n",
3397 n->name (), n->order,
3398 likely_target->name (),
3399 likely_target->order);
3401 if (!likely_target->can_be_discarded_p ())
3404 alias = dyn_cast<cgraph_node *> (likely_target->noninterposable_alias ());
3406 likely_target = alias;
3411 (likely_target, e->count * 8 / 10, e->frequency * 8 / 10);
3415 inline_update_overall_summary (n);
3417 if (warn_suggest_final_methods || warn_suggest_final_types)
3419 if (warn_suggest_final_types)
3421 final_warning_records->type_warnings.qsort (type_warning_cmp);
3422 for (unsigned int i = 0;
3423 i < final_warning_records->type_warnings.length (); i++)
3424 if (final_warning_records->type_warnings[i].count)
3426 tree type = final_warning_records->type_warnings[i].type;
3427 int count = final_warning_records->type_warnings[i].count;
3429 = final_warning_records->type_warnings[i].dyn_count;
3432 warning_n (DECL_SOURCE_LOCATION (TYPE_NAME (type)),
3433 OPT_Wsuggest_final_types, count,
3434 "Declaring type %qD final "
3435 "would enable devirtualization of %i call",
3436 "Declaring type %qD final "
3437 "would enable devirtualization of %i calls",
3441 warning_n (DECL_SOURCE_LOCATION (TYPE_NAME (type)),
3442 OPT_Wsuggest_final_types, count,
3443 "Declaring type %qD final "
3444 "would enable devirtualization of %i call "
3445 "executed %lli times",
3446 "Declaring type %qD final "
3447 "would enable devirtualization of %i calls "
3448 "executed %lli times",
3455 if (warn_suggest_final_methods)
3457 vec<const decl_warn_count*> decl_warnings_vec = vNULL;
3459 final_warning_records->decl_warnings.traverse
3460 <vec<const decl_warn_count *> *, add_decl_warning> (&decl_warnings_vec);
3461 decl_warnings_vec.qsort (decl_warning_cmp);
3462 for (unsigned int i = 0; i < decl_warnings_vec.length (); i++)
3464 tree decl = decl_warnings_vec[i]->decl;
3465 int count = decl_warnings_vec[i]->count;
3466 long long dyn_count = decl_warnings_vec[i]->dyn_count;
3469 if (DECL_CXX_DESTRUCTOR_P (decl))
3470 warning_n (DECL_SOURCE_LOCATION (decl),
3471 OPT_Wsuggest_final_methods, count,
3472 "Declaring virtual destructor of %qD final "
3473 "would enable devirtualization of %i call",
3474 "Declaring virtual destructor of %qD final "
3475 "would enable devirtualization of %i calls",
3476 DECL_CONTEXT (decl), count);
3478 warning_n (DECL_SOURCE_LOCATION (decl),
3479 OPT_Wsuggest_final_methods, count,
3480 "Declaring method %qD final "
3481 "would enable devirtualization of %i call",
3482 "Declaring method %qD final "
3483 "would enable devirtualization of %i calls",
3485 else if (DECL_CXX_DESTRUCTOR_P (decl))
3486 warning_n (DECL_SOURCE_LOCATION (decl),
3487 OPT_Wsuggest_final_methods, count,
3488 "Declaring virtual destructor of %qD final "
3489 "would enable devirtualization of %i call "
3490 "executed %lli times",
3491 "Declaring virtual destructor of %qD final "
3492 "would enable devirtualization of %i calls "
3493 "executed %lli times",
3494 DECL_CONTEXT (decl), count, dyn_count);
3496 warning_n (DECL_SOURCE_LOCATION (decl),
3497 OPT_Wsuggest_final_methods, count,
3498 "Declaring method %qD final "
3499 "would enable devirtualization of %i call "
3500 "executed %lli times",
3501 "Declaring method %qD final "
3502 "would enable devirtualization of %i calls "
3503 "executed %lli times",
3504 decl, count, dyn_count);
3508 delete (final_warning_records);
3509 final_warning_records = 0;
3514 "%i polymorphic calls, %i devirtualized,"
3515 " %i speculatively devirtualized, %i cold\n"
3516 "%i have multiple targets, %i overwritable,"
3517 " %i already speculated (%i agree, %i disagree),"
3518 " %i external, %i not defined, %i artificial, %i infos dropped\n",
3519 npolymorphic, ndevirtualized, nconverted, ncold,
3520 nmultiple, noverwritable, nspeculated, nok, nwrong,
3521 nexternal, nnotdefined, nartificial, ndropped);
3522 return ndevirtualized || ndropped ? TODO_remove_functions : 0;
3527 const pass_data pass_data_ipa_devirt =
3529 IPA_PASS, /* type */
3530 "devirt", /* name */
3531 OPTGROUP_NONE, /* optinfo_flags */
3532 TV_IPA_DEVIRT, /* tv_id */
3533 0, /* properties_required */
3534 0, /* properties_provided */
3535 0, /* properties_destroyed */
3536 0, /* todo_flags_start */
3537 ( TODO_dump_symtab ), /* todo_flags_finish */
3540 class pass_ipa_devirt : public ipa_opt_pass_d
3543 pass_ipa_devirt (gcc::context *ctxt)
3544 : ipa_opt_pass_d (pass_data_ipa_devirt, ctxt,
3545 NULL, /* generate_summary */
3546 NULL, /* write_summary */
3547 NULL, /* read_summary */
3548 NULL, /* write_optimization_summary */
3549 NULL, /* read_optimization_summary */
3550 NULL, /* stmt_fixup */
3551 0, /* function_transform_todo_flags_start */
3552 NULL, /* function_transform */
3553 NULL) /* variable_transform */
3556 /* opt_pass methods: */
3557 virtual bool gate (function *)
3559 /* In LTO, always run the IPA passes and decide on function basis if the
3563 return (flag_devirtualize
3564 && (flag_devirtualize_speculatively
3565 || (warn_suggest_final_methods
3566 || warn_suggest_final_types))
3570 virtual unsigned int execute (function *) { return ipa_devirt (); }
3572 }; // class pass_ipa_devirt
3577 make_pass_ipa_devirt (gcc::context *ctxt)
3579 return new pass_ipa_devirt (ctxt);
3582 #include "gt-ipa-devirt.h"