2018-04-24 Steven G. Kargl <kargl@gcc.gnu.org>
[official-gcc.git] / gcc / ipa-devirt.c
blob308b6e6cdd5dbd5979d0487b9f0af9ad32cb75d7
1 /* Basic IPA utilities for type inheritance graph construction and
2 devirtualization.
3 Copyright (C) 2013-2018 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"
132 #include "stringpool.h"
133 #include "attribs.h"
135 /* Hash based set of pairs of types. */
136 struct type_pair
138 tree first;
139 tree second;
142 template <>
143 struct default_hash_traits <type_pair>
144 : typed_noop_remove <type_pair>
146 GTY((skip)) typedef type_pair value_type;
147 GTY((skip)) typedef type_pair compare_type;
148 static hashval_t
149 hash (type_pair p)
151 return TYPE_UID (p.first) ^ TYPE_UID (p.second);
153 static bool
154 is_empty (type_pair p)
156 return p.first == NULL;
158 static bool
159 is_deleted (type_pair p ATTRIBUTE_UNUSED)
161 return false;
163 static bool
164 equal (const type_pair &a, const type_pair &b)
166 return a.first==b.first && a.second == b.second;
168 static void
169 mark_empty (type_pair &e)
171 e.first = NULL;
175 static bool odr_types_equivalent_p (tree, tree, bool, bool *,
176 hash_set<type_pair> *,
177 location_t, location_t);
179 static bool odr_violation_reported = false;
182 /* Pointer set of all call targets appearing in the cache. */
183 static hash_set<cgraph_node *> *cached_polymorphic_call_targets;
185 /* The node of type inheritance graph. For each type unique in
186 One Definition Rule (ODR) sense, we produce one node linking all
187 main variants of types equivalent to it, bases and derived types. */
189 struct GTY(()) odr_type_d
191 /* leader type. */
192 tree type;
193 /* All bases; built only for main variants of types. */
194 vec<odr_type> GTY((skip)) bases;
195 /* All derived types with virtual methods seen in unit;
196 built only for main variants of types. */
197 vec<odr_type> GTY((skip)) derived_types;
199 /* All equivalent types, if more than one. */
200 vec<tree, va_gc> *types;
201 /* Set of all equivalent types, if NON-NULL. */
202 hash_set<tree> * GTY((skip)) types_set;
204 /* Unique ID indexing the type in odr_types array. */
205 int id;
206 /* Is it in anonymous namespace? */
207 bool anonymous_namespace;
208 /* Do we know about all derivations of given type? */
209 bool all_derivations_known;
210 /* Did we report ODR violation here? */
211 bool odr_violated;
212 /* Set when virtual table without RTTI previaled table with. */
213 bool rtti_broken;
216 /* Return TRUE if all derived types of T are known and thus
217 we may consider the walk of derived type complete.
219 This is typically true only for final anonymous namespace types and types
220 defined within functions (that may be COMDAT and thus shared across units,
221 but with the same set of derived types). */
223 bool
224 type_all_derivations_known_p (const_tree t)
226 if (TYPE_FINAL_P (t))
227 return true;
228 if (flag_ltrans)
229 return false;
230 /* Non-C++ types may have IDENTIFIER_NODE here, do not crash. */
231 if (!TYPE_NAME (t) || TREE_CODE (TYPE_NAME (t)) != TYPE_DECL)
232 return true;
233 if (type_in_anonymous_namespace_p (t))
234 return true;
235 return (decl_function_context (TYPE_NAME (t)) != NULL);
238 /* Return TRUE if type's constructors are all visible. */
240 static bool
241 type_all_ctors_visible_p (tree t)
243 return !flag_ltrans
244 && symtab->state >= CONSTRUCTION
245 /* We can not always use type_all_derivations_known_p.
246 For function local types we must assume case where
247 the function is COMDAT and shared in between units.
249 TODO: These cases are quite easy to get, but we need
250 to keep track of C++ privatizing via -Wno-weak
251 as well as the IPA privatizing. */
252 && type_in_anonymous_namespace_p (t);
255 /* Return TRUE if type may have instance. */
257 static bool
258 type_possibly_instantiated_p (tree t)
260 tree vtable;
261 varpool_node *vnode;
263 /* TODO: Add abstract types here. */
264 if (!type_all_ctors_visible_p (t))
265 return true;
267 vtable = BINFO_VTABLE (TYPE_BINFO (t));
268 if (TREE_CODE (vtable) == POINTER_PLUS_EXPR)
269 vtable = TREE_OPERAND (TREE_OPERAND (vtable, 0), 0);
270 vnode = varpool_node::get (vtable);
271 return vnode && vnode->definition;
274 /* Hash used to unify ODR types based on their mangled name and for anonymous
275 namespace types. */
277 struct odr_name_hasher : pointer_hash <odr_type_d>
279 typedef union tree_node *compare_type;
280 static inline hashval_t hash (const odr_type_d *);
281 static inline bool equal (const odr_type_d *, const tree_node *);
282 static inline void remove (odr_type_d *);
285 /* Has used to unify ODR types based on their associated virtual table.
286 This hash is needed to keep -fno-lto-odr-type-merging to work and contains
287 only polymorphic types. Types with mangled names are inserted to both. */
289 struct odr_vtable_hasher:odr_name_hasher
291 static inline hashval_t hash (const odr_type_d *);
292 static inline bool equal (const odr_type_d *, const tree_node *);
295 /* Return type that was declared with T's name so that T is an
296 qualified variant of it. */
298 static inline tree
299 main_odr_variant (const_tree t)
301 if (TYPE_NAME (t) && TREE_CODE (TYPE_NAME (t)) == TYPE_DECL)
302 return TREE_TYPE (TYPE_NAME (t));
303 /* Unnamed types and non-C++ produced types can be compared by variants. */
304 else
305 return TYPE_MAIN_VARIANT (t);
308 static bool
309 can_be_name_hashed_p (tree t)
311 return (!in_lto_p || odr_type_p (t));
314 /* Hash type by its ODR name. */
316 static hashval_t
317 hash_odr_name (const_tree t)
319 gcc_checking_assert (main_odr_variant (t) == t);
321 /* If not in LTO, all main variants are unique, so we can do
322 pointer hash. */
323 if (!in_lto_p)
324 return htab_hash_pointer (t);
326 /* Anonymous types are unique. */
327 if (type_with_linkage_p (t) && type_in_anonymous_namespace_p (t))
328 return htab_hash_pointer (t);
330 gcc_checking_assert (TYPE_NAME (t)
331 && DECL_ASSEMBLER_NAME_SET_P (TYPE_NAME (t)));
332 return IDENTIFIER_HASH_VALUE (DECL_ASSEMBLER_NAME (TYPE_NAME (t)));
335 /* Return the computed hashcode for ODR_TYPE. */
337 inline hashval_t
338 odr_name_hasher::hash (const odr_type_d *odr_type)
340 return hash_odr_name (odr_type->type);
343 static bool
344 can_be_vtable_hashed_p (tree t)
346 /* vtable hashing can distinguish only main variants. */
347 if (TYPE_MAIN_VARIANT (t) != t)
348 return false;
349 /* Anonymous namespace types are always handled by name hash. */
350 if (type_with_linkage_p (t) && type_in_anonymous_namespace_p (t))
351 return false;
352 return (TREE_CODE (t) == RECORD_TYPE
353 && TYPE_BINFO (t) && BINFO_VTABLE (TYPE_BINFO (t)));
356 /* Hash type by assembler name of its vtable. */
358 static hashval_t
359 hash_odr_vtable (const_tree t)
361 tree v = BINFO_VTABLE (TYPE_BINFO (TYPE_MAIN_VARIANT (t)));
362 inchash::hash hstate;
364 gcc_checking_assert (in_lto_p);
365 gcc_checking_assert (!type_in_anonymous_namespace_p (t));
366 gcc_checking_assert (TREE_CODE (t) == RECORD_TYPE
367 && TYPE_BINFO (t) && BINFO_VTABLE (TYPE_BINFO (t)));
368 gcc_checking_assert (main_odr_variant (t) == t);
370 if (TREE_CODE (v) == POINTER_PLUS_EXPR)
372 add_expr (TREE_OPERAND (v, 1), hstate);
373 v = TREE_OPERAND (TREE_OPERAND (v, 0), 0);
376 hstate.add_hwi (IDENTIFIER_HASH_VALUE (DECL_ASSEMBLER_NAME (v)));
377 return hstate.end ();
380 /* Return the computed hashcode for ODR_TYPE. */
382 inline hashval_t
383 odr_vtable_hasher::hash (const odr_type_d *odr_type)
385 return hash_odr_vtable (odr_type->type);
388 /* For languages with One Definition Rule, work out if
389 types are the same based on their name.
391 This is non-trivial for LTO where minor differences in
392 the type representation may have prevented type merging
393 to merge two copies of otherwise equivalent type.
395 Until we start streaming mangled type names, this function works
396 only for polymorphic types.
398 When STRICT is true, we compare types by their names for purposes of
399 ODR violation warnings. When strict is false, we consider variants
400 equivalent, because it is all that matters for devirtualization machinery.
403 bool
404 types_same_for_odr (const_tree type1, const_tree type2, bool strict)
406 gcc_checking_assert (TYPE_P (type1) && TYPE_P (type2));
408 type1 = main_odr_variant (type1);
409 type2 = main_odr_variant (type2);
410 if (!strict)
412 type1 = TYPE_MAIN_VARIANT (type1);
413 type2 = TYPE_MAIN_VARIANT (type2);
416 if (type1 == type2)
417 return true;
419 if (!in_lto_p)
420 return false;
422 /* Check for anonymous namespaces. Those have !TREE_PUBLIC
423 on the corresponding TYPE_STUB_DECL. */
424 if ((type_with_linkage_p (type1) && type_in_anonymous_namespace_p (type1))
425 || (type_with_linkage_p (type2) && type_in_anonymous_namespace_p (type2)))
426 return false;
429 /* ODR name of the type is set in DECL_ASSEMBLER_NAME of its TYPE_NAME.
431 Ideally we should never need types without ODR names here. It can however
432 happen in two cases:
434 1) for builtin types that are not streamed but rebuilt in lto/lto-lang.c
435 Here testing for equivalence is safe, since their MAIN_VARIANTs are
436 unique.
437 2) for units streamed with -fno-lto-odr-type-merging. Here we can't
438 establish precise ODR equivalency, but for correctness we care only
439 about equivalency on complete polymorphic types. For these we can
440 compare assembler names of their virtual tables. */
441 if ((!TYPE_NAME (type1) || !DECL_ASSEMBLER_NAME_SET_P (TYPE_NAME (type1)))
442 || (!TYPE_NAME (type2) || !DECL_ASSEMBLER_NAME_SET_P (TYPE_NAME (type2))))
444 /* See if types are obviously different (i.e. different codes
445 or polymorphic wrt non-polymorphic). This is not strictly correct
446 for ODR violating programs, but we can't do better without streaming
447 ODR names. */
448 if (TREE_CODE (type1) != TREE_CODE (type2))
449 return false;
450 if (TREE_CODE (type1) == RECORD_TYPE
451 && (TYPE_BINFO (type1) == NULL_TREE)
452 != (TYPE_BINFO (type2) == NULL_TREE))
453 return false;
454 if (TREE_CODE (type1) == RECORD_TYPE && TYPE_BINFO (type1)
455 && (BINFO_VTABLE (TYPE_BINFO (type1)) == NULL_TREE)
456 != (BINFO_VTABLE (TYPE_BINFO (type2)) == NULL_TREE))
457 return false;
459 /* At the moment we have no way to establish ODR equivalence at LTO
460 other than comparing virtual table pointers of polymorphic types.
461 Eventually we should start saving mangled names in TYPE_NAME.
462 Then this condition will become non-trivial. */
464 if (TREE_CODE (type1) == RECORD_TYPE
465 && TYPE_BINFO (type1) && TYPE_BINFO (type2)
466 && BINFO_VTABLE (TYPE_BINFO (type1))
467 && BINFO_VTABLE (TYPE_BINFO (type2)))
469 tree v1 = BINFO_VTABLE (TYPE_BINFO (type1));
470 tree v2 = BINFO_VTABLE (TYPE_BINFO (type2));
471 gcc_assert (TREE_CODE (v1) == POINTER_PLUS_EXPR
472 && TREE_CODE (v2) == POINTER_PLUS_EXPR);
473 return (operand_equal_p (TREE_OPERAND (v1, 1),
474 TREE_OPERAND (v2, 1), 0)
475 && DECL_ASSEMBLER_NAME
476 (TREE_OPERAND (TREE_OPERAND (v1, 0), 0))
477 == DECL_ASSEMBLER_NAME
478 (TREE_OPERAND (TREE_OPERAND (v2, 0), 0)));
480 gcc_unreachable ();
482 return (DECL_ASSEMBLER_NAME (TYPE_NAME (type1))
483 == DECL_ASSEMBLER_NAME (TYPE_NAME (type2)));
486 /* Return true if we can decide on ODR equivalency.
488 In non-LTO it is always decide, in LTO however it depends in the type has
489 ODR info attached.
491 When STRICT is false, compare main variants. */
493 bool
494 types_odr_comparable (tree t1, tree t2, bool strict)
496 return (!in_lto_p
497 || (strict ? (main_odr_variant (t1) == main_odr_variant (t2)
498 && main_odr_variant (t1))
499 : TYPE_MAIN_VARIANT (t1) == TYPE_MAIN_VARIANT (t2))
500 || (odr_type_p (t1) && odr_type_p (t2))
501 || (TREE_CODE (t1) == RECORD_TYPE && TREE_CODE (t2) == RECORD_TYPE
502 && TYPE_BINFO (t1) && TYPE_BINFO (t2)
503 && polymorphic_type_binfo_p (TYPE_BINFO (t1))
504 && polymorphic_type_binfo_p (TYPE_BINFO (t2))));
507 /* Return true if T1 and T2 are ODR equivalent. If ODR equivalency is not
508 known, be conservative and return false. */
510 bool
511 types_must_be_same_for_odr (tree t1, tree t2)
513 if (types_odr_comparable (t1, t2))
514 return types_same_for_odr (t1, t2);
515 else
516 return TYPE_MAIN_VARIANT (t1) == TYPE_MAIN_VARIANT (t2);
519 /* If T is compound type, return type it is based on. */
521 static tree
522 compound_type_base (const_tree t)
524 if (TREE_CODE (t) == ARRAY_TYPE
525 || POINTER_TYPE_P (t)
526 || TREE_CODE (t) == COMPLEX_TYPE
527 || VECTOR_TYPE_P (t))
528 return TREE_TYPE (t);
529 if (TREE_CODE (t) == METHOD_TYPE)
530 return TYPE_METHOD_BASETYPE (t);
531 if (TREE_CODE (t) == OFFSET_TYPE)
532 return TYPE_OFFSET_BASETYPE (t);
533 return NULL_TREE;
536 /* Return true if T is either ODR type or compound type based from it.
537 If the function return true, we know that T is a type originating from C++
538 source even at link-time. */
540 bool
541 odr_or_derived_type_p (const_tree t)
545 if (odr_type_p (t))
546 return true;
547 /* Function type is a tricky one. Basically we can consider it
548 ODR derived if return type or any of the parameters is.
549 We need to check all parameters because LTO streaming merges
550 common types (such as void) and they are not considered ODR then. */
551 if (TREE_CODE (t) == FUNCTION_TYPE)
553 if (TYPE_METHOD_BASETYPE (t))
554 t = TYPE_METHOD_BASETYPE (t);
555 else
557 if (TREE_TYPE (t) && odr_or_derived_type_p (TREE_TYPE (t)))
558 return true;
559 for (t = TYPE_ARG_TYPES (t); t; t = TREE_CHAIN (t))
560 if (odr_or_derived_type_p (TREE_VALUE (t)))
561 return true;
562 return false;
565 else
566 t = compound_type_base (t);
568 while (t);
569 return t;
572 /* Compare types T1 and T2 and return true if they are
573 equivalent. */
575 inline bool
576 odr_name_hasher::equal (const odr_type_d *o1, const tree_node *t2)
578 tree t1 = o1->type;
580 gcc_checking_assert (main_odr_variant (t2) == t2);
581 gcc_checking_assert (main_odr_variant (t1) == t1);
582 if (t1 == t2)
583 return true;
584 if (!in_lto_p)
585 return false;
586 /* Check for anonymous namespaces. Those have !TREE_PUBLIC
587 on the corresponding TYPE_STUB_DECL. */
588 if ((type_with_linkage_p (t1) && type_in_anonymous_namespace_p (t1))
589 || (type_with_linkage_p (t2) && type_in_anonymous_namespace_p (t2)))
590 return false;
591 gcc_checking_assert (DECL_ASSEMBLER_NAME (TYPE_NAME (t1)));
592 gcc_checking_assert (DECL_ASSEMBLER_NAME (TYPE_NAME (t2)));
593 return (DECL_ASSEMBLER_NAME (TYPE_NAME (t1))
594 == DECL_ASSEMBLER_NAME (TYPE_NAME (t2)));
597 /* Compare types T1 and T2 and return true if they are
598 equivalent. */
600 inline bool
601 odr_vtable_hasher::equal (const odr_type_d *o1, const tree_node *t2)
603 tree t1 = o1->type;
605 gcc_checking_assert (main_odr_variant (t2) == t2);
606 gcc_checking_assert (main_odr_variant (t1) == t1);
607 gcc_checking_assert (in_lto_p);
608 t1 = TYPE_MAIN_VARIANT (t1);
609 t2 = TYPE_MAIN_VARIANT (t2);
610 if (t1 == t2)
611 return true;
612 tree v1 = BINFO_VTABLE (TYPE_BINFO (t1));
613 tree v2 = BINFO_VTABLE (TYPE_BINFO (t2));
614 return (operand_equal_p (TREE_OPERAND (v1, 1),
615 TREE_OPERAND (v2, 1), 0)
616 && DECL_ASSEMBLER_NAME
617 (TREE_OPERAND (TREE_OPERAND (v1, 0), 0))
618 == DECL_ASSEMBLER_NAME
619 (TREE_OPERAND (TREE_OPERAND (v2, 0), 0)));
622 /* Free ODR type V. */
624 inline void
625 odr_name_hasher::remove (odr_type_d *v)
627 v->bases.release ();
628 v->derived_types.release ();
629 if (v->types_set)
630 delete v->types_set;
631 ggc_free (v);
634 /* ODR type hash used to look up ODR type based on tree type node. */
636 typedef hash_table<odr_name_hasher> odr_hash_type;
637 static odr_hash_type *odr_hash;
638 typedef hash_table<odr_vtable_hasher> odr_vtable_hash_type;
639 static odr_vtable_hash_type *odr_vtable_hash;
641 /* ODR types are also stored into ODR_TYPE vector to allow consistent
642 walking. Bases appear before derived types. Vector is garbage collected
643 so we won't end up visiting empty types. */
645 static GTY(()) vec <odr_type, va_gc> *odr_types_ptr;
646 #define odr_types (*odr_types_ptr)
648 /* Set TYPE_BINFO of TYPE and its variants to BINFO. */
649 void
650 set_type_binfo (tree type, tree binfo)
652 for (; type; type = TYPE_NEXT_VARIANT (type))
653 if (COMPLETE_TYPE_P (type))
654 TYPE_BINFO (type) = binfo;
655 else
656 gcc_assert (!TYPE_BINFO (type));
659 /* Compare T1 and T2 based on name or structure. */
661 static bool
662 odr_subtypes_equivalent_p (tree t1, tree t2,
663 hash_set<type_pair> *visited,
664 location_t loc1, location_t loc2)
667 /* This can happen in incomplete types that should be handled earlier. */
668 gcc_assert (t1 && t2);
670 t1 = main_odr_variant (t1);
671 t2 = main_odr_variant (t2);
672 if (t1 == t2)
673 return true;
675 /* Anonymous namespace types must match exactly. */
676 if ((type_with_linkage_p (t1) && type_in_anonymous_namespace_p (t1))
677 || (type_with_linkage_p (t2) && type_in_anonymous_namespace_p (t2)))
678 return false;
680 /* For ODR types be sure to compare their names.
681 To support -Wno-odr-type-merging we allow one type to be non-ODR
682 and other ODR even though it is a violation. */
683 if (types_odr_comparable (t1, t2, true))
685 if (!types_same_for_odr (t1, t2, true))
686 return false;
687 /* Limit recursion: If subtypes are ODR types and we know
688 that they are same, be happy. */
689 if (!odr_type_p (t1) || !get_odr_type (t1, true)->odr_violated)
690 return true;
693 /* Component types, builtins and possibly violating ODR types
694 have to be compared structurally. */
695 if (TREE_CODE (t1) != TREE_CODE (t2))
696 return false;
697 if (AGGREGATE_TYPE_P (t1)
698 && (TYPE_NAME (t1) == NULL_TREE) != (TYPE_NAME (t2) == NULL_TREE))
699 return false;
701 type_pair pair={t1,t2};
702 if (TYPE_UID (t1) > TYPE_UID (t2))
704 pair.first = t2;
705 pair.second = t1;
707 if (visited->add (pair))
708 return true;
709 return odr_types_equivalent_p (t1, t2, false, NULL, visited, loc1, loc2);
712 /* Return true if DECL1 and DECL2 are identical methods. Consider
713 name equivalent to name.localalias.xyz. */
715 static bool
716 methods_equal_p (tree decl1, tree decl2)
718 if (DECL_ASSEMBLER_NAME (decl1) == DECL_ASSEMBLER_NAME (decl2))
719 return true;
720 const char sep = symbol_table::symbol_suffix_separator ();
722 const char *name1 = IDENTIFIER_POINTER (DECL_ASSEMBLER_NAME (decl1));
723 const char *ptr1 = strchr (name1, sep);
724 int len1 = ptr1 ? ptr1 - name1 : strlen (name1);
726 const char *name2 = IDENTIFIER_POINTER (DECL_ASSEMBLER_NAME (decl2));
727 const char *ptr2 = strchr (name2, sep);
728 int len2 = ptr2 ? ptr2 - name2 : strlen (name2);
730 if (len1 != len2)
731 return false;
732 return !strncmp (name1, name2, len1);
735 /* Compare two virtual tables, PREVAILING and VTABLE and output ODR
736 violation warnings. */
738 void
739 compare_virtual_tables (varpool_node *prevailing, varpool_node *vtable)
741 int n1, n2;
743 if (DECL_VIRTUAL_P (prevailing->decl) != DECL_VIRTUAL_P (vtable->decl))
745 odr_violation_reported = true;
746 if (DECL_VIRTUAL_P (prevailing->decl))
748 varpool_node *tmp = prevailing;
749 prevailing = vtable;
750 vtable = tmp;
752 if (warning_at (DECL_SOURCE_LOCATION
753 (TYPE_NAME (DECL_CONTEXT (vtable->decl))),
754 OPT_Wodr,
755 "virtual table of type %qD violates one definition rule",
756 DECL_CONTEXT (vtable->decl)))
757 inform (DECL_SOURCE_LOCATION (prevailing->decl),
758 "variable of same assembler name as the virtual table is "
759 "defined in another translation unit");
760 return;
762 if (!prevailing->definition || !vtable->definition)
763 return;
765 /* If we do not stream ODR type info, do not bother to do useful compare. */
766 if (!TYPE_BINFO (DECL_CONTEXT (vtable->decl))
767 || !polymorphic_type_binfo_p (TYPE_BINFO (DECL_CONTEXT (vtable->decl))))
768 return;
770 odr_type class_type = get_odr_type (DECL_CONTEXT (vtable->decl), true);
772 if (class_type->odr_violated)
773 return;
775 for (n1 = 0, n2 = 0; true; n1++, n2++)
777 struct ipa_ref *ref1, *ref2;
778 bool end1, end2;
780 end1 = !prevailing->iterate_reference (n1, ref1);
781 end2 = !vtable->iterate_reference (n2, ref2);
783 /* !DECL_VIRTUAL_P means RTTI entry;
784 We warn when RTTI is lost because non-RTTI previals; we silently
785 accept the other case. */
786 while (!end2
787 && (end1
788 || (methods_equal_p (ref1->referred->decl,
789 ref2->referred->decl)
790 && TREE_CODE (ref1->referred->decl) == FUNCTION_DECL))
791 && TREE_CODE (ref2->referred->decl) != FUNCTION_DECL)
793 if (!class_type->rtti_broken
794 && warning_at (DECL_SOURCE_LOCATION
795 (TYPE_NAME (DECL_CONTEXT (vtable->decl))),
796 OPT_Wodr,
797 "virtual table of type %qD contains RTTI "
798 "information",
799 DECL_CONTEXT (vtable->decl)))
801 inform (DECL_SOURCE_LOCATION
802 (TYPE_NAME (DECL_CONTEXT (prevailing->decl))),
803 "but is prevailed by one without from other translation "
804 "unit");
805 inform (DECL_SOURCE_LOCATION
806 (TYPE_NAME (DECL_CONTEXT (prevailing->decl))),
807 "RTTI will not work on this type");
808 class_type->rtti_broken = true;
810 n2++;
811 end2 = !vtable->iterate_reference (n2, ref2);
813 while (!end1
814 && (end2
815 || (methods_equal_p (ref2->referred->decl, ref1->referred->decl)
816 && TREE_CODE (ref2->referred->decl) == FUNCTION_DECL))
817 && TREE_CODE (ref1->referred->decl) != FUNCTION_DECL)
819 n1++;
820 end1 = !prevailing->iterate_reference (n1, ref1);
823 /* Finished? */
824 if (end1 && end2)
826 /* Extra paranoia; compare the sizes. We do not have information
827 about virtual inheritance offsets, so just be sure that these
828 match.
829 Do this as very last check so the not very informative error
830 is not output too often. */
831 if (DECL_SIZE (prevailing->decl) != DECL_SIZE (vtable->decl))
833 class_type->odr_violated = true;
834 if (warning_at (DECL_SOURCE_LOCATION
835 (TYPE_NAME (DECL_CONTEXT (vtable->decl))),
836 OPT_Wodr,
837 "virtual table of type %qD violates "
838 "one definition rule ",
839 DECL_CONTEXT (vtable->decl)))
841 inform (DECL_SOURCE_LOCATION
842 (TYPE_NAME (DECL_CONTEXT (prevailing->decl))),
843 "the conflicting type defined in another translation "
844 "unit has virtual table of different size");
847 return;
850 if (!end1 && !end2)
852 if (methods_equal_p (ref1->referred->decl, ref2->referred->decl))
853 continue;
855 class_type->odr_violated = true;
857 /* If the loops above stopped on non-virtual pointer, we have
858 mismatch in RTTI information mangling. */
859 if (TREE_CODE (ref1->referred->decl) != FUNCTION_DECL
860 && TREE_CODE (ref2->referred->decl) != FUNCTION_DECL)
862 if (warning_at (DECL_SOURCE_LOCATION
863 (TYPE_NAME (DECL_CONTEXT (vtable->decl))),
864 OPT_Wodr,
865 "virtual table of type %qD violates "
866 "one definition rule ",
867 DECL_CONTEXT (vtable->decl)))
869 inform (DECL_SOURCE_LOCATION
870 (TYPE_NAME (DECL_CONTEXT (prevailing->decl))),
871 "the conflicting type defined in another translation "
872 "unit with different RTTI information");
874 return;
876 /* At this point both REF1 and REF2 points either to virtual table
877 or virtual method. If one points to virtual table and other to
878 method we can complain the same way as if one table was shorter
879 than other pointing out the extra method. */
880 if (TREE_CODE (ref1->referred->decl)
881 != TREE_CODE (ref2->referred->decl))
883 if (VAR_P (ref1->referred->decl))
884 end1 = true;
885 else if (VAR_P (ref2->referred->decl))
886 end2 = true;
890 class_type->odr_violated = true;
892 /* Complain about size mismatch. Either we have too many virutal
893 functions or too many virtual table pointers. */
894 if (end1 || end2)
896 if (end1)
898 varpool_node *tmp = prevailing;
899 prevailing = vtable;
900 vtable = tmp;
901 ref1 = ref2;
903 if (warning_at (DECL_SOURCE_LOCATION
904 (TYPE_NAME (DECL_CONTEXT (vtable->decl))),
905 OPT_Wodr,
906 "virtual table of type %qD violates "
907 "one definition rule",
908 DECL_CONTEXT (vtable->decl)))
910 if (TREE_CODE (ref1->referring->decl) == FUNCTION_DECL)
912 inform (DECL_SOURCE_LOCATION
913 (TYPE_NAME (DECL_CONTEXT (prevailing->decl))),
914 "the conflicting type defined in another translation "
915 "unit");
916 inform (DECL_SOURCE_LOCATION
917 (TYPE_NAME (DECL_CONTEXT (ref1->referring->decl))),
918 "contains additional virtual method %qD",
919 ref1->referred->decl);
921 else
923 inform (DECL_SOURCE_LOCATION
924 (TYPE_NAME (DECL_CONTEXT (prevailing->decl))),
925 "the conflicting type defined in another translation "
926 "unit has virtual table with more entries");
929 return;
932 /* And in the last case we have either mistmatch in between two virtual
933 methods or two virtual table pointers. */
934 if (warning_at (DECL_SOURCE_LOCATION
935 (TYPE_NAME (DECL_CONTEXT (vtable->decl))), OPT_Wodr,
936 "virtual table of type %qD violates "
937 "one definition rule ",
938 DECL_CONTEXT (vtable->decl)))
940 if (TREE_CODE (ref1->referred->decl) == FUNCTION_DECL)
942 inform (DECL_SOURCE_LOCATION
943 (TYPE_NAME (DECL_CONTEXT (prevailing->decl))),
944 "the conflicting type defined in another translation "
945 "unit");
946 gcc_assert (TREE_CODE (ref2->referred->decl)
947 == FUNCTION_DECL);
948 inform (DECL_SOURCE_LOCATION
949 (ref1->referred->ultimate_alias_target ()->decl),
950 "virtual method %qD",
951 ref1->referred->ultimate_alias_target ()->decl);
952 inform (DECL_SOURCE_LOCATION
953 (ref2->referred->ultimate_alias_target ()->decl),
954 "ought to match virtual method %qD but does not",
955 ref2->referred->ultimate_alias_target ()->decl);
957 else
958 inform (DECL_SOURCE_LOCATION
959 (TYPE_NAME (DECL_CONTEXT (prevailing->decl))),
960 "the conflicting type defined in another translation "
961 "unit has virtual table with different contents");
962 return;
967 /* Output ODR violation warning about T1 and T2 with REASON.
968 Display location of ST1 and ST2 if REASON speaks about field or
969 method of the type.
970 If WARN is false, do nothing. Set WARNED if warning was indeed
971 output. */
973 void
974 warn_odr (tree t1, tree t2, tree st1, tree st2,
975 bool warn, bool *warned, const char *reason)
977 tree decl2 = TYPE_NAME (t2);
978 if (warned)
979 *warned = false;
981 if (!warn || !TYPE_NAME(t1))
982 return;
984 /* ODR warnings are output druing LTO streaming; we must apply location
985 cache for potential warnings to be output correctly. */
986 if (lto_location_cache::current_cache)
987 lto_location_cache::current_cache->apply_location_cache ();
989 if (!warning_at (DECL_SOURCE_LOCATION (TYPE_NAME (t1)), OPT_Wodr,
990 "type %qT violates the C++ One Definition Rule",
991 t1))
992 return;
993 if (!st1 && !st2)
995 /* For FIELD_DECL support also case where one of fields is
996 NULL - this is used when the structures have mismatching number of
997 elements. */
998 else if (!st1 || TREE_CODE (st1) == FIELD_DECL)
1000 inform (DECL_SOURCE_LOCATION (decl2),
1001 "a different type is defined in another translation unit");
1002 if (!st1)
1004 st1 = st2;
1005 st2 = NULL;
1007 inform (DECL_SOURCE_LOCATION (st1),
1008 "the first difference of corresponding definitions is field %qD",
1009 st1);
1010 if (st2)
1011 decl2 = st2;
1013 else if (TREE_CODE (st1) == FUNCTION_DECL)
1015 inform (DECL_SOURCE_LOCATION (decl2),
1016 "a different type is defined in another translation unit");
1017 inform (DECL_SOURCE_LOCATION (st1),
1018 "the first difference of corresponding definitions is method %qD",
1019 st1);
1020 decl2 = st2;
1022 else
1023 return;
1024 inform (DECL_SOURCE_LOCATION (decl2), reason);
1026 if (warned)
1027 *warned = true;
1030 /* Return ture if T1 and T2 are incompatible and we want to recusively
1031 dive into them from warn_type_mismatch to give sensible answer. */
1033 static bool
1034 type_mismatch_p (tree t1, tree t2)
1036 if (odr_or_derived_type_p (t1) && odr_or_derived_type_p (t2)
1037 && !odr_types_equivalent_p (t1, t2))
1038 return true;
1039 return !types_compatible_p (t1, t2);
1043 /* Types T1 and T2 was found to be incompatible in a context they can't
1044 (either used to declare a symbol of same assembler name or unified by
1045 ODR rule). We already output warning about this, but if possible, output
1046 extra information on how the types mismatch.
1048 This is hard to do in general. We basically handle the common cases.
1050 If LOC1 and LOC2 are meaningful locations, use it in the case the types
1051 themselves do no thave one.*/
1053 void
1054 warn_types_mismatch (tree t1, tree t2, location_t loc1, location_t loc2)
1056 /* Location of type is known only if it has TYPE_NAME and the name is
1057 TYPE_DECL. */
1058 location_t loc_t1 = TYPE_NAME (t1) && TREE_CODE (TYPE_NAME (t1)) == TYPE_DECL
1059 ? DECL_SOURCE_LOCATION (TYPE_NAME (t1))
1060 : UNKNOWN_LOCATION;
1061 location_t loc_t2 = TYPE_NAME (t2) && TREE_CODE (TYPE_NAME (t2)) == TYPE_DECL
1062 ? DECL_SOURCE_LOCATION (TYPE_NAME (t2))
1063 : UNKNOWN_LOCATION;
1064 bool loc_t2_useful = false;
1066 /* With LTO it is a common case that the location of both types match.
1067 See if T2 has a location that is different from T1. If so, we will
1068 inform user about the location.
1069 Do not consider the location passed to us in LOC1/LOC2 as those are
1070 already output. */
1071 if (loc_t2 > BUILTINS_LOCATION && loc_t2 != loc_t1)
1073 if (loc_t1 <= BUILTINS_LOCATION)
1074 loc_t2_useful = true;
1075 else
1077 expanded_location xloc1 = expand_location (loc_t1);
1078 expanded_location xloc2 = expand_location (loc_t2);
1080 if (strcmp (xloc1.file, xloc2.file)
1081 || xloc1.line != xloc2.line
1082 || xloc1.column != xloc2.column)
1083 loc_t2_useful = true;
1087 if (loc_t1 <= BUILTINS_LOCATION)
1088 loc_t1 = loc1;
1089 if (loc_t2 <= BUILTINS_LOCATION)
1090 loc_t2 = loc2;
1092 location_t loc = loc_t1 <= BUILTINS_LOCATION ? loc_t2 : loc_t1;
1094 /* It is a quite common bug to reference anonymous namespace type in
1095 non-anonymous namespace class. */
1096 if ((type_with_linkage_p (t1) && type_in_anonymous_namespace_p (t1))
1097 || (type_with_linkage_p (t2) && type_in_anonymous_namespace_p (t2)))
1099 if (type_with_linkage_p (t1) && !type_in_anonymous_namespace_p (t1))
1101 std::swap (t1, t2);
1102 std::swap (loc_t1, loc_t2);
1104 gcc_assert (TYPE_NAME (t1) && TYPE_NAME (t2)
1105 && TREE_CODE (TYPE_NAME (t1)) == TYPE_DECL
1106 && TREE_CODE (TYPE_NAME (t2)) == TYPE_DECL);
1107 /* Most of the time, the type names will match, do not be unnecesarily
1108 verbose. */
1109 if (IDENTIFIER_POINTER (DECL_NAME (TYPE_NAME (t1)))
1110 != IDENTIFIER_POINTER (DECL_NAME (TYPE_NAME (t2))))
1111 inform (loc_t1,
1112 "type %qT defined in anonymous namespace can not match "
1113 "type %qT across the translation unit boundary",
1114 t1, t2);
1115 else
1116 inform (loc_t1,
1117 "type %qT defined in anonymous namespace can not match "
1118 "across the translation unit boundary",
1119 t1);
1120 if (loc_t2_useful)
1121 inform (loc_t2,
1122 "the incompatible type defined in another translation unit");
1123 return;
1125 /* If types have mangled ODR names and they are different, it is most
1126 informative to output those.
1127 This also covers types defined in different namespaces. */
1128 if (TYPE_NAME (t1) && TYPE_NAME (t2)
1129 && TREE_CODE (TYPE_NAME (t1)) == TYPE_DECL
1130 && TREE_CODE (TYPE_NAME (t2)) == TYPE_DECL
1131 && DECL_ASSEMBLER_NAME_SET_P (TYPE_NAME (t1))
1132 && DECL_ASSEMBLER_NAME_SET_P (TYPE_NAME (t2))
1133 && DECL_ASSEMBLER_NAME (TYPE_NAME (t1))
1134 != DECL_ASSEMBLER_NAME (TYPE_NAME (t2)))
1136 char *name1 = xstrdup (cplus_demangle
1137 (IDENTIFIER_POINTER (DECL_ASSEMBLER_NAME (TYPE_NAME (t1))),
1138 DMGL_PARAMS | DMGL_ANSI | DMGL_TYPES));
1139 char *name2 = cplus_demangle
1140 (IDENTIFIER_POINTER (DECL_ASSEMBLER_NAME (TYPE_NAME (t2))),
1141 DMGL_PARAMS | DMGL_ANSI | DMGL_TYPES);
1142 if (name1 && name2 && strcmp (name1, name2))
1144 inform (loc_t1,
1145 "type name %qs should match type name %qs",
1146 name1, name2);
1147 if (loc_t2_useful)
1148 inform (loc_t2,
1149 "the incompatible type is defined here");
1150 free (name1);
1151 return;
1153 free (name1);
1155 /* A tricky case are compound types. Often they appear the same in source
1156 code and the mismatch is dragged in by type they are build from.
1157 Look for those differences in subtypes and try to be informative. In other
1158 cases just output nothing because the source code is probably different
1159 and in this case we already output a all necessary info. */
1160 if (!TYPE_NAME (t1) || !TYPE_NAME (t2))
1162 if (TREE_CODE (t1) == TREE_CODE (t2))
1164 if (TREE_CODE (t1) == ARRAY_TYPE
1165 && COMPLETE_TYPE_P (t1) && COMPLETE_TYPE_P (t2))
1167 tree i1 = TYPE_DOMAIN (t1);
1168 tree i2 = TYPE_DOMAIN (t2);
1170 if (i1 && i2
1171 && TYPE_MAX_VALUE (i1)
1172 && TYPE_MAX_VALUE (i2)
1173 && !operand_equal_p (TYPE_MAX_VALUE (i1),
1174 TYPE_MAX_VALUE (i2), 0))
1176 inform (loc,
1177 "array types have different bounds");
1178 return;
1181 if ((POINTER_TYPE_P (t1) || TREE_CODE (t1) == ARRAY_TYPE)
1182 && type_mismatch_p (TREE_TYPE (t1), TREE_TYPE (t2)))
1183 warn_types_mismatch (TREE_TYPE (t1), TREE_TYPE (t2), loc_t1, loc_t2);
1184 else if (TREE_CODE (t1) == METHOD_TYPE
1185 || TREE_CODE (t1) == FUNCTION_TYPE)
1187 tree parms1 = NULL, parms2 = NULL;
1188 int count = 1;
1190 if (type_mismatch_p (TREE_TYPE (t1), TREE_TYPE (t2)))
1192 inform (loc, "return value type mismatch");
1193 warn_types_mismatch (TREE_TYPE (t1), TREE_TYPE (t2), loc_t1,
1194 loc_t2);
1195 return;
1197 if (prototype_p (t1) && prototype_p (t2))
1198 for (parms1 = TYPE_ARG_TYPES (t1), parms2 = TYPE_ARG_TYPES (t2);
1199 parms1 && parms2;
1200 parms1 = TREE_CHAIN (parms1), parms2 = TREE_CHAIN (parms2),
1201 count++)
1203 if (type_mismatch_p (TREE_VALUE (parms1), TREE_VALUE (parms2)))
1205 if (count == 1 && TREE_CODE (t1) == METHOD_TYPE)
1206 inform (loc,
1207 "implicit this pointer type mismatch");
1208 else
1209 inform (loc,
1210 "type mismatch in parameter %i",
1211 count - (TREE_CODE (t1) == METHOD_TYPE));
1212 warn_types_mismatch (TREE_VALUE (parms1),
1213 TREE_VALUE (parms2),
1214 loc_t1, loc_t2);
1215 return;
1218 if (parms1 || parms2)
1220 inform (loc,
1221 "types have different parameter counts");
1222 return;
1226 return;
1229 if (types_odr_comparable (t1, t2, true)
1230 && types_same_for_odr (t1, t2, true))
1231 inform (loc_t1,
1232 "type %qT itself violates the C++ One Definition Rule", t1);
1233 /* Prevent pointless warnings like "struct aa" should match "struct aa". */
1234 else if (TYPE_NAME (t1) == TYPE_NAME (t2)
1235 && TREE_CODE (t1) == TREE_CODE (t2) && !loc_t2_useful)
1236 return;
1237 else
1238 inform (loc_t1, "type %qT should match type %qT",
1239 t1, t2);
1240 if (loc_t2_useful)
1241 inform (loc_t2, "the incompatible type is defined here");
1244 /* Compare T1 and T2, report ODR violations if WARN is true and set
1245 WARNED to true if anything is reported. Return true if types match.
1246 If true is returned, the types are also compatible in the sense of
1247 gimple_canonical_types_compatible_p.
1248 If LOC1 and LOC2 is not UNKNOWN_LOCATION it may be used to output a warning
1249 about the type if the type itself do not have location. */
1251 static bool
1252 odr_types_equivalent_p (tree t1, tree t2, bool warn, bool *warned,
1253 hash_set<type_pair> *visited,
1254 location_t loc1, location_t loc2)
1256 /* Check first for the obvious case of pointer identity. */
1257 if (t1 == t2)
1258 return true;
1259 gcc_assert (!type_with_linkage_p (t1) || !type_in_anonymous_namespace_p (t1));
1260 gcc_assert (!type_with_linkage_p (t2) || !type_in_anonymous_namespace_p (t2));
1262 /* Can't be the same type if the types don't have the same code. */
1263 if (TREE_CODE (t1) != TREE_CODE (t2))
1265 warn_odr (t1, t2, NULL, NULL, warn, warned,
1266 G_("a different type is defined in another translation unit"));
1267 return false;
1270 if (TYPE_QUALS (t1) != TYPE_QUALS (t2))
1272 warn_odr (t1, t2, NULL, NULL, warn, warned,
1273 G_("a type with different qualifiers is defined in another "
1274 "translation unit"));
1275 return false;
1278 if ((type_with_linkage_p (t1) && type_in_anonymous_namespace_p (t1))
1279 || (type_with_linkage_p (t2) && type_in_anonymous_namespace_p (t2)))
1281 /* We can not trip this when comparing ODR types, only when trying to
1282 match different ODR derivations from different declarations.
1283 So WARN should be always false. */
1284 gcc_assert (!warn);
1285 return false;
1288 if (comp_type_attributes (t1, t2) != 1)
1290 warn_odr (t1, t2, NULL, NULL, warn, warned,
1291 G_("a type with different attributes "
1292 "is defined in another translation unit"));
1293 return false;
1296 if (TREE_CODE (t1) == ENUMERAL_TYPE
1297 && TYPE_VALUES (t1) && TYPE_VALUES (t2))
1299 tree v1, v2;
1300 for (v1 = TYPE_VALUES (t1), v2 = TYPE_VALUES (t2);
1301 v1 && v2 ; v1 = TREE_CHAIN (v1), v2 = TREE_CHAIN (v2))
1303 if (TREE_PURPOSE (v1) != TREE_PURPOSE (v2))
1305 warn_odr (t1, t2, NULL, NULL, warn, warned,
1306 G_("an enum with different value name"
1307 " is defined in another translation unit"));
1308 return false;
1310 if (TREE_VALUE (v1) != TREE_VALUE (v2)
1311 && !operand_equal_p (DECL_INITIAL (TREE_VALUE (v1)),
1312 DECL_INITIAL (TREE_VALUE (v2)), 0))
1314 warn_odr (t1, t2, NULL, NULL, warn, warned,
1315 G_("an enum with different values is defined"
1316 " in another translation unit"));
1317 return false;
1320 if (v1 || v2)
1322 warn_odr (t1, t2, NULL, NULL, warn, warned,
1323 G_("an enum with mismatching number of values "
1324 "is defined in another translation unit"));
1325 return false;
1329 /* Non-aggregate types can be handled cheaply. */
1330 if (INTEGRAL_TYPE_P (t1)
1331 || SCALAR_FLOAT_TYPE_P (t1)
1332 || FIXED_POINT_TYPE_P (t1)
1333 || TREE_CODE (t1) == VECTOR_TYPE
1334 || TREE_CODE (t1) == COMPLEX_TYPE
1335 || TREE_CODE (t1) == OFFSET_TYPE
1336 || POINTER_TYPE_P (t1))
1338 if (TYPE_PRECISION (t1) != TYPE_PRECISION (t2))
1340 warn_odr (t1, t2, NULL, NULL, warn, warned,
1341 G_("a type with different precision is defined "
1342 "in another translation unit"));
1343 return false;
1345 if (TYPE_UNSIGNED (t1) != TYPE_UNSIGNED (t2))
1347 warn_odr (t1, t2, NULL, NULL, warn, warned,
1348 G_("a type with different signedness is defined "
1349 "in another translation unit"));
1350 return false;
1353 if (TREE_CODE (t1) == INTEGER_TYPE
1354 && TYPE_STRING_FLAG (t1) != TYPE_STRING_FLAG (t2))
1356 /* char WRT uint_8? */
1357 warn_odr (t1, t2, NULL, NULL, warn, warned,
1358 G_("a different type is defined in another "
1359 "translation unit"));
1360 return false;
1363 /* For canonical type comparisons we do not want to build SCCs
1364 so we cannot compare pointed-to types. But we can, for now,
1365 require the same pointed-to type kind and match what
1366 useless_type_conversion_p would do. */
1367 if (POINTER_TYPE_P (t1))
1369 if (TYPE_ADDR_SPACE (TREE_TYPE (t1))
1370 != TYPE_ADDR_SPACE (TREE_TYPE (t2)))
1372 warn_odr (t1, t2, NULL, NULL, warn, warned,
1373 G_("it is defined as a pointer in different address "
1374 "space in another translation unit"));
1375 return false;
1378 if (!odr_subtypes_equivalent_p (TREE_TYPE (t1), TREE_TYPE (t2),
1379 visited, loc1, loc2))
1381 warn_odr (t1, t2, NULL, NULL, warn, warned,
1382 G_("it is defined as a pointer to different type "
1383 "in another translation unit"));
1384 if (warn && warned)
1385 warn_types_mismatch (TREE_TYPE (t1), TREE_TYPE (t2),
1386 loc1, loc2);
1387 return false;
1391 if ((TREE_CODE (t1) == VECTOR_TYPE || TREE_CODE (t1) == COMPLEX_TYPE)
1392 && !odr_subtypes_equivalent_p (TREE_TYPE (t1), TREE_TYPE (t2),
1393 visited, loc1, loc2))
1395 /* Probably specific enough. */
1396 warn_odr (t1, t2, NULL, NULL, warn, warned,
1397 G_("a different type is defined "
1398 "in another translation unit"));
1399 if (warn && warned)
1400 warn_types_mismatch (TREE_TYPE (t1), TREE_TYPE (t2), loc1, loc2);
1401 return false;
1404 /* Do type-specific comparisons. */
1405 else switch (TREE_CODE (t1))
1407 case ARRAY_TYPE:
1409 /* Array types are the same if the element types are the same and
1410 the number of elements are the same. */
1411 if (!odr_subtypes_equivalent_p (TREE_TYPE (t1), TREE_TYPE (t2),
1412 visited, loc1, loc2))
1414 warn_odr (t1, t2, NULL, NULL, warn, warned,
1415 G_("a different type is defined in another "
1416 "translation unit"));
1417 if (warn && warned)
1418 warn_types_mismatch (TREE_TYPE (t1), TREE_TYPE (t2), loc1, loc2);
1420 gcc_assert (TYPE_STRING_FLAG (t1) == TYPE_STRING_FLAG (t2));
1421 gcc_assert (TYPE_NONALIASED_COMPONENT (t1)
1422 == TYPE_NONALIASED_COMPONENT (t2));
1424 tree i1 = TYPE_DOMAIN (t1);
1425 tree i2 = TYPE_DOMAIN (t2);
1427 /* For an incomplete external array, the type domain can be
1428 NULL_TREE. Check this condition also. */
1429 if (i1 == NULL_TREE || i2 == NULL_TREE)
1430 return true;
1432 tree min1 = TYPE_MIN_VALUE (i1);
1433 tree min2 = TYPE_MIN_VALUE (i2);
1434 tree max1 = TYPE_MAX_VALUE (i1);
1435 tree max2 = TYPE_MAX_VALUE (i2);
1437 /* In C++, minimums should be always 0. */
1438 gcc_assert (min1 == min2);
1439 if (!operand_equal_p (max1, max2, 0))
1441 warn_odr (t1, t2, NULL, NULL, warn, warned,
1442 G_("an array of different size is defined "
1443 "in another translation unit"));
1444 return false;
1447 break;
1449 case METHOD_TYPE:
1450 case FUNCTION_TYPE:
1451 /* Function types are the same if the return type and arguments types
1452 are the same. */
1453 if (!odr_subtypes_equivalent_p (TREE_TYPE (t1), TREE_TYPE (t2),
1454 visited, loc1, loc2))
1456 warn_odr (t1, t2, NULL, NULL, warn, warned,
1457 G_("has different return value "
1458 "in another translation unit"));
1459 if (warn && warned)
1460 warn_types_mismatch (TREE_TYPE (t1), TREE_TYPE (t2), loc1, loc2);
1461 return false;
1464 if (TYPE_ARG_TYPES (t1) == TYPE_ARG_TYPES (t2)
1465 || !prototype_p (t1) || !prototype_p (t2))
1466 return true;
1467 else
1469 tree parms1, parms2;
1471 for (parms1 = TYPE_ARG_TYPES (t1), parms2 = TYPE_ARG_TYPES (t2);
1472 parms1 && parms2;
1473 parms1 = TREE_CHAIN (parms1), parms2 = TREE_CHAIN (parms2))
1475 if (!odr_subtypes_equivalent_p
1476 (TREE_VALUE (parms1), TREE_VALUE (parms2), visited,
1477 loc1, loc2))
1479 warn_odr (t1, t2, NULL, NULL, warn, warned,
1480 G_("has different parameters in another "
1481 "translation unit"));
1482 if (warn && warned)
1483 warn_types_mismatch (TREE_VALUE (parms1),
1484 TREE_VALUE (parms2), loc1, loc2);
1485 return false;
1489 if (parms1 || parms2)
1491 warn_odr (t1, t2, NULL, NULL, warn, warned,
1492 G_("has different parameters "
1493 "in another translation unit"));
1494 return false;
1497 return true;
1500 case RECORD_TYPE:
1501 case UNION_TYPE:
1502 case QUAL_UNION_TYPE:
1504 tree f1, f2;
1506 /* For aggregate types, all the fields must be the same. */
1507 if (COMPLETE_TYPE_P (t1) && COMPLETE_TYPE_P (t2))
1509 if (TYPE_BINFO (t1) && TYPE_BINFO (t2)
1510 && polymorphic_type_binfo_p (TYPE_BINFO (t1))
1511 != polymorphic_type_binfo_p (TYPE_BINFO (t2)))
1513 if (polymorphic_type_binfo_p (TYPE_BINFO (t1)))
1514 warn_odr (t1, t2, NULL, NULL, warn, warned,
1515 G_("a type defined in another translation unit "
1516 "is not polymorphic"));
1517 else
1518 warn_odr (t1, t2, NULL, NULL, warn, warned,
1519 G_("a type defined in another translation unit "
1520 "is polymorphic"));
1521 return false;
1523 for (f1 = TYPE_FIELDS (t1), f2 = TYPE_FIELDS (t2);
1524 f1 || f2;
1525 f1 = TREE_CHAIN (f1), f2 = TREE_CHAIN (f2))
1527 /* Skip non-fields. */
1528 while (f1 && TREE_CODE (f1) != FIELD_DECL)
1529 f1 = TREE_CHAIN (f1);
1530 while (f2 && TREE_CODE (f2) != FIELD_DECL)
1531 f2 = TREE_CHAIN (f2);
1532 if (!f1 || !f2)
1533 break;
1534 if (DECL_VIRTUAL_P (f1) != DECL_VIRTUAL_P (f2))
1536 warn_odr (t1, t2, NULL, NULL, warn, warned,
1537 G_("a type with different virtual table pointers"
1538 " is defined in another translation unit"));
1539 return false;
1541 if (DECL_ARTIFICIAL (f1) != DECL_ARTIFICIAL (f2))
1543 warn_odr (t1, t2, NULL, NULL, warn, warned,
1544 G_("a type with different bases is defined "
1545 "in another translation unit"));
1546 return false;
1548 if (DECL_NAME (f1) != DECL_NAME (f2)
1549 && !DECL_ARTIFICIAL (f1))
1551 warn_odr (t1, t2, f1, f2, warn, warned,
1552 G_("a field with different name is defined "
1553 "in another translation unit"));
1554 return false;
1556 if (!odr_subtypes_equivalent_p (TREE_TYPE (f1),
1557 TREE_TYPE (f2), visited,
1558 loc1, loc2))
1560 /* Do not warn about artificial fields and just go into
1561 generic field mismatch warning. */
1562 if (DECL_ARTIFICIAL (f1))
1563 break;
1565 warn_odr (t1, t2, f1, f2, warn, warned,
1566 G_("a field of same name but different type "
1567 "is defined in another translation unit"));
1568 if (warn && warned)
1569 warn_types_mismatch (TREE_TYPE (f1), TREE_TYPE (f2), loc1, loc2);
1570 return false;
1572 if (!gimple_compare_field_offset (f1, f2))
1574 /* Do not warn about artificial fields and just go into
1575 generic field mismatch warning. */
1576 if (DECL_ARTIFICIAL (f1))
1577 break;
1578 warn_odr (t1, t2, f1, f2, warn, warned,
1579 G_("fields have different layout "
1580 "in another translation unit"));
1581 return false;
1583 if (DECL_BIT_FIELD (f1) != DECL_BIT_FIELD (f2))
1585 warn_odr (t1, t2, f1, f2, warn, warned,
1586 G_("one field is bitfield while other is not"));
1587 return false;
1589 else
1590 gcc_assert (DECL_NONADDRESSABLE_P (f1)
1591 == DECL_NONADDRESSABLE_P (f2));
1594 /* If one aggregate has more fields than the other, they
1595 are not the same. */
1596 if (f1 || f2)
1598 if ((f1 && DECL_VIRTUAL_P (f1)) || (f2 && DECL_VIRTUAL_P (f2)))
1599 warn_odr (t1, t2, NULL, NULL, warn, warned,
1600 G_("a type with different virtual table pointers"
1601 " is defined in another translation unit"));
1602 else if ((f1 && DECL_ARTIFICIAL (f1))
1603 || (f2 && DECL_ARTIFICIAL (f2)))
1604 warn_odr (t1, t2, NULL, NULL, warn, warned,
1605 G_("a type with different bases is defined "
1606 "in another translation unit"));
1607 else
1608 warn_odr (t1, t2, f1, f2, warn, warned,
1609 G_("a type with different number of fields "
1610 "is defined in another translation unit"));
1612 return false;
1615 break;
1617 case VOID_TYPE:
1618 case NULLPTR_TYPE:
1619 break;
1621 default:
1622 debug_tree (t1);
1623 gcc_unreachable ();
1626 /* Those are better to come last as they are utterly uninformative. */
1627 if (TYPE_SIZE (t1) && TYPE_SIZE (t2)
1628 && !operand_equal_p (TYPE_SIZE (t1), TYPE_SIZE (t2), 0))
1630 warn_odr (t1, t2, NULL, NULL, warn, warned,
1631 G_("a type with different size "
1632 "is defined in another translation unit"));
1633 return false;
1635 if (COMPLETE_TYPE_P (t1) && COMPLETE_TYPE_P (t2)
1636 && TYPE_ALIGN (t1) != TYPE_ALIGN (t2))
1638 warn_odr (t1, t2, NULL, NULL, warn, warned,
1639 G_("a type with different alignment "
1640 "is defined in another translation unit"));
1641 return false;
1643 gcc_assert (!TYPE_SIZE_UNIT (t1) || !TYPE_SIZE_UNIT (t2)
1644 || operand_equal_p (TYPE_SIZE_UNIT (t1),
1645 TYPE_SIZE_UNIT (t2), 0));
1646 return true;
1649 /* Return true if TYPE1 and TYPE2 are equivalent for One Definition Rule. */
1651 bool
1652 odr_types_equivalent_p (tree type1, tree type2)
1654 gcc_checking_assert (odr_or_derived_type_p (type1)
1655 && odr_or_derived_type_p (type2));
1657 hash_set<type_pair> visited;
1658 return odr_types_equivalent_p (type1, type2, false, NULL,
1659 &visited, UNKNOWN_LOCATION, UNKNOWN_LOCATION);
1662 /* TYPE is equivalent to VAL by ODR, but its tree representation differs
1663 from VAL->type. This may happen in LTO where tree merging did not merge
1664 all variants of the same type or due to ODR violation.
1666 Analyze and report ODR violations and add type to duplicate list.
1667 If TYPE is more specified than VAL->type, prevail VAL->type. Also if
1668 this is first time we see definition of a class return true so the
1669 base types are analyzed. */
1671 static bool
1672 add_type_duplicate (odr_type val, tree type)
1674 bool build_bases = false;
1675 bool prevail = false;
1676 bool odr_must_violate = false;
1678 if (!val->types_set)
1679 val->types_set = new hash_set<tree>;
1681 /* Chose polymorphic type as leader (this happens only in case of ODR
1682 violations. */
1683 if ((TREE_CODE (type) == RECORD_TYPE && TYPE_BINFO (type)
1684 && polymorphic_type_binfo_p (TYPE_BINFO (type)))
1685 && (TREE_CODE (val->type) != RECORD_TYPE || !TYPE_BINFO (val->type)
1686 || !polymorphic_type_binfo_p (TYPE_BINFO (val->type))))
1688 prevail = true;
1689 build_bases = true;
1691 /* Always prefer complete type to be the leader. */
1692 else if (!COMPLETE_TYPE_P (val->type) && COMPLETE_TYPE_P (type))
1694 prevail = true;
1695 build_bases = TYPE_BINFO (type);
1697 else if (COMPLETE_TYPE_P (val->type) && !COMPLETE_TYPE_P (type))
1699 else if (TREE_CODE (val->type) == ENUMERAL_TYPE
1700 && TREE_CODE (type) == ENUMERAL_TYPE
1701 && !TYPE_VALUES (val->type) && TYPE_VALUES (type))
1702 prevail = true;
1703 else if (TREE_CODE (val->type) == RECORD_TYPE
1704 && TREE_CODE (type) == RECORD_TYPE
1705 && TYPE_BINFO (type) && !TYPE_BINFO (val->type))
1707 gcc_assert (!val->bases.length ());
1708 build_bases = true;
1709 prevail = true;
1712 if (prevail)
1713 std::swap (val->type, type);
1715 val->types_set->add (type);
1717 /* If we now have a mangled name, be sure to record it to val->type
1718 so ODR hash can work. */
1720 if (can_be_name_hashed_p (type) && !can_be_name_hashed_p (val->type))
1721 SET_DECL_ASSEMBLER_NAME (TYPE_NAME (val->type),
1722 DECL_ASSEMBLER_NAME (TYPE_NAME (type)));
1724 bool merge = true;
1725 bool base_mismatch = false;
1726 unsigned int i;
1727 bool warned = false;
1728 hash_set<type_pair> visited;
1730 gcc_assert (in_lto_p);
1731 vec_safe_push (val->types, type);
1733 /* If both are class types, compare the bases. */
1734 if (COMPLETE_TYPE_P (type) && COMPLETE_TYPE_P (val->type)
1735 && TREE_CODE (val->type) == RECORD_TYPE
1736 && TREE_CODE (type) == RECORD_TYPE
1737 && TYPE_BINFO (val->type) && TYPE_BINFO (type))
1739 if (BINFO_N_BASE_BINFOS (TYPE_BINFO (type))
1740 != BINFO_N_BASE_BINFOS (TYPE_BINFO (val->type)))
1742 if (!flag_ltrans && !warned && !val->odr_violated)
1744 tree extra_base;
1745 warn_odr (type, val->type, NULL, NULL, !warned, &warned,
1746 "a type with the same name but different "
1747 "number of polymorphic bases is "
1748 "defined in another translation unit");
1749 if (warned)
1751 if (BINFO_N_BASE_BINFOS (TYPE_BINFO (type))
1752 > BINFO_N_BASE_BINFOS (TYPE_BINFO (val->type)))
1753 extra_base = BINFO_BASE_BINFO
1754 (TYPE_BINFO (type),
1755 BINFO_N_BASE_BINFOS (TYPE_BINFO (val->type)));
1756 else
1757 extra_base = BINFO_BASE_BINFO
1758 (TYPE_BINFO (val->type),
1759 BINFO_N_BASE_BINFOS (TYPE_BINFO (type)));
1760 tree extra_base_type = BINFO_TYPE (extra_base);
1761 inform (DECL_SOURCE_LOCATION (TYPE_NAME (extra_base_type)),
1762 "the extra base is defined here");
1765 base_mismatch = true;
1767 else
1768 for (i = 0; i < BINFO_N_BASE_BINFOS (TYPE_BINFO (type)); i++)
1770 tree base1 = BINFO_BASE_BINFO (TYPE_BINFO (type), i);
1771 tree base2 = BINFO_BASE_BINFO (TYPE_BINFO (val->type), i);
1772 tree type1 = BINFO_TYPE (base1);
1773 tree type2 = BINFO_TYPE (base2);
1775 if (types_odr_comparable (type1, type2))
1777 if (!types_same_for_odr (type1, type2))
1778 base_mismatch = true;
1780 else
1781 if (!odr_types_equivalent_p (type1, type2))
1782 base_mismatch = true;
1783 if (base_mismatch)
1785 if (!warned && !val->odr_violated)
1787 warn_odr (type, val->type, NULL, NULL,
1788 !warned, &warned,
1789 "a type with the same name but different base "
1790 "type is defined in another translation unit");
1791 if (warned)
1792 warn_types_mismatch (type1, type2,
1793 UNKNOWN_LOCATION, UNKNOWN_LOCATION);
1795 break;
1797 if (BINFO_OFFSET (base1) != BINFO_OFFSET (base2))
1799 base_mismatch = true;
1800 if (!warned && !val->odr_violated)
1801 warn_odr (type, val->type, NULL, NULL,
1802 !warned, &warned,
1803 "a type with the same name but different base "
1804 "layout is defined in another translation unit");
1805 break;
1807 /* One of bases is not of complete type. */
1808 if (!TYPE_BINFO (type1) != !TYPE_BINFO (type2))
1810 /* If we have a polymorphic type info specified for TYPE1
1811 but not for TYPE2 we possibly missed a base when recording
1812 VAL->type earlier.
1813 Be sure this does not happen. */
1814 if (TYPE_BINFO (type1)
1815 && polymorphic_type_binfo_p (TYPE_BINFO (type1))
1816 && !build_bases)
1817 odr_must_violate = true;
1818 break;
1820 /* One base is polymorphic and the other not.
1821 This ought to be diagnosed earlier, but do not ICE in the
1822 checking bellow. */
1823 else if (TYPE_BINFO (type1)
1824 && polymorphic_type_binfo_p (TYPE_BINFO (type1))
1825 != polymorphic_type_binfo_p (TYPE_BINFO (type2)))
1827 if (!warned && !val->odr_violated)
1828 warn_odr (type, val->type, NULL, NULL,
1829 !warned, &warned,
1830 "a base of the type is polymorphic only in one "
1831 "translation unit");
1832 base_mismatch = true;
1833 break;
1836 if (base_mismatch)
1838 merge = false;
1839 odr_violation_reported = true;
1840 val->odr_violated = true;
1842 if (symtab->dump_file)
1844 fprintf (symtab->dump_file, "ODR base violation\n");
1846 print_node (symtab->dump_file, "", val->type, 0);
1847 putc ('\n',symtab->dump_file);
1848 print_node (symtab->dump_file, "", type, 0);
1849 putc ('\n',symtab->dump_file);
1854 /* Next compare memory layout.
1855 The DECL_SOURCE_LOCATIONs in this invocation came from LTO streaming.
1856 We must apply the location cache to ensure that they are valid
1857 before we can pass them to odr_types_equivalent_p (PR lto/83121). */
1858 if (lto_location_cache::current_cache)
1859 lto_location_cache::current_cache->apply_location_cache ();
1860 if (!odr_types_equivalent_p (val->type, type,
1861 !flag_ltrans && !val->odr_violated && !warned,
1862 &warned, &visited,
1863 DECL_SOURCE_LOCATION (TYPE_NAME (val->type)),
1864 DECL_SOURCE_LOCATION (TYPE_NAME (type))))
1866 merge = false;
1867 odr_violation_reported = true;
1868 val->odr_violated = true;
1870 gcc_assert (val->odr_violated || !odr_must_violate);
1871 /* Sanity check that all bases will be build same way again. */
1872 if (flag_checking
1873 && COMPLETE_TYPE_P (type) && COMPLETE_TYPE_P (val->type)
1874 && TREE_CODE (val->type) == RECORD_TYPE
1875 && TREE_CODE (type) == RECORD_TYPE
1876 && TYPE_BINFO (val->type) && TYPE_BINFO (type)
1877 && !val->odr_violated
1878 && !base_mismatch && val->bases.length ())
1880 unsigned int num_poly_bases = 0;
1881 unsigned int j;
1883 for (i = 0; i < BINFO_N_BASE_BINFOS (TYPE_BINFO (type)); i++)
1884 if (polymorphic_type_binfo_p (BINFO_BASE_BINFO
1885 (TYPE_BINFO (type), i)))
1886 num_poly_bases++;
1887 gcc_assert (num_poly_bases == val->bases.length ());
1888 for (j = 0, i = 0; i < BINFO_N_BASE_BINFOS (TYPE_BINFO (type));
1889 i++)
1890 if (polymorphic_type_binfo_p (BINFO_BASE_BINFO
1891 (TYPE_BINFO (type), i)))
1893 odr_type base = get_odr_type
1894 (BINFO_TYPE
1895 (BINFO_BASE_BINFO (TYPE_BINFO (type),
1896 i)),
1897 true);
1898 gcc_assert (val->bases[j] == base);
1899 j++;
1904 /* Regularize things a little. During LTO same types may come with
1905 different BINFOs. Either because their virtual table was
1906 not merged by tree merging and only later at decl merging or
1907 because one type comes with external vtable, while other
1908 with internal. We want to merge equivalent binfos to conserve
1909 memory and streaming overhead.
1911 The external vtables are more harmful: they contain references
1912 to external declarations of methods that may be defined in the
1913 merged LTO unit. For this reason we absolutely need to remove
1914 them and replace by internal variants. Not doing so will lead
1915 to incomplete answers from possible_polymorphic_call_targets.
1917 FIXME: disable for now; because ODR types are now build during
1918 streaming in, the variants do not need to be linked to the type,
1919 yet. We need to do the merging in cleanup pass to be implemented
1920 soon. */
1921 if (!flag_ltrans && merge
1922 && 0
1923 && TREE_CODE (val->type) == RECORD_TYPE
1924 && TREE_CODE (type) == RECORD_TYPE
1925 && TYPE_BINFO (val->type) && TYPE_BINFO (type)
1926 && TYPE_MAIN_VARIANT (type) == type
1927 && TYPE_MAIN_VARIANT (val->type) == val->type
1928 && BINFO_VTABLE (TYPE_BINFO (val->type))
1929 && BINFO_VTABLE (TYPE_BINFO (type)))
1931 tree master_binfo = TYPE_BINFO (val->type);
1932 tree v1 = BINFO_VTABLE (master_binfo);
1933 tree v2 = BINFO_VTABLE (TYPE_BINFO (type));
1935 if (TREE_CODE (v1) == POINTER_PLUS_EXPR)
1937 gcc_assert (TREE_CODE (v2) == POINTER_PLUS_EXPR
1938 && operand_equal_p (TREE_OPERAND (v1, 1),
1939 TREE_OPERAND (v2, 1), 0));
1940 v1 = TREE_OPERAND (TREE_OPERAND (v1, 0), 0);
1941 v2 = TREE_OPERAND (TREE_OPERAND (v2, 0), 0);
1943 gcc_assert (DECL_ASSEMBLER_NAME (v1)
1944 == DECL_ASSEMBLER_NAME (v2));
1946 if (DECL_EXTERNAL (v1) && !DECL_EXTERNAL (v2))
1948 unsigned int i;
1950 set_type_binfo (val->type, TYPE_BINFO (type));
1951 for (i = 0; i < val->types->length (); i++)
1953 if (TYPE_BINFO ((*val->types)[i])
1954 == master_binfo)
1955 set_type_binfo ((*val->types)[i], TYPE_BINFO (type));
1957 BINFO_TYPE (TYPE_BINFO (type)) = val->type;
1959 else
1960 set_type_binfo (type, master_binfo);
1962 return build_bases;
1965 /* Get ODR type hash entry for TYPE. If INSERT is true, create
1966 possibly new entry. */
1968 odr_type
1969 get_odr_type (tree type, bool insert)
1971 odr_type_d **slot = NULL;
1972 odr_type_d **vtable_slot = NULL;
1973 odr_type val = NULL;
1974 hashval_t hash;
1975 bool build_bases = false;
1976 bool insert_to_odr_array = false;
1977 int base_id = -1;
1979 type = main_odr_variant (type);
1981 gcc_checking_assert (can_be_name_hashed_p (type)
1982 || can_be_vtable_hashed_p (type));
1984 /* Lookup entry, first try name hash, fallback to vtable hash. */
1985 if (can_be_name_hashed_p (type))
1987 hash = hash_odr_name (type);
1988 slot = odr_hash->find_slot_with_hash (type, hash,
1989 insert ? INSERT : NO_INSERT);
1991 if ((!slot || !*slot) && in_lto_p && can_be_vtable_hashed_p (type))
1993 hash = hash_odr_vtable (type);
1994 vtable_slot = odr_vtable_hash->find_slot_with_hash (type, hash,
1995 insert ? INSERT : NO_INSERT);
1998 if (!slot && !vtable_slot)
1999 return NULL;
2001 /* See if we already have entry for type. */
2002 if ((slot && *slot) || (vtable_slot && *vtable_slot))
2004 if (slot && *slot)
2006 val = *slot;
2007 if (flag_checking
2008 && in_lto_p && can_be_vtable_hashed_p (type))
2010 hash = hash_odr_vtable (type);
2011 vtable_slot = odr_vtable_hash->find_slot_with_hash (type, hash,
2012 NO_INSERT);
2013 gcc_assert (!vtable_slot || *vtable_slot == *slot);
2014 vtable_slot = NULL;
2017 else if (*vtable_slot)
2018 val = *vtable_slot;
2020 if (val->type != type
2021 && (!val->types_set || !val->types_set->add (type)))
2023 gcc_assert (insert);
2024 /* We have type duplicate, but it may introduce vtable name or
2025 mangled name; be sure to keep hashes in sync. */
2026 if (in_lto_p && can_be_vtable_hashed_p (type)
2027 && (!vtable_slot || !*vtable_slot))
2029 if (!vtable_slot)
2031 hash = hash_odr_vtable (type);
2032 vtable_slot = odr_vtable_hash->find_slot_with_hash
2033 (type, hash, INSERT);
2034 gcc_checking_assert (!*vtable_slot || *vtable_slot == val);
2036 *vtable_slot = val;
2038 if (slot && !*slot)
2039 *slot = val;
2040 build_bases = add_type_duplicate (val, type);
2043 else
2045 val = ggc_cleared_alloc<odr_type_d> ();
2046 val->type = type;
2047 val->bases = vNULL;
2048 val->derived_types = vNULL;
2049 if (type_with_linkage_p (type))
2050 val->anonymous_namespace = type_in_anonymous_namespace_p (type);
2051 else
2052 val->anonymous_namespace = 0;
2053 build_bases = COMPLETE_TYPE_P (val->type);
2054 insert_to_odr_array = true;
2055 if (slot)
2056 *slot = val;
2057 if (vtable_slot)
2058 *vtable_slot = val;
2061 if (build_bases && TREE_CODE (type) == RECORD_TYPE && TYPE_BINFO (type)
2062 && type_with_linkage_p (type)
2063 && type == TYPE_MAIN_VARIANT (type))
2065 tree binfo = TYPE_BINFO (type);
2066 unsigned int i;
2068 gcc_assert (BINFO_TYPE (TYPE_BINFO (val->type)) == type);
2070 val->all_derivations_known = type_all_derivations_known_p (type);
2071 for (i = 0; i < BINFO_N_BASE_BINFOS (binfo); i++)
2072 /* For now record only polymorphic types. other are
2073 pointless for devirtualization and we can not precisely
2074 determine ODR equivalency of these during LTO. */
2075 if (polymorphic_type_binfo_p (BINFO_BASE_BINFO (binfo, i)))
2077 tree base_type= BINFO_TYPE (BINFO_BASE_BINFO (binfo, i));
2078 odr_type base = get_odr_type (base_type, true);
2079 gcc_assert (TYPE_MAIN_VARIANT (base_type) == base_type);
2080 base->derived_types.safe_push (val);
2081 val->bases.safe_push (base);
2082 if (base->id > base_id)
2083 base_id = base->id;
2086 /* Ensure that type always appears after bases. */
2087 if (insert_to_odr_array)
2089 if (odr_types_ptr)
2090 val->id = odr_types.length ();
2091 vec_safe_push (odr_types_ptr, val);
2093 else if (base_id > val->id)
2095 odr_types[val->id] = 0;
2096 /* Be sure we did not recorded any derived types; these may need
2097 renumbering too. */
2098 gcc_assert (val->derived_types.length() == 0);
2099 val->id = odr_types.length ();
2100 vec_safe_push (odr_types_ptr, val);
2102 return val;
2105 /* Add TYPE od ODR type hash. */
2107 void
2108 register_odr_type (tree type)
2110 if (!odr_hash)
2112 odr_hash = new odr_hash_type (23);
2113 if (in_lto_p)
2114 odr_vtable_hash = new odr_vtable_hash_type (23);
2116 /* Arrange things to be nicer and insert main variants first.
2117 ??? fundamental prerecorded types do not have mangled names; this
2118 makes it possible that non-ODR type is main_odr_variant of ODR type.
2119 Things may get smoother if LTO FE set mangled name of those types same
2120 way as C++ FE does. */
2121 if (odr_type_p (main_odr_variant (TYPE_MAIN_VARIANT (type)))
2122 && odr_type_p (TYPE_MAIN_VARIANT (type)))
2123 get_odr_type (TYPE_MAIN_VARIANT (type), true);
2124 if (TYPE_MAIN_VARIANT (type) != type && odr_type_p (main_odr_variant (type)))
2125 get_odr_type (type, true);
2128 /* Return true if type is known to have no derivations. */
2130 bool
2131 type_known_to_have_no_derivations_p (tree t)
2133 return (type_all_derivations_known_p (t)
2134 && (TYPE_FINAL_P (t)
2135 || (odr_hash
2136 && !get_odr_type (t, true)->derived_types.length())));
2139 /* Dump ODR type T and all its derived types. INDENT specifies indentation for
2140 recursive printing. */
2142 static void
2143 dump_odr_type (FILE *f, odr_type t, int indent=0)
2145 unsigned int i;
2146 fprintf (f, "%*s type %i: ", indent * 2, "", t->id);
2147 print_generic_expr (f, t->type, TDF_SLIM);
2148 fprintf (f, "%s", t->anonymous_namespace ? " (anonymous namespace)":"");
2149 fprintf (f, "%s\n", t->all_derivations_known ? " (derivations known)":"");
2150 if (TYPE_NAME (t->type))
2152 /*fprintf (f, "%*s defined at: %s:%i\n", indent * 2, "",
2153 DECL_SOURCE_FILE (TYPE_NAME (t->type)),
2154 DECL_SOURCE_LINE (TYPE_NAME (t->type)));*/
2155 if (DECL_ASSEMBLER_NAME_SET_P (TYPE_NAME (t->type)))
2156 fprintf (f, "%*s mangled name: %s\n", indent * 2, "",
2157 IDENTIFIER_POINTER
2158 (DECL_ASSEMBLER_NAME (TYPE_NAME (t->type))));
2160 if (t->bases.length ())
2162 fprintf (f, "%*s base odr type ids: ", indent * 2, "");
2163 for (i = 0; i < t->bases.length (); i++)
2164 fprintf (f, " %i", t->bases[i]->id);
2165 fprintf (f, "\n");
2167 if (t->derived_types.length ())
2169 fprintf (f, "%*s derived types:\n", indent * 2, "");
2170 for (i = 0; i < t->derived_types.length (); i++)
2171 dump_odr_type (f, t->derived_types[i], indent + 1);
2173 fprintf (f, "\n");
2176 /* Dump the type inheritance graph. */
2178 static void
2179 dump_type_inheritance_graph (FILE *f)
2181 unsigned int i;
2182 if (!odr_types_ptr)
2183 return;
2184 fprintf (f, "\n\nType inheritance graph:\n");
2185 for (i = 0; i < odr_types.length (); i++)
2187 if (odr_types[i] && odr_types[i]->bases.length () == 0)
2188 dump_odr_type (f, odr_types[i]);
2190 for (i = 0; i < odr_types.length (); i++)
2192 if (odr_types[i] && odr_types[i]->types && odr_types[i]->types->length ())
2194 unsigned int j;
2195 fprintf (f, "Duplicate tree types for odr type %i\n", i);
2196 print_node (f, "", odr_types[i]->type, 0);
2197 for (j = 0; j < odr_types[i]->types->length (); j++)
2199 tree t;
2200 fprintf (f, "duplicate #%i\n", j);
2201 print_node (f, "", (*odr_types[i]->types)[j], 0);
2202 t = (*odr_types[i]->types)[j];
2203 while (TYPE_P (t) && TYPE_CONTEXT (t))
2205 t = TYPE_CONTEXT (t);
2206 print_node (f, "", t, 0);
2208 putc ('\n',f);
2214 /* Initialize IPA devirt and build inheritance tree graph. */
2216 void
2217 build_type_inheritance_graph (void)
2219 struct symtab_node *n;
2220 FILE *inheritance_dump_file;
2221 dump_flags_t flags;
2223 if (odr_hash)
2224 return;
2225 timevar_push (TV_IPA_INHERITANCE);
2226 inheritance_dump_file = dump_begin (TDI_inheritance, &flags);
2227 odr_hash = new odr_hash_type (23);
2228 if (in_lto_p)
2229 odr_vtable_hash = new odr_vtable_hash_type (23);
2231 /* We reconstruct the graph starting of types of all methods seen in the
2232 unit. */
2233 FOR_EACH_SYMBOL (n)
2234 if (is_a <cgraph_node *> (n)
2235 && DECL_VIRTUAL_P (n->decl)
2236 && n->real_symbol_p ())
2237 get_odr_type (TYPE_METHOD_BASETYPE (TREE_TYPE (n->decl)), true);
2239 /* Look also for virtual tables of types that do not define any methods.
2241 We need it in a case where class B has virtual base of class A
2242 re-defining its virtual method and there is class C with no virtual
2243 methods with B as virtual base.
2245 Here we output B's virtual method in two variant - for non-virtual
2246 and virtual inheritance. B's virtual table has non-virtual version,
2247 while C's has virtual.
2249 For this reason we need to know about C in order to include both
2250 variants of B. More correctly, record_target_from_binfo should
2251 add both variants of the method when walking B, but we have no
2252 link in between them.
2254 We rely on fact that either the method is exported and thus we
2255 assume it is called externally or C is in anonymous namespace and
2256 thus we will see the vtable. */
2258 else if (is_a <varpool_node *> (n)
2259 && DECL_VIRTUAL_P (n->decl)
2260 && TREE_CODE (DECL_CONTEXT (n->decl)) == RECORD_TYPE
2261 && TYPE_BINFO (DECL_CONTEXT (n->decl))
2262 && polymorphic_type_binfo_p (TYPE_BINFO (DECL_CONTEXT (n->decl))))
2263 get_odr_type (TYPE_MAIN_VARIANT (DECL_CONTEXT (n->decl)), true);
2264 if (inheritance_dump_file)
2266 dump_type_inheritance_graph (inheritance_dump_file);
2267 dump_end (TDI_inheritance, inheritance_dump_file);
2269 timevar_pop (TV_IPA_INHERITANCE);
2272 /* Return true if N has reference from live virtual table
2273 (and thus can be a destination of polymorphic call).
2274 Be conservatively correct when callgraph is not built or
2275 if the method may be referred externally. */
2277 static bool
2278 referenced_from_vtable_p (struct cgraph_node *node)
2280 int i;
2281 struct ipa_ref *ref;
2282 bool found = false;
2284 if (node->externally_visible
2285 || DECL_EXTERNAL (node->decl)
2286 || node->used_from_other_partition)
2287 return true;
2289 /* Keep this test constant time.
2290 It is unlikely this can happen except for the case where speculative
2291 devirtualization introduced many speculative edges to this node.
2292 In this case the target is very likely alive anyway. */
2293 if (node->ref_list.referring.length () > 100)
2294 return true;
2296 /* We need references built. */
2297 if (symtab->state <= CONSTRUCTION)
2298 return true;
2300 for (i = 0; node->iterate_referring (i, ref); i++)
2301 if ((ref->use == IPA_REF_ALIAS
2302 && referenced_from_vtable_p (dyn_cast<cgraph_node *> (ref->referring)))
2303 || (ref->use == IPA_REF_ADDR
2304 && VAR_P (ref->referring->decl)
2305 && DECL_VIRTUAL_P (ref->referring->decl)))
2307 found = true;
2308 break;
2310 return found;
2313 /* Return if TARGET is cxa_pure_virtual. */
2315 static bool
2316 is_cxa_pure_virtual_p (tree target)
2318 return target && TREE_CODE (TREE_TYPE (target)) != METHOD_TYPE
2319 && DECL_NAME (target)
2320 && id_equal (DECL_NAME (target),
2321 "__cxa_pure_virtual");
2324 /* If TARGET has associated node, record it in the NODES array.
2325 CAN_REFER specify if program can refer to the target directly.
2326 if TARGET is unknown (NULL) or it can not be inserted (for example because
2327 its body was already removed and there is no way to refer to it), clear
2328 COMPLETEP. */
2330 static void
2331 maybe_record_node (vec <cgraph_node *> &nodes,
2332 tree target, hash_set<tree> *inserted,
2333 bool can_refer,
2334 bool *completep)
2336 struct cgraph_node *target_node, *alias_target;
2337 enum availability avail;
2338 bool pure_virtual = is_cxa_pure_virtual_p (target);
2340 /* __builtin_unreachable do not need to be added into
2341 list of targets; the runtime effect of calling them is undefined.
2342 Only "real" virtual methods should be accounted. */
2343 if (target && TREE_CODE (TREE_TYPE (target)) != METHOD_TYPE && !pure_virtual)
2344 return;
2346 if (!can_refer)
2348 /* The only case when method of anonymous namespace becomes unreferable
2349 is when we completely optimized it out. */
2350 if (flag_ltrans
2351 || !target
2352 || !type_in_anonymous_namespace_p (DECL_CONTEXT (target)))
2353 *completep = false;
2354 return;
2357 if (!target)
2358 return;
2360 target_node = cgraph_node::get (target);
2362 /* Prefer alias target over aliases, so we do not get confused by
2363 fake duplicates. */
2364 if (target_node)
2366 alias_target = target_node->ultimate_alias_target (&avail);
2367 if (target_node != alias_target
2368 && avail >= AVAIL_AVAILABLE
2369 && target_node->get_availability ())
2370 target_node = alias_target;
2373 /* Method can only be called by polymorphic call if any
2374 of vtables referring to it are alive.
2376 While this holds for non-anonymous functions, too, there are
2377 cases where we want to keep them in the list; for example
2378 inline functions with -fno-weak are static, but we still
2379 may devirtualize them when instance comes from other unit.
2380 The same holds for LTO.
2382 Currently we ignore these functions in speculative devirtualization.
2383 ??? Maybe it would make sense to be more aggressive for LTO even
2384 elsewhere. */
2385 if (!flag_ltrans
2386 && !pure_virtual
2387 && type_in_anonymous_namespace_p (DECL_CONTEXT (target))
2388 && (!target_node
2389 || !referenced_from_vtable_p (target_node)))
2391 /* See if TARGET is useful function we can deal with. */
2392 else if (target_node != NULL
2393 && (TREE_PUBLIC (target)
2394 || DECL_EXTERNAL (target)
2395 || target_node->definition)
2396 && target_node->real_symbol_p ())
2398 gcc_assert (!target_node->global.inlined_to);
2399 gcc_assert (target_node->real_symbol_p ());
2400 /* When sanitizing, do not assume that __cxa_pure_virtual is not called
2401 by valid program. */
2402 if (flag_sanitize & SANITIZE_UNREACHABLE)
2404 /* Only add pure virtual if it is the only possible target. This way
2405 we will preserve the diagnostics about pure virtual called in many
2406 cases without disabling optimization in other. */
2407 else if (pure_virtual)
2409 if (nodes.length ())
2410 return;
2412 /* If we found a real target, take away cxa_pure_virtual. */
2413 else if (!pure_virtual && nodes.length () == 1
2414 && is_cxa_pure_virtual_p (nodes[0]->decl))
2415 nodes.pop ();
2416 if (pure_virtual && nodes.length ())
2417 return;
2418 if (!inserted->add (target))
2420 cached_polymorphic_call_targets->add (target_node);
2421 nodes.safe_push (target_node);
2424 else if (!completep)
2426 /* We have definition of __cxa_pure_virtual that is not accessible (it is
2427 optimized out or partitioned to other unit) so we can not add it. When
2428 not sanitizing, there is nothing to do.
2429 Otherwise declare the list incomplete. */
2430 else if (pure_virtual)
2432 if (flag_sanitize & SANITIZE_UNREACHABLE)
2433 *completep = false;
2435 else if (flag_ltrans
2436 || !type_in_anonymous_namespace_p (DECL_CONTEXT (target)))
2437 *completep = false;
2440 /* See if BINFO's type matches OUTER_TYPE. If so, look up
2441 BINFO of subtype of OTR_TYPE at OFFSET and in that BINFO find
2442 method in vtable and insert method to NODES array
2443 or BASES_TO_CONSIDER if this array is non-NULL.
2444 Otherwise recurse to base BINFOs.
2445 This matches what get_binfo_at_offset does, but with offset
2446 being unknown.
2448 TYPE_BINFOS is a stack of BINFOS of types with defined
2449 virtual table seen on way from class type to BINFO.
2451 MATCHED_VTABLES tracks virtual tables we already did lookup
2452 for virtual function in. INSERTED tracks nodes we already
2453 inserted.
2455 ANONYMOUS is true if BINFO is part of anonymous namespace.
2457 Clear COMPLETEP when we hit unreferable target.
2460 static void
2461 record_target_from_binfo (vec <cgraph_node *> &nodes,
2462 vec <tree> *bases_to_consider,
2463 tree binfo,
2464 tree otr_type,
2465 vec <tree> &type_binfos,
2466 HOST_WIDE_INT otr_token,
2467 tree outer_type,
2468 HOST_WIDE_INT offset,
2469 hash_set<tree> *inserted,
2470 hash_set<tree> *matched_vtables,
2471 bool anonymous,
2472 bool *completep)
2474 tree type = BINFO_TYPE (binfo);
2475 int i;
2476 tree base_binfo;
2479 if (BINFO_VTABLE (binfo))
2480 type_binfos.safe_push (binfo);
2481 if (types_same_for_odr (type, outer_type))
2483 int i;
2484 tree type_binfo = NULL;
2486 /* Look up BINFO with virtual table. For normal types it is always last
2487 binfo on stack. */
2488 for (i = type_binfos.length () - 1; i >= 0; i--)
2489 if (BINFO_OFFSET (type_binfos[i]) == BINFO_OFFSET (binfo))
2491 type_binfo = type_binfos[i];
2492 break;
2494 if (BINFO_VTABLE (binfo))
2495 type_binfos.pop ();
2496 /* If this is duplicated BINFO for base shared by virtual inheritance,
2497 we may not have its associated vtable. This is not a problem, since
2498 we will walk it on the other path. */
2499 if (!type_binfo)
2500 return;
2501 tree inner_binfo = get_binfo_at_offset (type_binfo,
2502 offset, otr_type);
2503 if (!inner_binfo)
2505 gcc_assert (odr_violation_reported);
2506 return;
2508 /* For types in anonymous namespace first check if the respective vtable
2509 is alive. If not, we know the type can't be called. */
2510 if (!flag_ltrans && anonymous)
2512 tree vtable = BINFO_VTABLE (inner_binfo);
2513 varpool_node *vnode;
2515 if (TREE_CODE (vtable) == POINTER_PLUS_EXPR)
2516 vtable = TREE_OPERAND (TREE_OPERAND (vtable, 0), 0);
2517 vnode = varpool_node::get (vtable);
2518 if (!vnode || !vnode->definition)
2519 return;
2521 gcc_assert (inner_binfo);
2522 if (bases_to_consider
2523 ? !matched_vtables->contains (BINFO_VTABLE (inner_binfo))
2524 : !matched_vtables->add (BINFO_VTABLE (inner_binfo)))
2526 bool can_refer;
2527 tree target = gimple_get_virt_method_for_binfo (otr_token,
2528 inner_binfo,
2529 &can_refer);
2530 if (!bases_to_consider)
2531 maybe_record_node (nodes, target, inserted, can_refer, completep);
2532 /* Destructors are never called via construction vtables. */
2533 else if (!target || !DECL_CXX_DESTRUCTOR_P (target))
2534 bases_to_consider->safe_push (target);
2536 return;
2539 /* Walk bases. */
2540 for (i = 0; BINFO_BASE_ITERATE (binfo, i, base_binfo); i++)
2541 /* Walking bases that have no virtual method is pointless exercise. */
2542 if (polymorphic_type_binfo_p (base_binfo))
2543 record_target_from_binfo (nodes, bases_to_consider, base_binfo, otr_type,
2544 type_binfos,
2545 otr_token, outer_type, offset, inserted,
2546 matched_vtables, anonymous, completep);
2547 if (BINFO_VTABLE (binfo))
2548 type_binfos.pop ();
2551 /* Look up virtual methods matching OTR_TYPE (with OFFSET and OTR_TOKEN)
2552 of TYPE, insert them to NODES, recurse into derived nodes.
2553 INSERTED is used to avoid duplicate insertions of methods into NODES.
2554 MATCHED_VTABLES are used to avoid duplicate walking vtables.
2555 Clear COMPLETEP if unreferable target is found.
2557 If CONSIDER_CONSTRUCTION is true, record to BASES_TO_CONSIDER
2558 all cases where BASE_SKIPPED is true (because the base is abstract
2559 class). */
2561 static void
2562 possible_polymorphic_call_targets_1 (vec <cgraph_node *> &nodes,
2563 hash_set<tree> *inserted,
2564 hash_set<tree> *matched_vtables,
2565 tree otr_type,
2566 odr_type type,
2567 HOST_WIDE_INT otr_token,
2568 tree outer_type,
2569 HOST_WIDE_INT offset,
2570 bool *completep,
2571 vec <tree> &bases_to_consider,
2572 bool consider_construction)
2574 tree binfo = TYPE_BINFO (type->type);
2575 unsigned int i;
2576 auto_vec <tree, 8> type_binfos;
2577 bool possibly_instantiated = type_possibly_instantiated_p (type->type);
2579 /* We may need to consider types w/o instances because of possible derived
2580 types using their methods either directly or via construction vtables.
2581 We are safe to skip them when all derivations are known, since we will
2582 handle them later.
2583 This is done by recording them to BASES_TO_CONSIDER array. */
2584 if (possibly_instantiated || consider_construction)
2586 record_target_from_binfo (nodes,
2587 (!possibly_instantiated
2588 && type_all_derivations_known_p (type->type))
2589 ? &bases_to_consider : NULL,
2590 binfo, otr_type, type_binfos, otr_token,
2591 outer_type, offset,
2592 inserted, matched_vtables,
2593 type->anonymous_namespace, completep);
2595 for (i = 0; i < type->derived_types.length (); i++)
2596 possible_polymorphic_call_targets_1 (nodes, inserted,
2597 matched_vtables,
2598 otr_type,
2599 type->derived_types[i],
2600 otr_token, outer_type, offset, completep,
2601 bases_to_consider, consider_construction);
2604 /* Cache of queries for polymorphic call targets.
2606 Enumerating all call targets may get expensive when there are many
2607 polymorphic calls in the program, so we memoize all the previous
2608 queries and avoid duplicated work. */
2610 struct polymorphic_call_target_d
2612 HOST_WIDE_INT otr_token;
2613 ipa_polymorphic_call_context context;
2614 odr_type type;
2615 vec <cgraph_node *> targets;
2616 tree decl_warning;
2617 int type_warning;
2618 bool complete;
2619 bool speculative;
2622 /* Polymorphic call target cache helpers. */
2624 struct polymorphic_call_target_hasher
2625 : pointer_hash <polymorphic_call_target_d>
2627 static inline hashval_t hash (const polymorphic_call_target_d *);
2628 static inline bool equal (const polymorphic_call_target_d *,
2629 const polymorphic_call_target_d *);
2630 static inline void remove (polymorphic_call_target_d *);
2633 /* Return the computed hashcode for ODR_QUERY. */
2635 inline hashval_t
2636 polymorphic_call_target_hasher::hash (const polymorphic_call_target_d *odr_query)
2638 inchash::hash hstate (odr_query->otr_token);
2640 hstate.add_hwi (odr_query->type->id);
2641 hstate.merge_hash (TYPE_UID (odr_query->context.outer_type));
2642 hstate.add_hwi (odr_query->context.offset);
2644 if (odr_query->context.speculative_outer_type)
2646 hstate.merge_hash (TYPE_UID (odr_query->context.speculative_outer_type));
2647 hstate.add_hwi (odr_query->context.speculative_offset);
2649 hstate.add_flag (odr_query->speculative);
2650 hstate.add_flag (odr_query->context.maybe_in_construction);
2651 hstate.add_flag (odr_query->context.maybe_derived_type);
2652 hstate.add_flag (odr_query->context.speculative_maybe_derived_type);
2653 hstate.commit_flag ();
2654 return hstate.end ();
2657 /* Compare cache entries T1 and T2. */
2659 inline bool
2660 polymorphic_call_target_hasher::equal (const polymorphic_call_target_d *t1,
2661 const polymorphic_call_target_d *t2)
2663 return (t1->type == t2->type && t1->otr_token == t2->otr_token
2664 && t1->speculative == t2->speculative
2665 && t1->context.offset == t2->context.offset
2666 && t1->context.speculative_offset == t2->context.speculative_offset
2667 && t1->context.outer_type == t2->context.outer_type
2668 && t1->context.speculative_outer_type == t2->context.speculative_outer_type
2669 && t1->context.maybe_in_construction
2670 == t2->context.maybe_in_construction
2671 && t1->context.maybe_derived_type == t2->context.maybe_derived_type
2672 && (t1->context.speculative_maybe_derived_type
2673 == t2->context.speculative_maybe_derived_type));
2676 /* Remove entry in polymorphic call target cache hash. */
2678 inline void
2679 polymorphic_call_target_hasher::remove (polymorphic_call_target_d *v)
2681 v->targets.release ();
2682 free (v);
2685 /* Polymorphic call target query cache. */
2687 typedef hash_table<polymorphic_call_target_hasher>
2688 polymorphic_call_target_hash_type;
2689 static polymorphic_call_target_hash_type *polymorphic_call_target_hash;
2691 /* Destroy polymorphic call target query cache. */
2693 static void
2694 free_polymorphic_call_targets_hash ()
2696 if (cached_polymorphic_call_targets)
2698 delete polymorphic_call_target_hash;
2699 polymorphic_call_target_hash = NULL;
2700 delete cached_polymorphic_call_targets;
2701 cached_polymorphic_call_targets = NULL;
2705 /* Force rebuilding type inheritance graph from scratch.
2706 This is use to make sure that we do not keep references to types
2707 which was not visible to free_lang_data. */
2709 void
2710 rebuild_type_inheritance_graph ()
2712 if (!odr_hash)
2713 return;
2714 delete odr_hash;
2715 if (in_lto_p)
2716 delete odr_vtable_hash;
2717 odr_hash = NULL;
2718 odr_vtable_hash = NULL;
2719 odr_types_ptr = NULL;
2720 free_polymorphic_call_targets_hash ();
2723 /* When virtual function is removed, we may need to flush the cache. */
2725 static void
2726 devirt_node_removal_hook (struct cgraph_node *n, void *d ATTRIBUTE_UNUSED)
2728 if (cached_polymorphic_call_targets
2729 && cached_polymorphic_call_targets->contains (n))
2730 free_polymorphic_call_targets_hash ();
2733 /* Look up base of BINFO that has virtual table VTABLE with OFFSET. */
2735 tree
2736 subbinfo_with_vtable_at_offset (tree binfo, unsigned HOST_WIDE_INT offset,
2737 tree vtable)
2739 tree v = BINFO_VTABLE (binfo);
2740 int i;
2741 tree base_binfo;
2742 unsigned HOST_WIDE_INT this_offset;
2744 if (v)
2746 if (!vtable_pointer_value_to_vtable (v, &v, &this_offset))
2747 gcc_unreachable ();
2749 if (offset == this_offset
2750 && DECL_ASSEMBLER_NAME (v) == DECL_ASSEMBLER_NAME (vtable))
2751 return binfo;
2754 for (i = 0; BINFO_BASE_ITERATE (binfo, i, base_binfo); i++)
2755 if (polymorphic_type_binfo_p (base_binfo))
2757 base_binfo = subbinfo_with_vtable_at_offset (base_binfo, offset, vtable);
2758 if (base_binfo)
2759 return base_binfo;
2761 return NULL;
2764 /* T is known constant value of virtual table pointer.
2765 Store virtual table to V and its offset to OFFSET.
2766 Return false if T does not look like virtual table reference. */
2768 bool
2769 vtable_pointer_value_to_vtable (const_tree t, tree *v,
2770 unsigned HOST_WIDE_INT *offset)
2772 /* We expect &MEM[(void *)&virtual_table + 16B].
2773 We obtain object's BINFO from the context of the virtual table.
2774 This one contains pointer to virtual table represented via
2775 POINTER_PLUS_EXPR. Verify that this pointer matches what
2776 we propagated through.
2778 In the case of virtual inheritance, the virtual tables may
2779 be nested, i.e. the offset may be different from 16 and we may
2780 need to dive into the type representation. */
2781 if (TREE_CODE (t) == ADDR_EXPR
2782 && TREE_CODE (TREE_OPERAND (t, 0)) == MEM_REF
2783 && TREE_CODE (TREE_OPERAND (TREE_OPERAND (t, 0), 0)) == ADDR_EXPR
2784 && TREE_CODE (TREE_OPERAND (TREE_OPERAND (t, 0), 1)) == INTEGER_CST
2785 && (TREE_CODE (TREE_OPERAND (TREE_OPERAND (TREE_OPERAND (t, 0), 0), 0))
2786 == VAR_DECL)
2787 && DECL_VIRTUAL_P (TREE_OPERAND (TREE_OPERAND
2788 (TREE_OPERAND (t, 0), 0), 0)))
2790 *v = TREE_OPERAND (TREE_OPERAND (TREE_OPERAND (t, 0), 0), 0);
2791 *offset = tree_to_uhwi (TREE_OPERAND (TREE_OPERAND (t, 0), 1));
2792 return true;
2795 /* Alternative representation, used by C++ frontend is POINTER_PLUS_EXPR.
2796 We need to handle it when T comes from static variable initializer or
2797 BINFO. */
2798 if (TREE_CODE (t) == POINTER_PLUS_EXPR)
2800 *offset = tree_to_uhwi (TREE_OPERAND (t, 1));
2801 t = TREE_OPERAND (t, 0);
2803 else
2804 *offset = 0;
2806 if (TREE_CODE (t) != ADDR_EXPR)
2807 return false;
2808 *v = TREE_OPERAND (t, 0);
2809 return true;
2812 /* T is known constant value of virtual table pointer. Return BINFO of the
2813 instance type. */
2815 tree
2816 vtable_pointer_value_to_binfo (const_tree t)
2818 tree vtable;
2819 unsigned HOST_WIDE_INT offset;
2821 if (!vtable_pointer_value_to_vtable (t, &vtable, &offset))
2822 return NULL_TREE;
2824 /* FIXME: for stores of construction vtables we return NULL,
2825 because we do not have BINFO for those. Eventually we should fix
2826 our representation to allow this case to be handled, too.
2827 In the case we see store of BINFO we however may assume
2828 that standard folding will be able to cope with it. */
2829 return subbinfo_with_vtable_at_offset (TYPE_BINFO (DECL_CONTEXT (vtable)),
2830 offset, vtable);
2833 /* Walk bases of OUTER_TYPE that contain OTR_TYPE at OFFSET.
2834 Look up their respective virtual methods for OTR_TOKEN and OTR_TYPE
2835 and insert them in NODES.
2837 MATCHED_VTABLES and INSERTED is used to avoid duplicated work. */
2839 static void
2840 record_targets_from_bases (tree otr_type,
2841 HOST_WIDE_INT otr_token,
2842 tree outer_type,
2843 HOST_WIDE_INT offset,
2844 vec <cgraph_node *> &nodes,
2845 hash_set<tree> *inserted,
2846 hash_set<tree> *matched_vtables,
2847 bool *completep)
2849 while (true)
2851 HOST_WIDE_INT pos, size;
2852 tree base_binfo;
2853 tree fld;
2855 if (types_same_for_odr (outer_type, otr_type))
2856 return;
2858 for (fld = TYPE_FIELDS (outer_type); fld; fld = DECL_CHAIN (fld))
2860 if (TREE_CODE (fld) != FIELD_DECL)
2861 continue;
2863 pos = int_bit_position (fld);
2864 size = tree_to_shwi (DECL_SIZE (fld));
2865 if (pos <= offset && (pos + size) > offset
2866 /* Do not get confused by zero sized bases. */
2867 && polymorphic_type_binfo_p (TYPE_BINFO (TREE_TYPE (fld))))
2868 break;
2870 /* Within a class type we should always find corresponding fields. */
2871 gcc_assert (fld && TREE_CODE (TREE_TYPE (fld)) == RECORD_TYPE);
2873 /* Nonbase types should have been stripped by outer_class_type. */
2874 gcc_assert (DECL_ARTIFICIAL (fld));
2876 outer_type = TREE_TYPE (fld);
2877 offset -= pos;
2879 base_binfo = get_binfo_at_offset (TYPE_BINFO (outer_type),
2880 offset, otr_type);
2881 if (!base_binfo)
2883 gcc_assert (odr_violation_reported);
2884 return;
2886 gcc_assert (base_binfo);
2887 if (!matched_vtables->add (BINFO_VTABLE (base_binfo)))
2889 bool can_refer;
2890 tree target = gimple_get_virt_method_for_binfo (otr_token,
2891 base_binfo,
2892 &can_refer);
2893 if (!target || ! DECL_CXX_DESTRUCTOR_P (target))
2894 maybe_record_node (nodes, target, inserted, can_refer, completep);
2895 matched_vtables->add (BINFO_VTABLE (base_binfo));
2900 /* When virtual table is removed, we may need to flush the cache. */
2902 static void
2903 devirt_variable_node_removal_hook (varpool_node *n,
2904 void *d ATTRIBUTE_UNUSED)
2906 if (cached_polymorphic_call_targets
2907 && DECL_VIRTUAL_P (n->decl)
2908 && type_in_anonymous_namespace_p (DECL_CONTEXT (n->decl)))
2909 free_polymorphic_call_targets_hash ();
2912 /* Record about how many calls would benefit from given type to be final. */
2914 struct odr_type_warn_count
2916 tree type;
2917 int count;
2918 profile_count dyn_count;
2921 /* Record about how many calls would benefit from given method to be final. */
2923 struct decl_warn_count
2925 tree decl;
2926 int count;
2927 profile_count dyn_count;
2930 /* Information about type and decl warnings. */
2932 struct final_warning_record
2934 /* If needed grow type_warnings vector and initialize new decl_warn_count
2935 to have dyn_count set to profile_count::zero (). */
2936 void grow_type_warnings (unsigned newlen);
2938 profile_count dyn_count;
2939 auto_vec<odr_type_warn_count> type_warnings;
2940 hash_map<tree, decl_warn_count> decl_warnings;
2943 void
2944 final_warning_record::grow_type_warnings (unsigned newlen)
2946 unsigned len = type_warnings.length ();
2947 if (newlen > len)
2949 type_warnings.safe_grow_cleared (newlen);
2950 for (unsigned i = len; i < newlen; i++)
2951 type_warnings[i].dyn_count = profile_count::zero ();
2955 struct final_warning_record *final_warning_records;
2957 /* Return vector containing possible targets of polymorphic call of type
2958 OTR_TYPE calling method OTR_TOKEN within type of OTR_OUTER_TYPE and OFFSET.
2959 If INCLUDE_BASES is true, walk also base types of OUTER_TYPES containing
2960 OTR_TYPE and include their virtual method. This is useful for types
2961 possibly in construction or destruction where the virtual table may
2962 temporarily change to one of base types. INCLUDE_DERIVER_TYPES make
2963 us to walk the inheritance graph for all derivations.
2965 If COMPLETEP is non-NULL, store true if the list is complete.
2966 CACHE_TOKEN (if non-NULL) will get stored to an unique ID of entry
2967 in the target cache. If user needs to visit every target list
2968 just once, it can memoize them.
2970 If SPECULATIVE is set, the list will not contain targets that
2971 are not speculatively taken.
2973 Returned vector is placed into cache. It is NOT caller's responsibility
2974 to free it. The vector can be freed on cgraph_remove_node call if
2975 the particular node is a virtual function present in the cache. */
2977 vec <cgraph_node *>
2978 possible_polymorphic_call_targets (tree otr_type,
2979 HOST_WIDE_INT otr_token,
2980 ipa_polymorphic_call_context context,
2981 bool *completep,
2982 void **cache_token,
2983 bool speculative)
2985 static struct cgraph_node_hook_list *node_removal_hook_holder;
2986 vec <cgraph_node *> nodes = vNULL;
2987 auto_vec <tree, 8> bases_to_consider;
2988 odr_type type, outer_type;
2989 polymorphic_call_target_d key;
2990 polymorphic_call_target_d **slot;
2991 unsigned int i;
2992 tree binfo, target;
2993 bool complete;
2994 bool can_refer = false;
2995 bool skipped = false;
2997 otr_type = TYPE_MAIN_VARIANT (otr_type);
2999 /* If ODR is not initialized or the context is invalid, return empty
3000 incomplete list. */
3001 if (!odr_hash || context.invalid || !TYPE_BINFO (otr_type))
3003 if (completep)
3004 *completep = context.invalid;
3005 if (cache_token)
3006 *cache_token = NULL;
3007 return nodes;
3010 /* Do not bother to compute speculative info when user do not asks for it. */
3011 if (!speculative || !context.speculative_outer_type)
3012 context.clear_speculation ();
3014 type = get_odr_type (otr_type, true);
3016 /* Recording type variants would waste results cache. */
3017 gcc_assert (!context.outer_type
3018 || TYPE_MAIN_VARIANT (context.outer_type) == context.outer_type);
3020 /* Look up the outer class type we want to walk.
3021 If we fail to do so, the context is invalid. */
3022 if ((context.outer_type || context.speculative_outer_type)
3023 && !context.restrict_to_inner_class (otr_type))
3025 if (completep)
3026 *completep = true;
3027 if (cache_token)
3028 *cache_token = NULL;
3029 return nodes;
3031 gcc_assert (!context.invalid);
3033 /* Check that restrict_to_inner_class kept the main variant. */
3034 gcc_assert (!context.outer_type
3035 || TYPE_MAIN_VARIANT (context.outer_type) == context.outer_type);
3037 /* We canonicalize our query, so we do not need extra hashtable entries. */
3039 /* Without outer type, we have no use for offset. Just do the
3040 basic search from inner type. */
3041 if (!context.outer_type)
3042 context.clear_outer_type (otr_type);
3043 /* We need to update our hierarchy if the type does not exist. */
3044 outer_type = get_odr_type (context.outer_type, true);
3045 /* If the type is complete, there are no derivations. */
3046 if (TYPE_FINAL_P (outer_type->type))
3047 context.maybe_derived_type = false;
3049 /* Initialize query cache. */
3050 if (!cached_polymorphic_call_targets)
3052 cached_polymorphic_call_targets = new hash_set<cgraph_node *>;
3053 polymorphic_call_target_hash
3054 = new polymorphic_call_target_hash_type (23);
3055 if (!node_removal_hook_holder)
3057 node_removal_hook_holder =
3058 symtab->add_cgraph_removal_hook (&devirt_node_removal_hook, NULL);
3059 symtab->add_varpool_removal_hook (&devirt_variable_node_removal_hook,
3060 NULL);
3064 if (in_lto_p)
3066 if (context.outer_type != otr_type)
3067 context.outer_type
3068 = get_odr_type (context.outer_type, true)->type;
3069 if (context.speculative_outer_type)
3070 context.speculative_outer_type
3071 = get_odr_type (context.speculative_outer_type, true)->type;
3074 /* Look up cached answer. */
3075 key.type = type;
3076 key.otr_token = otr_token;
3077 key.speculative = speculative;
3078 key.context = context;
3079 slot = polymorphic_call_target_hash->find_slot (&key, INSERT);
3080 if (cache_token)
3081 *cache_token = (void *)*slot;
3082 if (*slot)
3084 if (completep)
3085 *completep = (*slot)->complete;
3086 if ((*slot)->type_warning && final_warning_records)
3088 final_warning_records->type_warnings[(*slot)->type_warning - 1].count++;
3089 if (!final_warning_records->type_warnings
3090 [(*slot)->type_warning - 1].dyn_count.initialized_p ())
3091 final_warning_records->type_warnings
3092 [(*slot)->type_warning - 1].dyn_count = profile_count::zero ();
3093 if (final_warning_records->dyn_count > 0)
3094 final_warning_records->type_warnings[(*slot)->type_warning - 1].dyn_count
3095 = final_warning_records->type_warnings[(*slot)->type_warning - 1].dyn_count
3096 + final_warning_records->dyn_count;
3098 if (!speculative && (*slot)->decl_warning && final_warning_records)
3100 struct decl_warn_count *c =
3101 final_warning_records->decl_warnings.get ((*slot)->decl_warning);
3102 c->count++;
3103 if (final_warning_records->dyn_count > 0)
3104 c->dyn_count += final_warning_records->dyn_count;
3106 return (*slot)->targets;
3109 complete = true;
3111 /* Do actual search. */
3112 timevar_push (TV_IPA_VIRTUAL_CALL);
3113 *slot = XCNEW (polymorphic_call_target_d);
3114 if (cache_token)
3115 *cache_token = (void *)*slot;
3116 (*slot)->type = type;
3117 (*slot)->otr_token = otr_token;
3118 (*slot)->context = context;
3119 (*slot)->speculative = speculative;
3121 hash_set<tree> inserted;
3122 hash_set<tree> matched_vtables;
3124 /* First insert targets we speculatively identified as likely. */
3125 if (context.speculative_outer_type)
3127 odr_type speculative_outer_type;
3128 bool speculation_complete = true;
3130 /* First insert target from type itself and check if it may have
3131 derived types. */
3132 speculative_outer_type = get_odr_type (context.speculative_outer_type, true);
3133 if (TYPE_FINAL_P (speculative_outer_type->type))
3134 context.speculative_maybe_derived_type = false;
3135 binfo = get_binfo_at_offset (TYPE_BINFO (speculative_outer_type->type),
3136 context.speculative_offset, otr_type);
3137 if (binfo)
3138 target = gimple_get_virt_method_for_binfo (otr_token, binfo,
3139 &can_refer);
3140 else
3141 target = NULL;
3143 /* In the case we get complete method, we don't need
3144 to walk derivations. */
3145 if (target && DECL_FINAL_P (target))
3146 context.speculative_maybe_derived_type = false;
3147 if (type_possibly_instantiated_p (speculative_outer_type->type))
3148 maybe_record_node (nodes, target, &inserted, can_refer, &speculation_complete);
3149 if (binfo)
3150 matched_vtables.add (BINFO_VTABLE (binfo));
3153 /* Next walk recursively all derived types. */
3154 if (context.speculative_maybe_derived_type)
3155 for (i = 0; i < speculative_outer_type->derived_types.length(); i++)
3156 possible_polymorphic_call_targets_1 (nodes, &inserted,
3157 &matched_vtables,
3158 otr_type,
3159 speculative_outer_type->derived_types[i],
3160 otr_token, speculative_outer_type->type,
3161 context.speculative_offset,
3162 &speculation_complete,
3163 bases_to_consider,
3164 false);
3167 if (!speculative || !nodes.length ())
3169 /* First see virtual method of type itself. */
3170 binfo = get_binfo_at_offset (TYPE_BINFO (outer_type->type),
3171 context.offset, otr_type);
3172 if (binfo)
3173 target = gimple_get_virt_method_for_binfo (otr_token, binfo,
3174 &can_refer);
3175 else
3177 gcc_assert (odr_violation_reported);
3178 target = NULL;
3181 /* Destructors are never called through construction virtual tables,
3182 because the type is always known. */
3183 if (target && DECL_CXX_DESTRUCTOR_P (target))
3184 context.maybe_in_construction = false;
3186 if (target)
3188 /* In the case we get complete method, we don't need
3189 to walk derivations. */
3190 if (DECL_FINAL_P (target))
3191 context.maybe_derived_type = false;
3194 /* If OUTER_TYPE is abstract, we know we are not seeing its instance. */
3195 if (type_possibly_instantiated_p (outer_type->type))
3196 maybe_record_node (nodes, target, &inserted, can_refer, &complete);
3197 else
3198 skipped = true;
3200 if (binfo)
3201 matched_vtables.add (BINFO_VTABLE (binfo));
3203 /* Next walk recursively all derived types. */
3204 if (context.maybe_derived_type)
3206 for (i = 0; i < outer_type->derived_types.length(); i++)
3207 possible_polymorphic_call_targets_1 (nodes, &inserted,
3208 &matched_vtables,
3209 otr_type,
3210 outer_type->derived_types[i],
3211 otr_token, outer_type->type,
3212 context.offset, &complete,
3213 bases_to_consider,
3214 context.maybe_in_construction);
3216 if (!outer_type->all_derivations_known)
3218 if (!speculative && final_warning_records
3219 && nodes.length () == 1
3220 && TREE_CODE (TREE_TYPE (nodes[0]->decl)) == METHOD_TYPE)
3222 if (complete
3223 && warn_suggest_final_types
3224 && !outer_type->derived_types.length ())
3226 final_warning_records->grow_type_warnings
3227 (outer_type->id);
3228 final_warning_records->type_warnings[outer_type->id].count++;
3229 if (!final_warning_records->type_warnings
3230 [outer_type->id].dyn_count.initialized_p ())
3231 final_warning_records->type_warnings
3232 [outer_type->id].dyn_count = profile_count::zero ();
3233 final_warning_records->type_warnings[outer_type->id].dyn_count
3234 += final_warning_records->dyn_count;
3235 final_warning_records->type_warnings[outer_type->id].type
3236 = outer_type->type;
3237 (*slot)->type_warning = outer_type->id + 1;
3239 if (complete
3240 && warn_suggest_final_methods
3241 && types_same_for_odr (DECL_CONTEXT (nodes[0]->decl),
3242 outer_type->type))
3244 bool existed;
3245 struct decl_warn_count &c =
3246 final_warning_records->decl_warnings.get_or_insert
3247 (nodes[0]->decl, &existed);
3249 if (existed)
3251 c.count++;
3252 c.dyn_count += final_warning_records->dyn_count;
3254 else
3256 c.count = 1;
3257 c.dyn_count = final_warning_records->dyn_count;
3258 c.decl = nodes[0]->decl;
3260 (*slot)->decl_warning = nodes[0]->decl;
3263 complete = false;
3267 if (!speculative)
3269 /* Destructors are never called through construction virtual tables,
3270 because the type is always known. One of entries may be
3271 cxa_pure_virtual so look to at least two of them. */
3272 if (context.maybe_in_construction)
3273 for (i =0 ; i < MIN (nodes.length (), 2); i++)
3274 if (DECL_CXX_DESTRUCTOR_P (nodes[i]->decl))
3275 context.maybe_in_construction = false;
3276 if (context.maybe_in_construction)
3278 if (type != outer_type
3279 && (!skipped
3280 || (context.maybe_derived_type
3281 && !type_all_derivations_known_p (outer_type->type))))
3282 record_targets_from_bases (otr_type, otr_token, outer_type->type,
3283 context.offset, nodes, &inserted,
3284 &matched_vtables, &complete);
3285 if (skipped)
3286 maybe_record_node (nodes, target, &inserted, can_refer, &complete);
3287 for (i = 0; i < bases_to_consider.length(); i++)
3288 maybe_record_node (nodes, bases_to_consider[i], &inserted, can_refer, &complete);
3293 (*slot)->targets = nodes;
3294 (*slot)->complete = complete;
3295 if (completep)
3296 *completep = complete;
3298 timevar_pop (TV_IPA_VIRTUAL_CALL);
3299 return nodes;
3302 bool
3303 add_decl_warning (const tree &key ATTRIBUTE_UNUSED, const decl_warn_count &value,
3304 vec<const decl_warn_count*> *vec)
3306 vec->safe_push (&value);
3307 return true;
3310 /* Dump target list TARGETS into FILE. */
3312 static void
3313 dump_targets (FILE *f, vec <cgraph_node *> targets)
3315 unsigned int i;
3317 for (i = 0; i < targets.length (); i++)
3319 char *name = NULL;
3320 if (in_lto_p)
3321 name = cplus_demangle_v3 (targets[i]->asm_name (), 0);
3322 fprintf (f, " %s/%i", name ? name : targets[i]->name (),
3323 targets[i]->order);
3324 if (in_lto_p)
3325 free (name);
3326 if (!targets[i]->definition)
3327 fprintf (f, " (no definition%s)",
3328 DECL_DECLARED_INLINE_P (targets[i]->decl)
3329 ? " inline" : "");
3331 fprintf (f, "\n");
3334 /* Dump all possible targets of a polymorphic call. */
3336 void
3337 dump_possible_polymorphic_call_targets (FILE *f,
3338 tree otr_type,
3339 HOST_WIDE_INT otr_token,
3340 const ipa_polymorphic_call_context &ctx)
3342 vec <cgraph_node *> targets;
3343 bool final;
3344 odr_type type = get_odr_type (TYPE_MAIN_VARIANT (otr_type), false);
3345 unsigned int len;
3347 if (!type)
3348 return;
3349 targets = possible_polymorphic_call_targets (otr_type, otr_token,
3350 ctx,
3351 &final, NULL, false);
3352 fprintf (f, " Targets of polymorphic call of type %i:", type->id);
3353 print_generic_expr (f, type->type, TDF_SLIM);
3354 fprintf (f, " token %i\n", (int)otr_token);
3356 ctx.dump (f);
3358 fprintf (f, " %s%s%s%s\n ",
3359 final ? "This is a complete list." :
3360 "This is partial list; extra targets may be defined in other units.",
3361 ctx.maybe_in_construction ? " (base types included)" : "",
3362 ctx.maybe_derived_type ? " (derived types included)" : "",
3363 ctx.speculative_maybe_derived_type ? " (speculative derived types included)" : "");
3364 len = targets.length ();
3365 dump_targets (f, targets);
3367 targets = possible_polymorphic_call_targets (otr_type, otr_token,
3368 ctx,
3369 &final, NULL, true);
3370 if (targets.length () != len)
3372 fprintf (f, " Speculative targets:");
3373 dump_targets (f, targets);
3375 /* Ugly: during callgraph construction the target cache may get populated
3376 before all targets are found. While this is harmless (because all local
3377 types are discovered and only in those case we devirtualize fully and we
3378 don't do speculative devirtualization before IPA stage) it triggers
3379 assert here when dumping at that stage also populates the case with
3380 speculative targets. Quietly ignore this. */
3381 gcc_assert (symtab->state < IPA_SSA || targets.length () <= len);
3382 fprintf (f, "\n");
3386 /* Return true if N can be possibly target of a polymorphic call of
3387 OTR_TYPE/OTR_TOKEN. */
3389 bool
3390 possible_polymorphic_call_target_p (tree otr_type,
3391 HOST_WIDE_INT otr_token,
3392 const ipa_polymorphic_call_context &ctx,
3393 struct cgraph_node *n)
3395 vec <cgraph_node *> targets;
3396 unsigned int i;
3397 enum built_in_function fcode;
3398 bool final;
3400 if (TREE_CODE (TREE_TYPE (n->decl)) == FUNCTION_TYPE
3401 && ((fcode = DECL_FUNCTION_CODE (n->decl)) == BUILT_IN_UNREACHABLE
3402 || fcode == BUILT_IN_TRAP))
3403 return true;
3405 if (is_cxa_pure_virtual_p (n->decl))
3406 return true;
3408 if (!odr_hash)
3409 return true;
3410 targets = possible_polymorphic_call_targets (otr_type, otr_token, ctx, &final);
3411 for (i = 0; i < targets.length (); i++)
3412 if (n->semantically_equivalent_p (targets[i]))
3413 return true;
3415 /* At a moment we allow middle end to dig out new external declarations
3416 as a targets of polymorphic calls. */
3417 if (!final && !n->definition)
3418 return true;
3419 return false;
3424 /* Return true if N can be possibly target of a polymorphic call of
3425 OBJ_TYPE_REF expression REF in STMT. */
3427 bool
3428 possible_polymorphic_call_target_p (tree ref,
3429 gimple *stmt,
3430 struct cgraph_node *n)
3432 ipa_polymorphic_call_context context (current_function_decl, ref, stmt);
3433 tree call_fn = gimple_call_fn (stmt);
3435 return possible_polymorphic_call_target_p (obj_type_ref_class (call_fn),
3436 tree_to_uhwi
3437 (OBJ_TYPE_REF_TOKEN (call_fn)),
3438 context,
3443 /* After callgraph construction new external nodes may appear.
3444 Add them into the graph. */
3446 void
3447 update_type_inheritance_graph (void)
3449 struct cgraph_node *n;
3451 if (!odr_hash)
3452 return;
3453 free_polymorphic_call_targets_hash ();
3454 timevar_push (TV_IPA_INHERITANCE);
3455 /* We reconstruct the graph starting from types of all methods seen in the
3456 unit. */
3457 FOR_EACH_FUNCTION (n)
3458 if (DECL_VIRTUAL_P (n->decl)
3459 && !n->definition
3460 && n->real_symbol_p ())
3461 get_odr_type (TYPE_METHOD_BASETYPE (TREE_TYPE (n->decl)), true);
3462 timevar_pop (TV_IPA_INHERITANCE);
3466 /* Return true if N looks like likely target of a polymorphic call.
3467 Rule out cxa_pure_virtual, noreturns, function declared cold and
3468 other obvious cases. */
3470 bool
3471 likely_target_p (struct cgraph_node *n)
3473 int flags;
3474 /* cxa_pure_virtual and similar things are not likely. */
3475 if (TREE_CODE (TREE_TYPE (n->decl)) != METHOD_TYPE)
3476 return false;
3477 flags = flags_from_decl_or_type (n->decl);
3478 if (flags & ECF_NORETURN)
3479 return false;
3480 if (lookup_attribute ("cold",
3481 DECL_ATTRIBUTES (n->decl)))
3482 return false;
3483 if (n->frequency < NODE_FREQUENCY_NORMAL)
3484 return false;
3485 /* If there are no live virtual tables referring the target,
3486 the only way the target can be called is an instance coming from other
3487 compilation unit; speculative devirtualization is built around an
3488 assumption that won't happen. */
3489 if (!referenced_from_vtable_p (n))
3490 return false;
3491 return true;
3494 /* Compare type warning records P1 and P2 and choose one with larger count;
3495 helper for qsort. */
3498 type_warning_cmp (const void *p1, const void *p2)
3500 const odr_type_warn_count *t1 = (const odr_type_warn_count *)p1;
3501 const odr_type_warn_count *t2 = (const odr_type_warn_count *)p2;
3503 if (t1->dyn_count < t2->dyn_count)
3504 return 1;
3505 if (t1->dyn_count > t2->dyn_count)
3506 return -1;
3507 return t2->count - t1->count;
3510 /* Compare decl warning records P1 and P2 and choose one with larger count;
3511 helper for qsort. */
3514 decl_warning_cmp (const void *p1, const void *p2)
3516 const decl_warn_count *t1 = *(const decl_warn_count * const *)p1;
3517 const decl_warn_count *t2 = *(const decl_warn_count * const *)p2;
3519 if (t1->dyn_count < t2->dyn_count)
3520 return 1;
3521 if (t1->dyn_count > t2->dyn_count)
3522 return -1;
3523 return t2->count - t1->count;
3527 /* Try to speculatively devirtualize call to OTR_TYPE with OTR_TOKEN with
3528 context CTX. */
3530 struct cgraph_node *
3531 try_speculative_devirtualization (tree otr_type, HOST_WIDE_INT otr_token,
3532 ipa_polymorphic_call_context ctx)
3534 vec <cgraph_node *>targets
3535 = possible_polymorphic_call_targets
3536 (otr_type, otr_token, ctx, NULL, NULL, true);
3537 unsigned int i;
3538 struct cgraph_node *likely_target = NULL;
3540 for (i = 0; i < targets.length (); i++)
3541 if (likely_target_p (targets[i]))
3543 if (likely_target)
3544 return NULL;
3545 likely_target = targets[i];
3547 if (!likely_target
3548 ||!likely_target->definition
3549 || DECL_EXTERNAL (likely_target->decl))
3550 return NULL;
3552 /* Don't use an implicitly-declared destructor (c++/58678). */
3553 struct cgraph_node *non_thunk_target
3554 = likely_target->function_symbol ();
3555 if (DECL_ARTIFICIAL (non_thunk_target->decl))
3556 return NULL;
3557 if (likely_target->get_availability () <= AVAIL_INTERPOSABLE
3558 && likely_target->can_be_discarded_p ())
3559 return NULL;
3560 return likely_target;
3563 /* The ipa-devirt pass.
3564 When polymorphic call has only one likely target in the unit,
3565 turn it into a speculative call. */
3567 static unsigned int
3568 ipa_devirt (void)
3570 struct cgraph_node *n;
3571 hash_set<void *> bad_call_targets;
3572 struct cgraph_edge *e;
3574 int npolymorphic = 0, nspeculated = 0, nconverted = 0, ncold = 0;
3575 int nmultiple = 0, noverwritable = 0, ndevirtualized = 0, nnotdefined = 0;
3576 int nwrong = 0, nok = 0, nexternal = 0, nartificial = 0;
3577 int ndropped = 0;
3579 if (!odr_types_ptr)
3580 return 0;
3582 if (dump_file)
3583 dump_type_inheritance_graph (dump_file);
3585 /* We can output -Wsuggest-final-methods and -Wsuggest-final-types warnings.
3586 This is implemented by setting up final_warning_records that are updated
3587 by get_polymorphic_call_targets.
3588 We need to clear cache in this case to trigger recomputation of all
3589 entries. */
3590 if (warn_suggest_final_methods || warn_suggest_final_types)
3592 final_warning_records = new (final_warning_record);
3593 final_warning_records->dyn_count = profile_count::zero ();
3594 final_warning_records->grow_type_warnings (odr_types.length ());
3595 free_polymorphic_call_targets_hash ();
3598 FOR_EACH_DEFINED_FUNCTION (n)
3600 bool update = false;
3601 if (!opt_for_fn (n->decl, flag_devirtualize))
3602 continue;
3603 if (dump_file && n->indirect_calls)
3604 fprintf (dump_file, "\n\nProcesing function %s\n",
3605 n->dump_name ());
3606 for (e = n->indirect_calls; e; e = e->next_callee)
3607 if (e->indirect_info->polymorphic)
3609 struct cgraph_node *likely_target = NULL;
3610 void *cache_token;
3611 bool final;
3613 if (final_warning_records)
3614 final_warning_records->dyn_count = e->count.ipa ();
3616 vec <cgraph_node *>targets
3617 = possible_polymorphic_call_targets
3618 (e, &final, &cache_token, true);
3619 unsigned int i;
3621 /* Trigger warnings by calculating non-speculative targets. */
3622 if (warn_suggest_final_methods || warn_suggest_final_types)
3623 possible_polymorphic_call_targets (e);
3625 if (dump_file)
3626 dump_possible_polymorphic_call_targets
3627 (dump_file, e);
3629 npolymorphic++;
3631 /* See if the call can be devirtualized by means of ipa-prop's
3632 polymorphic call context propagation. If not, we can just
3633 forget about this call being polymorphic and avoid some heavy
3634 lifting in remove_unreachable_nodes that will otherwise try to
3635 keep all possible targets alive until inlining and in the inliner
3636 itself.
3638 This may need to be revisited once we add further ways to use
3639 the may edges, but it is a resonable thing to do right now. */
3641 if ((e->indirect_info->param_index == -1
3642 || (!opt_for_fn (n->decl, flag_devirtualize_speculatively)
3643 && e->indirect_info->vptr_changed))
3644 && !flag_ltrans_devirtualize)
3646 e->indirect_info->polymorphic = false;
3647 ndropped++;
3648 if (dump_file)
3649 fprintf (dump_file, "Dropping polymorphic call info;"
3650 " it can not be used by ipa-prop\n");
3653 if (!opt_for_fn (n->decl, flag_devirtualize_speculatively))
3654 continue;
3656 if (!e->maybe_hot_p ())
3658 if (dump_file)
3659 fprintf (dump_file, "Call is cold\n\n");
3660 ncold++;
3661 continue;
3663 if (e->speculative)
3665 if (dump_file)
3666 fprintf (dump_file, "Call is already speculated\n\n");
3667 nspeculated++;
3669 /* When dumping see if we agree with speculation. */
3670 if (!dump_file)
3671 continue;
3673 if (bad_call_targets.contains (cache_token))
3675 if (dump_file)
3676 fprintf (dump_file, "Target list is known to be useless\n\n");
3677 nmultiple++;
3678 continue;
3680 for (i = 0; i < targets.length (); i++)
3681 if (likely_target_p (targets[i]))
3683 if (likely_target)
3685 likely_target = NULL;
3686 if (dump_file)
3687 fprintf (dump_file, "More than one likely target\n\n");
3688 nmultiple++;
3689 break;
3691 likely_target = targets[i];
3693 if (!likely_target)
3695 bad_call_targets.add (cache_token);
3696 continue;
3698 /* This is reached only when dumping; check if we agree or disagree
3699 with the speculation. */
3700 if (e->speculative)
3702 struct cgraph_edge *e2;
3703 struct ipa_ref *ref;
3704 e->speculative_call_info (e2, e, ref);
3705 if (e2->callee->ultimate_alias_target ()
3706 == likely_target->ultimate_alias_target ())
3708 fprintf (dump_file, "We agree with speculation\n\n");
3709 nok++;
3711 else
3713 fprintf (dump_file, "We disagree with speculation\n\n");
3714 nwrong++;
3716 continue;
3718 if (!likely_target->definition)
3720 if (dump_file)
3721 fprintf (dump_file, "Target is not a definition\n\n");
3722 nnotdefined++;
3723 continue;
3725 /* Do not introduce new references to external symbols. While we
3726 can handle these just well, it is common for programs to
3727 incorrectly with headers defining methods they are linked
3728 with. */
3729 if (DECL_EXTERNAL (likely_target->decl))
3731 if (dump_file)
3732 fprintf (dump_file, "Target is external\n\n");
3733 nexternal++;
3734 continue;
3736 /* Don't use an implicitly-declared destructor (c++/58678). */
3737 struct cgraph_node *non_thunk_target
3738 = likely_target->function_symbol ();
3739 if (DECL_ARTIFICIAL (non_thunk_target->decl))
3741 if (dump_file)
3742 fprintf (dump_file, "Target is artificial\n\n");
3743 nartificial++;
3744 continue;
3746 if (likely_target->get_availability () <= AVAIL_INTERPOSABLE
3747 && likely_target->can_be_discarded_p ())
3749 if (dump_file)
3750 fprintf (dump_file, "Target is overwritable\n\n");
3751 noverwritable++;
3752 continue;
3754 else if (dbg_cnt (devirt))
3756 if (dump_enabled_p ())
3758 location_t locus = gimple_location_safe (e->call_stmt);
3759 dump_printf_loc (MSG_OPTIMIZED_LOCATIONS, locus,
3760 "speculatively devirtualizing call "
3761 "in %s to %s\n",
3762 n->dump_name (),
3763 likely_target->dump_name ());
3765 if (!likely_target->can_be_discarded_p ())
3767 cgraph_node *alias;
3768 alias = dyn_cast<cgraph_node *> (likely_target->noninterposable_alias ());
3769 if (alias)
3770 likely_target = alias;
3772 nconverted++;
3773 update = true;
3774 e->make_speculative
3775 (likely_target, e->count.apply_scale (8, 10));
3778 if (update)
3779 ipa_update_overall_fn_summary (n);
3781 if (warn_suggest_final_methods || warn_suggest_final_types)
3783 if (warn_suggest_final_types)
3785 final_warning_records->type_warnings.qsort (type_warning_cmp);
3786 for (unsigned int i = 0;
3787 i < final_warning_records->type_warnings.length (); i++)
3788 if (final_warning_records->type_warnings[i].count)
3790 tree type = final_warning_records->type_warnings[i].type;
3791 int count = final_warning_records->type_warnings[i].count;
3792 profile_count dyn_count
3793 = final_warning_records->type_warnings[i].dyn_count;
3795 if (!(dyn_count > 0))
3796 warning_n (DECL_SOURCE_LOCATION (TYPE_NAME (type)),
3797 OPT_Wsuggest_final_types, count,
3798 "Declaring type %qD final "
3799 "would enable devirtualization of %i call",
3800 "Declaring type %qD final "
3801 "would enable devirtualization of %i calls",
3802 type,
3803 count);
3804 else
3805 warning_n (DECL_SOURCE_LOCATION (TYPE_NAME (type)),
3806 OPT_Wsuggest_final_types, count,
3807 "Declaring type %qD final "
3808 "would enable devirtualization of %i call "
3809 "executed %lli times",
3810 "Declaring type %qD final "
3811 "would enable devirtualization of %i calls "
3812 "executed %lli times",
3813 type,
3814 count,
3815 (long long) dyn_count.to_gcov_type ());
3819 if (warn_suggest_final_methods)
3821 auto_vec<const decl_warn_count*> decl_warnings_vec;
3823 final_warning_records->decl_warnings.traverse
3824 <vec<const decl_warn_count *> *, add_decl_warning> (&decl_warnings_vec);
3825 decl_warnings_vec.qsort (decl_warning_cmp);
3826 for (unsigned int i = 0; i < decl_warnings_vec.length (); i++)
3828 tree decl = decl_warnings_vec[i]->decl;
3829 int count = decl_warnings_vec[i]->count;
3830 profile_count dyn_count
3831 = decl_warnings_vec[i]->dyn_count;
3833 if (!(dyn_count > 0))
3834 if (DECL_CXX_DESTRUCTOR_P (decl))
3835 warning_n (DECL_SOURCE_LOCATION (decl),
3836 OPT_Wsuggest_final_methods, count,
3837 "Declaring virtual destructor of %qD final "
3838 "would enable devirtualization of %i call",
3839 "Declaring virtual destructor of %qD final "
3840 "would enable devirtualization of %i calls",
3841 DECL_CONTEXT (decl), count);
3842 else
3843 warning_n (DECL_SOURCE_LOCATION (decl),
3844 OPT_Wsuggest_final_methods, count,
3845 "Declaring method %qD final "
3846 "would enable devirtualization of %i call",
3847 "Declaring method %qD final "
3848 "would enable devirtualization of %i calls",
3849 decl, count);
3850 else if (DECL_CXX_DESTRUCTOR_P (decl))
3851 warning_n (DECL_SOURCE_LOCATION (decl),
3852 OPT_Wsuggest_final_methods, count,
3853 "Declaring virtual destructor of %qD final "
3854 "would enable devirtualization of %i call "
3855 "executed %lli times",
3856 "Declaring virtual destructor of %qD final "
3857 "would enable devirtualization of %i calls "
3858 "executed %lli times",
3859 DECL_CONTEXT (decl), count,
3860 (long long)dyn_count.to_gcov_type ());
3861 else
3862 warning_n (DECL_SOURCE_LOCATION (decl),
3863 OPT_Wsuggest_final_methods, count,
3864 "Declaring method %qD final "
3865 "would enable devirtualization of %i call "
3866 "executed %lli times",
3867 "Declaring method %qD final "
3868 "would enable devirtualization of %i calls "
3869 "executed %lli times",
3870 decl, count,
3871 (long long)dyn_count.to_gcov_type ());
3875 delete (final_warning_records);
3876 final_warning_records = 0;
3879 if (dump_file)
3880 fprintf (dump_file,
3881 "%i polymorphic calls, %i devirtualized,"
3882 " %i speculatively devirtualized, %i cold\n"
3883 "%i have multiple targets, %i overwritable,"
3884 " %i already speculated (%i agree, %i disagree),"
3885 " %i external, %i not defined, %i artificial, %i infos dropped\n",
3886 npolymorphic, ndevirtualized, nconverted, ncold,
3887 nmultiple, noverwritable, nspeculated, nok, nwrong,
3888 nexternal, nnotdefined, nartificial, ndropped);
3889 return ndevirtualized || ndropped ? TODO_remove_functions : 0;
3892 namespace {
3894 const pass_data pass_data_ipa_devirt =
3896 IPA_PASS, /* type */
3897 "devirt", /* name */
3898 OPTGROUP_NONE, /* optinfo_flags */
3899 TV_IPA_DEVIRT, /* tv_id */
3900 0, /* properties_required */
3901 0, /* properties_provided */
3902 0, /* properties_destroyed */
3903 0, /* todo_flags_start */
3904 ( TODO_dump_symtab ), /* todo_flags_finish */
3907 class pass_ipa_devirt : public ipa_opt_pass_d
3909 public:
3910 pass_ipa_devirt (gcc::context *ctxt)
3911 : ipa_opt_pass_d (pass_data_ipa_devirt, ctxt,
3912 NULL, /* generate_summary */
3913 NULL, /* write_summary */
3914 NULL, /* read_summary */
3915 NULL, /* write_optimization_summary */
3916 NULL, /* read_optimization_summary */
3917 NULL, /* stmt_fixup */
3918 0, /* function_transform_todo_flags_start */
3919 NULL, /* function_transform */
3920 NULL) /* variable_transform */
3923 /* opt_pass methods: */
3924 virtual bool gate (function *)
3926 /* In LTO, always run the IPA passes and decide on function basis if the
3927 pass is enabled. */
3928 if (in_lto_p)
3929 return true;
3930 return (flag_devirtualize
3931 && (flag_devirtualize_speculatively
3932 || (warn_suggest_final_methods
3933 || warn_suggest_final_types))
3934 && optimize);
3937 virtual unsigned int execute (function *) { return ipa_devirt (); }
3939 }; // class pass_ipa_devirt
3941 } // anon namespace
3943 ipa_opt_pass_d *
3944 make_pass_ipa_devirt (gcc::context *ctxt)
3946 return new pass_ipa_devirt (ctxt);
3949 #include "gt-ipa-devirt.h"