Daily bump.
[official-gcc.git] / gcc / ipa-devirt.c
blobf0bc2501c273b6c3828456e568bcf310215ed3ab
1 /* Basic IPA utilities for type inheritance graph construction and
2 devirtualization.
3 Copyright (C) 2013-2017 Free Software Foundation, Inc.
4 Contributed by Jan Hubicka
6 This file is part of GCC.
8 GCC is free software; you can redistribute it and/or modify it under
9 the terms of the GNU General Public License as published by the Free
10 Software Foundation; either version 3, or (at your option) any later
11 version.
13 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
14 WARRANTY; without even the implied warranty of MERCHANTABILITY or
15 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
16 for more details.
18 You should have received a copy of the GNU General Public License
19 along with GCC; see the file COPYING3. If not see
20 <http://www.gnu.org/licenses/>. */
22 /* Brief vocabulary:
23 ODR = One Definition Rule
24 In short, the ODR states that:
25 1 In any translation unit, a template, type, function, or object can
26 have no more than one definition. Some of these can have any number
27 of declarations. A definition provides an instance.
28 2 In the entire program, an object or non-inline function cannot have
29 more than one definition; if an object or function is used, it must
30 have exactly one definition. You can declare an object or function
31 that is never used, in which case you don't have to provide
32 a definition. In no event can there be more than one definition.
33 3 Some things, like types, templates, and extern inline functions, can
34 be defined in more than one translation unit. For a given entity,
35 each definition must be the same. Non-extern objects and functions
36 in different translation units are different entities, even if their
37 names and types are the same.
39 OTR = OBJ_TYPE_REF
40 This is the Gimple representation of type information of a polymorphic call.
41 It contains two parameters:
42 otr_type is a type of class whose method is called.
43 otr_token is the index into virtual table where address is taken.
45 BINFO
46 This is the type inheritance information attached to each tree
47 RECORD_TYPE by the C++ frontend. It provides information about base
48 types and virtual tables.
50 BINFO is linked to the RECORD_TYPE by TYPE_BINFO.
51 BINFO also links to its type by BINFO_TYPE and to the virtual table by
52 BINFO_VTABLE.
54 Base types of a given type are enumerated by BINFO_BASE_BINFO
55 vector. Members of this vectors are not BINFOs associated
56 with a base type. Rather they are new copies of BINFOs
57 (base BINFOs). Their virtual tables may differ from
58 virtual table of the base type. Also BINFO_OFFSET specifies
59 offset of the base within the type.
61 In the case of single inheritance, the virtual table is shared
62 and BINFO_VTABLE of base BINFO is NULL. In the case of multiple
63 inheritance the individual virtual tables are pointer to by
64 BINFO_VTABLE of base binfos (that differs of BINFO_VTABLE of
65 binfo associated to the base type).
67 BINFO lookup for a given base type and offset can be done by
68 get_binfo_at_offset. It returns proper BINFO whose virtual table
69 can be used for lookup of virtual methods associated with the
70 base type.
72 token
73 This is an index of virtual method in virtual table associated
74 to the type defining it. Token can be looked up from OBJ_TYPE_REF
75 or from DECL_VINDEX of a given virtual table.
77 polymorphic (indirect) call
78 This is callgraph representation of virtual method call. Every
79 polymorphic call contains otr_type and otr_token taken from
80 original OBJ_TYPE_REF at callgraph construction time.
82 What we do here:
84 build_type_inheritance_graph triggers a construction of the type inheritance
85 graph.
87 We reconstruct it based on types of methods we see in the unit.
88 This means that the graph is not complete. Types with no methods are not
89 inserted into the graph. Also types without virtual methods are not
90 represented at all, though it may be easy to add this.
92 The inheritance graph is represented as follows:
94 Vertices are structures odr_type. Every odr_type may correspond
95 to one or more tree type nodes that are equivalent by ODR rule.
96 (the multiple type nodes appear only with linktime optimization)
98 Edges are represented by odr_type->base and odr_type->derived_types.
99 At the moment we do not track offsets of types for multiple inheritance.
100 Adding this is easy.
102 possible_polymorphic_call_targets returns, given an parameters found in
103 indirect polymorphic edge all possible polymorphic call targets of the call.
105 pass_ipa_devirt performs simple speculative devirtualization.
108 #include "config.h"
109 #include "system.h"
110 #include "coretypes.h"
111 #include "backend.h"
112 #include "rtl.h"
113 #include "tree.h"
114 #include "gimple.h"
115 #include "alloc-pool.h"
116 #include "tree-pass.h"
117 #include "cgraph.h"
118 #include "lto-streamer.h"
119 #include "fold-const.h"
120 #include "print-tree.h"
121 #include "calls.h"
122 #include "ipa-utils.h"
123 #include "gimple-fold.h"
124 #include "symbol-summary.h"
125 #include "tree-vrp.h"
126 #include "ipa-prop.h"
127 #include "ipa-fnsummary.h"
128 #include "demangle.h"
129 #include "dbgcnt.h"
130 #include "gimple-pretty-print.h"
131 #include "intl.h"
133 /* Hash based set of pairs of types. */
134 struct type_pair
136 tree first;
137 tree second;
140 template <>
141 struct default_hash_traits <type_pair>
142 : typed_noop_remove <type_pair>
144 GTY((skip)) typedef type_pair value_type;
145 GTY((skip)) typedef type_pair compare_type;
146 static hashval_t
147 hash (type_pair p)
149 return TYPE_UID (p.first) ^ TYPE_UID (p.second);
151 static bool
152 is_empty (type_pair p)
154 return p.first == NULL;
156 static bool
157 is_deleted (type_pair p ATTRIBUTE_UNUSED)
159 return false;
161 static bool
162 equal (const type_pair &a, const type_pair &b)
164 return a.first==b.first && a.second == b.second;
166 static void
167 mark_empty (type_pair &e)
169 e.first = NULL;
173 static bool odr_types_equivalent_p (tree, tree, bool, bool *,
174 hash_set<type_pair> *,
175 location_t, location_t);
177 static bool odr_violation_reported = false;
180 /* Pointer set of all call targets appearing in the cache. */
181 static hash_set<cgraph_node *> *cached_polymorphic_call_targets;
183 /* The node of type inheritance graph. For each type unique in
184 One Definition Rule (ODR) sense, we produce one node linking all
185 main variants of types equivalent to it, bases and derived types. */
187 struct GTY(()) odr_type_d
189 /* leader type. */
190 tree type;
191 /* All bases; built only for main variants of types. */
192 vec<odr_type> GTY((skip)) bases;
193 /* All derived types with virtual methods seen in unit;
194 built only for main variants of types. */
195 vec<odr_type> GTY((skip)) derived_types;
197 /* All equivalent types, if more than one. */
198 vec<tree, va_gc> *types;
199 /* Set of all equivalent types, if NON-NULL. */
200 hash_set<tree> * GTY((skip)) types_set;
202 /* Unique ID indexing the type in odr_types array. */
203 int id;
204 /* Is it in anonymous namespace? */
205 bool anonymous_namespace;
206 /* Do we know about all derivations of given type? */
207 bool all_derivations_known;
208 /* Did we report ODR violation here? */
209 bool odr_violated;
210 /* Set when virtual table without RTTI previaled table with. */
211 bool rtti_broken;
214 /* Return TRUE if all derived types of T are known and thus
215 we may consider the walk of derived type complete.
217 This is typically true only for final anonymous namespace types and types
218 defined within functions (that may be COMDAT and thus shared across units,
219 but with the same set of derived types). */
221 bool
222 type_all_derivations_known_p (const_tree t)
224 if (TYPE_FINAL_P (t))
225 return true;
226 if (flag_ltrans)
227 return false;
228 /* Non-C++ types may have IDENTIFIER_NODE here, do not crash. */
229 if (!TYPE_NAME (t) || TREE_CODE (TYPE_NAME (t)) != TYPE_DECL)
230 return true;
231 if (type_in_anonymous_namespace_p (t))
232 return true;
233 return (decl_function_context (TYPE_NAME (t)) != NULL);
236 /* Return TRUE if type's constructors are all visible. */
238 static bool
239 type_all_ctors_visible_p (tree t)
241 return !flag_ltrans
242 && symtab->state >= CONSTRUCTION
243 /* We can not always use type_all_derivations_known_p.
244 For function local types we must assume case where
245 the function is COMDAT and shared in between units.
247 TODO: These cases are quite easy to get, but we need
248 to keep track of C++ privatizing via -Wno-weak
249 as well as the IPA privatizing. */
250 && type_in_anonymous_namespace_p (t);
253 /* Return TRUE if type may have instance. */
255 static bool
256 type_possibly_instantiated_p (tree t)
258 tree vtable;
259 varpool_node *vnode;
261 /* TODO: Add abstract types here. */
262 if (!type_all_ctors_visible_p (t))
263 return true;
265 vtable = BINFO_VTABLE (TYPE_BINFO (t));
266 if (TREE_CODE (vtable) == POINTER_PLUS_EXPR)
267 vtable = TREE_OPERAND (TREE_OPERAND (vtable, 0), 0);
268 vnode = varpool_node::get (vtable);
269 return vnode && vnode->definition;
272 /* Hash used to unify ODR types based on their mangled name and for anonymous
273 namespace types. */
275 struct odr_name_hasher : pointer_hash <odr_type_d>
277 typedef union tree_node *compare_type;
278 static inline hashval_t hash (const odr_type_d *);
279 static inline bool equal (const odr_type_d *, const tree_node *);
280 static inline void remove (odr_type_d *);
283 /* Has used to unify ODR types based on their associated virtual table.
284 This hash is needed to keep -fno-lto-odr-type-merging to work and contains
285 only polymorphic types. Types with mangled names are inserted to both. */
287 struct odr_vtable_hasher:odr_name_hasher
289 static inline hashval_t hash (const odr_type_d *);
290 static inline bool equal (const odr_type_d *, const tree_node *);
293 /* Return type that was declared with T's name so that T is an
294 qualified variant of it. */
296 static inline tree
297 main_odr_variant (const_tree t)
299 if (TYPE_NAME (t) && TREE_CODE (TYPE_NAME (t)) == TYPE_DECL)
300 return TREE_TYPE (TYPE_NAME (t));
301 /* Unnamed types and non-C++ produced types can be compared by variants. */
302 else
303 return TYPE_MAIN_VARIANT (t);
306 static bool
307 can_be_name_hashed_p (tree t)
309 return (!in_lto_p || odr_type_p (t));
312 /* Hash type by its ODR name. */
314 static hashval_t
315 hash_odr_name (const_tree t)
317 gcc_checking_assert (main_odr_variant (t) == t);
319 /* If not in LTO, all main variants are unique, so we can do
320 pointer hash. */
321 if (!in_lto_p)
322 return htab_hash_pointer (t);
324 /* Anonymous types are unique. */
325 if (type_with_linkage_p (t) && type_in_anonymous_namespace_p (t))
326 return htab_hash_pointer (t);
328 gcc_checking_assert (TYPE_NAME (t)
329 && DECL_ASSEMBLER_NAME_SET_P (TYPE_NAME (t)));
330 return IDENTIFIER_HASH_VALUE (DECL_ASSEMBLER_NAME (TYPE_NAME (t)));
333 /* Return the computed hashcode for ODR_TYPE. */
335 inline hashval_t
336 odr_name_hasher::hash (const odr_type_d *odr_type)
338 return hash_odr_name (odr_type->type);
341 static bool
342 can_be_vtable_hashed_p (tree t)
344 /* vtable hashing can distinguish only main variants. */
345 if (TYPE_MAIN_VARIANT (t) != t)
346 return false;
347 /* Anonymous namespace types are always handled by name hash. */
348 if (type_with_linkage_p (t) && type_in_anonymous_namespace_p (t))
349 return false;
350 return (TREE_CODE (t) == RECORD_TYPE
351 && TYPE_BINFO (t) && BINFO_VTABLE (TYPE_BINFO (t)));
354 /* Hash type by assembler name of its vtable. */
356 static hashval_t
357 hash_odr_vtable (const_tree t)
359 tree v = BINFO_VTABLE (TYPE_BINFO (TYPE_MAIN_VARIANT (t)));
360 inchash::hash hstate;
362 gcc_checking_assert (in_lto_p);
363 gcc_checking_assert (!type_in_anonymous_namespace_p (t));
364 gcc_checking_assert (TREE_CODE (t) == RECORD_TYPE
365 && TYPE_BINFO (t) && BINFO_VTABLE (TYPE_BINFO (t)));
366 gcc_checking_assert (main_odr_variant (t) == t);
368 if (TREE_CODE (v) == POINTER_PLUS_EXPR)
370 add_expr (TREE_OPERAND (v, 1), hstate);
371 v = TREE_OPERAND (TREE_OPERAND (v, 0), 0);
374 hstate.add_wide_int (IDENTIFIER_HASH_VALUE (DECL_ASSEMBLER_NAME (v)));
375 return hstate.end ();
378 /* Return the computed hashcode for ODR_TYPE. */
380 inline hashval_t
381 odr_vtable_hasher::hash (const odr_type_d *odr_type)
383 return hash_odr_vtable (odr_type->type);
386 /* For languages with One Definition Rule, work out if
387 types are the same based on their name.
389 This is non-trivial for LTO where minor differences in
390 the type representation may have prevented type merging
391 to merge two copies of otherwise equivalent type.
393 Until we start streaming mangled type names, this function works
394 only for polymorphic types.
396 When STRICT is true, we compare types by their names for purposes of
397 ODR violation warnings. When strict is false, we consider variants
398 equivalent, because it is all that matters for devirtualization machinery.
401 bool
402 types_same_for_odr (const_tree type1, const_tree type2, bool strict)
404 gcc_checking_assert (TYPE_P (type1) && TYPE_P (type2));
406 type1 = main_odr_variant (type1);
407 type2 = main_odr_variant (type2);
408 if (!strict)
410 type1 = TYPE_MAIN_VARIANT (type1);
411 type2 = TYPE_MAIN_VARIANT (type2);
414 if (type1 == type2)
415 return true;
417 if (!in_lto_p)
418 return false;
420 /* Check for anonymous namespaces. Those have !TREE_PUBLIC
421 on the corresponding TYPE_STUB_DECL. */
422 if ((type_with_linkage_p (type1) && type_in_anonymous_namespace_p (type1))
423 || (type_with_linkage_p (type2) && type_in_anonymous_namespace_p (type2)))
424 return false;
427 /* ODR name of the type is set in DECL_ASSEMBLER_NAME of its TYPE_NAME.
429 Ideally we should never need types without ODR names here. It can however
430 happen in two cases:
432 1) for builtin types that are not streamed but rebuilt in lto/lto-lang.c
433 Here testing for equivalence is safe, since their MAIN_VARIANTs are
434 unique.
435 2) for units streamed with -fno-lto-odr-type-merging. Here we can't
436 establish precise ODR equivalency, but for correctness we care only
437 about equivalency on complete polymorphic types. For these we can
438 compare assembler names of their virtual tables. */
439 if ((!TYPE_NAME (type1) || !DECL_ASSEMBLER_NAME_SET_P (TYPE_NAME (type1)))
440 || (!TYPE_NAME (type2) || !DECL_ASSEMBLER_NAME_SET_P (TYPE_NAME (type2))))
442 /* See if types are obviously different (i.e. different codes
443 or polymorphic wrt non-polymorphic). This is not strictly correct
444 for ODR violating programs, but we can't do better without streaming
445 ODR names. */
446 if (TREE_CODE (type1) != TREE_CODE (type2))
447 return false;
448 if (TREE_CODE (type1) == RECORD_TYPE
449 && (TYPE_BINFO (type1) == NULL_TREE)
450 != (TYPE_BINFO (type2) == NULL_TREE))
451 return false;
452 if (TREE_CODE (type1) == RECORD_TYPE && TYPE_BINFO (type1)
453 && (BINFO_VTABLE (TYPE_BINFO (type1)) == NULL_TREE)
454 != (BINFO_VTABLE (TYPE_BINFO (type2)) == NULL_TREE))
455 return false;
457 /* At the moment we have no way to establish ODR equivalence at LTO
458 other than comparing virtual table pointers of polymorphic types.
459 Eventually we should start saving mangled names in TYPE_NAME.
460 Then this condition will become non-trivial. */
462 if (TREE_CODE (type1) == RECORD_TYPE
463 && TYPE_BINFO (type1) && TYPE_BINFO (type2)
464 && BINFO_VTABLE (TYPE_BINFO (type1))
465 && BINFO_VTABLE (TYPE_BINFO (type2)))
467 tree v1 = BINFO_VTABLE (TYPE_BINFO (type1));
468 tree v2 = BINFO_VTABLE (TYPE_BINFO (type2));
469 gcc_assert (TREE_CODE (v1) == POINTER_PLUS_EXPR
470 && TREE_CODE (v2) == POINTER_PLUS_EXPR);
471 return (operand_equal_p (TREE_OPERAND (v1, 1),
472 TREE_OPERAND (v2, 1), 0)
473 && DECL_ASSEMBLER_NAME
474 (TREE_OPERAND (TREE_OPERAND (v1, 0), 0))
475 == DECL_ASSEMBLER_NAME
476 (TREE_OPERAND (TREE_OPERAND (v2, 0), 0)));
478 gcc_unreachable ();
480 return (DECL_ASSEMBLER_NAME (TYPE_NAME (type1))
481 == DECL_ASSEMBLER_NAME (TYPE_NAME (type2)));
484 /* Return true if we can decide on ODR equivalency.
486 In non-LTO it is always decide, in LTO however it depends in the type has
487 ODR info attached.
489 When STRICT is false, compare main variants. */
491 bool
492 types_odr_comparable (tree t1, tree t2, bool strict)
494 return (!in_lto_p
495 || (strict ? (main_odr_variant (t1) == main_odr_variant (t2)
496 && main_odr_variant (t1))
497 : TYPE_MAIN_VARIANT (t1) == TYPE_MAIN_VARIANT (t2))
498 || (odr_type_p (t1) && odr_type_p (t2))
499 || (TREE_CODE (t1) == RECORD_TYPE && TREE_CODE (t2) == RECORD_TYPE
500 && TYPE_BINFO (t1) && TYPE_BINFO (t2)
501 && polymorphic_type_binfo_p (TYPE_BINFO (t1))
502 && polymorphic_type_binfo_p (TYPE_BINFO (t2))));
505 /* Return true if T1 and T2 are ODR equivalent. If ODR equivalency is not
506 known, be conservative and return false. */
508 bool
509 types_must_be_same_for_odr (tree t1, tree t2)
511 if (types_odr_comparable (t1, t2))
512 return types_same_for_odr (t1, t2);
513 else
514 return TYPE_MAIN_VARIANT (t1) == TYPE_MAIN_VARIANT (t2);
517 /* If T is compound type, return type it is based on. */
519 static tree
520 compound_type_base (const_tree t)
522 if (TREE_CODE (t) == ARRAY_TYPE
523 || POINTER_TYPE_P (t)
524 || TREE_CODE (t) == COMPLEX_TYPE
525 || VECTOR_TYPE_P (t))
526 return TREE_TYPE (t);
527 if (TREE_CODE (t) == METHOD_TYPE)
528 return TYPE_METHOD_BASETYPE (t);
529 if (TREE_CODE (t) == OFFSET_TYPE)
530 return TYPE_OFFSET_BASETYPE (t);
531 return NULL_TREE;
534 /* Return true if T is either ODR type or compound type based from it.
535 If the function return true, we know that T is a type originating from C++
536 source even at link-time. */
538 bool
539 odr_or_derived_type_p (const_tree t)
543 if (odr_type_p (t))
544 return true;
545 /* Function type is a tricky one. Basically we can consider it
546 ODR derived if return type or any of the parameters is.
547 We need to check all parameters because LTO streaming merges
548 common types (such as void) and they are not considered ODR then. */
549 if (TREE_CODE (t) == FUNCTION_TYPE)
551 if (TYPE_METHOD_BASETYPE (t))
552 t = TYPE_METHOD_BASETYPE (t);
553 else
555 if (TREE_TYPE (t) && odr_or_derived_type_p (TREE_TYPE (t)))
556 return true;
557 for (t = TYPE_ARG_TYPES (t); t; t = TREE_CHAIN (t))
558 if (odr_or_derived_type_p (TREE_VALUE (t)))
559 return true;
560 return false;
563 else
564 t = compound_type_base (t);
566 while (t);
567 return t;
570 /* Compare types T1 and T2 and return true if they are
571 equivalent. */
573 inline bool
574 odr_name_hasher::equal (const odr_type_d *o1, const tree_node *t2)
576 tree t1 = o1->type;
578 gcc_checking_assert (main_odr_variant (t2) == t2);
579 gcc_checking_assert (main_odr_variant (t1) == t1);
580 if (t1 == t2)
581 return true;
582 if (!in_lto_p)
583 return false;
584 /* Check for anonymous namespaces. Those have !TREE_PUBLIC
585 on the corresponding TYPE_STUB_DECL. */
586 if ((type_with_linkage_p (t1) && type_in_anonymous_namespace_p (t1))
587 || (type_with_linkage_p (t2) && type_in_anonymous_namespace_p (t2)))
588 return false;
589 gcc_checking_assert (DECL_ASSEMBLER_NAME (TYPE_NAME (t1)));
590 gcc_checking_assert (DECL_ASSEMBLER_NAME (TYPE_NAME (t2)));
591 return (DECL_ASSEMBLER_NAME (TYPE_NAME (t1))
592 == DECL_ASSEMBLER_NAME (TYPE_NAME (t2)));
595 /* Compare types T1 and T2 and return true if they are
596 equivalent. */
598 inline bool
599 odr_vtable_hasher::equal (const odr_type_d *o1, const tree_node *t2)
601 tree t1 = o1->type;
603 gcc_checking_assert (main_odr_variant (t2) == t2);
604 gcc_checking_assert (main_odr_variant (t1) == t1);
605 gcc_checking_assert (in_lto_p);
606 t1 = TYPE_MAIN_VARIANT (t1);
607 t2 = TYPE_MAIN_VARIANT (t2);
608 if (t1 == t2)
609 return true;
610 tree v1 = BINFO_VTABLE (TYPE_BINFO (t1));
611 tree v2 = BINFO_VTABLE (TYPE_BINFO (t2));
612 return (operand_equal_p (TREE_OPERAND (v1, 1),
613 TREE_OPERAND (v2, 1), 0)
614 && DECL_ASSEMBLER_NAME
615 (TREE_OPERAND (TREE_OPERAND (v1, 0), 0))
616 == DECL_ASSEMBLER_NAME
617 (TREE_OPERAND (TREE_OPERAND (v2, 0), 0)));
620 /* Free ODR type V. */
622 inline void
623 odr_name_hasher::remove (odr_type_d *v)
625 v->bases.release ();
626 v->derived_types.release ();
627 if (v->types_set)
628 delete v->types_set;
629 ggc_free (v);
632 /* ODR type hash used to look up ODR type based on tree type node. */
634 typedef hash_table<odr_name_hasher> odr_hash_type;
635 static odr_hash_type *odr_hash;
636 typedef hash_table<odr_vtable_hasher> odr_vtable_hash_type;
637 static odr_vtable_hash_type *odr_vtable_hash;
639 /* ODR types are also stored into ODR_TYPE vector to allow consistent
640 walking. Bases appear before derived types. Vector is garbage collected
641 so we won't end up visiting empty types. */
643 static GTY(()) vec <odr_type, va_gc> *odr_types_ptr;
644 #define odr_types (*odr_types_ptr)
646 /* Set TYPE_BINFO of TYPE and its variants to BINFO. */
647 void
648 set_type_binfo (tree type, tree binfo)
650 for (; type; type = TYPE_NEXT_VARIANT (type))
651 if (COMPLETE_TYPE_P (type))
652 TYPE_BINFO (type) = binfo;
653 else
654 gcc_assert (!TYPE_BINFO (type));
657 /* Compare T2 and T2 based on name or structure. */
659 static bool
660 odr_subtypes_equivalent_p (tree t1, tree t2,
661 hash_set<type_pair> *visited,
662 location_t loc1, location_t loc2)
665 /* This can happen in incomplete types that should be handled earlier. */
666 gcc_assert (t1 && t2);
668 t1 = main_odr_variant (t1);
669 t2 = main_odr_variant (t2);
670 if (t1 == t2)
671 return true;
673 /* Anonymous namespace types must match exactly. */
674 if ((type_with_linkage_p (t1) && type_in_anonymous_namespace_p (t1))
675 || (type_with_linkage_p (t2) && type_in_anonymous_namespace_p (t2)))
676 return false;
678 /* For ODR types be sure to compare their names.
679 To support -wno-odr-type-merging we allow one type to be non-ODR
680 and other ODR even though it is a violation. */
681 if (types_odr_comparable (t1, t2, true))
683 if (!types_same_for_odr (t1, t2, true))
684 return false;
685 /* Limit recursion: If subtypes are ODR types and we know
686 that they are same, be happy. */
687 if (!odr_type_p (t1) || !get_odr_type (t1, true)->odr_violated)
688 return true;
691 /* Component types, builtins and possibly violating ODR types
692 have to be compared structurally. */
693 if (TREE_CODE (t1) != TREE_CODE (t2))
694 return false;
695 if (AGGREGATE_TYPE_P (t1)
696 && (TYPE_NAME (t1) == NULL_TREE) != (TYPE_NAME (t2) == NULL_TREE))
697 return false;
699 type_pair pair={t1,t2};
700 if (TYPE_UID (t1) > TYPE_UID (t2))
702 pair.first = t2;
703 pair.second = t1;
705 if (visited->add (pair))
706 return true;
707 return odr_types_equivalent_p (t1, t2, false, NULL, visited, loc1, loc2);
710 /* Return true if DECL1 and DECL2 are identical methods. Consider
711 name equivalent to name.localalias.xyz. */
713 static bool
714 methods_equal_p (tree decl1, tree decl2)
716 if (DECL_ASSEMBLER_NAME (decl1) == DECL_ASSEMBLER_NAME (decl2))
717 return true;
718 const char sep = symbol_table::symbol_suffix_separator ();
720 const char *name1 = IDENTIFIER_POINTER (DECL_ASSEMBLER_NAME (decl1));
721 const char *ptr1 = strchr (name1, sep);
722 int len1 = ptr1 ? ptr1 - name1 : strlen (name1);
724 const char *name2 = IDENTIFIER_POINTER (DECL_ASSEMBLER_NAME (decl2));
725 const char *ptr2 = strchr (name2, sep);
726 int len2 = ptr2 ? ptr2 - name2 : strlen (name2);
728 if (len1 != len2)
729 return false;
730 return !strncmp (name1, name2, len1);
733 /* Compare two virtual tables, PREVAILING and VTABLE and output ODR
734 violation warnings. */
736 void
737 compare_virtual_tables (varpool_node *prevailing, varpool_node *vtable)
739 int n1, n2;
741 if (DECL_VIRTUAL_P (prevailing->decl) != DECL_VIRTUAL_P (vtable->decl))
743 odr_violation_reported = true;
744 if (DECL_VIRTUAL_P (prevailing->decl))
746 varpool_node *tmp = prevailing;
747 prevailing = vtable;
748 vtable = tmp;
750 if (warning_at (DECL_SOURCE_LOCATION
751 (TYPE_NAME (DECL_CONTEXT (vtable->decl))),
752 OPT_Wodr,
753 "virtual table of type %qD violates one definition rule",
754 DECL_CONTEXT (vtable->decl)))
755 inform (DECL_SOURCE_LOCATION (prevailing->decl),
756 "variable of same assembler name as the virtual table is "
757 "defined in another translation unit");
758 return;
760 if (!prevailing->definition || !vtable->definition)
761 return;
763 /* If we do not stream ODR type info, do not bother to do useful compare. */
764 if (!TYPE_BINFO (DECL_CONTEXT (vtable->decl))
765 || !polymorphic_type_binfo_p (TYPE_BINFO (DECL_CONTEXT (vtable->decl))))
766 return;
768 odr_type class_type = get_odr_type (DECL_CONTEXT (vtable->decl), true);
770 if (class_type->odr_violated)
771 return;
773 for (n1 = 0, n2 = 0; true; n1++, n2++)
775 struct ipa_ref *ref1, *ref2;
776 bool end1, end2;
778 end1 = !prevailing->iterate_reference (n1, ref1);
779 end2 = !vtable->iterate_reference (n2, ref2);
781 /* !DECL_VIRTUAL_P means RTTI entry;
782 We warn when RTTI is lost because non-RTTI previals; we silently
783 accept the other case. */
784 while (!end2
785 && (end1
786 || (methods_equal_p (ref1->referred->decl,
787 ref2->referred->decl)
788 && TREE_CODE (ref1->referred->decl) == FUNCTION_DECL))
789 && TREE_CODE (ref2->referred->decl) != FUNCTION_DECL)
791 if (!class_type->rtti_broken
792 && warning_at (DECL_SOURCE_LOCATION
793 (TYPE_NAME (DECL_CONTEXT (vtable->decl))),
794 OPT_Wodr,
795 "virtual table of type %qD contains RTTI "
796 "information",
797 DECL_CONTEXT (vtable->decl)))
799 inform (DECL_SOURCE_LOCATION
800 (TYPE_NAME (DECL_CONTEXT (prevailing->decl))),
801 "but is prevailed by one without from other translation "
802 "unit");
803 inform (DECL_SOURCE_LOCATION
804 (TYPE_NAME (DECL_CONTEXT (prevailing->decl))),
805 "RTTI will not work on this type");
806 class_type->rtti_broken = true;
808 n2++;
809 end2 = !vtable->iterate_reference (n2, ref2);
811 while (!end1
812 && (end2
813 || (methods_equal_p (ref2->referred->decl, ref1->referred->decl)
814 && TREE_CODE (ref2->referred->decl) == FUNCTION_DECL))
815 && TREE_CODE (ref1->referred->decl) != FUNCTION_DECL)
817 n1++;
818 end1 = !prevailing->iterate_reference (n1, ref1);
821 /* Finished? */
822 if (end1 && end2)
824 /* Extra paranoia; compare the sizes. We do not have information
825 about virtual inheritance offsets, so just be sure that these
826 match.
827 Do this as very last check so the not very informative error
828 is not output too often. */
829 if (DECL_SIZE (prevailing->decl) != DECL_SIZE (vtable->decl))
831 class_type->odr_violated = true;
832 if (warning_at (DECL_SOURCE_LOCATION
833 (TYPE_NAME (DECL_CONTEXT (vtable->decl))),
834 OPT_Wodr,
835 "virtual table of type %qD violates "
836 "one definition rule ",
837 DECL_CONTEXT (vtable->decl)))
839 inform (DECL_SOURCE_LOCATION
840 (TYPE_NAME (DECL_CONTEXT (prevailing->decl))),
841 "the conflicting type defined in another translation "
842 "unit has virtual table of different size");
845 return;
848 if (!end1 && !end2)
850 if (methods_equal_p (ref1->referred->decl, ref2->referred->decl))
851 continue;
853 class_type->odr_violated = true;
855 /* If the loops above stopped on non-virtual pointer, we have
856 mismatch in RTTI information mangling. */
857 if (TREE_CODE (ref1->referred->decl) != FUNCTION_DECL
858 && TREE_CODE (ref2->referred->decl) != FUNCTION_DECL)
860 if (warning_at (DECL_SOURCE_LOCATION
861 (TYPE_NAME (DECL_CONTEXT (vtable->decl))),
862 OPT_Wodr,
863 "virtual table of type %qD violates "
864 "one definition rule ",
865 DECL_CONTEXT (vtable->decl)))
867 inform (DECL_SOURCE_LOCATION
868 (TYPE_NAME (DECL_CONTEXT (prevailing->decl))),
869 "the conflicting type defined in another translation "
870 "unit with different RTTI information");
872 return;
874 /* At this point both REF1 and REF2 points either to virtual table
875 or virtual method. If one points to virtual table and other to
876 method we can complain the same way as if one table was shorter
877 than other pointing out the extra method. */
878 if (TREE_CODE (ref1->referred->decl)
879 != TREE_CODE (ref2->referred->decl))
881 if (VAR_P (ref1->referred->decl))
882 end1 = true;
883 else if (VAR_P (ref2->referred->decl))
884 end2 = true;
888 class_type->odr_violated = true;
890 /* Complain about size mismatch. Either we have too many virutal
891 functions or too many virtual table pointers. */
892 if (end1 || end2)
894 if (end1)
896 varpool_node *tmp = prevailing;
897 prevailing = vtable;
898 vtable = tmp;
899 ref1 = ref2;
901 if (warning_at (DECL_SOURCE_LOCATION
902 (TYPE_NAME (DECL_CONTEXT (vtable->decl))),
903 OPT_Wodr,
904 "virtual table of type %qD violates "
905 "one definition rule",
906 DECL_CONTEXT (vtable->decl)))
908 if (TREE_CODE (ref1->referring->decl) == FUNCTION_DECL)
910 inform (DECL_SOURCE_LOCATION
911 (TYPE_NAME (DECL_CONTEXT (prevailing->decl))),
912 "the conflicting type defined in another translation "
913 "unit");
914 inform (DECL_SOURCE_LOCATION
915 (TYPE_NAME (DECL_CONTEXT (ref1->referring->decl))),
916 "contains additional virtual method %qD",
917 ref1->referred->decl);
919 else
921 inform (DECL_SOURCE_LOCATION
922 (TYPE_NAME (DECL_CONTEXT (prevailing->decl))),
923 "the conflicting type defined in another translation "
924 "unit has virtual table with more entries");
927 return;
930 /* And in the last case we have either mistmatch in between two virtual
931 methods or two virtual table pointers. */
932 if (warning_at (DECL_SOURCE_LOCATION
933 (TYPE_NAME (DECL_CONTEXT (vtable->decl))), OPT_Wodr,
934 "virtual table of type %qD violates "
935 "one definition rule ",
936 DECL_CONTEXT (vtable->decl)))
938 if (TREE_CODE (ref1->referred->decl) == FUNCTION_DECL)
940 inform (DECL_SOURCE_LOCATION
941 (TYPE_NAME (DECL_CONTEXT (prevailing->decl))),
942 "the conflicting type defined in another translation "
943 "unit");
944 gcc_assert (TREE_CODE (ref2->referred->decl)
945 == FUNCTION_DECL);
946 inform (DECL_SOURCE_LOCATION
947 (ref1->referred->ultimate_alias_target ()->decl),
948 "virtual method %qD",
949 ref1->referred->ultimate_alias_target ()->decl);
950 inform (DECL_SOURCE_LOCATION
951 (ref2->referred->ultimate_alias_target ()->decl),
952 "ought to match virtual method %qD but does not",
953 ref2->referred->ultimate_alias_target ()->decl);
955 else
956 inform (DECL_SOURCE_LOCATION
957 (TYPE_NAME (DECL_CONTEXT (prevailing->decl))),
958 "the conflicting type defined in another translation "
959 "unit has virtual table with different contents");
960 return;
965 /* Output ODR violation warning about T1 and T2 with REASON.
966 Display location of ST1 and ST2 if REASON speaks about field or
967 method of the type.
968 If WARN is false, do nothing. Set WARNED if warning was indeed
969 output. */
971 void
972 warn_odr (tree t1, tree t2, tree st1, tree st2,
973 bool warn, bool *warned, const char *reason)
975 tree decl2 = TYPE_NAME (t2);
976 if (warned)
977 *warned = false;
979 if (!warn || !TYPE_NAME(t1))
980 return;
982 /* ODR warnings are output druing LTO streaming; we must apply location
983 cache for potential warnings to be output correctly. */
984 if (lto_location_cache::current_cache)
985 lto_location_cache::current_cache->apply_location_cache ();
987 if (!warning_at (DECL_SOURCE_LOCATION (TYPE_NAME (t1)), OPT_Wodr,
988 "type %qT violates the C++ One Definition Rule",
989 t1))
990 return;
991 if (!st1 && !st2)
993 /* For FIELD_DECL support also case where one of fields is
994 NULL - this is used when the structures have mismatching number of
995 elements. */
996 else if (!st1 || TREE_CODE (st1) == FIELD_DECL)
998 inform (DECL_SOURCE_LOCATION (decl2),
999 "a different type is defined in another translation unit");
1000 if (!st1)
1002 st1 = st2;
1003 st2 = NULL;
1005 inform (DECL_SOURCE_LOCATION (st1),
1006 "the first difference of corresponding definitions is field %qD",
1007 st1);
1008 if (st2)
1009 decl2 = st2;
1011 else if (TREE_CODE (st1) == FUNCTION_DECL)
1013 inform (DECL_SOURCE_LOCATION (decl2),
1014 "a different type is defined in another translation unit");
1015 inform (DECL_SOURCE_LOCATION (st1),
1016 "the first difference of corresponding definitions is method %qD",
1017 st1);
1018 decl2 = st2;
1020 else
1021 return;
1022 inform (DECL_SOURCE_LOCATION (decl2), reason);
1024 if (warned)
1025 *warned = true;
1028 /* Return ture if T1 and T2 are incompatible and we want to recusively
1029 dive into them from warn_type_mismatch to give sensible answer. */
1031 static bool
1032 type_mismatch_p (tree t1, tree t2)
1034 if (odr_or_derived_type_p (t1) && odr_or_derived_type_p (t2)
1035 && !odr_types_equivalent_p (t1, t2))
1036 return true;
1037 return !types_compatible_p (t1, t2);
1041 /* Types T1 and T2 was found to be incompatible in a context they can't
1042 (either used to declare a symbol of same assembler name or unified by
1043 ODR rule). We already output warning about this, but if possible, output
1044 extra information on how the types mismatch.
1046 This is hard to do in general. We basically handle the common cases.
1048 If LOC1 and LOC2 are meaningful locations, use it in the case the types
1049 themselves do no thave one.*/
1051 void
1052 warn_types_mismatch (tree t1, tree t2, location_t loc1, location_t loc2)
1054 /* Location of type is known only if it has TYPE_NAME and the name is
1055 TYPE_DECL. */
1056 location_t loc_t1 = TYPE_NAME (t1) && TREE_CODE (TYPE_NAME (t1)) == TYPE_DECL
1057 ? DECL_SOURCE_LOCATION (TYPE_NAME (t1))
1058 : UNKNOWN_LOCATION;
1059 location_t loc_t2 = TYPE_NAME (t2) && TREE_CODE (TYPE_NAME (t2)) == TYPE_DECL
1060 ? DECL_SOURCE_LOCATION (TYPE_NAME (t2))
1061 : UNKNOWN_LOCATION;
1062 bool loc_t2_useful = false;
1064 /* With LTO it is a common case that the location of both types match.
1065 See if T2 has a location that is different from T1. If so, we will
1066 inform user about the location.
1067 Do not consider the location passed to us in LOC1/LOC2 as those are
1068 already output. */
1069 if (loc_t2 > BUILTINS_LOCATION && loc_t2 != loc_t1)
1071 if (loc_t1 <= BUILTINS_LOCATION)
1072 loc_t2_useful = true;
1073 else
1075 expanded_location xloc1 = expand_location (loc_t1);
1076 expanded_location xloc2 = expand_location (loc_t2);
1078 if (strcmp (xloc1.file, xloc2.file)
1079 || xloc1.line != xloc2.line
1080 || xloc1.column != xloc2.column)
1081 loc_t2_useful = true;
1085 if (loc_t1 <= BUILTINS_LOCATION)
1086 loc_t1 = loc1;
1087 if (loc_t2 <= BUILTINS_LOCATION)
1088 loc_t2 = loc2;
1090 location_t loc = loc_t1 <= BUILTINS_LOCATION ? loc_t2 : loc_t1;
1092 /* It is a quite common bug to reference anonymous namespace type in
1093 non-anonymous namespace class. */
1094 if ((type_with_linkage_p (t1) && type_in_anonymous_namespace_p (t1))
1095 || (type_with_linkage_p (t2) && type_in_anonymous_namespace_p (t2)))
1097 if (type_with_linkage_p (t1) && !type_in_anonymous_namespace_p (t1))
1099 std::swap (t1, t2);
1100 std::swap (loc_t1, loc_t2);
1102 gcc_assert (TYPE_NAME (t1) && TYPE_NAME (t2)
1103 && TREE_CODE (TYPE_NAME (t1)) == TYPE_DECL
1104 && TREE_CODE (TYPE_NAME (t2)) == TYPE_DECL);
1105 /* Most of the time, the type names will match, do not be unnecesarily
1106 verbose. */
1107 if (IDENTIFIER_POINTER (DECL_NAME (TYPE_NAME (t1)))
1108 != IDENTIFIER_POINTER (DECL_NAME (TYPE_NAME (t2))))
1109 inform (loc_t1,
1110 "type %qT defined in anonymous namespace can not match "
1111 "type %qT across the translation unit boundary",
1112 t1, t2);
1113 else
1114 inform (loc_t1,
1115 "type %qT defined in anonymous namespace can not match "
1116 "across the translation unit boundary",
1117 t1);
1118 if (loc_t2_useful)
1119 inform (loc_t2,
1120 "the incompatible type defined in another translation unit");
1121 return;
1123 /* If types have mangled ODR names and they are different, it is most
1124 informative to output those.
1125 This also covers types defined in different namespaces. */
1126 if (TYPE_NAME (t1) && TYPE_NAME (t2)
1127 && TREE_CODE (TYPE_NAME (t1)) == TYPE_DECL
1128 && TREE_CODE (TYPE_NAME (t2)) == TYPE_DECL
1129 && DECL_ASSEMBLER_NAME_SET_P (TYPE_NAME (t1))
1130 && DECL_ASSEMBLER_NAME_SET_P (TYPE_NAME (t2))
1131 && DECL_ASSEMBLER_NAME (TYPE_NAME (t1))
1132 != DECL_ASSEMBLER_NAME (TYPE_NAME (t2)))
1134 char *name1 = xstrdup (cplus_demangle
1135 (IDENTIFIER_POINTER (DECL_ASSEMBLER_NAME (TYPE_NAME (t1))),
1136 DMGL_PARAMS | DMGL_ANSI | DMGL_TYPES));
1137 char *name2 = cplus_demangle
1138 (IDENTIFIER_POINTER (DECL_ASSEMBLER_NAME (TYPE_NAME (t2))),
1139 DMGL_PARAMS | DMGL_ANSI | DMGL_TYPES);
1140 if (name1 && name2 && strcmp (name1, name2))
1142 inform (loc_t1,
1143 "type name %qs should match type name %qs",
1144 name1, name2);
1145 if (loc_t2_useful)
1146 inform (loc_t2,
1147 "the incompatible type is defined here");
1148 free (name1);
1149 return;
1151 free (name1);
1153 /* A tricky case are compound types. Often they appear the same in source
1154 code and the mismatch is dragged in by type they are build from.
1155 Look for those differences in subtypes and try to be informative. In other
1156 cases just output nothing because the source code is probably different
1157 and in this case we already output a all necessary info. */
1158 if (!TYPE_NAME (t1) || !TYPE_NAME (t2))
1160 if (TREE_CODE (t1) == TREE_CODE (t2))
1162 if (TREE_CODE (t1) == ARRAY_TYPE
1163 && COMPLETE_TYPE_P (t1) && COMPLETE_TYPE_P (t2))
1165 tree i1 = TYPE_DOMAIN (t1);
1166 tree i2 = TYPE_DOMAIN (t2);
1168 if (i1 && i2
1169 && TYPE_MAX_VALUE (i1)
1170 && TYPE_MAX_VALUE (i2)
1171 && !operand_equal_p (TYPE_MAX_VALUE (i1),
1172 TYPE_MAX_VALUE (i2), 0))
1174 inform (loc,
1175 "array types have different bounds");
1176 return;
1179 if ((POINTER_TYPE_P (t1) || TREE_CODE (t1) == ARRAY_TYPE)
1180 && type_mismatch_p (TREE_TYPE (t1), TREE_TYPE (t2)))
1181 warn_types_mismatch (TREE_TYPE (t1), TREE_TYPE (t2), loc_t1, loc_t2);
1182 else if (TREE_CODE (t1) == METHOD_TYPE
1183 || TREE_CODE (t1) == FUNCTION_TYPE)
1185 tree parms1 = NULL, parms2 = NULL;
1186 int count = 1;
1188 if (type_mismatch_p (TREE_TYPE (t1), TREE_TYPE (t2)))
1190 inform (loc, "return value type mismatch");
1191 warn_types_mismatch (TREE_TYPE (t1), TREE_TYPE (t2), loc_t1,
1192 loc_t2);
1193 return;
1195 if (prototype_p (t1) && prototype_p (t2))
1196 for (parms1 = TYPE_ARG_TYPES (t1), parms2 = TYPE_ARG_TYPES (t2);
1197 parms1 && parms2;
1198 parms1 = TREE_CHAIN (parms1), parms2 = TREE_CHAIN (parms2),
1199 count++)
1201 if (type_mismatch_p (TREE_VALUE (parms1), TREE_VALUE (parms2)))
1203 if (count == 1 && TREE_CODE (t1) == METHOD_TYPE)
1204 inform (loc,
1205 "implicit this pointer type mismatch");
1206 else
1207 inform (loc,
1208 "type mismatch in parameter %i",
1209 count - (TREE_CODE (t1) == METHOD_TYPE));
1210 warn_types_mismatch (TREE_VALUE (parms1),
1211 TREE_VALUE (parms2),
1212 loc_t1, loc_t2);
1213 return;
1216 if (parms1 || parms2)
1218 inform (loc,
1219 "types have different parameter counts");
1220 return;
1224 return;
1227 if (types_odr_comparable (t1, t2, true)
1228 && types_same_for_odr (t1, t2, true))
1229 inform (loc_t1,
1230 "type %qT itself violates the C++ One Definition Rule", t1);
1231 /* Prevent pointless warnings like "struct aa" should match "struct aa". */
1232 else if (TYPE_NAME (t1) == TYPE_NAME (t2)
1233 && TREE_CODE (t1) == TREE_CODE (t2) && !loc_t2_useful)
1234 return;
1235 else
1236 inform (loc_t1, "type %qT should match type %qT",
1237 t1, t2);
1238 if (loc_t2_useful)
1239 inform (loc_t2, "the incompatible type is defined here");
1242 /* Compare T1 and T2, report ODR violations if WARN is true and set
1243 WARNED to true if anything is reported. Return true if types match.
1244 If true is returned, the types are also compatible in the sense of
1245 gimple_canonical_types_compatible_p.
1246 If LOC1 and LOC2 is not UNKNOWN_LOCATION it may be used to output a warning
1247 about the type if the type itself do not have location. */
1249 static bool
1250 odr_types_equivalent_p (tree t1, tree t2, bool warn, bool *warned,
1251 hash_set<type_pair> *visited,
1252 location_t loc1, location_t loc2)
1254 /* Check first for the obvious case of pointer identity. */
1255 if (t1 == t2)
1256 return true;
1257 gcc_assert (!type_with_linkage_p (t1) || !type_in_anonymous_namespace_p (t1));
1258 gcc_assert (!type_with_linkage_p (t2) || !type_in_anonymous_namespace_p (t2));
1260 /* Can't be the same type if the types don't have the same code. */
1261 if (TREE_CODE (t1) != TREE_CODE (t2))
1263 warn_odr (t1, t2, NULL, NULL, warn, warned,
1264 G_("a different type is defined in another translation unit"));
1265 return false;
1268 if (TYPE_QUALS (t1) != TYPE_QUALS (t2))
1270 warn_odr (t1, t2, NULL, NULL, warn, warned,
1271 G_("a type with different qualifiers is defined in another "
1272 "translation unit"));
1273 return false;
1276 if ((type_with_linkage_p (t1) && type_in_anonymous_namespace_p (t1))
1277 || (type_with_linkage_p (t2) && type_in_anonymous_namespace_p (t2)))
1279 /* We can not trip this when comparing ODR types, only when trying to
1280 match different ODR derivations from different declarations.
1281 So WARN should be always false. */
1282 gcc_assert (!warn);
1283 return false;
1286 if (comp_type_attributes (t1, t2) != 1)
1288 warn_odr (t1, t2, NULL, NULL, warn, warned,
1289 G_("a type with different attributes "
1290 "is defined in another translation unit"));
1291 return false;
1294 if (TREE_CODE (t1) == ENUMERAL_TYPE
1295 && TYPE_VALUES (t1) && TYPE_VALUES (t2))
1297 tree v1, v2;
1298 for (v1 = TYPE_VALUES (t1), v2 = TYPE_VALUES (t2);
1299 v1 && v2 ; v1 = TREE_CHAIN (v1), v2 = TREE_CHAIN (v2))
1301 if (TREE_PURPOSE (v1) != TREE_PURPOSE (v2))
1303 warn_odr (t1, t2, NULL, NULL, warn, warned,
1304 G_("an enum with different value name"
1305 " is defined in another translation unit"));
1306 return false;
1308 if (TREE_VALUE (v1) != TREE_VALUE (v2)
1309 && !operand_equal_p (DECL_INITIAL (TREE_VALUE (v1)),
1310 DECL_INITIAL (TREE_VALUE (v2)), 0))
1312 warn_odr (t1, t2, NULL, NULL, warn, warned,
1313 G_("an enum with different values is defined"
1314 " in another translation unit"));
1315 return false;
1318 if (v1 || v2)
1320 warn_odr (t1, t2, NULL, NULL, warn, warned,
1321 G_("an enum with mismatching number of values "
1322 "is defined in another translation unit"));
1323 return false;
1327 /* Non-aggregate types can be handled cheaply. */
1328 if (INTEGRAL_TYPE_P (t1)
1329 || SCALAR_FLOAT_TYPE_P (t1)
1330 || FIXED_POINT_TYPE_P (t1)
1331 || TREE_CODE (t1) == VECTOR_TYPE
1332 || TREE_CODE (t1) == COMPLEX_TYPE
1333 || TREE_CODE (t1) == OFFSET_TYPE
1334 || POINTER_TYPE_P (t1))
1336 if (TYPE_PRECISION (t1) != TYPE_PRECISION (t2))
1338 warn_odr (t1, t2, NULL, NULL, warn, warned,
1339 G_("a type with different precision is defined "
1340 "in another translation unit"));
1341 return false;
1343 if (TYPE_UNSIGNED (t1) != TYPE_UNSIGNED (t2))
1345 warn_odr (t1, t2, NULL, NULL, warn, warned,
1346 G_("a type with different signedness is defined "
1347 "in another translation unit"));
1348 return false;
1351 if (TREE_CODE (t1) == INTEGER_TYPE
1352 && TYPE_STRING_FLAG (t1) != TYPE_STRING_FLAG (t2))
1354 /* char WRT uint_8? */
1355 warn_odr (t1, t2, NULL, NULL, warn, warned,
1356 G_("a different type is defined in another "
1357 "translation unit"));
1358 return false;
1361 /* For canonical type comparisons we do not want to build SCCs
1362 so we cannot compare pointed-to types. But we can, for now,
1363 require the same pointed-to type kind and match what
1364 useless_type_conversion_p would do. */
1365 if (POINTER_TYPE_P (t1))
1367 if (TYPE_ADDR_SPACE (TREE_TYPE (t1))
1368 != TYPE_ADDR_SPACE (TREE_TYPE (t2)))
1370 warn_odr (t1, t2, NULL, NULL, warn, warned,
1371 G_("it is defined as a pointer in different address "
1372 "space in another translation unit"));
1373 return false;
1376 if (!odr_subtypes_equivalent_p (TREE_TYPE (t1), TREE_TYPE (t2),
1377 visited, loc1, loc2))
1379 warn_odr (t1, t2, NULL, NULL, warn, warned,
1380 G_("it is defined as a pointer to different type "
1381 "in another translation unit"));
1382 if (warn && warned)
1383 warn_types_mismatch (TREE_TYPE (t1), TREE_TYPE (t2),
1384 loc1, loc2);
1385 return false;
1389 if ((TREE_CODE (t1) == VECTOR_TYPE || TREE_CODE (t1) == COMPLEX_TYPE)
1390 && !odr_subtypes_equivalent_p (TREE_TYPE (t1), TREE_TYPE (t2),
1391 visited, loc1, loc2))
1393 /* Probably specific enough. */
1394 warn_odr (t1, t2, NULL, NULL, warn, warned,
1395 G_("a different type is defined "
1396 "in another translation unit"));
1397 if (warn && warned)
1398 warn_types_mismatch (TREE_TYPE (t1), TREE_TYPE (t2), loc1, loc2);
1399 return false;
1402 /* Do type-specific comparisons. */
1403 else switch (TREE_CODE (t1))
1405 case ARRAY_TYPE:
1407 /* Array types are the same if the element types are the same and
1408 the number of elements are the same. */
1409 if (!odr_subtypes_equivalent_p (TREE_TYPE (t1), TREE_TYPE (t2),
1410 visited, loc1, loc2))
1412 warn_odr (t1, t2, NULL, NULL, warn, warned,
1413 G_("a different type is defined in another "
1414 "translation unit"));
1415 if (warn && warned)
1416 warn_types_mismatch (TREE_TYPE (t1), TREE_TYPE (t2), loc1, loc2);
1418 gcc_assert (TYPE_STRING_FLAG (t1) == TYPE_STRING_FLAG (t2));
1419 gcc_assert (TYPE_NONALIASED_COMPONENT (t1)
1420 == TYPE_NONALIASED_COMPONENT (t2));
1422 tree i1 = TYPE_DOMAIN (t1);
1423 tree i2 = TYPE_DOMAIN (t2);
1425 /* For an incomplete external array, the type domain can be
1426 NULL_TREE. Check this condition also. */
1427 if (i1 == NULL_TREE || i2 == NULL_TREE)
1428 return true;
1430 tree min1 = TYPE_MIN_VALUE (i1);
1431 tree min2 = TYPE_MIN_VALUE (i2);
1432 tree max1 = TYPE_MAX_VALUE (i1);
1433 tree max2 = TYPE_MAX_VALUE (i2);
1435 /* In C++, minimums should be always 0. */
1436 gcc_assert (min1 == min2);
1437 if (!operand_equal_p (max1, max2, 0))
1439 warn_odr (t1, t2, NULL, NULL, warn, warned,
1440 G_("an array of different size is defined "
1441 "in another translation unit"));
1442 return false;
1445 break;
1447 case METHOD_TYPE:
1448 case FUNCTION_TYPE:
1449 /* Function types are the same if the return type and arguments types
1450 are the same. */
1451 if (!odr_subtypes_equivalent_p (TREE_TYPE (t1), TREE_TYPE (t2),
1452 visited, loc1, loc2))
1454 warn_odr (t1, t2, NULL, NULL, warn, warned,
1455 G_("has different return value "
1456 "in another translation unit"));
1457 if (warn && warned)
1458 warn_types_mismatch (TREE_TYPE (t1), TREE_TYPE (t2), loc1, loc2);
1459 return false;
1462 if (TYPE_ARG_TYPES (t1) == TYPE_ARG_TYPES (t2)
1463 || !prototype_p (t1) || !prototype_p (t2))
1464 return true;
1465 else
1467 tree parms1, parms2;
1469 for (parms1 = TYPE_ARG_TYPES (t1), parms2 = TYPE_ARG_TYPES (t2);
1470 parms1 && parms2;
1471 parms1 = TREE_CHAIN (parms1), parms2 = TREE_CHAIN (parms2))
1473 if (!odr_subtypes_equivalent_p
1474 (TREE_VALUE (parms1), TREE_VALUE (parms2), visited,
1475 loc1, loc2))
1477 warn_odr (t1, t2, NULL, NULL, warn, warned,
1478 G_("has different parameters in another "
1479 "translation unit"));
1480 if (warn && warned)
1481 warn_types_mismatch (TREE_VALUE (parms1),
1482 TREE_VALUE (parms2), loc1, loc2);
1483 return false;
1487 if (parms1 || parms2)
1489 warn_odr (t1, t2, NULL, NULL, warn, warned,
1490 G_("has different parameters "
1491 "in another translation unit"));
1492 return false;
1495 return true;
1498 case RECORD_TYPE:
1499 case UNION_TYPE:
1500 case QUAL_UNION_TYPE:
1502 tree f1, f2;
1504 /* For aggregate types, all the fields must be the same. */
1505 if (COMPLETE_TYPE_P (t1) && COMPLETE_TYPE_P (t2))
1507 if (TYPE_BINFO (t1) && TYPE_BINFO (t2)
1508 && polymorphic_type_binfo_p (TYPE_BINFO (t1))
1509 != polymorphic_type_binfo_p (TYPE_BINFO (t2)))
1511 if (polymorphic_type_binfo_p (TYPE_BINFO (t1)))
1512 warn_odr (t1, t2, NULL, NULL, warn, warned,
1513 G_("a type defined in another translation unit "
1514 "is not polymorphic"));
1515 else
1516 warn_odr (t1, t2, NULL, NULL, warn, warned,
1517 G_("a type defined in another translation unit "
1518 "is polymorphic"));
1519 return false;
1521 for (f1 = TYPE_FIELDS (t1), f2 = TYPE_FIELDS (t2);
1522 f1 || f2;
1523 f1 = TREE_CHAIN (f1), f2 = TREE_CHAIN (f2))
1525 /* Skip non-fields. */
1526 while (f1 && TREE_CODE (f1) != FIELD_DECL)
1527 f1 = TREE_CHAIN (f1);
1528 while (f2 && TREE_CODE (f2) != FIELD_DECL)
1529 f2 = TREE_CHAIN (f2);
1530 if (!f1 || !f2)
1531 break;
1532 if (DECL_VIRTUAL_P (f1) != DECL_VIRTUAL_P (f2))
1534 warn_odr (t1, t2, NULL, NULL, warn, warned,
1535 G_("a type with different virtual table pointers"
1536 " is defined in another translation unit"));
1537 return false;
1539 if (DECL_ARTIFICIAL (f1) != DECL_ARTIFICIAL (f2))
1541 warn_odr (t1, t2, NULL, NULL, warn, warned,
1542 G_("a type with different bases is defined "
1543 "in another translation unit"));
1544 return false;
1546 if (DECL_NAME (f1) != DECL_NAME (f2)
1547 && !DECL_ARTIFICIAL (f1))
1549 warn_odr (t1, t2, f1, f2, warn, warned,
1550 G_("a field with different name is defined "
1551 "in another translation unit"));
1552 return false;
1554 if (!odr_subtypes_equivalent_p (TREE_TYPE (f1),
1555 TREE_TYPE (f2), visited,
1556 loc1, loc2))
1558 /* Do not warn about artificial fields and just go into
1559 generic field mismatch warning. */
1560 if (DECL_ARTIFICIAL (f1))
1561 break;
1563 warn_odr (t1, t2, f1, f2, warn, warned,
1564 G_("a field of same name but different type "
1565 "is defined in another translation unit"));
1566 if (warn && warned)
1567 warn_types_mismatch (TREE_TYPE (f1), TREE_TYPE (f2), loc1, loc2);
1568 return false;
1570 if (!gimple_compare_field_offset (f1, f2))
1572 /* Do not warn about artificial fields and just go into
1573 generic field mismatch warning. */
1574 if (DECL_ARTIFICIAL (f1))
1575 break;
1576 warn_odr (t1, t2, f1, f2, warn, warned,
1577 G_("fields have different layout "
1578 "in another translation unit"));
1579 return false;
1581 gcc_assert (DECL_NONADDRESSABLE_P (f1)
1582 == DECL_NONADDRESSABLE_P (f2));
1585 /* If one aggregate has more fields than the other, they
1586 are not the same. */
1587 if (f1 || f2)
1589 if ((f1 && DECL_VIRTUAL_P (f1)) || (f2 && DECL_VIRTUAL_P (f2)))
1590 warn_odr (t1, t2, NULL, NULL, warn, warned,
1591 G_("a type with different virtual table pointers"
1592 " is defined in another translation unit"));
1593 else if ((f1 && DECL_ARTIFICIAL (f1))
1594 || (f2 && DECL_ARTIFICIAL (f2)))
1595 warn_odr (t1, t2, NULL, NULL, warn, warned,
1596 G_("a type with different bases is defined "
1597 "in another translation unit"));
1598 else
1599 warn_odr (t1, t2, f1, f2, warn, warned,
1600 G_("a type with different number of fields "
1601 "is defined in another translation unit"));
1603 return false;
1605 if ((TYPE_MAIN_VARIANT (t1) == t1 || TYPE_MAIN_VARIANT (t2) == t2)
1606 && COMPLETE_TYPE_P (TYPE_MAIN_VARIANT (t1))
1607 && COMPLETE_TYPE_P (TYPE_MAIN_VARIANT (t2))
1608 && odr_type_p (TYPE_MAIN_VARIANT (t1))
1609 && odr_type_p (TYPE_MAIN_VARIANT (t2))
1610 && (TYPE_METHODS (TYPE_MAIN_VARIANT (t1))
1611 != TYPE_METHODS (TYPE_MAIN_VARIANT (t2))))
1613 /* Currently free_lang_data sets TYPE_METHODS to error_mark_node
1614 if it is non-NULL so this loop will never realy execute. */
1615 if (TYPE_METHODS (TYPE_MAIN_VARIANT (t1)) != error_mark_node
1616 && TYPE_METHODS (TYPE_MAIN_VARIANT (t2)) != error_mark_node)
1617 for (f1 = TYPE_METHODS (TYPE_MAIN_VARIANT (t1)),
1618 f2 = TYPE_METHODS (TYPE_MAIN_VARIANT (t2));
1619 f1 && f2 ; f1 = DECL_CHAIN (f1), f2 = DECL_CHAIN (f2))
1621 if (DECL_ASSEMBLER_NAME (f1) != DECL_ASSEMBLER_NAME (f2))
1623 warn_odr (t1, t2, f1, f2, warn, warned,
1624 G_("a different method of same type "
1625 "is defined in another "
1626 "translation unit"));
1627 return false;
1629 if (DECL_VIRTUAL_P (f1) != DECL_VIRTUAL_P (f2))
1631 warn_odr (t1, t2, f1, f2, warn, warned,
1632 G_("a definition that differs by virtual "
1633 "keyword in another translation unit"));
1634 return false;
1636 if (DECL_VINDEX (f1) != DECL_VINDEX (f2))
1638 warn_odr (t1, t2, f1, f2, warn, warned,
1639 G_("virtual table layout differs "
1640 "in another translation unit"));
1641 return false;
1643 if (odr_subtypes_equivalent_p (TREE_TYPE (f1),
1644 TREE_TYPE (f2), visited,
1645 loc1, loc2))
1647 warn_odr (t1, t2, f1, f2, warn, warned,
1648 G_("method with incompatible type is "
1649 "defined in another translation unit"));
1650 return false;
1653 if ((f1 == NULL) != (f2 == NULL))
1655 warn_odr (t1, t2, NULL, NULL, warn, warned,
1656 G_("a type with different number of methods "
1657 "is defined in another translation unit"));
1658 return false;
1662 break;
1664 case VOID_TYPE:
1665 case NULLPTR_TYPE:
1666 break;
1668 default:
1669 debug_tree (t1);
1670 gcc_unreachable ();
1673 /* Those are better to come last as they are utterly uninformative. */
1674 if (TYPE_SIZE (t1) && TYPE_SIZE (t2)
1675 && !operand_equal_p (TYPE_SIZE (t1), TYPE_SIZE (t2), 0))
1677 warn_odr (t1, t2, NULL, NULL, warn, warned,
1678 G_("a type with different size "
1679 "is defined in another translation unit"));
1680 return false;
1682 if (COMPLETE_TYPE_P (t1) && COMPLETE_TYPE_P (t2)
1683 && TYPE_ALIGN (t1) != TYPE_ALIGN (t2))
1685 warn_odr (t1, t2, NULL, NULL, warn, warned,
1686 G_("a type with different alignment "
1687 "is defined in another translation unit"));
1688 return false;
1690 gcc_assert (!TYPE_SIZE_UNIT (t1) || !TYPE_SIZE_UNIT (t2)
1691 || operand_equal_p (TYPE_SIZE_UNIT (t1),
1692 TYPE_SIZE_UNIT (t2), 0));
1693 return true;
1696 /* Return true if TYPE1 and TYPE2 are equivalent for One Definition Rule. */
1698 bool
1699 odr_types_equivalent_p (tree type1, tree type2)
1701 gcc_checking_assert (odr_or_derived_type_p (type1)
1702 && odr_or_derived_type_p (type2));
1704 hash_set<type_pair> visited;
1705 return odr_types_equivalent_p (type1, type2, false, NULL,
1706 &visited, UNKNOWN_LOCATION, UNKNOWN_LOCATION);
1709 /* TYPE is equivalent to VAL by ODR, but its tree representation differs
1710 from VAL->type. This may happen in LTO where tree merging did not merge
1711 all variants of the same type or due to ODR violation.
1713 Analyze and report ODR violations and add type to duplicate list.
1714 If TYPE is more specified than VAL->type, prevail VAL->type. Also if
1715 this is first time we see definition of a class return true so the
1716 base types are analyzed. */
1718 static bool
1719 add_type_duplicate (odr_type val, tree type)
1721 bool build_bases = false;
1722 bool prevail = false;
1723 bool odr_must_violate = false;
1725 if (!val->types_set)
1726 val->types_set = new hash_set<tree>;
1728 /* Chose polymorphic type as leader (this happens only in case of ODR
1729 violations. */
1730 if ((TREE_CODE (type) == RECORD_TYPE && TYPE_BINFO (type)
1731 && polymorphic_type_binfo_p (TYPE_BINFO (type)))
1732 && (TREE_CODE (val->type) != RECORD_TYPE || !TYPE_BINFO (val->type)
1733 || !polymorphic_type_binfo_p (TYPE_BINFO (val->type))))
1735 prevail = true;
1736 build_bases = true;
1738 /* Always prefer complete type to be the leader. */
1739 else if (!COMPLETE_TYPE_P (val->type) && COMPLETE_TYPE_P (type))
1741 prevail = true;
1742 build_bases = TYPE_BINFO (type);
1744 else if (COMPLETE_TYPE_P (val->type) && !COMPLETE_TYPE_P (type))
1746 else if (TREE_CODE (val->type) == ENUMERAL_TYPE
1747 && TREE_CODE (type) == ENUMERAL_TYPE
1748 && !TYPE_VALUES (val->type) && TYPE_VALUES (type))
1749 prevail = true;
1750 else if (TREE_CODE (val->type) == RECORD_TYPE
1751 && TREE_CODE (type) == RECORD_TYPE
1752 && TYPE_BINFO (type) && !TYPE_BINFO (val->type))
1754 gcc_assert (!val->bases.length ());
1755 build_bases = true;
1756 prevail = true;
1759 if (prevail)
1760 std::swap (val->type, type);
1762 val->types_set->add (type);
1764 /* If we now have a mangled name, be sure to record it to val->type
1765 so ODR hash can work. */
1767 if (can_be_name_hashed_p (type) && !can_be_name_hashed_p (val->type))
1768 SET_DECL_ASSEMBLER_NAME (TYPE_NAME (val->type),
1769 DECL_ASSEMBLER_NAME (TYPE_NAME (type)));
1771 bool merge = true;
1772 bool base_mismatch = false;
1773 unsigned int i;
1774 bool warned = false;
1775 hash_set<type_pair> visited;
1777 gcc_assert (in_lto_p);
1778 vec_safe_push (val->types, type);
1780 /* If both are class types, compare the bases. */
1781 if (COMPLETE_TYPE_P (type) && COMPLETE_TYPE_P (val->type)
1782 && TREE_CODE (val->type) == RECORD_TYPE
1783 && TREE_CODE (type) == RECORD_TYPE
1784 && TYPE_BINFO (val->type) && TYPE_BINFO (type))
1786 if (BINFO_N_BASE_BINFOS (TYPE_BINFO (type))
1787 != BINFO_N_BASE_BINFOS (TYPE_BINFO (val->type)))
1789 if (!flag_ltrans && !warned && !val->odr_violated)
1791 tree extra_base;
1792 warn_odr (type, val->type, NULL, NULL, !warned, &warned,
1793 "a type with the same name but different "
1794 "number of polymorphic bases is "
1795 "defined in another translation unit");
1796 if (warned)
1798 if (BINFO_N_BASE_BINFOS (TYPE_BINFO (type))
1799 > BINFO_N_BASE_BINFOS (TYPE_BINFO (val->type)))
1800 extra_base = BINFO_BASE_BINFO
1801 (TYPE_BINFO (type),
1802 BINFO_N_BASE_BINFOS (TYPE_BINFO (val->type)));
1803 else
1804 extra_base = BINFO_BASE_BINFO
1805 (TYPE_BINFO (val->type),
1806 BINFO_N_BASE_BINFOS (TYPE_BINFO (type)));
1807 tree extra_base_type = BINFO_TYPE (extra_base);
1808 inform (DECL_SOURCE_LOCATION (TYPE_NAME (extra_base_type)),
1809 "the extra base is defined here");
1812 base_mismatch = true;
1814 else
1815 for (i = 0; i < BINFO_N_BASE_BINFOS (TYPE_BINFO (type)); i++)
1817 tree base1 = BINFO_BASE_BINFO (TYPE_BINFO (type), i);
1818 tree base2 = BINFO_BASE_BINFO (TYPE_BINFO (val->type), i);
1819 tree type1 = BINFO_TYPE (base1);
1820 tree type2 = BINFO_TYPE (base2);
1822 if (types_odr_comparable (type1, type2))
1824 if (!types_same_for_odr (type1, type2))
1825 base_mismatch = true;
1827 else
1828 if (!odr_types_equivalent_p (type1, type2))
1829 base_mismatch = true;
1830 if (base_mismatch)
1832 if (!warned && !val->odr_violated)
1834 warn_odr (type, val->type, NULL, NULL,
1835 !warned, &warned,
1836 "a type with the same name but different base "
1837 "type is defined in another translation unit");
1838 if (warned)
1839 warn_types_mismatch (type1, type2,
1840 UNKNOWN_LOCATION, UNKNOWN_LOCATION);
1842 break;
1844 if (BINFO_OFFSET (base1) != BINFO_OFFSET (base2))
1846 base_mismatch = true;
1847 if (!warned && !val->odr_violated)
1848 warn_odr (type, val->type, NULL, NULL,
1849 !warned, &warned,
1850 "a type with the same name but different base "
1851 "layout is defined in another translation unit");
1852 break;
1854 /* One of bases is not of complete type. */
1855 if (!TYPE_BINFO (type1) != !TYPE_BINFO (type2))
1857 /* If we have a polymorphic type info specified for TYPE1
1858 but not for TYPE2 we possibly missed a base when recording
1859 VAL->type earlier.
1860 Be sure this does not happen. */
1861 if (TYPE_BINFO (type1)
1862 && polymorphic_type_binfo_p (TYPE_BINFO (type1))
1863 && !build_bases)
1864 odr_must_violate = true;
1865 break;
1867 /* One base is polymorphic and the other not.
1868 This ought to be diagnosed earlier, but do not ICE in the
1869 checking bellow. */
1870 else if (TYPE_BINFO (type1)
1871 && polymorphic_type_binfo_p (TYPE_BINFO (type1))
1872 != polymorphic_type_binfo_p (TYPE_BINFO (type2)))
1874 if (!warned && !val->odr_violated)
1875 warn_odr (type, val->type, NULL, NULL,
1876 !warned, &warned,
1877 "a base of the type is polymorphic only in one "
1878 "translation unit");
1879 base_mismatch = true;
1880 break;
1883 if (base_mismatch)
1885 merge = false;
1886 odr_violation_reported = true;
1887 val->odr_violated = true;
1889 if (symtab->dump_file)
1891 fprintf (symtab->dump_file, "ODR base violation\n");
1893 print_node (symtab->dump_file, "", val->type, 0);
1894 putc ('\n',symtab->dump_file);
1895 print_node (symtab->dump_file, "", type, 0);
1896 putc ('\n',symtab->dump_file);
1901 /* Next compare memory layout. */
1902 if (!odr_types_equivalent_p (val->type, type,
1903 !flag_ltrans && !val->odr_violated && !warned,
1904 &warned, &visited,
1905 DECL_SOURCE_LOCATION (TYPE_NAME (val->type)),
1906 DECL_SOURCE_LOCATION (TYPE_NAME (type))))
1908 merge = false;
1909 odr_violation_reported = true;
1910 val->odr_violated = true;
1912 gcc_assert (val->odr_violated || !odr_must_violate);
1913 /* Sanity check that all bases will be build same way again. */
1914 if (flag_checking
1915 && COMPLETE_TYPE_P (type) && COMPLETE_TYPE_P (val->type)
1916 && TREE_CODE (val->type) == RECORD_TYPE
1917 && TREE_CODE (type) == RECORD_TYPE
1918 && TYPE_BINFO (val->type) && TYPE_BINFO (type)
1919 && !val->odr_violated
1920 && !base_mismatch && val->bases.length ())
1922 unsigned int num_poly_bases = 0;
1923 unsigned int j;
1925 for (i = 0; i < BINFO_N_BASE_BINFOS (TYPE_BINFO (type)); i++)
1926 if (polymorphic_type_binfo_p (BINFO_BASE_BINFO
1927 (TYPE_BINFO (type), i)))
1928 num_poly_bases++;
1929 gcc_assert (num_poly_bases == val->bases.length ());
1930 for (j = 0, i = 0; i < BINFO_N_BASE_BINFOS (TYPE_BINFO (type));
1931 i++)
1932 if (polymorphic_type_binfo_p (BINFO_BASE_BINFO
1933 (TYPE_BINFO (type), i)))
1935 odr_type base = get_odr_type
1936 (BINFO_TYPE
1937 (BINFO_BASE_BINFO (TYPE_BINFO (type),
1938 i)),
1939 true);
1940 gcc_assert (val->bases[j] == base);
1941 j++;
1946 /* Regularize things a little. During LTO same types may come with
1947 different BINFOs. Either because their virtual table was
1948 not merged by tree merging and only later at decl merging or
1949 because one type comes with external vtable, while other
1950 with internal. We want to merge equivalent binfos to conserve
1951 memory and streaming overhead.
1953 The external vtables are more harmful: they contain references
1954 to external declarations of methods that may be defined in the
1955 merged LTO unit. For this reason we absolutely need to remove
1956 them and replace by internal variants. Not doing so will lead
1957 to incomplete answers from possible_polymorphic_call_targets.
1959 FIXME: disable for now; because ODR types are now build during
1960 streaming in, the variants do not need to be linked to the type,
1961 yet. We need to do the merging in cleanup pass to be implemented
1962 soon. */
1963 if (!flag_ltrans && merge
1964 && 0
1965 && TREE_CODE (val->type) == RECORD_TYPE
1966 && TREE_CODE (type) == RECORD_TYPE
1967 && TYPE_BINFO (val->type) && TYPE_BINFO (type)
1968 && TYPE_MAIN_VARIANT (type) == type
1969 && TYPE_MAIN_VARIANT (val->type) == val->type
1970 && BINFO_VTABLE (TYPE_BINFO (val->type))
1971 && BINFO_VTABLE (TYPE_BINFO (type)))
1973 tree master_binfo = TYPE_BINFO (val->type);
1974 tree v1 = BINFO_VTABLE (master_binfo);
1975 tree v2 = BINFO_VTABLE (TYPE_BINFO (type));
1977 if (TREE_CODE (v1) == POINTER_PLUS_EXPR)
1979 gcc_assert (TREE_CODE (v2) == POINTER_PLUS_EXPR
1980 && operand_equal_p (TREE_OPERAND (v1, 1),
1981 TREE_OPERAND (v2, 1), 0));
1982 v1 = TREE_OPERAND (TREE_OPERAND (v1, 0), 0);
1983 v2 = TREE_OPERAND (TREE_OPERAND (v2, 0), 0);
1985 gcc_assert (DECL_ASSEMBLER_NAME (v1)
1986 == DECL_ASSEMBLER_NAME (v2));
1988 if (DECL_EXTERNAL (v1) && !DECL_EXTERNAL (v2))
1990 unsigned int i;
1992 set_type_binfo (val->type, TYPE_BINFO (type));
1993 for (i = 0; i < val->types->length (); i++)
1995 if (TYPE_BINFO ((*val->types)[i])
1996 == master_binfo)
1997 set_type_binfo ((*val->types)[i], TYPE_BINFO (type));
1999 BINFO_TYPE (TYPE_BINFO (type)) = val->type;
2001 else
2002 set_type_binfo (type, master_binfo);
2004 return build_bases;
2007 /* Get ODR type hash entry for TYPE. If INSERT is true, create
2008 possibly new entry. */
2010 odr_type
2011 get_odr_type (tree type, bool insert)
2013 odr_type_d **slot = NULL;
2014 odr_type_d **vtable_slot = NULL;
2015 odr_type val = NULL;
2016 hashval_t hash;
2017 bool build_bases = false;
2018 bool insert_to_odr_array = false;
2019 int base_id = -1;
2021 type = main_odr_variant (type);
2023 gcc_checking_assert (can_be_name_hashed_p (type)
2024 || can_be_vtable_hashed_p (type));
2026 /* Lookup entry, first try name hash, fallback to vtable hash. */
2027 if (can_be_name_hashed_p (type))
2029 hash = hash_odr_name (type);
2030 slot = odr_hash->find_slot_with_hash (type, hash,
2031 insert ? INSERT : NO_INSERT);
2033 if ((!slot || !*slot) && in_lto_p && can_be_vtable_hashed_p (type))
2035 hash = hash_odr_vtable (type);
2036 vtable_slot = odr_vtable_hash->find_slot_with_hash (type, hash,
2037 insert ? INSERT : NO_INSERT);
2040 if (!slot && !vtable_slot)
2041 return NULL;
2043 /* See if we already have entry for type. */
2044 if ((slot && *slot) || (vtable_slot && *vtable_slot))
2046 if (slot && *slot)
2048 val = *slot;
2049 if (flag_checking
2050 && in_lto_p && can_be_vtable_hashed_p (type))
2052 hash = hash_odr_vtable (type);
2053 vtable_slot = odr_vtable_hash->find_slot_with_hash (type, hash,
2054 NO_INSERT);
2055 gcc_assert (!vtable_slot || *vtable_slot == *slot);
2056 vtable_slot = NULL;
2059 else if (*vtable_slot)
2060 val = *vtable_slot;
2062 if (val->type != type
2063 && (!val->types_set || !val->types_set->add (type)))
2065 gcc_assert (insert);
2066 /* We have type duplicate, but it may introduce vtable name or
2067 mangled name; be sure to keep hashes in sync. */
2068 if (in_lto_p && can_be_vtable_hashed_p (type)
2069 && (!vtable_slot || !*vtable_slot))
2071 if (!vtable_slot)
2073 hash = hash_odr_vtable (type);
2074 vtable_slot = odr_vtable_hash->find_slot_with_hash
2075 (type, hash, INSERT);
2076 gcc_checking_assert (!*vtable_slot || *vtable_slot == val);
2078 *vtable_slot = val;
2080 if (slot && !*slot)
2081 *slot = val;
2082 build_bases = add_type_duplicate (val, type);
2085 else
2087 val = ggc_cleared_alloc<odr_type_d> ();
2088 val->type = type;
2089 val->bases = vNULL;
2090 val->derived_types = vNULL;
2091 if (type_with_linkage_p (type))
2092 val->anonymous_namespace = type_in_anonymous_namespace_p (type);
2093 else
2094 val->anonymous_namespace = 0;
2095 build_bases = COMPLETE_TYPE_P (val->type);
2096 insert_to_odr_array = true;
2097 if (slot)
2098 *slot = val;
2099 if (vtable_slot)
2100 *vtable_slot = val;
2103 if (build_bases && TREE_CODE (type) == RECORD_TYPE && TYPE_BINFO (type)
2104 && type_with_linkage_p (type)
2105 && type == TYPE_MAIN_VARIANT (type))
2107 tree binfo = TYPE_BINFO (type);
2108 unsigned int i;
2110 gcc_assert (BINFO_TYPE (TYPE_BINFO (val->type)) == type);
2112 val->all_derivations_known = type_all_derivations_known_p (type);
2113 for (i = 0; i < BINFO_N_BASE_BINFOS (binfo); i++)
2114 /* For now record only polymorphic types. other are
2115 pointless for devirtualization and we can not precisely
2116 determine ODR equivalency of these during LTO. */
2117 if (polymorphic_type_binfo_p (BINFO_BASE_BINFO (binfo, i)))
2119 tree base_type= BINFO_TYPE (BINFO_BASE_BINFO (binfo, i));
2120 odr_type base = get_odr_type (base_type, true);
2121 gcc_assert (TYPE_MAIN_VARIANT (base_type) == base_type);
2122 base->derived_types.safe_push (val);
2123 val->bases.safe_push (base);
2124 if (base->id > base_id)
2125 base_id = base->id;
2128 /* Ensure that type always appears after bases. */
2129 if (insert_to_odr_array)
2131 if (odr_types_ptr)
2132 val->id = odr_types.length ();
2133 vec_safe_push (odr_types_ptr, val);
2135 else if (base_id > val->id)
2137 odr_types[val->id] = 0;
2138 /* Be sure we did not recorded any derived types; these may need
2139 renumbering too. */
2140 gcc_assert (val->derived_types.length() == 0);
2141 val->id = odr_types.length ();
2142 vec_safe_push (odr_types_ptr, val);
2144 return val;
2147 /* Add TYPE od ODR type hash. */
2149 void
2150 register_odr_type (tree type)
2152 if (!odr_hash)
2154 odr_hash = new odr_hash_type (23);
2155 if (in_lto_p)
2156 odr_vtable_hash = new odr_vtable_hash_type (23);
2158 /* Arrange things to be nicer and insert main variants first.
2159 ??? fundamental prerecorded types do not have mangled names; this
2160 makes it possible that non-ODR type is main_odr_variant of ODR type.
2161 Things may get smoother if LTO FE set mangled name of those types same
2162 way as C++ FE does. */
2163 if (odr_type_p (main_odr_variant (TYPE_MAIN_VARIANT (type)))
2164 && odr_type_p (TYPE_MAIN_VARIANT (type)))
2165 get_odr_type (TYPE_MAIN_VARIANT (type), true);
2166 if (TYPE_MAIN_VARIANT (type) != type && odr_type_p (main_odr_variant (type)))
2167 get_odr_type (type, true);
2170 /* Return true if type is known to have no derivations. */
2172 bool
2173 type_known_to_have_no_derivations_p (tree t)
2175 return (type_all_derivations_known_p (t)
2176 && (TYPE_FINAL_P (t)
2177 || (odr_hash
2178 && !get_odr_type (t, true)->derived_types.length())));
2181 /* Dump ODR type T and all its derived types. INDENT specifies indentation for
2182 recursive printing. */
2184 static void
2185 dump_odr_type (FILE *f, odr_type t, int indent=0)
2187 unsigned int i;
2188 fprintf (f, "%*s type %i: ", indent * 2, "", t->id);
2189 print_generic_expr (f, t->type, TDF_SLIM);
2190 fprintf (f, "%s", t->anonymous_namespace ? " (anonymous namespace)":"");
2191 fprintf (f, "%s\n", t->all_derivations_known ? " (derivations known)":"");
2192 if (TYPE_NAME (t->type))
2194 /*fprintf (f, "%*s defined at: %s:%i\n", indent * 2, "",
2195 DECL_SOURCE_FILE (TYPE_NAME (t->type)),
2196 DECL_SOURCE_LINE (TYPE_NAME (t->type)));*/
2197 if (DECL_ASSEMBLER_NAME_SET_P (TYPE_NAME (t->type)))
2198 fprintf (f, "%*s mangled name: %s\n", indent * 2, "",
2199 IDENTIFIER_POINTER
2200 (DECL_ASSEMBLER_NAME (TYPE_NAME (t->type))));
2202 if (t->bases.length ())
2204 fprintf (f, "%*s base odr type ids: ", indent * 2, "");
2205 for (i = 0; i < t->bases.length (); i++)
2206 fprintf (f, " %i", t->bases[i]->id);
2207 fprintf (f, "\n");
2209 if (t->derived_types.length ())
2211 fprintf (f, "%*s derived types:\n", indent * 2, "");
2212 for (i = 0; i < t->derived_types.length (); i++)
2213 dump_odr_type (f, t->derived_types[i], indent + 1);
2215 fprintf (f, "\n");
2218 /* Dump the type inheritance graph. */
2220 static void
2221 dump_type_inheritance_graph (FILE *f)
2223 unsigned int i;
2224 if (!odr_types_ptr)
2225 return;
2226 fprintf (f, "\n\nType inheritance graph:\n");
2227 for (i = 0; i < odr_types.length (); i++)
2229 if (odr_types[i] && odr_types[i]->bases.length () == 0)
2230 dump_odr_type (f, odr_types[i]);
2232 for (i = 0; i < odr_types.length (); i++)
2234 if (odr_types[i] && odr_types[i]->types && odr_types[i]->types->length ())
2236 unsigned int j;
2237 fprintf (f, "Duplicate tree types for odr type %i\n", i);
2238 print_node (f, "", odr_types[i]->type, 0);
2239 for (j = 0; j < odr_types[i]->types->length (); j++)
2241 tree t;
2242 fprintf (f, "duplicate #%i\n", j);
2243 print_node (f, "", (*odr_types[i]->types)[j], 0);
2244 t = (*odr_types[i]->types)[j];
2245 while (TYPE_P (t) && TYPE_CONTEXT (t))
2247 t = TYPE_CONTEXT (t);
2248 print_node (f, "", t, 0);
2250 putc ('\n',f);
2256 /* Initialize IPA devirt and build inheritance tree graph. */
2258 void
2259 build_type_inheritance_graph (void)
2261 struct symtab_node *n;
2262 FILE *inheritance_dump_file;
2263 dump_flags_t flags;
2265 if (odr_hash)
2266 return;
2267 timevar_push (TV_IPA_INHERITANCE);
2268 inheritance_dump_file = dump_begin (TDI_inheritance, &flags);
2269 odr_hash = new odr_hash_type (23);
2270 if (in_lto_p)
2271 odr_vtable_hash = new odr_vtable_hash_type (23);
2273 /* We reconstruct the graph starting of types of all methods seen in the
2274 unit. */
2275 FOR_EACH_SYMBOL (n)
2276 if (is_a <cgraph_node *> (n)
2277 && DECL_VIRTUAL_P (n->decl)
2278 && n->real_symbol_p ())
2279 get_odr_type (TYPE_METHOD_BASETYPE (TREE_TYPE (n->decl)), true);
2281 /* Look also for virtual tables of types that do not define any methods.
2283 We need it in a case where class B has virtual base of class A
2284 re-defining its virtual method and there is class C with no virtual
2285 methods with B as virtual base.
2287 Here we output B's virtual method in two variant - for non-virtual
2288 and virtual inheritance. B's virtual table has non-virtual version,
2289 while C's has virtual.
2291 For this reason we need to know about C in order to include both
2292 variants of B. More correctly, record_target_from_binfo should
2293 add both variants of the method when walking B, but we have no
2294 link in between them.
2296 We rely on fact that either the method is exported and thus we
2297 assume it is called externally or C is in anonymous namespace and
2298 thus we will see the vtable. */
2300 else if (is_a <varpool_node *> (n)
2301 && DECL_VIRTUAL_P (n->decl)
2302 && TREE_CODE (DECL_CONTEXT (n->decl)) == RECORD_TYPE
2303 && TYPE_BINFO (DECL_CONTEXT (n->decl))
2304 && polymorphic_type_binfo_p (TYPE_BINFO (DECL_CONTEXT (n->decl))))
2305 get_odr_type (TYPE_MAIN_VARIANT (DECL_CONTEXT (n->decl)), true);
2306 if (inheritance_dump_file)
2308 dump_type_inheritance_graph (inheritance_dump_file);
2309 dump_end (TDI_inheritance, inheritance_dump_file);
2311 timevar_pop (TV_IPA_INHERITANCE);
2314 /* Return true if N has reference from live virtual table
2315 (and thus can be a destination of polymorphic call).
2316 Be conservatively correct when callgraph is not built or
2317 if the method may be referred externally. */
2319 static bool
2320 referenced_from_vtable_p (struct cgraph_node *node)
2322 int i;
2323 struct ipa_ref *ref;
2324 bool found = false;
2326 if (node->externally_visible
2327 || DECL_EXTERNAL (node->decl)
2328 || node->used_from_other_partition)
2329 return true;
2331 /* Keep this test constant time.
2332 It is unlikely this can happen except for the case where speculative
2333 devirtualization introduced many speculative edges to this node.
2334 In this case the target is very likely alive anyway. */
2335 if (node->ref_list.referring.length () > 100)
2336 return true;
2338 /* We need references built. */
2339 if (symtab->state <= CONSTRUCTION)
2340 return true;
2342 for (i = 0; node->iterate_referring (i, ref); i++)
2343 if ((ref->use == IPA_REF_ALIAS
2344 && referenced_from_vtable_p (dyn_cast<cgraph_node *> (ref->referring)))
2345 || (ref->use == IPA_REF_ADDR
2346 && VAR_P (ref->referring->decl)
2347 && DECL_VIRTUAL_P (ref->referring->decl)))
2349 found = true;
2350 break;
2352 return found;
2355 /* Return if TARGET is cxa_pure_virtual. */
2357 static bool
2358 is_cxa_pure_virtual_p (tree target)
2360 return target && TREE_CODE (TREE_TYPE (target)) != METHOD_TYPE
2361 && DECL_NAME (target)
2362 && id_equal (DECL_NAME (target),
2363 "__cxa_pure_virtual");
2366 /* If TARGET has associated node, record it in the NODES array.
2367 CAN_REFER specify if program can refer to the target directly.
2368 if TARGET is unknown (NULL) or it can not be inserted (for example because
2369 its body was already removed and there is no way to refer to it), clear
2370 COMPLETEP. */
2372 static void
2373 maybe_record_node (vec <cgraph_node *> &nodes,
2374 tree target, hash_set<tree> *inserted,
2375 bool can_refer,
2376 bool *completep)
2378 struct cgraph_node *target_node, *alias_target;
2379 enum availability avail;
2380 bool pure_virtual = is_cxa_pure_virtual_p (target);
2382 /* __builtin_unreachable do not need to be added into
2383 list of targets; the runtime effect of calling them is undefined.
2384 Only "real" virtual methods should be accounted. */
2385 if (target && TREE_CODE (TREE_TYPE (target)) != METHOD_TYPE && !pure_virtual)
2386 return;
2388 if (!can_refer)
2390 /* The only case when method of anonymous namespace becomes unreferable
2391 is when we completely optimized it out. */
2392 if (flag_ltrans
2393 || !target
2394 || !type_in_anonymous_namespace_p (DECL_CONTEXT (target)))
2395 *completep = false;
2396 return;
2399 if (!target)
2400 return;
2402 target_node = cgraph_node::get (target);
2404 /* Prefer alias target over aliases, so we do not get confused by
2405 fake duplicates. */
2406 if (target_node)
2408 alias_target = target_node->ultimate_alias_target (&avail);
2409 if (target_node != alias_target
2410 && avail >= AVAIL_AVAILABLE
2411 && target_node->get_availability ())
2412 target_node = alias_target;
2415 /* Method can only be called by polymorphic call if any
2416 of vtables referring to it are alive.
2418 While this holds for non-anonymous functions, too, there are
2419 cases where we want to keep them in the list; for example
2420 inline functions with -fno-weak are static, but we still
2421 may devirtualize them when instance comes from other unit.
2422 The same holds for LTO.
2424 Currently we ignore these functions in speculative devirtualization.
2425 ??? Maybe it would make sense to be more aggressive for LTO even
2426 elsewhere. */
2427 if (!flag_ltrans
2428 && !pure_virtual
2429 && type_in_anonymous_namespace_p (DECL_CONTEXT (target))
2430 && (!target_node
2431 || !referenced_from_vtable_p (target_node)))
2433 /* See if TARGET is useful function we can deal with. */
2434 else if (target_node != NULL
2435 && (TREE_PUBLIC (target)
2436 || DECL_EXTERNAL (target)
2437 || target_node->definition)
2438 && target_node->real_symbol_p ())
2440 gcc_assert (!target_node->global.inlined_to);
2441 gcc_assert (target_node->real_symbol_p ());
2442 /* When sanitizing, do not assume that __cxa_pure_virtual is not called
2443 by valid program. */
2444 if (flag_sanitize & SANITIZE_UNREACHABLE)
2446 /* Only add pure virtual if it is the only possible target. This way
2447 we will preserve the diagnostics about pure virtual called in many
2448 cases without disabling optimization in other. */
2449 else if (pure_virtual)
2451 if (nodes.length ())
2452 return;
2454 /* If we found a real target, take away cxa_pure_virtual. */
2455 else if (!pure_virtual && nodes.length () == 1
2456 && is_cxa_pure_virtual_p (nodes[0]->decl))
2457 nodes.pop ();
2458 if (pure_virtual && nodes.length ())
2459 return;
2460 if (!inserted->add (target))
2462 cached_polymorphic_call_targets->add (target_node);
2463 nodes.safe_push (target_node);
2466 else if (!completep)
2468 /* We have definition of __cxa_pure_virtual that is not accessible (it is
2469 optimized out or partitioned to other unit) so we can not add it. When
2470 not sanitizing, there is nothing to do.
2471 Otherwise declare the list incomplete. */
2472 else if (pure_virtual)
2474 if (flag_sanitize & SANITIZE_UNREACHABLE)
2475 *completep = false;
2477 else if (flag_ltrans
2478 || !type_in_anonymous_namespace_p (DECL_CONTEXT (target)))
2479 *completep = false;
2482 /* See if BINFO's type matches OUTER_TYPE. If so, look up
2483 BINFO of subtype of OTR_TYPE at OFFSET and in that BINFO find
2484 method in vtable and insert method to NODES array
2485 or BASES_TO_CONSIDER if this array is non-NULL.
2486 Otherwise recurse to base BINFOs.
2487 This matches what get_binfo_at_offset does, but with offset
2488 being unknown.
2490 TYPE_BINFOS is a stack of BINFOS of types with defined
2491 virtual table seen on way from class type to BINFO.
2493 MATCHED_VTABLES tracks virtual tables we already did lookup
2494 for virtual function in. INSERTED tracks nodes we already
2495 inserted.
2497 ANONYMOUS is true if BINFO is part of anonymous namespace.
2499 Clear COMPLETEP when we hit unreferable target.
2502 static void
2503 record_target_from_binfo (vec <cgraph_node *> &nodes,
2504 vec <tree> *bases_to_consider,
2505 tree binfo,
2506 tree otr_type,
2507 vec <tree> &type_binfos,
2508 HOST_WIDE_INT otr_token,
2509 tree outer_type,
2510 HOST_WIDE_INT offset,
2511 hash_set<tree> *inserted,
2512 hash_set<tree> *matched_vtables,
2513 bool anonymous,
2514 bool *completep)
2516 tree type = BINFO_TYPE (binfo);
2517 int i;
2518 tree base_binfo;
2521 if (BINFO_VTABLE (binfo))
2522 type_binfos.safe_push (binfo);
2523 if (types_same_for_odr (type, outer_type))
2525 int i;
2526 tree type_binfo = NULL;
2528 /* Look up BINFO with virtual table. For normal types it is always last
2529 binfo on stack. */
2530 for (i = type_binfos.length () - 1; i >= 0; i--)
2531 if (BINFO_OFFSET (type_binfos[i]) == BINFO_OFFSET (binfo))
2533 type_binfo = type_binfos[i];
2534 break;
2536 if (BINFO_VTABLE (binfo))
2537 type_binfos.pop ();
2538 /* If this is duplicated BINFO for base shared by virtual inheritance,
2539 we may not have its associated vtable. This is not a problem, since
2540 we will walk it on the other path. */
2541 if (!type_binfo)
2542 return;
2543 tree inner_binfo = get_binfo_at_offset (type_binfo,
2544 offset, otr_type);
2545 if (!inner_binfo)
2547 gcc_assert (odr_violation_reported);
2548 return;
2550 /* For types in anonymous namespace first check if the respective vtable
2551 is alive. If not, we know the type can't be called. */
2552 if (!flag_ltrans && anonymous)
2554 tree vtable = BINFO_VTABLE (inner_binfo);
2555 varpool_node *vnode;
2557 if (TREE_CODE (vtable) == POINTER_PLUS_EXPR)
2558 vtable = TREE_OPERAND (TREE_OPERAND (vtable, 0), 0);
2559 vnode = varpool_node::get (vtable);
2560 if (!vnode || !vnode->definition)
2561 return;
2563 gcc_assert (inner_binfo);
2564 if (bases_to_consider
2565 ? !matched_vtables->contains (BINFO_VTABLE (inner_binfo))
2566 : !matched_vtables->add (BINFO_VTABLE (inner_binfo)))
2568 bool can_refer;
2569 tree target = gimple_get_virt_method_for_binfo (otr_token,
2570 inner_binfo,
2571 &can_refer);
2572 if (!bases_to_consider)
2573 maybe_record_node (nodes, target, inserted, can_refer, completep);
2574 /* Destructors are never called via construction vtables. */
2575 else if (!target || !DECL_CXX_DESTRUCTOR_P (target))
2576 bases_to_consider->safe_push (target);
2578 return;
2581 /* Walk bases. */
2582 for (i = 0; BINFO_BASE_ITERATE (binfo, i, base_binfo); i++)
2583 /* Walking bases that have no virtual method is pointless exercise. */
2584 if (polymorphic_type_binfo_p (base_binfo))
2585 record_target_from_binfo (nodes, bases_to_consider, base_binfo, otr_type,
2586 type_binfos,
2587 otr_token, outer_type, offset, inserted,
2588 matched_vtables, anonymous, completep);
2589 if (BINFO_VTABLE (binfo))
2590 type_binfos.pop ();
2593 /* Look up virtual methods matching OTR_TYPE (with OFFSET and OTR_TOKEN)
2594 of TYPE, insert them to NODES, recurse into derived nodes.
2595 INSERTED is used to avoid duplicate insertions of methods into NODES.
2596 MATCHED_VTABLES are used to avoid duplicate walking vtables.
2597 Clear COMPLETEP if unreferable target is found.
2599 If CONSIDER_CONSTRUCTION is true, record to BASES_TO_CONSIDER
2600 all cases where BASE_SKIPPED is true (because the base is abstract
2601 class). */
2603 static void
2604 possible_polymorphic_call_targets_1 (vec <cgraph_node *> &nodes,
2605 hash_set<tree> *inserted,
2606 hash_set<tree> *matched_vtables,
2607 tree otr_type,
2608 odr_type type,
2609 HOST_WIDE_INT otr_token,
2610 tree outer_type,
2611 HOST_WIDE_INT offset,
2612 bool *completep,
2613 vec <tree> &bases_to_consider,
2614 bool consider_construction)
2616 tree binfo = TYPE_BINFO (type->type);
2617 unsigned int i;
2618 auto_vec <tree, 8> type_binfos;
2619 bool possibly_instantiated = type_possibly_instantiated_p (type->type);
2621 /* We may need to consider types w/o instances because of possible derived
2622 types using their methods either directly or via construction vtables.
2623 We are safe to skip them when all derivations are known, since we will
2624 handle them later.
2625 This is done by recording them to BASES_TO_CONSIDER array. */
2626 if (possibly_instantiated || consider_construction)
2628 record_target_from_binfo (nodes,
2629 (!possibly_instantiated
2630 && type_all_derivations_known_p (type->type))
2631 ? &bases_to_consider : NULL,
2632 binfo, otr_type, type_binfos, otr_token,
2633 outer_type, offset,
2634 inserted, matched_vtables,
2635 type->anonymous_namespace, completep);
2637 for (i = 0; i < type->derived_types.length (); i++)
2638 possible_polymorphic_call_targets_1 (nodes, inserted,
2639 matched_vtables,
2640 otr_type,
2641 type->derived_types[i],
2642 otr_token, outer_type, offset, completep,
2643 bases_to_consider, consider_construction);
2646 /* Cache of queries for polymorphic call targets.
2648 Enumerating all call targets may get expensive when there are many
2649 polymorphic calls in the program, so we memoize all the previous
2650 queries and avoid duplicated work. */
2652 struct polymorphic_call_target_d
2654 HOST_WIDE_INT otr_token;
2655 ipa_polymorphic_call_context context;
2656 odr_type type;
2657 vec <cgraph_node *> targets;
2658 tree decl_warning;
2659 int type_warning;
2660 bool complete;
2661 bool speculative;
2664 /* Polymorphic call target cache helpers. */
2666 struct polymorphic_call_target_hasher
2667 : pointer_hash <polymorphic_call_target_d>
2669 static inline hashval_t hash (const polymorphic_call_target_d *);
2670 static inline bool equal (const polymorphic_call_target_d *,
2671 const polymorphic_call_target_d *);
2672 static inline void remove (polymorphic_call_target_d *);
2675 /* Return the computed hashcode for ODR_QUERY. */
2677 inline hashval_t
2678 polymorphic_call_target_hasher::hash (const polymorphic_call_target_d *odr_query)
2680 inchash::hash hstate (odr_query->otr_token);
2682 hstate.add_wide_int (odr_query->type->id);
2683 hstate.merge_hash (TYPE_UID (odr_query->context.outer_type));
2684 hstate.add_wide_int (odr_query->context.offset);
2686 if (odr_query->context.speculative_outer_type)
2688 hstate.merge_hash (TYPE_UID (odr_query->context.speculative_outer_type));
2689 hstate.add_wide_int (odr_query->context.speculative_offset);
2691 hstate.add_flag (odr_query->speculative);
2692 hstate.add_flag (odr_query->context.maybe_in_construction);
2693 hstate.add_flag (odr_query->context.maybe_derived_type);
2694 hstate.add_flag (odr_query->context.speculative_maybe_derived_type);
2695 hstate.commit_flag ();
2696 return hstate.end ();
2699 /* Compare cache entries T1 and T2. */
2701 inline bool
2702 polymorphic_call_target_hasher::equal (const polymorphic_call_target_d *t1,
2703 const polymorphic_call_target_d *t2)
2705 return (t1->type == t2->type && t1->otr_token == t2->otr_token
2706 && t1->speculative == t2->speculative
2707 && t1->context.offset == t2->context.offset
2708 && t1->context.speculative_offset == t2->context.speculative_offset
2709 && t1->context.outer_type == t2->context.outer_type
2710 && t1->context.speculative_outer_type == t2->context.speculative_outer_type
2711 && t1->context.maybe_in_construction
2712 == t2->context.maybe_in_construction
2713 && t1->context.maybe_derived_type == t2->context.maybe_derived_type
2714 && (t1->context.speculative_maybe_derived_type
2715 == t2->context.speculative_maybe_derived_type));
2718 /* Remove entry in polymorphic call target cache hash. */
2720 inline void
2721 polymorphic_call_target_hasher::remove (polymorphic_call_target_d *v)
2723 v->targets.release ();
2724 free (v);
2727 /* Polymorphic call target query cache. */
2729 typedef hash_table<polymorphic_call_target_hasher>
2730 polymorphic_call_target_hash_type;
2731 static polymorphic_call_target_hash_type *polymorphic_call_target_hash;
2733 /* Destroy polymorphic call target query cache. */
2735 static void
2736 free_polymorphic_call_targets_hash ()
2738 if (cached_polymorphic_call_targets)
2740 delete polymorphic_call_target_hash;
2741 polymorphic_call_target_hash = NULL;
2742 delete cached_polymorphic_call_targets;
2743 cached_polymorphic_call_targets = NULL;
2747 /* When virtual function is removed, we may need to flush the cache. */
2749 static void
2750 devirt_node_removal_hook (struct cgraph_node *n, void *d ATTRIBUTE_UNUSED)
2752 if (cached_polymorphic_call_targets
2753 && cached_polymorphic_call_targets->contains (n))
2754 free_polymorphic_call_targets_hash ();
2757 /* Look up base of BINFO that has virtual table VTABLE with OFFSET. */
2759 tree
2760 subbinfo_with_vtable_at_offset (tree binfo, unsigned HOST_WIDE_INT offset,
2761 tree vtable)
2763 tree v = BINFO_VTABLE (binfo);
2764 int i;
2765 tree base_binfo;
2766 unsigned HOST_WIDE_INT this_offset;
2768 if (v)
2770 if (!vtable_pointer_value_to_vtable (v, &v, &this_offset))
2771 gcc_unreachable ();
2773 if (offset == this_offset
2774 && DECL_ASSEMBLER_NAME (v) == DECL_ASSEMBLER_NAME (vtable))
2775 return binfo;
2778 for (i = 0; BINFO_BASE_ITERATE (binfo, i, base_binfo); i++)
2779 if (polymorphic_type_binfo_p (base_binfo))
2781 base_binfo = subbinfo_with_vtable_at_offset (base_binfo, offset, vtable);
2782 if (base_binfo)
2783 return base_binfo;
2785 return NULL;
2788 /* T is known constant value of virtual table pointer.
2789 Store virtual table to V and its offset to OFFSET.
2790 Return false if T does not look like virtual table reference. */
2792 bool
2793 vtable_pointer_value_to_vtable (const_tree t, tree *v,
2794 unsigned HOST_WIDE_INT *offset)
2796 /* We expect &MEM[(void *)&virtual_table + 16B].
2797 We obtain object's BINFO from the context of the virtual table.
2798 This one contains pointer to virtual table represented via
2799 POINTER_PLUS_EXPR. Verify that this pointer matches what
2800 we propagated through.
2802 In the case of virtual inheritance, the virtual tables may
2803 be nested, i.e. the offset may be different from 16 and we may
2804 need to dive into the type representation. */
2805 if (TREE_CODE (t) == ADDR_EXPR
2806 && TREE_CODE (TREE_OPERAND (t, 0)) == MEM_REF
2807 && TREE_CODE (TREE_OPERAND (TREE_OPERAND (t, 0), 0)) == ADDR_EXPR
2808 && TREE_CODE (TREE_OPERAND (TREE_OPERAND (t, 0), 1)) == INTEGER_CST
2809 && (TREE_CODE (TREE_OPERAND (TREE_OPERAND (TREE_OPERAND (t, 0), 0), 0))
2810 == VAR_DECL)
2811 && DECL_VIRTUAL_P (TREE_OPERAND (TREE_OPERAND
2812 (TREE_OPERAND (t, 0), 0), 0)))
2814 *v = TREE_OPERAND (TREE_OPERAND (TREE_OPERAND (t, 0), 0), 0);
2815 *offset = tree_to_uhwi (TREE_OPERAND (TREE_OPERAND (t, 0), 1));
2816 return true;
2819 /* Alternative representation, used by C++ frontend is POINTER_PLUS_EXPR.
2820 We need to handle it when T comes from static variable initializer or
2821 BINFO. */
2822 if (TREE_CODE (t) == POINTER_PLUS_EXPR)
2824 *offset = tree_to_uhwi (TREE_OPERAND (t, 1));
2825 t = TREE_OPERAND (t, 0);
2827 else
2828 *offset = 0;
2830 if (TREE_CODE (t) != ADDR_EXPR)
2831 return false;
2832 *v = TREE_OPERAND (t, 0);
2833 return true;
2836 /* T is known constant value of virtual table pointer. Return BINFO of the
2837 instance type. */
2839 tree
2840 vtable_pointer_value_to_binfo (const_tree t)
2842 tree vtable;
2843 unsigned HOST_WIDE_INT offset;
2845 if (!vtable_pointer_value_to_vtable (t, &vtable, &offset))
2846 return NULL_TREE;
2848 /* FIXME: for stores of construction vtables we return NULL,
2849 because we do not have BINFO for those. Eventually we should fix
2850 our representation to allow this case to be handled, too.
2851 In the case we see store of BINFO we however may assume
2852 that standard folding will be able to cope with it. */
2853 return subbinfo_with_vtable_at_offset (TYPE_BINFO (DECL_CONTEXT (vtable)),
2854 offset, vtable);
2857 /* Walk bases of OUTER_TYPE that contain OTR_TYPE at OFFSET.
2858 Look up their respective virtual methods for OTR_TOKEN and OTR_TYPE
2859 and insert them in NODES.
2861 MATCHED_VTABLES and INSERTED is used to avoid duplicated work. */
2863 static void
2864 record_targets_from_bases (tree otr_type,
2865 HOST_WIDE_INT otr_token,
2866 tree outer_type,
2867 HOST_WIDE_INT offset,
2868 vec <cgraph_node *> &nodes,
2869 hash_set<tree> *inserted,
2870 hash_set<tree> *matched_vtables,
2871 bool *completep)
2873 while (true)
2875 HOST_WIDE_INT pos, size;
2876 tree base_binfo;
2877 tree fld;
2879 if (types_same_for_odr (outer_type, otr_type))
2880 return;
2882 for (fld = TYPE_FIELDS (outer_type); fld; fld = DECL_CHAIN (fld))
2884 if (TREE_CODE (fld) != FIELD_DECL)
2885 continue;
2887 pos = int_bit_position (fld);
2888 size = tree_to_shwi (DECL_SIZE (fld));
2889 if (pos <= offset && (pos + size) > offset
2890 /* Do not get confused by zero sized bases. */
2891 && polymorphic_type_binfo_p (TYPE_BINFO (TREE_TYPE (fld))))
2892 break;
2894 /* Within a class type we should always find corresponding fields. */
2895 gcc_assert (fld && TREE_CODE (TREE_TYPE (fld)) == RECORD_TYPE);
2897 /* Nonbase types should have been stripped by outer_class_type. */
2898 gcc_assert (DECL_ARTIFICIAL (fld));
2900 outer_type = TREE_TYPE (fld);
2901 offset -= pos;
2903 base_binfo = get_binfo_at_offset (TYPE_BINFO (outer_type),
2904 offset, otr_type);
2905 if (!base_binfo)
2907 gcc_assert (odr_violation_reported);
2908 return;
2910 gcc_assert (base_binfo);
2911 if (!matched_vtables->add (BINFO_VTABLE (base_binfo)))
2913 bool can_refer;
2914 tree target = gimple_get_virt_method_for_binfo (otr_token,
2915 base_binfo,
2916 &can_refer);
2917 if (!target || ! DECL_CXX_DESTRUCTOR_P (target))
2918 maybe_record_node (nodes, target, inserted, can_refer, completep);
2919 matched_vtables->add (BINFO_VTABLE (base_binfo));
2924 /* When virtual table is removed, we may need to flush the cache. */
2926 static void
2927 devirt_variable_node_removal_hook (varpool_node *n,
2928 void *d ATTRIBUTE_UNUSED)
2930 if (cached_polymorphic_call_targets
2931 && DECL_VIRTUAL_P (n->decl)
2932 && type_in_anonymous_namespace_p (DECL_CONTEXT (n->decl)))
2933 free_polymorphic_call_targets_hash ();
2936 /* Record about how many calls would benefit from given type to be final. */
2938 struct odr_type_warn_count
2940 tree type;
2941 int count;
2942 profile_count dyn_count;
2945 /* Record about how many calls would benefit from given method to be final. */
2947 struct decl_warn_count
2949 tree decl;
2950 int count;
2951 profile_count dyn_count;
2954 /* Information about type and decl warnings. */
2956 struct final_warning_record
2958 profile_count dyn_count;
2959 auto_vec<odr_type_warn_count> type_warnings;
2960 hash_map<tree, decl_warn_count> decl_warnings;
2962 struct final_warning_record *final_warning_records;
2964 /* Return vector containing possible targets of polymorphic call of type
2965 OTR_TYPE calling method OTR_TOKEN within type of OTR_OUTER_TYPE and OFFSET.
2966 If INCLUDE_BASES is true, walk also base types of OUTER_TYPES containing
2967 OTR_TYPE and include their virtual method. This is useful for types
2968 possibly in construction or destruction where the virtual table may
2969 temporarily change to one of base types. INCLUDE_DERIVER_TYPES make
2970 us to walk the inheritance graph for all derivations.
2972 If COMPLETEP is non-NULL, store true if the list is complete.
2973 CACHE_TOKEN (if non-NULL) will get stored to an unique ID of entry
2974 in the target cache. If user needs to visit every target list
2975 just once, it can memoize them.
2977 If SPECULATIVE is set, the list will not contain targets that
2978 are not speculatively taken.
2980 Returned vector is placed into cache. It is NOT caller's responsibility
2981 to free it. The vector can be freed on cgraph_remove_node call if
2982 the particular node is a virtual function present in the cache. */
2984 vec <cgraph_node *>
2985 possible_polymorphic_call_targets (tree otr_type,
2986 HOST_WIDE_INT otr_token,
2987 ipa_polymorphic_call_context context,
2988 bool *completep,
2989 void **cache_token,
2990 bool speculative)
2992 static struct cgraph_node_hook_list *node_removal_hook_holder;
2993 vec <cgraph_node *> nodes = vNULL;
2994 auto_vec <tree, 8> bases_to_consider;
2995 odr_type type, outer_type;
2996 polymorphic_call_target_d key;
2997 polymorphic_call_target_d **slot;
2998 unsigned int i;
2999 tree binfo, target;
3000 bool complete;
3001 bool can_refer = false;
3002 bool skipped = false;
3004 otr_type = TYPE_MAIN_VARIANT (otr_type);
3006 /* If ODR is not initialized or the context is invalid, return empty
3007 incomplete list. */
3008 if (!odr_hash || context.invalid || !TYPE_BINFO (otr_type))
3010 if (completep)
3011 *completep = context.invalid;
3012 if (cache_token)
3013 *cache_token = NULL;
3014 return nodes;
3017 /* Do not bother to compute speculative info when user do not asks for it. */
3018 if (!speculative || !context.speculative_outer_type)
3019 context.clear_speculation ();
3021 type = get_odr_type (otr_type, true);
3023 /* Recording type variants would waste results cache. */
3024 gcc_assert (!context.outer_type
3025 || TYPE_MAIN_VARIANT (context.outer_type) == context.outer_type);
3027 /* Look up the outer class type we want to walk.
3028 If we fail to do so, the context is invalid. */
3029 if ((context.outer_type || context.speculative_outer_type)
3030 && !context.restrict_to_inner_class (otr_type))
3032 if (completep)
3033 *completep = true;
3034 if (cache_token)
3035 *cache_token = NULL;
3036 return nodes;
3038 gcc_assert (!context.invalid);
3040 /* Check that restrict_to_inner_class kept the main variant. */
3041 gcc_assert (!context.outer_type
3042 || TYPE_MAIN_VARIANT (context.outer_type) == context.outer_type);
3044 /* We canonicalize our query, so we do not need extra hashtable entries. */
3046 /* Without outer type, we have no use for offset. Just do the
3047 basic search from inner type. */
3048 if (!context.outer_type)
3049 context.clear_outer_type (otr_type);
3050 /* We need to update our hierarchy if the type does not exist. */
3051 outer_type = get_odr_type (context.outer_type, true);
3052 /* If the type is complete, there are no derivations. */
3053 if (TYPE_FINAL_P (outer_type->type))
3054 context.maybe_derived_type = false;
3056 /* Initialize query cache. */
3057 if (!cached_polymorphic_call_targets)
3059 cached_polymorphic_call_targets = new hash_set<cgraph_node *>;
3060 polymorphic_call_target_hash
3061 = new polymorphic_call_target_hash_type (23);
3062 if (!node_removal_hook_holder)
3064 node_removal_hook_holder =
3065 symtab->add_cgraph_removal_hook (&devirt_node_removal_hook, NULL);
3066 symtab->add_varpool_removal_hook (&devirt_variable_node_removal_hook,
3067 NULL);
3071 if (in_lto_p)
3073 if (context.outer_type != otr_type)
3074 context.outer_type
3075 = get_odr_type (context.outer_type, true)->type;
3076 if (context.speculative_outer_type)
3077 context.speculative_outer_type
3078 = get_odr_type (context.speculative_outer_type, true)->type;
3081 /* Look up cached answer. */
3082 key.type = type;
3083 key.otr_token = otr_token;
3084 key.speculative = speculative;
3085 key.context = context;
3086 slot = polymorphic_call_target_hash->find_slot (&key, INSERT);
3087 if (cache_token)
3088 *cache_token = (void *)*slot;
3089 if (*slot)
3091 if (completep)
3092 *completep = (*slot)->complete;
3093 if ((*slot)->type_warning && final_warning_records)
3095 final_warning_records->type_warnings[(*slot)->type_warning - 1].count++;
3096 if (!final_warning_records->type_warnings
3097 [(*slot)->type_warning - 1].dyn_count.initialized_p ())
3098 final_warning_records->type_warnings
3099 [(*slot)->type_warning - 1].dyn_count = profile_count::zero ();
3100 if (final_warning_records->dyn_count > 0)
3101 final_warning_records->type_warnings[(*slot)->type_warning - 1].dyn_count
3102 = final_warning_records->type_warnings[(*slot)->type_warning - 1].dyn_count
3103 + final_warning_records->dyn_count;
3105 if (!speculative && (*slot)->decl_warning && final_warning_records)
3107 struct decl_warn_count *c =
3108 final_warning_records->decl_warnings.get ((*slot)->decl_warning);
3109 c->count++;
3110 if (final_warning_records->dyn_count > 0)
3111 c->dyn_count += final_warning_records->dyn_count;
3113 return (*slot)->targets;
3116 complete = true;
3118 /* Do actual search. */
3119 timevar_push (TV_IPA_VIRTUAL_CALL);
3120 *slot = XCNEW (polymorphic_call_target_d);
3121 if (cache_token)
3122 *cache_token = (void *)*slot;
3123 (*slot)->type = type;
3124 (*slot)->otr_token = otr_token;
3125 (*slot)->context = context;
3126 (*slot)->speculative = speculative;
3128 hash_set<tree> inserted;
3129 hash_set<tree> matched_vtables;
3131 /* First insert targets we speculatively identified as likely. */
3132 if (context.speculative_outer_type)
3134 odr_type speculative_outer_type;
3135 bool speculation_complete = true;
3137 /* First insert target from type itself and check if it may have
3138 derived types. */
3139 speculative_outer_type = get_odr_type (context.speculative_outer_type, true);
3140 if (TYPE_FINAL_P (speculative_outer_type->type))
3141 context.speculative_maybe_derived_type = false;
3142 binfo = get_binfo_at_offset (TYPE_BINFO (speculative_outer_type->type),
3143 context.speculative_offset, otr_type);
3144 if (binfo)
3145 target = gimple_get_virt_method_for_binfo (otr_token, binfo,
3146 &can_refer);
3147 else
3148 target = NULL;
3150 /* In the case we get complete method, we don't need
3151 to walk derivations. */
3152 if (target && DECL_FINAL_P (target))
3153 context.speculative_maybe_derived_type = false;
3154 if (type_possibly_instantiated_p (speculative_outer_type->type))
3155 maybe_record_node (nodes, target, &inserted, can_refer, &speculation_complete);
3156 if (binfo)
3157 matched_vtables.add (BINFO_VTABLE (binfo));
3160 /* Next walk recursively all derived types. */
3161 if (context.speculative_maybe_derived_type)
3162 for (i = 0; i < speculative_outer_type->derived_types.length(); i++)
3163 possible_polymorphic_call_targets_1 (nodes, &inserted,
3164 &matched_vtables,
3165 otr_type,
3166 speculative_outer_type->derived_types[i],
3167 otr_token, speculative_outer_type->type,
3168 context.speculative_offset,
3169 &speculation_complete,
3170 bases_to_consider,
3171 false);
3174 if (!speculative || !nodes.length ())
3176 /* First see virtual method of type itself. */
3177 binfo = get_binfo_at_offset (TYPE_BINFO (outer_type->type),
3178 context.offset, otr_type);
3179 if (binfo)
3180 target = gimple_get_virt_method_for_binfo (otr_token, binfo,
3181 &can_refer);
3182 else
3184 gcc_assert (odr_violation_reported);
3185 target = NULL;
3188 /* Destructors are never called through construction virtual tables,
3189 because the type is always known. */
3190 if (target && DECL_CXX_DESTRUCTOR_P (target))
3191 context.maybe_in_construction = false;
3193 if (target)
3195 /* In the case we get complete method, we don't need
3196 to walk derivations. */
3197 if (DECL_FINAL_P (target))
3198 context.maybe_derived_type = false;
3201 /* If OUTER_TYPE is abstract, we know we are not seeing its instance. */
3202 if (type_possibly_instantiated_p (outer_type->type))
3203 maybe_record_node (nodes, target, &inserted, can_refer, &complete);
3204 else
3205 skipped = true;
3207 if (binfo)
3208 matched_vtables.add (BINFO_VTABLE (binfo));
3210 /* Next walk recursively all derived types. */
3211 if (context.maybe_derived_type)
3213 for (i = 0; i < outer_type->derived_types.length(); i++)
3214 possible_polymorphic_call_targets_1 (nodes, &inserted,
3215 &matched_vtables,
3216 otr_type,
3217 outer_type->derived_types[i],
3218 otr_token, outer_type->type,
3219 context.offset, &complete,
3220 bases_to_consider,
3221 context.maybe_in_construction);
3223 if (!outer_type->all_derivations_known)
3225 if (!speculative && final_warning_records
3226 && nodes.length () == 1
3227 && TREE_CODE (TREE_TYPE (nodes[0]->decl)) == METHOD_TYPE)
3229 if (complete
3230 && warn_suggest_final_types
3231 && !outer_type->derived_types.length ())
3233 if (outer_type->id >= (int)final_warning_records->type_warnings.length ())
3234 final_warning_records->type_warnings.safe_grow_cleared
3235 (odr_types.length ());
3236 final_warning_records->type_warnings[outer_type->id].count++;
3237 if (!final_warning_records->type_warnings
3238 [outer_type->id].dyn_count.initialized_p ())
3239 final_warning_records->type_warnings
3240 [outer_type->id].dyn_count = profile_count::zero ();
3241 final_warning_records->type_warnings[outer_type->id].dyn_count
3242 += final_warning_records->dyn_count;
3243 final_warning_records->type_warnings[outer_type->id].type
3244 = outer_type->type;
3245 (*slot)->type_warning = outer_type->id + 1;
3247 if (complete
3248 && warn_suggest_final_methods
3249 && types_same_for_odr (DECL_CONTEXT (nodes[0]->decl),
3250 outer_type->type))
3252 bool existed;
3253 struct decl_warn_count &c =
3254 final_warning_records->decl_warnings.get_or_insert
3255 (nodes[0]->decl, &existed);
3257 if (existed)
3259 c.count++;
3260 c.dyn_count += final_warning_records->dyn_count;
3262 else
3264 c.count = 1;
3265 c.dyn_count = final_warning_records->dyn_count;
3266 c.decl = nodes[0]->decl;
3268 (*slot)->decl_warning = nodes[0]->decl;
3271 complete = false;
3275 if (!speculative)
3277 /* Destructors are never called through construction virtual tables,
3278 because the type is always known. One of entries may be
3279 cxa_pure_virtual so look to at least two of them. */
3280 if (context.maybe_in_construction)
3281 for (i =0 ; i < MIN (nodes.length (), 2); i++)
3282 if (DECL_CXX_DESTRUCTOR_P (nodes[i]->decl))
3283 context.maybe_in_construction = false;
3284 if (context.maybe_in_construction)
3286 if (type != outer_type
3287 && (!skipped
3288 || (context.maybe_derived_type
3289 && !type_all_derivations_known_p (outer_type->type))))
3290 record_targets_from_bases (otr_type, otr_token, outer_type->type,
3291 context.offset, nodes, &inserted,
3292 &matched_vtables, &complete);
3293 if (skipped)
3294 maybe_record_node (nodes, target, &inserted, can_refer, &complete);
3295 for (i = 0; i < bases_to_consider.length(); i++)
3296 maybe_record_node (nodes, bases_to_consider[i], &inserted, can_refer, &complete);
3301 (*slot)->targets = nodes;
3302 (*slot)->complete = complete;
3303 if (completep)
3304 *completep = complete;
3306 timevar_pop (TV_IPA_VIRTUAL_CALL);
3307 return nodes;
3310 bool
3311 add_decl_warning (const tree &key ATTRIBUTE_UNUSED, const decl_warn_count &value,
3312 vec<const decl_warn_count*> *vec)
3314 vec->safe_push (&value);
3315 return true;
3318 /* Dump target list TARGETS into FILE. */
3320 static void
3321 dump_targets (FILE *f, vec <cgraph_node *> targets)
3323 unsigned int i;
3325 for (i = 0; i < targets.length (); i++)
3327 char *name = NULL;
3328 if (in_lto_p)
3329 name = cplus_demangle_v3 (targets[i]->asm_name (), 0);
3330 fprintf (f, " %s/%i", name ? name : targets[i]->name (),
3331 targets[i]->order);
3332 if (in_lto_p)
3333 free (name);
3334 if (!targets[i]->definition)
3335 fprintf (f, " (no definition%s)",
3336 DECL_DECLARED_INLINE_P (targets[i]->decl)
3337 ? " inline" : "");
3339 fprintf (f, "\n");
3342 /* Dump all possible targets of a polymorphic call. */
3344 void
3345 dump_possible_polymorphic_call_targets (FILE *f,
3346 tree otr_type,
3347 HOST_WIDE_INT otr_token,
3348 const ipa_polymorphic_call_context &ctx)
3350 vec <cgraph_node *> targets;
3351 bool final;
3352 odr_type type = get_odr_type (TYPE_MAIN_VARIANT (otr_type), false);
3353 unsigned int len;
3355 if (!type)
3356 return;
3357 targets = possible_polymorphic_call_targets (otr_type, otr_token,
3358 ctx,
3359 &final, NULL, false);
3360 fprintf (f, " Targets of polymorphic call of type %i:", type->id);
3361 print_generic_expr (f, type->type, TDF_SLIM);
3362 fprintf (f, " token %i\n", (int)otr_token);
3364 ctx.dump (f);
3366 fprintf (f, " %s%s%s%s\n ",
3367 final ? "This is a complete list." :
3368 "This is partial list; extra targets may be defined in other units.",
3369 ctx.maybe_in_construction ? " (base types included)" : "",
3370 ctx.maybe_derived_type ? " (derived types included)" : "",
3371 ctx.speculative_maybe_derived_type ? " (speculative derived types included)" : "");
3372 len = targets.length ();
3373 dump_targets (f, targets);
3375 targets = possible_polymorphic_call_targets (otr_type, otr_token,
3376 ctx,
3377 &final, NULL, true);
3378 if (targets.length () != len)
3380 fprintf (f, " Speculative targets:");
3381 dump_targets (f, targets);
3383 /* Ugly: during callgraph construction the target cache may get populated
3384 before all targets are found. While this is harmless (because all local
3385 types are discovered and only in those case we devirtualize fully and we
3386 don't do speculative devirtualization before IPA stage) it triggers
3387 assert here when dumping at that stage also populates the case with
3388 speculative targets. Quietly ignore this. */
3389 gcc_assert (symtab->state < IPA_SSA || targets.length () <= len);
3390 fprintf (f, "\n");
3394 /* Return true if N can be possibly target of a polymorphic call of
3395 OTR_TYPE/OTR_TOKEN. */
3397 bool
3398 possible_polymorphic_call_target_p (tree otr_type,
3399 HOST_WIDE_INT otr_token,
3400 const ipa_polymorphic_call_context &ctx,
3401 struct cgraph_node *n)
3403 vec <cgraph_node *> targets;
3404 unsigned int i;
3405 enum built_in_function fcode;
3406 bool final;
3408 if (TREE_CODE (TREE_TYPE (n->decl)) == FUNCTION_TYPE
3409 && ((fcode = DECL_FUNCTION_CODE (n->decl)) == BUILT_IN_UNREACHABLE
3410 || fcode == BUILT_IN_TRAP))
3411 return true;
3413 if (is_cxa_pure_virtual_p (n->decl))
3414 return true;
3416 if (!odr_hash)
3417 return true;
3418 targets = possible_polymorphic_call_targets (otr_type, otr_token, ctx, &final);
3419 for (i = 0; i < targets.length (); i++)
3420 if (n->semantically_equivalent_p (targets[i]))
3421 return true;
3423 /* At a moment we allow middle end to dig out new external declarations
3424 as a targets of polymorphic calls. */
3425 if (!final && !n->definition)
3426 return true;
3427 return false;
3432 /* Return true if N can be possibly target of a polymorphic call of
3433 OBJ_TYPE_REF expression REF in STMT. */
3435 bool
3436 possible_polymorphic_call_target_p (tree ref,
3437 gimple *stmt,
3438 struct cgraph_node *n)
3440 ipa_polymorphic_call_context context (current_function_decl, ref, stmt);
3441 tree call_fn = gimple_call_fn (stmt);
3443 return possible_polymorphic_call_target_p (obj_type_ref_class (call_fn),
3444 tree_to_uhwi
3445 (OBJ_TYPE_REF_TOKEN (call_fn)),
3446 context,
3451 /* After callgraph construction new external nodes may appear.
3452 Add them into the graph. */
3454 void
3455 update_type_inheritance_graph (void)
3457 struct cgraph_node *n;
3459 if (!odr_hash)
3460 return;
3461 free_polymorphic_call_targets_hash ();
3462 timevar_push (TV_IPA_INHERITANCE);
3463 /* We reconstruct the graph starting from types of all methods seen in the
3464 unit. */
3465 FOR_EACH_FUNCTION (n)
3466 if (DECL_VIRTUAL_P (n->decl)
3467 && !n->definition
3468 && n->real_symbol_p ())
3469 get_odr_type (TYPE_METHOD_BASETYPE (TREE_TYPE (n->decl)), true);
3470 timevar_pop (TV_IPA_INHERITANCE);
3474 /* Return true if N looks like likely target of a polymorphic call.
3475 Rule out cxa_pure_virtual, noreturns, function declared cold and
3476 other obvious cases. */
3478 bool
3479 likely_target_p (struct cgraph_node *n)
3481 int flags;
3482 /* cxa_pure_virtual and similar things are not likely. */
3483 if (TREE_CODE (TREE_TYPE (n->decl)) != METHOD_TYPE)
3484 return false;
3485 flags = flags_from_decl_or_type (n->decl);
3486 if (flags & ECF_NORETURN)
3487 return false;
3488 if (lookup_attribute ("cold",
3489 DECL_ATTRIBUTES (n->decl)))
3490 return false;
3491 if (n->frequency < NODE_FREQUENCY_NORMAL)
3492 return false;
3493 /* If there are no live virtual tables referring the target,
3494 the only way the target can be called is an instance coming from other
3495 compilation unit; speculative devirtualization is built around an
3496 assumption that won't happen. */
3497 if (!referenced_from_vtable_p (n))
3498 return false;
3499 return true;
3502 /* Compare type warning records P1 and P2 and choose one with larger count;
3503 helper for qsort. */
3506 type_warning_cmp (const void *p1, const void *p2)
3508 const odr_type_warn_count *t1 = (const odr_type_warn_count *)p1;
3509 const odr_type_warn_count *t2 = (const odr_type_warn_count *)p2;
3511 if (t1->dyn_count < t2->dyn_count)
3512 return 1;
3513 if (t1->dyn_count > t2->dyn_count)
3514 return -1;
3515 return t2->count - t1->count;
3518 /* Compare decl warning records P1 and P2 and choose one with larger count;
3519 helper for qsort. */
3522 decl_warning_cmp (const void *p1, const void *p2)
3524 const decl_warn_count *t1 = *(const decl_warn_count * const *)p1;
3525 const decl_warn_count *t2 = *(const decl_warn_count * const *)p2;
3527 if (t1->dyn_count < t2->dyn_count)
3528 return 1;
3529 if (t1->dyn_count > t2->dyn_count)
3530 return -1;
3531 return t2->count - t1->count;
3535 /* Try to speculatively devirtualize call to OTR_TYPE with OTR_TOKEN with
3536 context CTX. */
3538 struct cgraph_node *
3539 try_speculative_devirtualization (tree otr_type, HOST_WIDE_INT otr_token,
3540 ipa_polymorphic_call_context ctx)
3542 vec <cgraph_node *>targets
3543 = possible_polymorphic_call_targets
3544 (otr_type, otr_token, ctx, NULL, NULL, true);
3545 unsigned int i;
3546 struct cgraph_node *likely_target = NULL;
3548 for (i = 0; i < targets.length (); i++)
3549 if (likely_target_p (targets[i]))
3551 if (likely_target)
3552 return NULL;
3553 likely_target = targets[i];
3555 if (!likely_target
3556 ||!likely_target->definition
3557 || DECL_EXTERNAL (likely_target->decl))
3558 return NULL;
3560 /* Don't use an implicitly-declared destructor (c++/58678). */
3561 struct cgraph_node *non_thunk_target
3562 = likely_target->function_symbol ();
3563 if (DECL_ARTIFICIAL (non_thunk_target->decl))
3564 return NULL;
3565 if (likely_target->get_availability () <= AVAIL_INTERPOSABLE
3566 && likely_target->can_be_discarded_p ())
3567 return NULL;
3568 return likely_target;
3571 /* The ipa-devirt pass.
3572 When polymorphic call has only one likely target in the unit,
3573 turn it into a speculative call. */
3575 static unsigned int
3576 ipa_devirt (void)
3578 struct cgraph_node *n;
3579 hash_set<void *> bad_call_targets;
3580 struct cgraph_edge *e;
3582 int npolymorphic = 0, nspeculated = 0, nconverted = 0, ncold = 0;
3583 int nmultiple = 0, noverwritable = 0, ndevirtualized = 0, nnotdefined = 0;
3584 int nwrong = 0, nok = 0, nexternal = 0, nartificial = 0;
3585 int ndropped = 0;
3587 if (!odr_types_ptr)
3588 return 0;
3590 if (dump_file)
3591 dump_type_inheritance_graph (dump_file);
3593 /* We can output -Wsuggest-final-methods and -Wsuggest-final-types warnings.
3594 This is implemented by setting up final_warning_records that are updated
3595 by get_polymorphic_call_targets.
3596 We need to clear cache in this case to trigger recomputation of all
3597 entries. */
3598 if (warn_suggest_final_methods || warn_suggest_final_types)
3600 final_warning_records = new (final_warning_record);
3601 final_warning_records->dyn_count = profile_count::zero ();
3602 final_warning_records->type_warnings.safe_grow_cleared
3603 (odr_types.length ());
3604 free_polymorphic_call_targets_hash ();
3607 FOR_EACH_DEFINED_FUNCTION (n)
3609 bool update = false;
3610 if (!opt_for_fn (n->decl, flag_devirtualize))
3611 continue;
3612 if (dump_file && n->indirect_calls)
3613 fprintf (dump_file, "\n\nProcesing function %s\n",
3614 n->dump_name ());
3615 for (e = n->indirect_calls; e; e = e->next_callee)
3616 if (e->indirect_info->polymorphic)
3618 struct cgraph_node *likely_target = NULL;
3619 void *cache_token;
3620 bool final;
3622 if (final_warning_records)
3623 final_warning_records->dyn_count = e->count;
3625 vec <cgraph_node *>targets
3626 = possible_polymorphic_call_targets
3627 (e, &final, &cache_token, true);
3628 unsigned int i;
3630 /* Trigger warnings by calculating non-speculative targets. */
3631 if (warn_suggest_final_methods || warn_suggest_final_types)
3632 possible_polymorphic_call_targets (e);
3634 if (dump_file)
3635 dump_possible_polymorphic_call_targets
3636 (dump_file, e);
3638 npolymorphic++;
3640 /* See if the call can be devirtualized by means of ipa-prop's
3641 polymorphic call context propagation. If not, we can just
3642 forget about this call being polymorphic and avoid some heavy
3643 lifting in remove_unreachable_nodes that will otherwise try to
3644 keep all possible targets alive until inlining and in the inliner
3645 itself.
3647 This may need to be revisited once we add further ways to use
3648 the may edges, but it is a resonable thing to do right now. */
3650 if ((e->indirect_info->param_index == -1
3651 || (!opt_for_fn (n->decl, flag_devirtualize_speculatively)
3652 && e->indirect_info->vptr_changed))
3653 && !flag_ltrans_devirtualize)
3655 e->indirect_info->polymorphic = false;
3656 ndropped++;
3657 if (dump_file)
3658 fprintf (dump_file, "Dropping polymorphic call info;"
3659 " it can not be used by ipa-prop\n");
3662 if (!opt_for_fn (n->decl, flag_devirtualize_speculatively))
3663 continue;
3665 if (!e->maybe_hot_p ())
3667 if (dump_file)
3668 fprintf (dump_file, "Call is cold\n\n");
3669 ncold++;
3670 continue;
3672 if (e->speculative)
3674 if (dump_file)
3675 fprintf (dump_file, "Call is already speculated\n\n");
3676 nspeculated++;
3678 /* When dumping see if we agree with speculation. */
3679 if (!dump_file)
3680 continue;
3682 if (bad_call_targets.contains (cache_token))
3684 if (dump_file)
3685 fprintf (dump_file, "Target list is known to be useless\n\n");
3686 nmultiple++;
3687 continue;
3689 for (i = 0; i < targets.length (); i++)
3690 if (likely_target_p (targets[i]))
3692 if (likely_target)
3694 likely_target = NULL;
3695 if (dump_file)
3696 fprintf (dump_file, "More than one likely target\n\n");
3697 nmultiple++;
3698 break;
3700 likely_target = targets[i];
3702 if (!likely_target)
3704 bad_call_targets.add (cache_token);
3705 continue;
3707 /* This is reached only when dumping; check if we agree or disagree
3708 with the speculation. */
3709 if (e->speculative)
3711 struct cgraph_edge *e2;
3712 struct ipa_ref *ref;
3713 e->speculative_call_info (e2, e, ref);
3714 if (e2->callee->ultimate_alias_target ()
3715 == likely_target->ultimate_alias_target ())
3717 fprintf (dump_file, "We agree with speculation\n\n");
3718 nok++;
3720 else
3722 fprintf (dump_file, "We disagree with speculation\n\n");
3723 nwrong++;
3725 continue;
3727 if (!likely_target->definition)
3729 if (dump_file)
3730 fprintf (dump_file, "Target is not a definition\n\n");
3731 nnotdefined++;
3732 continue;
3734 /* Do not introduce new references to external symbols. While we
3735 can handle these just well, it is common for programs to
3736 incorrectly with headers defining methods they are linked
3737 with. */
3738 if (DECL_EXTERNAL (likely_target->decl))
3740 if (dump_file)
3741 fprintf (dump_file, "Target is external\n\n");
3742 nexternal++;
3743 continue;
3745 /* Don't use an implicitly-declared destructor (c++/58678). */
3746 struct cgraph_node *non_thunk_target
3747 = likely_target->function_symbol ();
3748 if (DECL_ARTIFICIAL (non_thunk_target->decl))
3750 if (dump_file)
3751 fprintf (dump_file, "Target is artificial\n\n");
3752 nartificial++;
3753 continue;
3755 if (likely_target->get_availability () <= AVAIL_INTERPOSABLE
3756 && likely_target->can_be_discarded_p ())
3758 if (dump_file)
3759 fprintf (dump_file, "Target is overwritable\n\n");
3760 noverwritable++;
3761 continue;
3763 else if (dbg_cnt (devirt))
3765 if (dump_enabled_p ())
3767 location_t locus = gimple_location_safe (e->call_stmt);
3768 dump_printf_loc (MSG_OPTIMIZED_LOCATIONS, locus,
3769 "speculatively devirtualizing call "
3770 "in %s to %s\n",
3771 n->dump_name (),
3772 likely_target->dump_name ());
3774 if (!likely_target->can_be_discarded_p ())
3776 cgraph_node *alias;
3777 alias = dyn_cast<cgraph_node *> (likely_target->noninterposable_alias ());
3778 if (alias)
3779 likely_target = alias;
3781 nconverted++;
3782 update = true;
3783 e->make_speculative
3784 (likely_target, e->count.apply_scale (8, 10),
3785 e->frequency * 8 / 10);
3788 if (update)
3789 ipa_update_overall_fn_summary (n);
3791 if (warn_suggest_final_methods || warn_suggest_final_types)
3793 if (warn_suggest_final_types)
3795 final_warning_records->type_warnings.qsort (type_warning_cmp);
3796 for (unsigned int i = 0;
3797 i < final_warning_records->type_warnings.length (); i++)
3798 if (final_warning_records->type_warnings[i].count)
3800 tree type = final_warning_records->type_warnings[i].type;
3801 int count = final_warning_records->type_warnings[i].count;
3802 profile_count dyn_count
3803 = final_warning_records->type_warnings[i].dyn_count;
3805 if (!(dyn_count > 0))
3806 warning_n (DECL_SOURCE_LOCATION (TYPE_NAME (type)),
3807 OPT_Wsuggest_final_types, count,
3808 "Declaring type %qD final "
3809 "would enable devirtualization of %i call",
3810 "Declaring type %qD final "
3811 "would enable devirtualization of %i calls",
3812 type,
3813 count);
3814 else
3815 warning_n (DECL_SOURCE_LOCATION (TYPE_NAME (type)),
3816 OPT_Wsuggest_final_types, count,
3817 "Declaring type %qD final "
3818 "would enable devirtualization of %i call "
3819 "executed %lli times",
3820 "Declaring type %qD final "
3821 "would enable devirtualization of %i calls "
3822 "executed %lli times",
3823 type,
3824 count,
3825 (long long) dyn_count.to_gcov_type ());
3829 if (warn_suggest_final_methods)
3831 auto_vec<const decl_warn_count*> decl_warnings_vec;
3833 final_warning_records->decl_warnings.traverse
3834 <vec<const decl_warn_count *> *, add_decl_warning> (&decl_warnings_vec);
3835 decl_warnings_vec.qsort (decl_warning_cmp);
3836 for (unsigned int i = 0; i < decl_warnings_vec.length (); i++)
3838 tree decl = decl_warnings_vec[i]->decl;
3839 int count = decl_warnings_vec[i]->count;
3840 profile_count dyn_count
3841 = decl_warnings_vec[i]->dyn_count;
3843 if (!(dyn_count > 0))
3844 if (DECL_CXX_DESTRUCTOR_P (decl))
3845 warning_n (DECL_SOURCE_LOCATION (decl),
3846 OPT_Wsuggest_final_methods, count,
3847 "Declaring virtual destructor of %qD final "
3848 "would enable devirtualization of %i call",
3849 "Declaring virtual destructor of %qD final "
3850 "would enable devirtualization of %i calls",
3851 DECL_CONTEXT (decl), count);
3852 else
3853 warning_n (DECL_SOURCE_LOCATION (decl),
3854 OPT_Wsuggest_final_methods, count,
3855 "Declaring method %qD final "
3856 "would enable devirtualization of %i call",
3857 "Declaring method %qD final "
3858 "would enable devirtualization of %i calls",
3859 decl, count);
3860 else if (DECL_CXX_DESTRUCTOR_P (decl))
3861 warning_n (DECL_SOURCE_LOCATION (decl),
3862 OPT_Wsuggest_final_methods, count,
3863 "Declaring virtual destructor of %qD final "
3864 "would enable devirtualization of %i call "
3865 "executed %lli times",
3866 "Declaring virtual destructor of %qD final "
3867 "would enable devirtualization of %i calls "
3868 "executed %lli times",
3869 DECL_CONTEXT (decl), count,
3870 (long long)dyn_count.to_gcov_type ());
3871 else
3872 warning_n (DECL_SOURCE_LOCATION (decl),
3873 OPT_Wsuggest_final_methods, count,
3874 "Declaring method %qD final "
3875 "would enable devirtualization of %i call "
3876 "executed %lli times",
3877 "Declaring method %qD final "
3878 "would enable devirtualization of %i calls "
3879 "executed %lli times",
3880 decl, count,
3881 (long long)dyn_count.to_gcov_type ());
3885 delete (final_warning_records);
3886 final_warning_records = 0;
3889 if (dump_file)
3890 fprintf (dump_file,
3891 "%i polymorphic calls, %i devirtualized,"
3892 " %i speculatively devirtualized, %i cold\n"
3893 "%i have multiple targets, %i overwritable,"
3894 " %i already speculated (%i agree, %i disagree),"
3895 " %i external, %i not defined, %i artificial, %i infos dropped\n",
3896 npolymorphic, ndevirtualized, nconverted, ncold,
3897 nmultiple, noverwritable, nspeculated, nok, nwrong,
3898 nexternal, nnotdefined, nartificial, ndropped);
3899 return ndevirtualized || ndropped ? TODO_remove_functions : 0;
3902 namespace {
3904 const pass_data pass_data_ipa_devirt =
3906 IPA_PASS, /* type */
3907 "devirt", /* name */
3908 OPTGROUP_NONE, /* optinfo_flags */
3909 TV_IPA_DEVIRT, /* tv_id */
3910 0, /* properties_required */
3911 0, /* properties_provided */
3912 0, /* properties_destroyed */
3913 0, /* todo_flags_start */
3914 ( TODO_dump_symtab ), /* todo_flags_finish */
3917 class pass_ipa_devirt : public ipa_opt_pass_d
3919 public:
3920 pass_ipa_devirt (gcc::context *ctxt)
3921 : ipa_opt_pass_d (pass_data_ipa_devirt, ctxt,
3922 NULL, /* generate_summary */
3923 NULL, /* write_summary */
3924 NULL, /* read_summary */
3925 NULL, /* write_optimization_summary */
3926 NULL, /* read_optimization_summary */
3927 NULL, /* stmt_fixup */
3928 0, /* function_transform_todo_flags_start */
3929 NULL, /* function_transform */
3930 NULL) /* variable_transform */
3933 /* opt_pass methods: */
3934 virtual bool gate (function *)
3936 /* In LTO, always run the IPA passes and decide on function basis if the
3937 pass is enabled. */
3938 if (in_lto_p)
3939 return true;
3940 return (flag_devirtualize
3941 && (flag_devirtualize_speculatively
3942 || (warn_suggest_final_methods
3943 || warn_suggest_final_types))
3944 && optimize);
3947 virtual unsigned int execute (function *) { return ipa_devirt (); }
3949 }; // class pass_ipa_devirt
3951 } // anon namespace
3953 ipa_opt_pass_d *
3954 make_pass_ipa_devirt (gcc::context *ctxt)
3956 return new pass_ipa_devirt (ctxt);
3959 #include "gt-ipa-devirt.h"