1/* Basic IPA utilities for type inheritance graph construction and
2 devirtualization.
3 Copyright (C) 2013-2017 Free Software Foundation, Inc.
4 Contributed by Jan Hubicka
5
6This file is part of GCC.
7
8GCC is free software; you can redistribute it and/or modify it under
9the terms of the GNU General Public License as published by the Free
10Software Foundation; either version 3, or (at your option) any later
11version.
12
13GCC is distributed in the hope that it will be useful, but WITHOUT ANY
14WARRANTY; without even the implied warranty of MERCHANTABILITY or
15FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
16for more details.
17
18You should have received a copy of the GNU General Public License
19along with GCC; see the file COPYING3. If not see
20<http://www.gnu.org/licenses/>. */
21
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.
38
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.
44
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.
49
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.
53
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.
60
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).
66
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.
71
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.
76
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.
81
82 What we do here:
83
84 build_type_inheritance_graph triggers a construction of the type inheritance
85 graph.
86
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.
91
92 The inheritance graph is represented as follows:
93
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)
97
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.
101
102 possible_polymorphic_call_targets returns, given an parameters found in
103 indirect polymorphic edge all possible polymorphic call targets of the call.
104
105 pass_ipa_devirt performs simple speculative devirtualization.
106*/
107
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"
134
135/* Hash based set of pairs of types. */
136struct type_pair
137{
138 tree first;
139 tree second;
140};
141
142template <>
143struct default_hash_traits <type_pair>
144 : typed_noop_remove <type_pair>
145{
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)
150 {
151 return TYPE_UID (p.first) ^ TYPE_UID (p.second);
152 }
153 static bool
154 is_empty (type_pair p)
155 {
156 return p.first == NULL;
157 }
158 static bool
159 is_deleted (type_pair p ATTRIBUTE_UNUSED)
160 {
161 return false;
162 }
163 static bool
164 equal (const type_pair &a, const type_pair &b)
165 {
166 return a.first==b.first && a.second == b.second;
167 }
168 static void
169 mark_empty (type_pair &e)
170 {
171 e.first = NULL;
172 }
173};
174
175static bool odr_types_equivalent_p (tree, tree, bool, bool *,
176 hash_set<type_pair> *,
177 location_t, location_t);
178
179static bool odr_violation_reported = false;
180
181
182/* Pointer set of all call targets appearing in the cache. */
183static hash_set<cgraph_node *> *cached_polymorphic_call_targets;
184
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. */
188
189struct GTY(()) odr_type_d
190{
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;
198
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;
203
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;
214};
215
216/* Return TRUE if all derived types of T are known and thus
217 we may consider the walk of derived type complete.
218
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). */
222
223bool
224type_all_derivations_known_p (const_tree t)
225{
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);
236}
237
238/* Return TRUE if type's constructors are all visible. */
239
240static bool
241type_all_ctors_visible_p (tree t)
242{
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.
248
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);
253}
254
255/* Return TRUE if type may have instance. */
256
257static bool
258type_possibly_instantiated_p (tree t)
259{
260 tree vtable;
261 varpool_node *vnode;
262
263 /* TODO: Add abstract types here. */
264 if (!type_all_ctors_visible_p (t))
265 return true;
266
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;
272}
273
274/* Hash used to unify ODR types based on their mangled name and for anonymous
275 namespace types. */
276
277struct odr_name_hasher : pointer_hash <odr_type_d>
278{
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 *);
283};
284
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. */
288
289struct odr_vtable_hasher:odr_name_hasher
290{
291 static inline hashval_t hash (const odr_type_d *);
292 static inline bool equal (const odr_type_d *, const tree_node *);
293};
294
295/* Return type that was declared with T's name so that T is an
296 qualified variant of it. */
297
298static inline tree
299main_odr_variant (const_tree t)
300{
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);
306}
307
308static bool
309can_be_name_hashed_p (tree t)
310{
311 return (!in_lto_p || odr_type_p (t));
312}
313
314/* Hash type by its ODR name. */
315
316static hashval_t
317hash_odr_name (const_tree t)
318{
319 gcc_checking_assert (main_odr_variant (t) == t);
320
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);
325
326 /* Anonymous types are unique. */
327 if (type_with_linkage_p (t) && type_in_anonymous_namespace_p (t))
328 return htab_hash_pointer (t);
329
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)));
333}
334
335/* Return the computed hashcode for ODR_TYPE. */
336
337inline hashval_t
338odr_name_hasher::hash (const odr_type_d *odr_type)
339{
340 return hash_odr_name (odr_type->type);
341}
342
343static bool
344can_be_vtable_hashed_p (tree t)
345{
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)));
354}
355
356/* Hash type by assembler name of its vtable. */
357
358static hashval_t
359hash_odr_vtable (const_tree t)
360{
361 tree v = BINFO_VTABLE (TYPE_BINFO (TYPE_MAIN_VARIANT (t)));
362 inchash::hash hstate;
363
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);
369
370 if (TREE_CODE (v) == POINTER_PLUS_EXPR)
371 {
372 add_expr (TREE_OPERAND (v, 1), hstate);
373 v = TREE_OPERAND (TREE_OPERAND (v, 0), 0);
374 }
375
376 hstate.add_hwi (IDENTIFIER_HASH_VALUE (DECL_ASSEMBLER_NAME (v)));
377 return hstate.end ();
378}
379
380/* Return the computed hashcode for ODR_TYPE. */
381
382inline hashval_t
383odr_vtable_hasher::hash (const odr_type_d *odr_type)
384{
385 return hash_odr_vtable (odr_type->type);
386}
387
388/* For languages with One Definition Rule, work out if
389 types are the same based on their name.
390
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.
394
395 Until we start streaming mangled type names, this function works
396 only for polymorphic types.
397
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.
401*/
402
403bool
404types_same_for_odr (const_tree type1, const_tree type2, bool strict)
405{
406 gcc_checking_assert (TYPE_P (type1) && TYPE_P (type2));
407
408 type1 = main_odr_variant (type1);
409 type2 = main_odr_variant (type2);
410 if (!strict)
411 {
412 type1 = TYPE_MAIN_VARIANT (type1);
413 type2 = TYPE_MAIN_VARIANT (type2);
414 }
415
416 if (type1 == type2)
417 return true;
418
419 if (!in_lto_p)
420 return false;
421
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;
427
428
429 /* ODR name of the type is set in DECL_ASSEMBLER_NAME of its TYPE_NAME.
430
431 Ideally we should never need types without ODR names here. It can however
432 happen in two cases:
433
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))))
443 {
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;
458
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. */
463
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)))
468 {
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)));
479 }
480 gcc_unreachable ();
481 }
482 return (DECL_ASSEMBLER_NAME (TYPE_NAME (type1))
483 == DECL_ASSEMBLER_NAME (TYPE_NAME (type2)));
484}
485
486/* Return true if we can decide on ODR equivalency.
487
488 In non-LTO it is always decide, in LTO however it depends in the type has
489 ODR info attached.
490
491 When STRICT is false, compare main variants. */
492
493bool
494types_odr_comparable (tree t1, tree t2, bool strict)
495{
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))));
505}
506
507/* Return true if T1 and T2 are ODR equivalent. If ODR equivalency is not
508 known, be conservative and return false. */
509
510bool
511types_must_be_same_for_odr (tree t1, tree t2)
512{
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);
517}
518
519/* If T is compound type, return type it is based on. */
520
521static tree
522compound_type_base (const_tree t)
523{
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;
534}
535
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. */
539
540bool
541odr_or_derived_type_p (const_tree t)
542{
543 do
544 {
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)
552 {
553 if (TYPE_METHOD_BASETYPE (t))
554 t = TYPE_METHOD_BASETYPE (t);
555 else
556 {
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;
563 }
564 }
565 else
566 t = compound_type_base (t);
567 }
568 while (t);
569 return t;
570}
571
572/* Compare types T1 and T2 and return true if they are
573 equivalent. */
574
575inline bool
576odr_name_hasher::equal (const odr_type_d *o1, const tree_node *t2)
577{
578 tree t1 = o1->type;
579
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)));
595}
596
597/* Compare types T1 and T2 and return true if they are
598 equivalent. */
599
600inline bool
601odr_vtable_hasher::equal (const odr_type_d *o1, const tree_node *t2)
602{
603 tree t1 = o1->type;
604
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)));
620}
621
622/* Free ODR type V. */
623
624inline void
625odr_name_hasher::remove (odr_type_d *v)
626{
627 v->bases.release ();
628 v->derived_types.release ();
629 if (v->types_set)
630 delete v->types_set;
631 ggc_free (v);
632}
633
634/* ODR type hash used to look up ODR type based on tree type node. */
635
636typedef hash_table<odr_name_hasher> odr_hash_type;
637static odr_hash_type *odr_hash;
638typedef hash_table<odr_vtable_hasher> odr_vtable_hash_type;
639static odr_vtable_hash_type *odr_vtable_hash;
640
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. */
644
645static GTY(()) vec <odr_type, va_gc> *odr_types_ptr;
646#define odr_types (*odr_types_ptr)
647
648/* Set TYPE_BINFO of TYPE and its variants to BINFO. */
649void
650set_type_binfo (tree type, tree binfo)
651{
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));
657}
658
659/* Compare T2 and T2 based on name or structure. */
660
661static bool
662odr_subtypes_equivalent_p (tree t1, tree t2,
663 hash_set<type_pair> *visited,
664 location_t loc1, location_t loc2)
665{
666
667 /* This can happen in incomplete types that should be handled earlier. */
668 gcc_assert (t1 && t2);
669
670 t1 = main_odr_variant (t1);
671 t2 = main_odr_variant (t2);
672 if (t1 == t2)
673 return true;
674
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;
679
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))
684 {
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;
691 }
692
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;
700
701 type_pair pair={t1,t2};
702 if (TYPE_UID (t1) > TYPE_UID (t2))
703 {
704 pair.first = t2;
705 pair.second = t1;
706 }
707 if (visited->add (pair))
708 return true;
709 return odr_types_equivalent_p (t1, t2, false, NULL, visited, loc1, loc2);
710}
711
712/* Return true if DECL1 and DECL2 are identical methods. Consider
713 name equivalent to name.localalias.xyz. */
714
715static bool
716methods_equal_p (tree decl1, tree decl2)
717{
718 if (DECL_ASSEMBLER_NAME (decl1) == DECL_ASSEMBLER_NAME (decl2))
719 return true;
720 const char sep = symbol_table::symbol_suffix_separator ();
721
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);
725
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);
729
730 if (len1 != len2)
731 return false;
732 return !strncmp (name1, name2, len1);
733}
734
735/* Compare two virtual tables, PREVAILING and VTABLE and output ODR
736 violation warnings. */
737
738void
739compare_virtual_tables (varpool_node *prevailing, varpool_node *vtable)
740{
741 int n1, n2;
742
743 if (DECL_VIRTUAL_P (prevailing->decl) != DECL_VIRTUAL_P (vtable->decl))
744 {
745 odr_violation_reported = true;
746 if (DECL_VIRTUAL_P (prevailing->decl))
747 {
748 varpool_node *tmp = prevailing;
749 prevailing = vtable;
750 vtable = tmp;
751 }
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;
761 }
762 if (!prevailing->definition || !vtable->definition)
763 return;
764
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;
769
770 odr_type class_type = get_odr_type (DECL_CONTEXT (vtable->decl), true);
771
772 if (class_type->odr_violated)
773 return;
774
775 for (n1 = 0, n2 = 0; true; n1++, n2++)
776 {
777 struct ipa_ref *ref1, *ref2;
778 bool end1, end2;
779
780 end1 = !prevailing->iterate_reference (n1, ref1);
781 end2 = !vtable->iterate_reference (n2, ref2);
782
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)
792 {
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)))
800 {
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;
809 }
810 n2++;
811 end2 = !vtable->iterate_reference (n2, ref2);
812 }
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)
818 {
819 n1++;
820 end1 = !prevailing->iterate_reference (n1, ref1);
821 }
822
823 /* Finished? */
824 if (end1 && end2)
825 {
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))
832 {
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)))
840 {
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");
845 }
846 }
847 return;
848 }
849
850 if (!end1 && !end2)
851 {
852 if (methods_equal_p (ref1->referred->decl, ref2->referred->decl))
853 continue;
854
855 class_type->odr_violated = true;
856
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)
861 {
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)))
868 {
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");
873 }
874 return;
875 }
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))
882 {
883 if (VAR_P (ref1->referred->decl))
884 end1 = true;
885 else if (VAR_P (ref2->referred->decl))
886 end2 = true;
887 }
888 }
889
890 class_type->odr_violated = true;
891
892 /* Complain about size mismatch. Either we have too many virutal
893 functions or too many virtual table pointers. */
894 if (end1 || end2)
895 {
896 if (end1)
897 {
898 varpool_node *tmp = prevailing;
899 prevailing = vtable;
900 vtable = tmp;
901 ref1 = ref2;
902 }
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)))
909 {
910 if (TREE_CODE (ref1->referring->decl) == FUNCTION_DECL)
911 {
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);
920 }
921 else
922 {
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");
927 }
928 }
929 return;
930 }
931
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)))
939 {
940 if (TREE_CODE (ref1->referred->decl) == FUNCTION_DECL)
941 {
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);
956 }
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;
963 }
964 }
965}
966
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. */
972
973void
974warn_odr (tree t1, tree t2, tree st1, tree st2,
975 bool warn, bool *warned, const char *reason)
976{
977 tree decl2 = TYPE_NAME (t2);
978 if (warned)
979 *warned = false;
980
981 if (!warn || !TYPE_NAME(t1))
982 return;
983
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 ();
988
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)
994 ;
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)
999 {
1000 inform (DECL_SOURCE_LOCATION (decl2),
1001 "a different type is defined in another translation unit");
1002 if (!st1)
1003 {
1004 st1 = st2;
1005 st2 = NULL;
1006 }
1007 inform (DECL_SOURCE_LOCATION (st1),
1008 "the first difference of corresponding definitions is field %qD",
1009 st1);
1010 if (st2)
1011 decl2 = st2;
1012 }
1013 else if (TREE_CODE (st1) == FUNCTION_DECL)
1014 {
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;
1021 }
1022 else
1023 return;
1024 inform (DECL_SOURCE_LOCATION (decl2), reason);
1025
1026 if (warned)
1027 *warned = true;
1028}
1029
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. */
1032
1033static bool
1034type_mismatch_p (tree t1, tree t2)
1035{
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);
1040}
1041
1042
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.
1047
1048 This is hard to do in general. We basically handle the common cases.
1049
1050 If LOC1 and LOC2 are meaningful locations, use it in the case the types
1051 themselves do no thave one.*/
1052
1053void
1054warn_types_mismatch (tree t1, tree t2, location_t loc1, location_t loc2)
1055{
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;
1065
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)
1072 {
1073 if (loc_t1 <= BUILTINS_LOCATION)
1074 loc_t2_useful = true;
1075 else
1076 {
1077 expanded_location xloc1 = expand_location (loc_t1);
1078 expanded_location xloc2 = expand_location (loc_t2);
1079
1080 if (strcmp (xloc1.file, xloc2.file)
1081 || xloc1.line != xloc2.line
1082 || xloc1.column != xloc2.column)
1083 loc_t2_useful = true;
1084 }
1085 }
1086
1087 if (loc_t1 <= BUILTINS_LOCATION)
1088 loc_t1 = loc1;
1089 if (loc_t2 <= BUILTINS_LOCATION)
1090 loc_t2 = loc2;
1091
1092 location_t loc = loc_t1 <= BUILTINS_LOCATION ? loc_t2 : loc_t1;
1093
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)))
1098 {
1099 if (type_with_linkage_p (t1) && !type_in_anonymous_namespace_p (t1))
1100 {
1101 std::swap (t1, t2);
1102 std::swap (loc_t1, loc_t2);
1103 }
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;
1124 }
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)))
1135 {
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))
1143 {
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;
1152 }
1153 free (name1);
1154 }
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))
1161 {
1162 if (TREE_CODE (t1) == TREE_CODE (t2))
1163 {
1164 if (TREE_CODE (t1) == ARRAY_TYPE
1165 && COMPLETE_TYPE_P (t1) && COMPLETE_TYPE_P (t2))
1166 {
1167 tree i1 = TYPE_DOMAIN (t1);
1168 tree i2 = TYPE_DOMAIN (t2);
1169
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))
1175 {
1176 inform (loc,
1177 "array types have different bounds");
1178 return;
1179 }
1180 }
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)
1186 {
1187 tree parms1 = NULL, parms2 = NULL;
1188 int count = 1;
1189
1190 if (type_mismatch_p (TREE_TYPE (t1), TREE_TYPE (t2)))
1191 {
1192 inform (loc, "return value type mismatch");
1193 warn_types_mismatch (TREE_TYPE (t1), TREE_TYPE (t2), loc_t1,
1194 loc_t2);
1195 return;
1196 }
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++)
1202 {
1203 if (type_mismatch_p (TREE_VALUE (parms1), TREE_VALUE (parms2)))
1204 {
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;
1216 }
1217 }
1218 if (parms1 || parms2)
1219 {
1220 inform (loc,
1221 "types have different parameter counts");
1222 return;
1223 }
1224 }
1225 }
1226 return;
1227 }
1228
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");
1242}
1243
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. */
1250
1251static bool
1252odr_types_equivalent_p (tree t1, tree t2, bool warn, bool *warned,
1253 hash_set<type_pair> *visited,
1254 location_t loc1, location_t loc2)
1255{
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));
1261
1262 /* Can't be the same type if the types don't have the same code. */
1263 if (TREE_CODE (t1) != TREE_CODE (t2))
1264 {
1265 warn_odr (t1, t2, NULL, NULL, warn, warned,
1266 G_("a different type is defined in another translation unit"));
1267 return false;
1268 }
1269
1270 if (TYPE_QUALS (t1) != TYPE_QUALS (t2))
1271 {
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;
1276 }
1277
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)))
1280 {
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;
1286 }
1287
1288 if (comp_type_attributes (t1, t2) != 1)
1289 {
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;
1294 }
1295
1296 if (TREE_CODE (t1) == ENUMERAL_TYPE
1297 && TYPE_VALUES (t1) && TYPE_VALUES (t2))
1298 {
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))
1302 {
1303 if (TREE_PURPOSE (v1) != TREE_PURPOSE (v2))
1304 {
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;
1309 }
1310 if (TREE_VALUE (v1) != TREE_VALUE (v2)
1311 && !operand_equal_p (DECL_INITIAL (TREE_VALUE (v1)),
1312 DECL_INITIAL (TREE_VALUE (v2)), 0))
1313 {
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;
1318 }
1319 }
1320 if (v1 || v2)
1321 {
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;
1326 }
1327 }
1328
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))
1337 {
1338 if (TYPE_PRECISION (t1) != TYPE_PRECISION (t2))
1339 {
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;
1344 }
1345 if (TYPE_UNSIGNED (t1) != TYPE_UNSIGNED (t2))
1346 {
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;
1351 }
1352
1353 if (TREE_CODE (t1) == INTEGER_TYPE
1354 && TYPE_STRING_FLAG (t1) != TYPE_STRING_FLAG (t2))
1355 {
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;
1361 }
1362
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))
1368 {
1369 if (TYPE_ADDR_SPACE (TREE_TYPE (t1))
1370 != TYPE_ADDR_SPACE (TREE_TYPE (t2)))
1371 {
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;
1376 }
1377
1378 if (!odr_subtypes_equivalent_p (TREE_TYPE (t1), TREE_TYPE (t2),
1379 visited, loc1, loc2))
1380 {
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;
1388 }
1389 }
1390
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))
1394 {
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;
1402 }
1403 }
1404 /* Do type-specific comparisons. */
1405 else switch (TREE_CODE (t1))
1406 {
1407 case ARRAY_TYPE:
1408 {
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))
1413 {
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);
1419 }
1420 gcc_assert (TYPE_STRING_FLAG (t1) == TYPE_STRING_FLAG (t2));
1421 gcc_assert (TYPE_NONALIASED_COMPONENT (t1)
1422 == TYPE_NONALIASED_COMPONENT (t2));
1423
1424 tree i1 = TYPE_DOMAIN (t1);
1425 tree i2 = TYPE_DOMAIN (t2);
1426
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;
1431
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);
1436
1437 /* In C++, minimums should be always 0. */
1438 gcc_assert (min1 == min2);
1439 if (!operand_equal_p (max1, max2, 0))
1440 {
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;
1445 }
1446 }
1447 break;
1448
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))
1455 {
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;
1462 }
1463
1464 if (TYPE_ARG_TYPES (t1) == TYPE_ARG_TYPES (t2)
1465 || !prototype_p (t1) || !prototype_p (t2))
1466 return true;
1467 else
1468 {
1469 tree parms1, parms2;
1470
1471 for (parms1 = TYPE_ARG_TYPES (t1), parms2 = TYPE_ARG_TYPES (t2);
1472 parms1 && parms2;
1473 parms1 = TREE_CHAIN (parms1), parms2 = TREE_CHAIN (parms2))
1474 {
1475 if (!odr_subtypes_equivalent_p
1476 (TREE_VALUE (parms1), TREE_VALUE (parms2), visited,
1477 loc1, loc2))
1478 {
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;
1486 }
1487 }
1488
1489 if (parms1 || parms2)
1490 {
1491 warn_odr (t1, t2, NULL, NULL, warn, warned,
1492 G_("has different parameters "
1493 "in another translation unit"));
1494 return false;
1495 }
1496
1497 return true;
1498 }
1499
1500 case RECORD_TYPE:
1501 case UNION_TYPE:
1502 case QUAL_UNION_TYPE:
1503 {
1504 tree f1, f2;
1505
1506 /* For aggregate types, all the fields must be the same. */
1507 if (COMPLETE_TYPE_P (t1) && COMPLETE_TYPE_P (t2))
1508 {
1509 if (TYPE_BINFO (t1) && TYPE_BINFO (t2)
1510 && polymorphic_type_binfo_p (TYPE_BINFO (t1))
1511 != polymorphic_type_binfo_p (TYPE_BINFO (t2)))
1512 {
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;
1522 }
1523 for (f1 = TYPE_FIELDS (t1), f2 = TYPE_FIELDS (t2);
1524 f1 || f2;
1525 f1 = TREE_CHAIN (f1), f2 = TREE_CHAIN (f2))
1526 {
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))
1535 {
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;
1540 }
1541 if (DECL_ARTIFICIAL (f1) != DECL_ARTIFICIAL (f2))
1542 {
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;
1547 }
1548 if (DECL_NAME (f1) != DECL_NAME (f2)
1549 && !DECL_ARTIFICIAL (f1))
1550 {
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;
1555 }
1556 if (!odr_subtypes_equivalent_p (TREE_TYPE (f1),
1557 TREE_TYPE (f2), visited,
1558 loc1, loc2))
1559 {
1560 /* Do not warn about artificial fields and just go into
1561 generic field mismatch warning. */
1562 if (DECL_ARTIFICIAL (f1))
1563 break;
1564
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;
1571 }
1572 if (!gimple_compare_field_offset (f1, f2))
1573 {
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;
1582 }
1583 gcc_assert (DECL_NONADDRESSABLE_P (f1)
1584 == DECL_NONADDRESSABLE_P (f2));
1585 }
1586
1587 /* If one aggregate has more fields than the other, they
1588 are not the same. */
1589 if (f1 || f2)
1590 {
1591 if ((f1 && DECL_VIRTUAL_P (f1)) || (f2 && DECL_VIRTUAL_P (f2)))
1592 warn_odr (t1, t2, NULL, NULL, warn, warned,
1593 G_("a type with different virtual table pointers"
1594 " is defined in another translation unit"));
1595 else if ((f1 && DECL_ARTIFICIAL (f1))
1596 || (f2 && DECL_ARTIFICIAL (f2)))
1597 warn_odr (t1, t2, NULL, NULL, warn, warned,
1598 G_("a type with different bases is defined "
1599 "in another translation unit"));
1600 else
1601 warn_odr (t1, t2, f1, f2, warn, warned,
1602 G_("a type with different number of fields "
1603 "is defined in another translation unit"));
1604
1605 return false;
1606 }
1607 }
1608 break;
1609 }
1610 case VOID_TYPE:
1611 case NULLPTR_TYPE:
1612 break;
1613
1614 default:
1615 debug_tree (t1);
1616 gcc_unreachable ();
1617 }
1618
1619 /* Those are better to come last as they are utterly uninformative. */
1620 if (TYPE_SIZE (t1) && TYPE_SIZE (t2)
1621 && !operand_equal_p (TYPE_SIZE (t1), TYPE_SIZE (t2), 0))
1622 {
1623 warn_odr (t1, t2, NULL, NULL, warn, warned,
1624 G_("a type with different size "
1625 "is defined in another translation unit"));
1626 return false;
1627 }
1628 if (COMPLETE_TYPE_P (t1) && COMPLETE_TYPE_P (t2)
1629 && TYPE_ALIGN (t1) != TYPE_ALIGN (t2))
1630 {
1631 warn_odr (t1, t2, NULL, NULL, warn, warned,
1632 G_("a type with different alignment "
1633 "is defined in another translation unit"));
1634 return false;
1635 }
1636 gcc_assert (!TYPE_SIZE_UNIT (t1) || !TYPE_SIZE_UNIT (t2)
1637 || operand_equal_p (TYPE_SIZE_UNIT (t1),
1638 TYPE_SIZE_UNIT (t2), 0));
1639 return true;
1640}
1641
1642/* Return true if TYPE1 and TYPE2 are equivalent for One Definition Rule. */
1643
1644bool
1645odr_types_equivalent_p (tree type1, tree type2)
1646{
1647 gcc_checking_assert (odr_or_derived_type_p (type1)
1648 && odr_or_derived_type_p (type2));
1649
1650 hash_set<type_pair> visited;
1651 return odr_types_equivalent_p (type1, type2, false, NULL,
1652 &visited, UNKNOWN_LOCATION, UNKNOWN_LOCATION);
1653}
1654
1655/* TYPE is equivalent to VAL by ODR, but its tree representation differs
1656 from VAL->type. This may happen in LTO where tree merging did not merge
1657 all variants of the same type or due to ODR violation.
1658
1659 Analyze and report ODR violations and add type to duplicate list.
1660 If TYPE is more specified than VAL->type, prevail VAL->type. Also if
1661 this is first time we see definition of a class return true so the
1662 base types are analyzed. */
1663
1664static bool
1665add_type_duplicate (odr_type val, tree type)
1666{
1667 bool build_bases = false;
1668 bool prevail = false;
1669 bool odr_must_violate = false;
1670
1671 if (!val->types_set)
1672 val->types_set = new hash_set<tree>;
1673
1674 /* Chose polymorphic type as leader (this happens only in case of ODR
1675 violations. */
1676 if ((TREE_CODE (type) == RECORD_TYPE && TYPE_BINFO (type)
1677 && polymorphic_type_binfo_p (TYPE_BINFO (type)))
1678 && (TREE_CODE (val->type) != RECORD_TYPE || !TYPE_BINFO (val->type)
1679 || !polymorphic_type_binfo_p (TYPE_BINFO (val->type))))
1680 {
1681 prevail = true;
1682 build_bases = true;
1683 }
1684 /* Always prefer complete type to be the leader. */
1685 else if (!COMPLETE_TYPE_P (val->type) && COMPLETE_TYPE_P (type))
1686 {
1687 prevail = true;
1688 build_bases = TYPE_BINFO (type);
1689 }
1690 else if (COMPLETE_TYPE_P (val->type) && !COMPLETE_TYPE_P (type))
1691 ;
1692 else if (TREE_CODE (val->type) == ENUMERAL_TYPE
1693 && TREE_CODE (type) == ENUMERAL_TYPE
1694 && !TYPE_VALUES (val->type) && TYPE_VALUES (type))
1695 prevail = true;
1696 else if (TREE_CODE (val->type) == RECORD_TYPE
1697 && TREE_CODE (type) == RECORD_TYPE
1698 && TYPE_BINFO (type) && !TYPE_BINFO (val->type))
1699 {
1700 gcc_assert (!val->bases.length ());
1701 build_bases = true;
1702 prevail = true;
1703 }
1704
1705 if (prevail)
1706 std::swap (val->type, type);
1707
1708 val->types_set->add (type);
1709
1710 /* If we now have a mangled name, be sure to record it to val->type
1711 so ODR hash can work. */
1712
1713 if (can_be_name_hashed_p (type) && !can_be_name_hashed_p (val->type))
1714 SET_DECL_ASSEMBLER_NAME (TYPE_NAME (val->type),
1715 DECL_ASSEMBLER_NAME (TYPE_NAME (type)));
1716
1717 bool merge = true;
1718 bool base_mismatch = false;
1719 unsigned int i;
1720 bool warned = false;
1721 hash_set<type_pair> visited;
1722
1723 gcc_assert (in_lto_p);
1724 vec_safe_push (val->types, type);
1725
1726 /* If both are class types, compare the bases. */
1727 if (COMPLETE_TYPE_P (type) && COMPLETE_TYPE_P (val->type)
1728 && TREE_CODE (val->type) == RECORD_TYPE
1729 && TREE_CODE (type) == RECORD_TYPE
1730 && TYPE_BINFO (val->type) && TYPE_BINFO (type))
1731 {
1732 if (BINFO_N_BASE_BINFOS (TYPE_BINFO (type))
1733 != BINFO_N_BASE_BINFOS (TYPE_BINFO (val->type)))
1734 {
1735 if (!flag_ltrans && !warned && !val->odr_violated)
1736 {
1737 tree extra_base;
1738 warn_odr (type, val->type, NULL, NULL, !warned, &warned,
1739 "a type with the same name but different "
1740 "number of polymorphic bases is "
1741 "defined in another translation unit");
1742 if (warned)
1743 {
1744 if (BINFO_N_BASE_BINFOS (TYPE_BINFO (type))
1745 > BINFO_N_BASE_BINFOS (TYPE_BINFO (val->type)))
1746 extra_base = BINFO_BASE_BINFO
1747 (TYPE_BINFO (type),
1748 BINFO_N_BASE_BINFOS (TYPE_BINFO (val->type)));
1749 else
1750 extra_base = BINFO_BASE_BINFO
1751 (TYPE_BINFO (val->type),
1752 BINFO_N_BASE_BINFOS (TYPE_BINFO (type)));
1753 tree extra_base_type = BINFO_TYPE (extra_base);
1754 inform (DECL_SOURCE_LOCATION (TYPE_NAME (extra_base_type)),
1755 "the extra base is defined here");
1756 }
1757 }
1758 base_mismatch = true;
1759 }
1760 else
1761 for (i = 0; i < BINFO_N_BASE_BINFOS (TYPE_BINFO (type)); i++)
1762 {
1763 tree base1 = BINFO_BASE_BINFO (TYPE_BINFO (type), i);
1764 tree base2 = BINFO_BASE_BINFO (TYPE_BINFO (val->type), i);
1765 tree type1 = BINFO_TYPE (base1);
1766 tree type2 = BINFO_TYPE (base2);
1767
1768 if (types_odr_comparable (type1, type2))
1769 {
1770 if (!types_same_for_odr (type1, type2))
1771 base_mismatch = true;
1772 }
1773 else
1774 if (!odr_types_equivalent_p (type1, type2))
1775 base_mismatch = true;
1776 if (base_mismatch)
1777 {
1778 if (!warned && !val->odr_violated)
1779 {
1780 warn_odr (type, val->type, NULL, NULL,
1781 !warned, &warned,
1782 "a type with the same name but different base "
1783 "type is defined in another translation unit");
1784 if (warned)
1785 warn_types_mismatch (type1, type2,
1786 UNKNOWN_LOCATION, UNKNOWN_LOCATION);
1787 }
1788 break;
1789 }
1790 if (BINFO_OFFSET (base1) != BINFO_OFFSET (base2))
1791 {
1792 base_mismatch = true;
1793 if (!warned && !val->odr_violated)
1794 warn_odr (type, val->type, NULL, NULL,
1795 !warned, &warned,
1796 "a type with the same name but different base "
1797 "layout is defined in another translation unit");
1798 break;
1799 }
1800 /* One of bases is not of complete type. */
1801 if (!TYPE_BINFO (type1) != !TYPE_BINFO (type2))
1802 {
1803 /* If we have a polymorphic type info specified for TYPE1
1804 but not for TYPE2 we possibly missed a base when recording
1805 VAL->type earlier.
1806 Be sure this does not happen. */
1807 if (TYPE_BINFO (type1)
1808 && polymorphic_type_binfo_p (TYPE_BINFO (type1))
1809 && !build_bases)
1810 odr_must_violate = true;
1811 break;
1812 }
1813 /* One base is polymorphic and the other not.
1814 This ought to be diagnosed earlier, but do not ICE in the
1815 checking bellow. */
1816 else if (TYPE_BINFO (type1)
1817 && polymorphic_type_binfo_p (TYPE_BINFO (type1))
1818 != polymorphic_type_binfo_p (TYPE_BINFO (type2)))
1819 {
1820 if (!warned && !val->odr_violated)
1821 warn_odr (type, val->type, NULL, NULL,
1822 !warned, &warned,
1823 "a base of the type is polymorphic only in one "
1824 "translation unit");
1825 base_mismatch = true;
1826 break;
1827 }
1828 }
1829 if (base_mismatch)
1830 {
1831 merge = false;
1832 odr_violation_reported = true;
1833 val->odr_violated = true;
1834
1835 if (symtab->dump_file)
1836 {
1837 fprintf (symtab->dump_file, "ODR base violation\n");
1838
1839 print_node (symtab->dump_file, "", val->type, 0);
1840 putc ('\n',symtab->dump_file);
1841 print_node (symtab->dump_file, "", type, 0);
1842 putc ('\n',symtab->dump_file);
1843 }
1844 }
1845 }
1846
1847 /* Next compare memory layout. */
1848 if (!odr_types_equivalent_p (val->type, type,
1849 !flag_ltrans && !val->odr_violated && !warned,
1850 &warned, &visited,
1851 DECL_SOURCE_LOCATION (TYPE_NAME (val->type)),
1852 DECL_SOURCE_LOCATION (TYPE_NAME (type))))
1853 {
1854 merge = false;
1855 odr_violation_reported = true;
1856 val->odr_violated = true;
1857 }
1858 gcc_assert (val->odr_violated || !odr_must_violate);
1859 /* Sanity check that all bases will be build same way again. */
1860 if (flag_checking
1861 && COMPLETE_TYPE_P (type) && COMPLETE_TYPE_P (val->type)
1862 && TREE_CODE (val->type) == RECORD_TYPE
1863 && TREE_CODE (type) == RECORD_TYPE
1864 && TYPE_BINFO (val->type) && TYPE_BINFO (type)
1865 && !val->odr_violated
1866 && !base_mismatch && val->bases.length ())
1867 {
1868 unsigned int num_poly_bases = 0;
1869 unsigned int j;
1870
1871 for (i = 0; i < BINFO_N_BASE_BINFOS (TYPE_BINFO (type)); i++)
1872 if (polymorphic_type_binfo_p (BINFO_BASE_BINFO
1873 (TYPE_BINFO (type), i)))
1874 num_poly_bases++;
1875 gcc_assert (num_poly_bases == val->bases.length ());
1876 for (j = 0, i = 0; i < BINFO_N_BASE_BINFOS (TYPE_BINFO (type));
1877 i++)
1878 if (polymorphic_type_binfo_p (BINFO_BASE_BINFO
1879 (TYPE_BINFO (type), i)))
1880 {
1881 odr_type base = get_odr_type
1882 (BINFO_TYPE
1883 (BINFO_BASE_BINFO (TYPE_BINFO (type),
1884 i)),
1885 true);
1886 gcc_assert (val->bases[j] == base);
1887 j++;
1888 }
1889 }
1890
1891
1892 /* Regularize things a little. During LTO same types may come with
1893 different BINFOs. Either because their virtual table was
1894 not merged by tree merging and only later at decl merging or
1895 because one type comes with external vtable, while other
1896 with internal. We want to merge equivalent binfos to conserve
1897 memory and streaming overhead.
1898
1899 The external vtables are more harmful: they contain references
1900 to external declarations of methods that may be defined in the
1901 merged LTO unit. For this reason we absolutely need to remove
1902 them and replace by internal variants. Not doing so will lead
1903 to incomplete answers from possible_polymorphic_call_targets.
1904
1905 FIXME: disable for now; because ODR types are now build during
1906 streaming in, the variants do not need to be linked to the type,
1907 yet. We need to do the merging in cleanup pass to be implemented
1908 soon. */
1909 if (!flag_ltrans && merge
1910 && 0
1911 && TREE_CODE (val->type) == RECORD_TYPE
1912 && TREE_CODE (type) == RECORD_TYPE
1913 && TYPE_BINFO (val->type) && TYPE_BINFO (type)
1914 && TYPE_MAIN_VARIANT (type) == type
1915 && TYPE_MAIN_VARIANT (val->type) == val->type
1916 && BINFO_VTABLE (TYPE_BINFO (val->type))
1917 && BINFO_VTABLE (TYPE_BINFO (type)))
1918 {
1919 tree master_binfo = TYPE_BINFO (val->type);
1920 tree v1 = BINFO_VTABLE (master_binfo);
1921 tree v2 = BINFO_VTABLE (TYPE_BINFO (type));
1922
1923 if (TREE_CODE (v1) == POINTER_PLUS_EXPR)
1924 {
1925 gcc_assert (TREE_CODE (v2) == POINTER_PLUS_EXPR
1926 && operand_equal_p (TREE_OPERAND (v1, 1),
1927 TREE_OPERAND (v2, 1), 0));
1928 v1 = TREE_OPERAND (TREE_OPERAND (v1, 0), 0);
1929 v2 = TREE_OPERAND (TREE_OPERAND (v2, 0), 0);
1930 }
1931 gcc_assert (DECL_ASSEMBLER_NAME (v1)
1932 == DECL_ASSEMBLER_NAME (v2));
1933
1934 if (DECL_EXTERNAL (v1) && !DECL_EXTERNAL (v2))
1935 {
1936 unsigned int i;
1937
1938 set_type_binfo (val->type, TYPE_BINFO (type));
1939 for (i = 0; i < val->types->length (); i++)
1940 {
1941 if (TYPE_BINFO ((*val->types)[i])
1942 == master_binfo)
1943 set_type_binfo ((*val->types)[i], TYPE_BINFO (type));
1944 }
1945 BINFO_TYPE (TYPE_BINFO (type)) = val->type;
1946 }
1947 else
1948 set_type_binfo (type, master_binfo);
1949 }
1950 return build_bases;
1951}
1952
1953/* Get ODR type hash entry for TYPE. If INSERT is true, create
1954 possibly new entry. */
1955
1956odr_type
1957get_odr_type (tree type, bool insert)
1958{
1959 odr_type_d **slot = NULL;
1960 odr_type_d **vtable_slot = NULL;
1961 odr_type val = NULL;
1962 hashval_t hash;
1963 bool build_bases = false;
1964 bool insert_to_odr_array = false;
1965 int base_id = -1;
1966
1967 type = main_odr_variant (type);
1968
1969 gcc_checking_assert (can_be_name_hashed_p (type)
1970 || can_be_vtable_hashed_p (type));
1971
1972 /* Lookup entry, first try name hash, fallback to vtable hash. */
1973 if (can_be_name_hashed_p (type))
1974 {
1975 hash = hash_odr_name (type);
1976 slot = odr_hash->find_slot_with_hash (type, hash,
1977 insert ? INSERT : NO_INSERT);
1978 }
1979 if ((!slot || !*slot) && in_lto_p && can_be_vtable_hashed_p (type))
1980 {
1981 hash = hash_odr_vtable (type);
1982 vtable_slot = odr_vtable_hash->find_slot_with_hash (type, hash,
1983 insert ? INSERT : NO_INSERT);
1984 }
1985
1986 if (!slot && !vtable_slot)
1987 return NULL;
1988
1989 /* See if we already have entry for type. */
1990 if ((slot && *slot) || (vtable_slot && *vtable_slot))
1991 {
1992 if (slot && *slot)
1993 {
1994 val = *slot;
1995 if (flag_checking
1996 && in_lto_p && can_be_vtable_hashed_p (type))
1997 {
1998 hash = hash_odr_vtable (type);
1999 vtable_slot = odr_vtable_hash->find_slot_with_hash (type, hash,
2000 NO_INSERT);
2001 gcc_assert (!vtable_slot || *vtable_slot == *slot);
2002 vtable_slot = NULL;
2003 }
2004 }
2005 else if (*vtable_slot)
2006 val = *vtable_slot;
2007
2008 if (val->type != type
2009 && (!val->types_set || !val->types_set->add (type)))
2010 {
2011 gcc_assert (insert);
2012 /* We have type duplicate, but it may introduce vtable name or
2013 mangled name; be sure to keep hashes in sync. */
2014 if (in_lto_p && can_be_vtable_hashed_p (type)
2015 && (!vtable_slot || !*vtable_slot))
2016 {
2017 if (!vtable_slot)
2018 {
2019 hash = hash_odr_vtable (type);
2020 vtable_slot = odr_vtable_hash->find_slot_with_hash
2021 (type, hash, INSERT);
2022 gcc_checking_assert (!*vtable_slot || *vtable_slot == val);
2023 }
2024 *vtable_slot = val;
2025 }
2026 if (slot && !*slot)
2027 *slot = val;
2028 build_bases = add_type_duplicate (val, type);
2029 }
2030 }
2031 else
2032 {
2033 val = ggc_cleared_alloc<odr_type_d> ();
2034 val->type = type;
2035 val->bases = vNULL;
2036 val->derived_types = vNULL;
2037 if (type_with_linkage_p (type))
2038 val->anonymous_namespace = type_in_anonymous_namespace_p (type);
2039 else
2040 val->anonymous_namespace = 0;
2041 build_bases = COMPLETE_TYPE_P (val->type);
2042 insert_to_odr_array = true;
2043 if (slot)
2044 *slot = val;
2045 if (vtable_slot)
2046 *vtable_slot = val;
2047 }
2048
2049 if (build_bases && TREE_CODE (type) == RECORD_TYPE && TYPE_BINFO (type)
2050 && type_with_linkage_p (type)
2051 && type == TYPE_MAIN_VARIANT (type))
2052 {
2053 tree binfo = TYPE_BINFO (type);
2054 unsigned int i;
2055
2056 gcc_assert (BINFO_TYPE (TYPE_BINFO (val->type)) == type);
2057
2058 val->all_derivations_known = type_all_derivations_known_p (type);
2059 for (i = 0; i < BINFO_N_BASE_BINFOS (binfo); i++)
2060 /* For now record only polymorphic types. other are
2061 pointless for devirtualization and we can not precisely
2062 determine ODR equivalency of these during LTO. */
2063 if (polymorphic_type_binfo_p (BINFO_BASE_BINFO (binfo, i)))
2064 {
2065 tree base_type= BINFO_TYPE (BINFO_BASE_BINFO (binfo, i));
2066 odr_type base = get_odr_type (base_type, true);
2067 gcc_assert (TYPE_MAIN_VARIANT (base_type) == base_type);
2068 base->derived_types.safe_push (val);
2069 val->bases.safe_push (base);
2070 if (base->id > base_id)
2071 base_id = base->id;
2072 }
2073 }
2074 /* Ensure that type always appears after bases. */
2075 if (insert_to_odr_array)
2076 {
2077 if (odr_types_ptr)
2078 val->id = odr_types.length ();
2079 vec_safe_push (odr_types_ptr, val);
2080 }
2081 else if (base_id > val->id)
2082 {
2083 odr_types[val->id] = 0;
2084 /* Be sure we did not recorded any derived types; these may need
2085 renumbering too. */
2086 gcc_assert (val->derived_types.length() == 0);
2087 val->id = odr_types.length ();
2088 vec_safe_push (odr_types_ptr, val);
2089 }
2090 return val;
2091}
2092
2093/* Add TYPE od ODR type hash. */
2094
2095void
2096register_odr_type (tree type)
2097{
2098 if (!odr_hash)
2099 {
2100 odr_hash = new odr_hash_type (23);
2101 if (in_lto_p)
2102 odr_vtable_hash = new odr_vtable_hash_type (23);
2103 }
2104 /* Arrange things to be nicer and insert main variants first.
2105 ??? fundamental prerecorded types do not have mangled names; this
2106 makes it possible that non-ODR type is main_odr_variant of ODR type.
2107 Things may get smoother if LTO FE set mangled name of those types same
2108 way as C++ FE does. */
2109 if (odr_type_p (main_odr_variant (TYPE_MAIN_VARIANT (type)))
2110 && odr_type_p (TYPE_MAIN_VARIANT (type)))
2111 get_odr_type (TYPE_MAIN_VARIANT (type), true);
2112 if (TYPE_MAIN_VARIANT (type) != type && odr_type_p (main_odr_variant (type)))
2113 get_odr_type (type, true);
2114}
2115
2116/* Return true if type is known to have no derivations. */
2117
2118bool
2119type_known_to_have_no_derivations_p (tree t)
2120{
2121 return (type_all_derivations_known_p (t)
2122 && (TYPE_FINAL_P (t)
2123 || (odr_hash
2124 && !get_odr_type (t, true)->derived_types.length())));
2125}
2126
2127/* Dump ODR type T and all its derived types. INDENT specifies indentation for
2128 recursive printing. */
2129
2130static void
2131dump_odr_type (FILE *f, odr_type t, int indent=0)
2132{
2133 unsigned int i;
2134 fprintf (f, "%*s type %i: ", indent * 2, "", t->id);
2135 print_generic_expr (f, t->type, TDF_SLIM);
2136 fprintf (f, "%s", t->anonymous_namespace ? " (anonymous namespace)":"");
2137 fprintf (f, "%s\n", t->all_derivations_known ? " (derivations known)":"");
2138 if (TYPE_NAME (t->type))
2139 {
2140 /*fprintf (f, "%*s defined at: %s:%i\n", indent * 2, "",
2141 DECL_SOURCE_FILE (TYPE_NAME (t->type)),
2142 DECL_SOURCE_LINE (TYPE_NAME (t->type)));*/
2143 if (DECL_ASSEMBLER_NAME_SET_P (TYPE_NAME (t->type)))
2144 fprintf (f, "%*s mangled name: %s\n", indent * 2, "",
2145 IDENTIFIER_POINTER
2146 (DECL_ASSEMBLER_NAME (TYPE_NAME (t->type))));
2147 }
2148 if (t->bases.length ())
2149 {
2150 fprintf (f, "%*s base odr type ids: ", indent * 2, "");
2151 for (i = 0; i < t->bases.length (); i++)
2152 fprintf (f, " %i", t->bases[i]->id);
2153 fprintf (f, "\n");
2154 }
2155 if (t->derived_types.length ())
2156 {
2157 fprintf (f, "%*s derived types:\n", indent * 2, "");
2158 for (i = 0; i < t->derived_types.length (); i++)
2159 dump_odr_type (f, t->derived_types[i], indent + 1);
2160 }
2161 fprintf (f, "\n");
2162}
2163
2164/* Dump the type inheritance graph. */
2165
2166static void
2167dump_type_inheritance_graph (FILE *f)
2168{
2169 unsigned int i;
2170 if (!odr_types_ptr)
2171 return;
2172 fprintf (f, "\n\nType inheritance graph:\n");
2173 for (i = 0; i < odr_types.length (); i++)
2174 {
2175 if (odr_types[i] && odr_types[i]->bases.length () == 0)
2176 dump_odr_type (f, odr_types[i]);
2177 }
2178 for (i = 0; i < odr_types.length (); i++)
2179 {
2180 if (odr_types[i] && odr_types[i]->types && odr_types[i]->types->length ())
2181 {
2182 unsigned int j;
2183 fprintf (f, "Duplicate tree types for odr type %i\n", i);
2184 print_node (f, "", odr_types[i]->type, 0);
2185 for (j = 0; j < odr_types[i]->types->length (); j++)
2186 {
2187 tree t;
2188 fprintf (f, "duplicate #%i\n", j);
2189 print_node (f, "", (*odr_types[i]->types)[j], 0);
2190 t = (*odr_types[i]->types)[j];
2191 while (TYPE_P (t) && TYPE_CONTEXT (t))
2192 {
2193 t = TYPE_CONTEXT (t);
2194 print_node (f, "", t, 0);
2195 }
2196 putc ('\n',f);
2197 }
2198 }
2199 }
2200}
2201
2202/* Initialize IPA devirt and build inheritance tree graph. */
2203
2204void
2205build_type_inheritance_graph (void)
2206{
2207 struct symtab_node *n;
2208 FILE *inheritance_dump_file;
2209 dump_flags_t flags;
2210
2211 if (odr_hash)
2212 return;
2213 timevar_push (TV_IPA_INHERITANCE);
2214 inheritance_dump_file = dump_begin (TDI_inheritance, &flags);
2215 odr_hash = new odr_hash_type (23);
2216 if (in_lto_p)
2217 odr_vtable_hash = new odr_vtable_hash_type (23);
2218
2219 /* We reconstruct the graph starting of types of all methods seen in the
2220 unit. */
2221 FOR_EACH_SYMBOL (n)
2222 if (is_a <cgraph_node *> (n)
2223 && DECL_VIRTUAL_P (n->decl)
2224 && n->real_symbol_p ())
2225 get_odr_type (TYPE_METHOD_BASETYPE (TREE_TYPE (n->decl)), true);
2226
2227 /* Look also for virtual tables of types that do not define any methods.
2228
2229 We need it in a case where class B has virtual base of class A
2230 re-defining its virtual method and there is class C with no virtual
2231 methods with B as virtual base.
2232
2233 Here we output B's virtual method in two variant - for non-virtual
2234 and virtual inheritance. B's virtual table has non-virtual version,
2235 while C's has virtual.
2236
2237 For this reason we need to know about C in order to include both
2238 variants of B. More correctly, record_target_from_binfo should
2239 add both variants of the method when walking B, but we have no
2240 link in between them.
2241
2242 We rely on fact that either the method is exported and thus we
2243 assume it is called externally or C is in anonymous namespace and
2244 thus we will see the vtable. */
2245
2246 else if (is_a <varpool_node *> (n)
2247 && DECL_VIRTUAL_P (n->decl)
2248 && TREE_CODE (DECL_CONTEXT (n->decl)) == RECORD_TYPE
2249 && TYPE_BINFO (DECL_CONTEXT (n->decl))
2250 && polymorphic_type_binfo_p (TYPE_BINFO (DECL_CONTEXT (n->decl))))
2251 get_odr_type (TYPE_MAIN_VARIANT (DECL_CONTEXT (n->decl)), true);
2252 if (inheritance_dump_file)
2253 {
2254 dump_type_inheritance_graph (inheritance_dump_file);
2255 dump_end (TDI_inheritance, inheritance_dump_file);
2256 }
2257 timevar_pop (TV_IPA_INHERITANCE);
2258}
2259
2260/* Return true if N has reference from live virtual table
2261 (and thus can be a destination of polymorphic call).
2262 Be conservatively correct when callgraph is not built or
2263 if the method may be referred externally. */
2264
2265static bool
2266referenced_from_vtable_p (struct cgraph_node *node)
2267{
2268 int i;
2269 struct ipa_ref *ref;
2270 bool found = false;
2271
2272 if (node->externally_visible
2273 || DECL_EXTERNAL (node->decl)
2274 || node->used_from_other_partition)
2275 return true;
2276
2277 /* Keep this test constant time.
2278 It is unlikely this can happen except for the case where speculative
2279 devirtualization introduced many speculative edges to this node.
2280 In this case the target is very likely alive anyway. */
2281 if (node->ref_list.referring.length () > 100)
2282 return true;
2283
2284 /* We need references built. */
2285 if (symtab->state <= CONSTRUCTION)
2286 return true;
2287
2288 for (i = 0; node->iterate_referring (i, ref); i++)
2289 if ((ref->use == IPA_REF_ALIAS
2290 && referenced_from_vtable_p (dyn_cast<cgraph_node *> (ref->referring)))
2291 || (ref->use == IPA_REF_ADDR
2292 && VAR_P (ref->referring->decl)
2293 && DECL_VIRTUAL_P (ref->referring->decl)))
2294 {
2295 found = true;
2296 break;
2297 }
2298 return found;
2299}
2300
2301/* Return if TARGET is cxa_pure_virtual. */
2302
2303static bool
2304is_cxa_pure_virtual_p (tree target)
2305{
2306 return target && TREE_CODE (TREE_TYPE (target)) != METHOD_TYPE
2307 && DECL_NAME (target)
2308 && id_equal (DECL_NAME (target),
2309 "__cxa_pure_virtual");
2310}
2311
2312/* If TARGET has associated node, record it in the NODES array.
2313 CAN_REFER specify if program can refer to the target directly.
2314 if TARGET is unknown (NULL) or it can not be inserted (for example because
2315 its body was already removed and there is no way to refer to it), clear
2316 COMPLETEP. */
2317
2318static void
2319maybe_record_node (vec <cgraph_node *> &nodes,
2320 tree target, hash_set<tree> *inserted,
2321 bool can_refer,
2322 bool *completep)
2323{
2324 struct cgraph_node *target_node, *alias_target;
2325 enum availability avail;
2326 bool pure_virtual = is_cxa_pure_virtual_p (target);
2327
2328 /* __builtin_unreachable do not need to be added into
2329 list of targets; the runtime effect of calling them is undefined.
2330 Only "real" virtual methods should be accounted. */
2331 if (target && TREE_CODE (TREE_TYPE (target)) != METHOD_TYPE && !pure_virtual)
2332 return;
2333
2334 if (!can_refer)
2335 {
2336 /* The only case when method of anonymous namespace becomes unreferable
2337 is when we completely optimized it out. */
2338 if (flag_ltrans
2339 || !target
2340 || !type_in_anonymous_namespace_p (DECL_CONTEXT (target)))
2341 *completep = false;
2342 return;
2343 }
2344
2345 if (!target)
2346 return;
2347
2348 target_node = cgraph_node::get (target);
2349
2350 /* Prefer alias target over aliases, so we do not get confused by
2351 fake duplicates. */
2352 if (target_node)
2353 {
2354 alias_target = target_node->ultimate_alias_target (&avail);
2355 if (target_node != alias_target
2356 && avail >= AVAIL_AVAILABLE
2357 && target_node->get_availability ())
2358 target_node = alias_target;
2359 }
2360
2361 /* Method can only be called by polymorphic call if any
2362 of vtables referring to it are alive.
2363
2364 While this holds for non-anonymous functions, too, there are
2365 cases where we want to keep them in the list; for example
2366 inline functions with -fno-weak are static, but we still
2367 may devirtualize them when instance comes from other unit.
2368 The same holds for LTO.
2369
2370 Currently we ignore these functions in speculative devirtualization.
2371 ??? Maybe it would make sense to be more aggressive for LTO even
2372 elsewhere. */
2373 if (!flag_ltrans
2374 && !pure_virtual
2375 && type_in_anonymous_namespace_p (DECL_CONTEXT (target))
2376 && (!target_node
2377 || !referenced_from_vtable_p (target_node)))
2378 ;
2379 /* See if TARGET is useful function we can deal with. */
2380 else if (target_node != NULL
2381 && (TREE_PUBLIC (target)
2382 || DECL_EXTERNAL (target)
2383 || target_node->definition)
2384 && target_node->real_symbol_p ())
2385 {
2386 gcc_assert (!target_node->global.inlined_to);
2387 gcc_assert (target_node->real_symbol_p ());
2388 /* When sanitizing, do not assume that __cxa_pure_virtual is not called
2389 by valid program. */
2390 if (flag_sanitize & SANITIZE_UNREACHABLE)
2391 ;
2392 /* Only add pure virtual if it is the only possible target. This way
2393 we will preserve the diagnostics about pure virtual called in many
2394 cases without disabling optimization in other. */
2395 else if (pure_virtual)
2396 {
2397 if (nodes.length ())
2398 return;
2399 }
2400 /* If we found a real target, take away cxa_pure_virtual. */
2401 else if (!pure_virtual && nodes.length () == 1
2402 && is_cxa_pure_virtual_p (nodes[0]->decl))
2403 nodes.pop ();
2404 if (pure_virtual && nodes.length ())
2405 return;
2406 if (!inserted->add (target))
2407 {
2408 cached_polymorphic_call_targets->add (target_node);
2409 nodes.safe_push (target_node);
2410 }
2411 }
2412 else if (!completep)
2413 ;
2414 /* We have definition of __cxa_pure_virtual that is not accessible (it is
2415 optimized out or partitioned to other unit) so we can not add it. When
2416 not sanitizing, there is nothing to do.
2417 Otherwise declare the list incomplete. */
2418 else if (pure_virtual)
2419 {
2420 if (flag_sanitize & SANITIZE_UNREACHABLE)
2421 *completep = false;
2422 }
2423 else if (flag_ltrans
2424 || !type_in_anonymous_namespace_p (DECL_CONTEXT (target)))
2425 *completep = false;
2426}
2427
2428/* See if BINFO's type matches OUTER_TYPE. If so, look up
2429 BINFO of subtype of OTR_TYPE at OFFSET and in that BINFO find
2430 method in vtable and insert method to NODES array
2431 or BASES_TO_CONSIDER if this array is non-NULL.
2432 Otherwise recurse to base BINFOs.
2433 This matches what get_binfo_at_offset does, but with offset
2434 being unknown.
2435
2436 TYPE_BINFOS is a stack of BINFOS of types with defined
2437 virtual table seen on way from class type to BINFO.
2438
2439 MATCHED_VTABLES tracks virtual tables we already did lookup
2440 for virtual function in. INSERTED tracks nodes we already
2441 inserted.
2442
2443 ANONYMOUS is true if BINFO is part of anonymous namespace.
2444
2445 Clear COMPLETEP when we hit unreferable target.
2446 */
2447
2448static void
2449record_target_from_binfo (vec <cgraph_node *> &nodes,
2450 vec <tree> *bases_to_consider,
2451 tree binfo,
2452 tree otr_type,
2453 vec <tree> &type_binfos,
2454 HOST_WIDE_INT otr_token,
2455 tree outer_type,
2456 HOST_WIDE_INT offset,
2457 hash_set<tree> *inserted,
2458 hash_set<tree> *matched_vtables,
2459 bool anonymous,
2460 bool *completep)
2461{
2462 tree type = BINFO_TYPE (binfo);
2463 int i;
2464 tree base_binfo;
2465
2466
2467 if (BINFO_VTABLE (binfo))
2468 type_binfos.safe_push (binfo);
2469 if (types_same_for_odr (type, outer_type))
2470 {
2471 int i;
2472 tree type_binfo = NULL;
2473
2474 /* Look up BINFO with virtual table. For normal types it is always last
2475 binfo on stack. */
2476 for (i = type_binfos.length () - 1; i >= 0; i--)
2477 if (BINFO_OFFSET (type_binfos[i]) == BINFO_OFFSET (binfo))
2478 {
2479 type_binfo = type_binfos[i];
2480 break;
2481 }
2482 if (BINFO_VTABLE (binfo))
2483 type_binfos.pop ();
2484 /* If this is duplicated BINFO for base shared by virtual inheritance,
2485 we may not have its associated vtable. This is not a problem, since
2486 we will walk it on the other path. */
2487 if (!type_binfo)
2488 return;
2489 tree inner_binfo = get_binfo_at_offset (type_binfo,
2490 offset, otr_type);
2491 if (!inner_binfo)
2492 {
2493 gcc_assert (odr_violation_reported);
2494 return;
2495 }
2496 /* For types in anonymous namespace first check if the respective vtable
2497 is alive. If not, we know the type can't be called. */
2498 if (!flag_ltrans && anonymous)
2499 {
2500 tree vtable = BINFO_VTABLE (inner_binfo);
2501 varpool_node *vnode;
2502
2503 if (TREE_CODE (vtable) == POINTER_PLUS_EXPR)
2504 vtable = TREE_OPERAND (TREE_OPERAND (vtable, 0), 0);
2505 vnode = varpool_node::get (vtable);
2506 if (!vnode || !vnode->definition)
2507 return;
2508 }
2509 gcc_assert (inner_binfo);
2510 if (bases_to_consider
2511 ? !matched_vtables->contains (BINFO_VTABLE (inner_binfo))
2512 : !matched_vtables->add (BINFO_VTABLE (inner_binfo)))
2513 {
2514 bool can_refer;
2515 tree target = gimple_get_virt_method_for_binfo (otr_token,
2516 inner_binfo,
2517 &can_refer);
2518 if (!bases_to_consider)
2519 maybe_record_node (nodes, target, inserted, can_refer, completep);
2520 /* Destructors are never called via construction vtables. */
2521 else if (!target || !DECL_CXX_DESTRUCTOR_P (target))
2522 bases_to_consider->safe_push (target);
2523 }
2524 return;
2525 }
2526
2527 /* Walk bases. */
2528 for (i = 0; BINFO_BASE_ITERATE (binfo, i, base_binfo); i++)
2529 /* Walking bases that have no virtual method is pointless exercise. */
2530 if (polymorphic_type_binfo_p (base_binfo))
2531 record_target_from_binfo (nodes, bases_to_consider, base_binfo, otr_type,
2532 type_binfos,
2533 otr_token, outer_type, offset, inserted,
2534 matched_vtables, anonymous, completep);
2535 if (BINFO_VTABLE (binfo))
2536 type_binfos.pop ();
2537}
2538
2539/* Look up virtual methods matching OTR_TYPE (with OFFSET and OTR_TOKEN)
2540 of TYPE, insert them to NODES, recurse into derived nodes.
2541 INSERTED is used to avoid duplicate insertions of methods into NODES.
2542 MATCHED_VTABLES are used to avoid duplicate walking vtables.
2543 Clear COMPLETEP if unreferable target is found.
2544
2545 If CONSIDER_CONSTRUCTION is true, record to BASES_TO_CONSIDER
2546 all cases where BASE_SKIPPED is true (because the base is abstract
2547 class). */
2548
2549static void
2550possible_polymorphic_call_targets_1 (vec <cgraph_node *> &nodes,
2551 hash_set<tree> *inserted,
2552 hash_set<tree> *matched_vtables,
2553 tree otr_type,
2554 odr_type type,
2555 HOST_WIDE_INT otr_token,
2556 tree outer_type,
2557 HOST_WIDE_INT offset,
2558 bool *completep,
2559 vec <tree> &bases_to_consider,
2560 bool consider_construction)
2561{
2562 tree binfo = TYPE_BINFO (type->type);
2563 unsigned int i;
2564 auto_vec <tree, 8> type_binfos;
2565 bool possibly_instantiated = type_possibly_instantiated_p (type->type);
2566
2567 /* We may need to consider types w/o instances because of possible derived
2568 types using their methods either directly or via construction vtables.
2569 We are safe to skip them when all derivations are known, since we will
2570 handle them later.
2571 This is done by recording them to BASES_TO_CONSIDER array. */
2572 if (possibly_instantiated || consider_construction)
2573 {
2574 record_target_from_binfo (nodes,
2575 (!possibly_instantiated
2576 && type_all_derivations_known_p (type->type))
2577 ? &bases_to_consider : NULL,
2578 binfo, otr_type, type_binfos, otr_token,
2579 outer_type, offset,
2580 inserted, matched_vtables,
2581 type->anonymous_namespace, completep);
2582 }
2583 for (i = 0; i < type->derived_types.length (); i++)
2584 possible_polymorphic_call_targets_1 (nodes, inserted,
2585 matched_vtables,
2586 otr_type,
2587 type->derived_types[i],
2588 otr_token, outer_type, offset, completep,
2589 bases_to_consider, consider_construction);
2590}
2591
2592/* Cache of queries for polymorphic call targets.
2593
2594 Enumerating all call targets may get expensive when there are many
2595 polymorphic calls in the program, so we memoize all the previous
2596 queries and avoid duplicated work. */
2597
2598struct polymorphic_call_target_d
2599{
2600 HOST_WIDE_INT otr_token;
2601 ipa_polymorphic_call_context context;
2602 odr_type type;
2603 vec <cgraph_node *> targets;
2604 tree decl_warning;
2605 int type_warning;
2606 bool complete;
2607 bool speculative;
2608};
2609
2610/* Polymorphic call target cache helpers. */
2611
2612struct polymorphic_call_target_hasher
2613 : pointer_hash <polymorphic_call_target_d>
2614{
2615 static inline hashval_t hash (const polymorphic_call_target_d *);
2616 static inline bool equal (const polymorphic_call_target_d *,
2617 const polymorphic_call_target_d *);
2618 static inline void remove (polymorphic_call_target_d *);
2619};
2620
2621/* Return the computed hashcode for ODR_QUERY. */
2622
2623inline hashval_t
2624polymorphic_call_target_hasher::hash (const polymorphic_call_target_d *odr_query)
2625{
2626 inchash::hash hstate (odr_query->otr_token);
2627
2628 hstate.add_hwi (odr_query->type->id);
2629 hstate.merge_hash (TYPE_UID (odr_query->context.outer_type));
2630 hstate.add_hwi (odr_query->context.offset);
2631
2632 if (odr_query->context.speculative_outer_type)
2633 {
2634 hstate.merge_hash (TYPE_UID (odr_query->context.speculative_outer_type));
2635 hstate.add_hwi (odr_query->context.speculative_offset);
2636 }
2637 hstate.add_flag (odr_query->speculative);
2638 hstate.add_flag (odr_query->context.maybe_in_construction);
2639 hstate.add_flag (odr_query->context.maybe_derived_type);
2640 hstate.add_flag (odr_query->context.speculative_maybe_derived_type);
2641 hstate.commit_flag ();
2642 return hstate.end ();
2643}
2644
2645/* Compare cache entries T1 and T2. */
2646
2647inline bool
2648polymorphic_call_target_hasher::equal (const polymorphic_call_target_d *t1,
2649 const polymorphic_call_target_d *t2)
2650{
2651 return (t1->type == t2->type && t1->otr_token == t2->otr_token
2652 && t1->speculative == t2->speculative
2653 && t1->context.offset == t2->context.offset
2654 && t1->context.speculative_offset == t2->context.speculative_offset
2655 && t1->context.outer_type == t2->context.outer_type
2656 && t1->context.speculative_outer_type == t2->context.speculative_outer_type
2657 && t1->context.maybe_in_construction
2658 == t2->context.maybe_in_construction
2659 && t1->context.maybe_derived_type == t2->context.maybe_derived_type
2660 && (t1->context.speculative_maybe_derived_type
2661 == t2->context.speculative_maybe_derived_type));
2662}
2663
2664/* Remove entry in polymorphic call target cache hash. */
2665
2666inline void
2667polymorphic_call_target_hasher::remove (polymorphic_call_target_d *v)
2668{
2669 v->targets.release ();
2670 free (v);
2671}
2672
2673/* Polymorphic call target query cache. */
2674
2675typedef hash_table<polymorphic_call_target_hasher>
2676 polymorphic_call_target_hash_type;
2677static polymorphic_call_target_hash_type *polymorphic_call_target_hash;
2678
2679/* Destroy polymorphic call target query cache. */
2680
2681static void
2682free_polymorphic_call_targets_hash ()
2683{
2684 if (cached_polymorphic_call_targets)
2685 {
2686 delete polymorphic_call_target_hash;
2687 polymorphic_call_target_hash = NULL;
2688 delete cached_polymorphic_call_targets;
2689 cached_polymorphic_call_targets = NULL;
2690 }
2691}
2692
2693/* When virtual function is removed, we may need to flush the cache. */
2694
2695static void
2696devirt_node_removal_hook (struct cgraph_node *n, void *d ATTRIBUTE_UNUSED)
2697{
2698 if (cached_polymorphic_call_targets
2699 && cached_polymorphic_call_targets->contains (n))
2700 free_polymorphic_call_targets_hash ();
2701}
2702
2703/* Look up base of BINFO that has virtual table VTABLE with OFFSET. */
2704
2705tree
2706subbinfo_with_vtable_at_offset (tree binfo, unsigned HOST_WIDE_INT offset,
2707 tree vtable)
2708{
2709 tree v = BINFO_VTABLE (binfo);
2710 int i;
2711 tree base_binfo;
2712 unsigned HOST_WIDE_INT this_offset;
2713
2714 if (v)
2715 {
2716 if (!vtable_pointer_value_to_vtable (v, &v, &this_offset))
2717 gcc_unreachable ();
2718
2719 if (offset == this_offset
2720 && DECL_ASSEMBLER_NAME (v) == DECL_ASSEMBLER_NAME (vtable))
2721 return binfo;
2722 }
2723
2724 for (i = 0; BINFO_BASE_ITERATE (binfo, i, base_binfo); i++)
2725 if (polymorphic_type_binfo_p (base_binfo))
2726 {
2727 base_binfo = subbinfo_with_vtable_at_offset (base_binfo, offset, vtable);
2728 if (base_binfo)
2729 return base_binfo;
2730 }
2731 return NULL;
2732}
2733
2734/* T is known constant value of virtual table pointer.
2735 Store virtual table to V and its offset to OFFSET.
2736 Return false if T does not look like virtual table reference. */
2737
2738bool
2739vtable_pointer_value_to_vtable (const_tree t, tree *v,
2740 unsigned HOST_WIDE_INT *offset)
2741{
2742 /* We expect &MEM[(void *)&virtual_table + 16B].
2743 We obtain object's BINFO from the context of the virtual table.
2744 This one contains pointer to virtual table represented via
2745 POINTER_PLUS_EXPR. Verify that this pointer matches what
2746 we propagated through.
2747
2748 In the case of virtual inheritance, the virtual tables may
2749 be nested, i.e. the offset may be different from 16 and we may
2750 need to dive into the type representation. */
2751 if (TREE_CODE (t) == ADDR_EXPR
2752 && TREE_CODE (TREE_OPERAND (t, 0)) == MEM_REF
2753 && TREE_CODE (TREE_OPERAND (TREE_OPERAND (t, 0), 0)) == ADDR_EXPR
2754 && TREE_CODE (TREE_OPERAND (TREE_OPERAND (t, 0), 1)) == INTEGER_CST
2755 && (TREE_CODE (TREE_OPERAND (TREE_OPERAND (TREE_OPERAND (t, 0), 0), 0))
2756 == VAR_DECL)
2757 && DECL_VIRTUAL_P (TREE_OPERAND (TREE_OPERAND
2758 (TREE_OPERAND (t, 0), 0), 0)))
2759 {
2760 *v = TREE_OPERAND (TREE_OPERAND (TREE_OPERAND (t, 0), 0), 0);
2761 *offset = tree_to_uhwi (TREE_OPERAND (TREE_OPERAND (t, 0), 1));
2762 return true;
2763 }
2764
2765 /* Alternative representation, used by C++ frontend is POINTER_PLUS_EXPR.
2766 We need to handle it when T comes from static variable initializer or
2767 BINFO. */
2768 if (TREE_CODE (t) == POINTER_PLUS_EXPR)
2769 {
2770 *offset = tree_to_uhwi (TREE_OPERAND (t, 1));
2771 t = TREE_OPERAND (t, 0);
2772 }
2773 else
2774 *offset = 0;
2775
2776 if (TREE_CODE (t) != ADDR_EXPR)
2777 return false;
2778 *v = TREE_OPERAND (t, 0);
2779 return true;
2780}
2781
2782/* T is known constant value of virtual table pointer. Return BINFO of the
2783 instance type. */
2784
2785tree
2786vtable_pointer_value_to_binfo (const_tree t)
2787{
2788 tree vtable;
2789 unsigned HOST_WIDE_INT offset;
2790
2791 if (!vtable_pointer_value_to_vtable (t, &vtable, &offset))
2792 return NULL_TREE;
2793
2794 /* FIXME: for stores of construction vtables we return NULL,
2795 because we do not have BINFO for those. Eventually we should fix
2796 our representation to allow this case to be handled, too.
2797 In the case we see store of BINFO we however may assume
2798 that standard folding will be able to cope with it. */
2799 return subbinfo_with_vtable_at_offset (TYPE_BINFO (DECL_CONTEXT (vtable)),
2800 offset, vtable);
2801}
2802
2803/* Walk bases of OUTER_TYPE that contain OTR_TYPE at OFFSET.
2804 Look up their respective virtual methods for OTR_TOKEN and OTR_TYPE
2805 and insert them in NODES.
2806
2807 MATCHED_VTABLES and INSERTED is used to avoid duplicated work. */
2808
2809static void
2810record_targets_from_bases (tree otr_type,
2811 HOST_WIDE_INT otr_token,
2812 tree outer_type,
2813 HOST_WIDE_INT offset,
2814 vec <cgraph_node *> &nodes,
2815 hash_set<tree> *inserted,
2816 hash_set<tree> *matched_vtables,
2817 bool *completep)
2818{
2819 while (true)
2820 {
2821 HOST_WIDE_INT pos, size;
2822 tree base_binfo;
2823 tree fld;
2824
2825 if (types_same_for_odr (outer_type, otr_type))
2826 return;
2827
2828 for (fld = TYPE_FIELDS (outer_type); fld; fld = DECL_CHAIN (fld))
2829 {
2830 if (TREE_CODE (fld) != FIELD_DECL)
2831 continue;
2832
2833 pos = int_bit_position (fld);
2834 size = tree_to_shwi (DECL_SIZE (fld));
2835 if (pos <= offset && (pos + size) > offset
2836 /* Do not get confused by zero sized bases. */
2837 && polymorphic_type_binfo_p (TYPE_BINFO (TREE_TYPE (fld))))
2838 break;
2839 }
2840 /* Within a class type we should always find corresponding fields. */
2841 gcc_assert (fld && TREE_CODE (TREE_TYPE (fld)) == RECORD_TYPE);
2842
2843 /* Nonbase types should have been stripped by outer_class_type. */
2844 gcc_assert (DECL_ARTIFICIAL (fld));
2845
2846 outer_type = TREE_TYPE (fld);
2847 offset -= pos;
2848
2849 base_binfo = get_binfo_at_offset (TYPE_BINFO (outer_type),
2850 offset, otr_type);
2851 if (!base_binfo)
2852 {
2853 gcc_assert (odr_violation_reported);
2854 return;
2855 }
2856 gcc_assert (base_binfo);
2857 if (!matched_vtables->add (BINFO_VTABLE (base_binfo)))
2858 {
2859 bool can_refer;
2860 tree target = gimple_get_virt_method_for_binfo (otr_token,
2861 base_binfo,
2862 &can_refer);
2863 if (!target || ! DECL_CXX_DESTRUCTOR_P (target))
2864 maybe_record_node (nodes, target, inserted, can_refer, completep);
2865 matched_vtables->add (BINFO_VTABLE (base_binfo));
2866 }
2867 }
2868}
2869
2870/* When virtual table is removed, we may need to flush the cache. */
2871
2872static void
2873devirt_variable_node_removal_hook (varpool_node *n,
2874 void *d ATTRIBUTE_UNUSED)
2875{
2876 if (cached_polymorphic_call_targets
2877 && DECL_VIRTUAL_P (n->decl)
2878 && type_in_anonymous_namespace_p (DECL_CONTEXT (n->decl)))
2879 free_polymorphic_call_targets_hash ();
2880}
2881
2882/* Record about how many calls would benefit from given type to be final. */
2883
2884struct odr_type_warn_count
2885{
2886 tree type;
2887 int count;
2888 profile_count dyn_count;
2889};
2890
2891/* Record about how many calls would benefit from given method to be final. */
2892
2893struct decl_warn_count
2894{
2895 tree decl;
2896 int count;
2897 profile_count dyn_count;
2898};
2899
2900/* Information about type and decl warnings. */
2901
2902struct final_warning_record
2903{
2904 profile_count dyn_count;
2905 auto_vec<odr_type_warn_count> type_warnings;
2906 hash_map<tree, decl_warn_count> decl_warnings;
2907};
2908struct final_warning_record *final_warning_records;
2909
2910/* Return vector containing possible targets of polymorphic call of type
2911 OTR_TYPE calling method OTR_TOKEN within type of OTR_OUTER_TYPE and OFFSET.
2912 If INCLUDE_BASES is true, walk also base types of OUTER_TYPES containing
2913 OTR_TYPE and include their virtual method. This is useful for types
2914 possibly in construction or destruction where the virtual table may
2915 temporarily change to one of base types. INCLUDE_DERIVER_TYPES make
2916 us to walk the inheritance graph for all derivations.
2917
2918 If COMPLETEP is non-NULL, store true if the list is complete.
2919 CACHE_TOKEN (if non-NULL) will get stored to an unique ID of entry
2920 in the target cache. If user needs to visit every target list
2921 just once, it can memoize them.
2922
2923 If SPECULATIVE is set, the list will not contain targets that
2924 are not speculatively taken.
2925
2926 Returned vector is placed into cache. It is NOT caller's responsibility
2927 to free it. The vector can be freed on cgraph_remove_node call if
2928 the particular node is a virtual function present in the cache. */
2929
2930vec <cgraph_node *>
2931possible_polymorphic_call_targets (tree otr_type,
2932 HOST_WIDE_INT otr_token,
2933 ipa_polymorphic_call_context context,
2934 bool *completep,
2935 void **cache_token,
2936 bool speculative)
2937{
2938 static struct cgraph_node_hook_list *node_removal_hook_holder;
2939 vec <cgraph_node *> nodes = vNULL;
2940 auto_vec <tree, 8> bases_to_consider;
2941 odr_type type, outer_type;
2942 polymorphic_call_target_d key;
2943 polymorphic_call_target_d **slot;
2944 unsigned int i;
2945 tree binfo, target;
2946 bool complete;
2947 bool can_refer = false;
2948 bool skipped = false;
2949
2950 otr_type = TYPE_MAIN_VARIANT (otr_type);
2951
2952 /* If ODR is not initialized or the context is invalid, return empty
2953 incomplete list. */
2954 if (!odr_hash || context.invalid || !TYPE_BINFO (otr_type))
2955 {
2956 if (completep)
2957 *completep = context.invalid;
2958 if (cache_token)
2959 *cache_token = NULL;
2960 return nodes;
2961 }
2962
2963 /* Do not bother to compute speculative info when user do not asks for it. */
2964 if (!speculative || !context.speculative_outer_type)
2965 context.clear_speculation ();
2966
2967 type = get_odr_type (otr_type, true);
2968
2969 /* Recording type variants would waste results cache. */
2970 gcc_assert (!context.outer_type
2971 || TYPE_MAIN_VARIANT (context.outer_type) == context.outer_type);
2972
2973 /* Look up the outer class type we want to walk.
2974 If we fail to do so, the context is invalid. */
2975 if ((context.outer_type || context.speculative_outer_type)
2976 && !context.restrict_to_inner_class (otr_type))
2977 {
2978 if (completep)
2979 *completep = true;
2980 if (cache_token)
2981 *cache_token = NULL;
2982 return nodes;
2983 }
2984 gcc_assert (!context.invalid);
2985
2986 /* Check that restrict_to_inner_class kept the main variant. */
2987 gcc_assert (!context.outer_type
2988 || TYPE_MAIN_VARIANT (context.outer_type) == context.outer_type);
2989
2990 /* We canonicalize our query, so we do not need extra hashtable entries. */
2991
2992 /* Without outer type, we have no use for offset. Just do the
2993 basic search from inner type. */
2994 if (!context.outer_type)
2995 context.clear_outer_type (otr_type);
2996 /* We need to update our hierarchy if the type does not exist. */
2997 outer_type = get_odr_type (context.outer_type, true);
2998 /* If the type is complete, there are no derivations. */
2999 if (TYPE_FINAL_P (outer_type->type))
3000 context.maybe_derived_type = false;
3001
3002 /* Initialize query cache. */
3003 if (!cached_polymorphic_call_targets)
3004 {
3005 cached_polymorphic_call_targets = new hash_set<cgraph_node *>;
3006 polymorphic_call_target_hash
3007 = new polymorphic_call_target_hash_type (23);
3008 if (!node_removal_hook_holder)
3009 {
3010 node_removal_hook_holder =
3011 symtab->add_cgraph_removal_hook (&devirt_node_removal_hook, NULL);
3012 symtab->add_varpool_removal_hook (&devirt_variable_node_removal_hook,
3013 NULL);
3014 }
3015 }
3016
3017 if (in_lto_p)
3018 {
3019 if (context.outer_type != otr_type)
3020 context.outer_type
3021 = get_odr_type (context.outer_type, true)->type;
3022 if (context.speculative_outer_type)
3023 context.speculative_outer_type
3024 = get_odr_type (context.speculative_outer_type, true)->type;
3025 }
3026
3027 /* Look up cached answer. */
3028 key.type = type;
3029 key.otr_token = otr_token;
3030 key.speculative = speculative;
3031 key.context = context;
3032 slot = polymorphic_call_target_hash->find_slot (&key, INSERT);
3033 if (cache_token)
3034 *cache_token = (void *)*slot;
3035 if (*slot)
3036 {
3037 if (completep)
3038 *completep = (*slot)->complete;
3039 if ((*slot)->type_warning && final_warning_records)
3040 {
3041 final_warning_records->type_warnings[(*slot)->type_warning - 1].count++;
3042 if (!final_warning_records->type_warnings
3043 [(*slot)->type_warning - 1].dyn_count.initialized_p ())
3044 final_warning_records->type_warnings
3045 [(*slot)->type_warning - 1].dyn_count = profile_count::zero ();
3046 if (final_warning_records->dyn_count > 0)
3047 final_warning_records->type_warnings[(*slot)->type_warning - 1].dyn_count
3048 = final_warning_records->type_warnings[(*slot)->type_warning - 1].dyn_count
3049 + final_warning_records->dyn_count;
3050 }
3051 if (!speculative && (*slot)->decl_warning && final_warning_records)
3052 {
3053 struct decl_warn_count *c =
3054 final_warning_records->decl_warnings.get ((*slot)->decl_warning);
3055 c->count++;
3056 if (final_warning_records->dyn_count > 0)
3057 c->dyn_count += final_warning_records->dyn_count;
3058 }
3059 return (*slot)->targets;
3060 }
3061
3062 complete = true;
3063
3064 /* Do actual search. */
3065 timevar_push (TV_IPA_VIRTUAL_CALL);
3066 *slot = XCNEW (polymorphic_call_target_d);
3067 if (cache_token)
3068 *cache_token = (void *)*slot;
3069 (*slot)->type = type;
3070 (*slot)->otr_token = otr_token;
3071 (*slot)->context = context;
3072 (*slot)->speculative = speculative;
3073
3074 hash_set<tree> inserted;
3075 hash_set<tree> matched_vtables;
3076
3077 /* First insert targets we speculatively identified as likely. */
3078 if (context.speculative_outer_type)
3079 {
3080 odr_type speculative_outer_type;
3081 bool speculation_complete = true;
3082
3083 /* First insert target from type itself and check if it may have
3084 derived types. */
3085 speculative_outer_type = get_odr_type (context.speculative_outer_type, true);
3086 if (TYPE_FINAL_P (speculative_outer_type->type))
3087 context.speculative_maybe_derived_type = false;
3088 binfo = get_binfo_at_offset (TYPE_BINFO (speculative_outer_type->type),
3089 context.speculative_offset, otr_type);
3090 if (binfo)
3091 target = gimple_get_virt_method_for_binfo (otr_token, binfo,
3092 &can_refer);
3093 else
3094 target = NULL;
3095
3096 /* In the case we get complete method, we don't need
3097 to walk derivations. */
3098 if (target && DECL_FINAL_P (target))
3099 context.speculative_maybe_derived_type = false;
3100 if (type_possibly_instantiated_p (speculative_outer_type->type))
3101 maybe_record_node (nodes, target, &inserted, can_refer, &speculation_complete);
3102 if (binfo)
3103 matched_vtables.add (BINFO_VTABLE (binfo));
3104
3105
3106 /* Next walk recursively all derived types. */
3107 if (context.speculative_maybe_derived_type)
3108 for (i = 0; i < speculative_outer_type->derived_types.length(); i++)
3109 possible_polymorphic_call_targets_1 (nodes, &inserted,
3110 &matched_vtables,
3111 otr_type,
3112 speculative_outer_type->derived_types[i],
3113 otr_token, speculative_outer_type->type,
3114 context.speculative_offset,
3115 &speculation_complete,
3116 bases_to_consider,
3117 false);
3118 }
3119
3120 if (!speculative || !nodes.length ())
3121 {
3122 /* First see virtual method of type itself. */
3123 binfo = get_binfo_at_offset (TYPE_BINFO (outer_type->type),
3124 context.offset, otr_type);
3125 if (binfo)
3126 target = gimple_get_virt_method_for_binfo (otr_token, binfo,
3127 &can_refer);
3128 else
3129 {
3130 gcc_assert (odr_violation_reported);
3131 target = NULL;
3132 }
3133
3134 /* Destructors are never called through construction virtual tables,
3135 because the type is always known. */
3136 if (target && DECL_CXX_DESTRUCTOR_P (target))
3137 context.maybe_in_construction = false;
3138
3139 if (target)
3140 {
3141 /* In the case we get complete method, we don't need
3142 to walk derivations. */
3143 if (DECL_FINAL_P (target))
3144 context.maybe_derived_type = false;
3145 }
3146
3147 /* If OUTER_TYPE is abstract, we know we are not seeing its instance. */
3148 if (type_possibly_instantiated_p (outer_type->type))
3149 maybe_record_node (nodes, target, &inserted, can_refer, &complete);
3150 else
3151 skipped = true;
3152
3153 if (binfo)
3154 matched_vtables.add (BINFO_VTABLE (binfo));
3155
3156 /* Next walk recursively all derived types. */
3157 if (context.maybe_derived_type)
3158 {
3159 for (i = 0; i < outer_type->derived_types.length(); i++)
3160 possible_polymorphic_call_targets_1 (nodes, &inserted,
3161 &matched_vtables,
3162 otr_type,
3163 outer_type->derived_types[i],
3164 otr_token, outer_type->type,
3165 context.offset, &complete,
3166 bases_to_consider,
3167 context.maybe_in_construction);
3168
3169 if (!outer_type->all_derivations_known)
3170 {
3171 if (!speculative && final_warning_records
3172 && nodes.length () == 1
3173 && TREE_CODE (TREE_TYPE (nodes[0]->decl)) == METHOD_TYPE)
3174 {
3175 if (complete
3176 && warn_suggest_final_types
3177 && !outer_type->derived_types.length ())
3178 {
3179 if (outer_type->id >= (int)final_warning_records->type_warnings.length ())
3180 final_warning_records->type_warnings.safe_grow_cleared
3181 (odr_types.length ());
3182 final_warning_records->type_warnings[outer_type->id].count++;
3183 if (!final_warning_records->type_warnings
3184 [outer_type->id].dyn_count.initialized_p ())
3185 final_warning_records->type_warnings
3186 [outer_type->id].dyn_count = profile_count::zero ();
3187 final_warning_records->type_warnings[outer_type->id].dyn_count
3188 += final_warning_records->dyn_count;
3189 final_warning_records->type_warnings[outer_type->id].type
3190 = outer_type->type;
3191 (*slot)->type_warning = outer_type->id + 1;
3192 }
3193 if (complete
3194 && warn_suggest_final_methods
3195 && types_same_for_odr (DECL_CONTEXT (nodes[0]->decl),
3196 outer_type->type))
3197 {
3198 bool existed;
3199 struct decl_warn_count &c =
3200 final_warning_records->decl_warnings.get_or_insert
3201 (nodes[0]->decl, &existed);
3202
3203 if (existed)
3204 {
3205 c.count++;
3206 c.dyn_count += final_warning_records->dyn_count;
3207 }
3208 else
3209 {
3210 c.count = 1;
3211 c.dyn_count = final_warning_records->dyn_count;
3212 c.decl = nodes[0]->decl;
3213 }
3214 (*slot)->decl_warning = nodes[0]->decl;
3215 }
3216 }
3217 complete = false;
3218 }
3219 }
3220
3221 if (!speculative)
3222 {
3223 /* Destructors are never called through construction virtual tables,
3224 because the type is always known. One of entries may be
3225 cxa_pure_virtual so look to at least two of them. */
3226 if (context.maybe_in_construction)
3227 for (i =0 ; i < MIN (nodes.length (), 2); i++)
3228 if (DECL_CXX_DESTRUCTOR_P (nodes[i]->decl))
3229 context.maybe_in_construction = false;
3230 if (context.maybe_in_construction)
3231 {
3232 if (type != outer_type
3233 && (!skipped
3234 || (context.maybe_derived_type
3235 && !type_all_derivations_known_p (outer_type->type))))
3236 record_targets_from_bases (otr_type, otr_token, outer_type->type,
3237 context.offset, nodes, &inserted,
3238 &matched_vtables, &complete);
3239 if (skipped)
3240 maybe_record_node (nodes, target, &inserted, can_refer, &complete);
3241 for (i = 0; i < bases_to_consider.length(); i++)
3242 maybe_record_node (nodes, bases_to_consider[i], &inserted, can_refer, &complete);
3243 }
3244 }
3245 }
3246
3247 (*slot)->targets = nodes;
3248 (*slot)->complete = complete;
3249 if (completep)
3250 *completep = complete;
3251
3252 timevar_pop (TV_IPA_VIRTUAL_CALL);
3253 return nodes;
3254}
3255
3256bool
3257add_decl_warning (const tree &key ATTRIBUTE_UNUSED, const decl_warn_count &value,
3258 vec<const decl_warn_count*> *vec)
3259{
3260 vec->safe_push (&value);
3261 return true;
3262}
3263
3264/* Dump target list TARGETS into FILE. */
3265
3266static void
3267dump_targets (FILE *f, vec <cgraph_node *> targets)
3268{
3269 unsigned int i;
3270
3271 for (i = 0; i < targets.length (); i++)
3272 {
3273 char *name = NULL;
3274 if (in_lto_p)
3275 name = cplus_demangle_v3 (targets[i]->asm_name (), 0);
3276 fprintf (f, " %s/%i", name ? name : targets[i]->name (),
3277 targets[i]->order);
3278 if (in_lto_p)
3279 free (name);
3280 if (!targets[i]->definition)
3281 fprintf (f, " (no definition%s)",
3282 DECL_DECLARED_INLINE_P (targets[i]->decl)
3283 ? " inline" : "");
3284 }
3285 fprintf (f, "\n");
3286}
3287
3288/* Dump all possible targets of a polymorphic call. */
3289
3290void
3291dump_possible_polymorphic_call_targets (FILE *f,
3292 tree otr_type,
3293 HOST_WIDE_INT otr_token,
3294 const ipa_polymorphic_call_context &ctx)
3295{
3296 vec <cgraph_node *> targets;
3297 bool final;
3298 odr_type type = get_odr_type (TYPE_MAIN_VARIANT (otr_type), false);
3299 unsigned int len;
3300
3301 if (!type)
3302 return;
3303 targets = possible_polymorphic_call_targets (otr_type, otr_token,
3304 ctx,
3305 &final, NULL, false);
3306 fprintf (f, " Targets of polymorphic call of type %i:", type->id);
3307 print_generic_expr (f, type->type, TDF_SLIM);
3308 fprintf (f, " token %i\n", (int)otr_token);
3309
3310 ctx.dump (f);
3311
3312 fprintf (f, " %s%s%s%s\n ",
3313 final ? "This is a complete list." :
3314 "This is partial list; extra targets may be defined in other units.",
3315 ctx.maybe_in_construction ? " (base types included)" : "",
3316 ctx.maybe_derived_type ? " (derived types included)" : "",
3317 ctx.speculative_maybe_derived_type ? " (speculative derived types included)" : "");
3318 len = targets.length ();
3319 dump_targets (f, targets);
3320
3321 targets = possible_polymorphic_call_targets (otr_type, otr_token,
3322 ctx,
3323 &final, NULL, true);
3324 if (targets.length () != len)
3325 {
3326 fprintf (f, " Speculative targets:");
3327 dump_targets (f, targets);
3328 }
3329 /* Ugly: during callgraph construction the target cache may get populated
3330 before all targets are found. While this is harmless (because all local
3331 types are discovered and only in those case we devirtualize fully and we
3332 don't do speculative devirtualization before IPA stage) it triggers
3333 assert here when dumping at that stage also populates the case with
3334 speculative targets. Quietly ignore this. */
3335 gcc_assert (symtab->state < IPA_SSA || targets.length () <= len);
3336 fprintf (f, "\n");
3337}
3338
3339
3340/* Return true if N can be possibly target of a polymorphic call of
3341 OTR_TYPE/OTR_TOKEN. */
3342
3343bool
3344possible_polymorphic_call_target_p (tree otr_type,
3345 HOST_WIDE_INT otr_token,
3346 const ipa_polymorphic_call_context &ctx,
3347 struct cgraph_node *n)
3348{
3349 vec <cgraph_node *> targets;
3350 unsigned int i;
3351 enum built_in_function fcode;
3352 bool final;
3353
3354 if (TREE_CODE (TREE_TYPE (n->decl)) == FUNCTION_TYPE
3355 && ((fcode = DECL_FUNCTION_CODE (n->decl)) == BUILT_IN_UNREACHABLE
3356 || fcode == BUILT_IN_TRAP))
3357 return true;
3358
3359 if (is_cxa_pure_virtual_p (n->decl))
3360 return true;
3361
3362 if (!odr_hash)
3363 return true;
3364 targets = possible_polymorphic_call_targets (otr_type, otr_token, ctx, &final);
3365 for (i = 0; i < targets.length (); i++)
3366 if (n->semantically_equivalent_p (targets[i]))
3367 return true;
3368
3369 /* At a moment we allow middle end to dig out new external declarations
3370 as a targets of polymorphic calls. */
3371 if (!final && !n->definition)
3372 return true;
3373 return false;
3374}
3375
3376
3377
3378/* Return true if N can be possibly target of a polymorphic call of
3379 OBJ_TYPE_REF expression REF in STMT. */
3380
3381bool
3382possible_polymorphic_call_target_p (tree ref,
3383 gimple *stmt,
3384 struct cgraph_node *n)
3385{
3386 ipa_polymorphic_call_context context (current_function_decl, ref, stmt);
3387 tree call_fn = gimple_call_fn (stmt);
3388
3389 return possible_polymorphic_call_target_p (obj_type_ref_class (call_fn),
3390 tree_to_uhwi
3391 (OBJ_TYPE_REF_TOKEN (call_fn)),
3392 context,
3393 n);
3394}
3395
3396
3397/* After callgraph construction new external nodes may appear.
3398 Add them into the graph. */
3399
3400void
3401update_type_inheritance_graph (void)
3402{
3403 struct cgraph_node *n;
3404
3405 if (!odr_hash)
3406 return;
3407 free_polymorphic_call_targets_hash ();
3408 timevar_push (TV_IPA_INHERITANCE);
3409 /* We reconstruct the graph starting from types of all methods seen in the
3410 unit. */
3411 FOR_EACH_FUNCTION (n)
3412 if (DECL_VIRTUAL_P (n->decl)
3413 && !n->definition
3414 && n->real_symbol_p ())
3415 get_odr_type (TYPE_METHOD_BASETYPE (TREE_TYPE (n->decl)), true);
3416 timevar_pop (TV_IPA_INHERITANCE);
3417}
3418
3419
3420/* Return true if N looks like likely target of a polymorphic call.
3421 Rule out cxa_pure_virtual, noreturns, function declared cold and
3422 other obvious cases. */
3423
3424bool
3425likely_target_p (struct cgraph_node *n)
3426{
3427 int flags;
3428 /* cxa_pure_virtual and similar things are not likely. */
3429 if (TREE_CODE (TREE_TYPE (n->decl)) != METHOD_TYPE)
3430 return false;
3431 flags = flags_from_decl_or_type (n->decl);
3432 if (flags & ECF_NORETURN)
3433 return false;
3434 if (lookup_attribute ("cold",
3435 DECL_ATTRIBUTES (n->decl)))
3436 return false;
3437 if (n->frequency < NODE_FREQUENCY_NORMAL)
3438 return false;
3439 /* If there are no live virtual tables referring the target,
3440 the only way the target can be called is an instance coming from other
3441 compilation unit; speculative devirtualization is built around an
3442 assumption that won't happen. */
3443 if (!referenced_from_vtable_p (n))
3444 return false;
3445 return true;
3446}
3447
3448/* Compare type warning records P1 and P2 and choose one with larger count;
3449 helper for qsort. */
3450
3451int
3452type_warning_cmp (const void *p1, const void *p2)
3453{
3454 const odr_type_warn_count *t1 = (const odr_type_warn_count *)p1;
3455 const odr_type_warn_count *t2 = (const odr_type_warn_count *)p2;
3456
3457 if (t1->dyn_count < t2->dyn_count)
3458 return 1;
3459 if (t1->dyn_count > t2->dyn_count)
3460 return -1;
3461 return t2->count - t1->count;
3462}
3463
3464/* Compare decl warning records P1 and P2 and choose one with larger count;
3465 helper for qsort. */
3466
3467int
3468decl_warning_cmp (const void *p1, const void *p2)
3469{
3470 const decl_warn_count *t1 = *(const decl_warn_count * const *)p1;
3471 const decl_warn_count *t2 = *(const decl_warn_count * const *)p2;
3472
3473 if (t1->dyn_count < t2->dyn_count)
3474 return 1;
3475 if (t1->dyn_count > t2->dyn_count)
3476 return -1;
3477 return t2->count - t1->count;
3478}
3479
3480
3481/* Try to speculatively devirtualize call to OTR_TYPE with OTR_TOKEN with
3482 context CTX. */
3483
3484struct cgraph_node *
3485try_speculative_devirtualization (tree otr_type, HOST_WIDE_INT otr_token,
3486 ipa_polymorphic_call_context ctx)
3487{
3488 vec <cgraph_node *>targets
3489 = possible_polymorphic_call_targets
3490 (otr_type, otr_token, ctx, NULL, NULL, true);
3491 unsigned int i;
3492 struct cgraph_node *likely_target = NULL;
3493
3494 for (i = 0; i < targets.length (); i++)
3495 if (likely_target_p (targets[i]))
3496 {
3497 if (likely_target)
3498 return NULL;
3499 likely_target = targets[i];
3500 }
3501 if (!likely_target
3502 ||!likely_target->definition
3503 || DECL_EXTERNAL (likely_target->decl))
3504 return NULL;
3505
3506 /* Don't use an implicitly-declared destructor (c++/58678). */
3507 struct cgraph_node *non_thunk_target
3508 = likely_target->function_symbol ();
3509 if (DECL_ARTIFICIAL (non_thunk_target->decl))
3510 return NULL;
3511 if (likely_target->get_availability () <= AVAIL_INTERPOSABLE
3512 && likely_target->can_be_discarded_p ())
3513 return NULL;
3514 return likely_target;
3515}
3516
3517/* The ipa-devirt pass.
3518 When polymorphic call has only one likely target in the unit,
3519 turn it into a speculative call. */
3520
3521static unsigned int
3522ipa_devirt (void)
3523{
3524 struct cgraph_node *n;
3525 hash_set<void *> bad_call_targets;
3526 struct cgraph_edge *e;
3527
3528 int npolymorphic = 0, nspeculated = 0, nconverted = 0, ncold = 0;
3529 int nmultiple = 0, noverwritable = 0, ndevirtualized = 0, nnotdefined = 0;
3530 int nwrong = 0, nok = 0, nexternal = 0, nartificial = 0;
3531 int ndropped = 0;
3532
3533 if (!odr_types_ptr)
3534 return 0;
3535
3536 if (dump_file)
3537 dump_type_inheritance_graph (dump_file);
3538
3539 /* We can output -Wsuggest-final-methods and -Wsuggest-final-types warnings.
3540 This is implemented by setting up final_warning_records that are updated
3541 by get_polymorphic_call_targets.
3542 We need to clear cache in this case to trigger recomputation of all
3543 entries. */
3544 if (warn_suggest_final_methods || warn_suggest_final_types)
3545 {
3546 final_warning_records = new (final_warning_record);
3547 final_warning_records->dyn_count = profile_count::zero ();
3548 final_warning_records->type_warnings.safe_grow_cleared
3549 (odr_types.length ());
3550 free_polymorphic_call_targets_hash ();
3551 }
3552
3553 FOR_EACH_DEFINED_FUNCTION (n)
3554 {
3555 bool update = false;
3556 if (!opt_for_fn (n->decl, flag_devirtualize))
3557 continue;
3558 if (dump_file && n->indirect_calls)
3559 fprintf (dump_file, "\n\nProcesing function %s\n",
3560 n->dump_name ());
3561 for (e = n->indirect_calls; e; e = e->next_callee)
3562 if (e->indirect_info->polymorphic)
3563 {
3564 struct cgraph_node *likely_target = NULL;
3565 void *cache_token;
3566 bool final;
3567
3568 if (final_warning_records)
3569 final_warning_records->dyn_count = e->count.ipa ();
3570
3571 vec <cgraph_node *>targets
3572 = possible_polymorphic_call_targets
3573 (e, &final, &cache_token, true);
3574 unsigned int i;
3575
3576 /* Trigger warnings by calculating non-speculative targets. */
3577 if (warn_suggest_final_methods || warn_suggest_final_types)
3578 possible_polymorphic_call_targets (e);
3579
3580 if (dump_file)
3581 dump_possible_polymorphic_call_targets
3582 (dump_file, e);
3583
3584 npolymorphic++;
3585
3586 /* See if the call can be devirtualized by means of ipa-prop's
3587 polymorphic call context propagation. If not, we can just
3588 forget about this call being polymorphic and avoid some heavy
3589 lifting in remove_unreachable_nodes that will otherwise try to
3590 keep all possible targets alive until inlining and in the inliner
3591 itself.
3592
3593 This may need to be revisited once we add further ways to use
3594 the may edges, but it is a resonable thing to do right now. */
3595
3596 if ((e->indirect_info->param_index == -1
3597 || (!opt_for_fn (n->decl, flag_devirtualize_speculatively)
3598 && e->indirect_info->vptr_changed))
3599 && !flag_ltrans_devirtualize)
3600 {
3601 e->indirect_info->polymorphic = false;
3602 ndropped++;
3603 if (dump_file)
3604 fprintf (dump_file, "Dropping polymorphic call info;"
3605 " it can not be used by ipa-prop\n");
3606 }
3607
3608 if (!opt_for_fn (n->decl, flag_devirtualize_speculatively))
3609 continue;
3610
3611 if (!e->maybe_hot_p ())
3612 {
3613 if (dump_file)
3614 fprintf (dump_file, "Call is cold\n\n");
3615 ncold++;
3616 continue;
3617 }
3618 if (e->speculative)
3619 {
3620 if (dump_file)
3621 fprintf (dump_file, "Call is already speculated\n\n");
3622 nspeculated++;
3623
3624 /* When dumping see if we agree with speculation. */
3625 if (!dump_file)
3626 continue;
3627 }
3628 if (bad_call_targets.contains (cache_token))
3629 {
3630 if (dump_file)
3631 fprintf (dump_file, "Target list is known to be useless\n\n");
3632 nmultiple++;
3633 continue;
3634 }
3635 for (i = 0; i < targets.length (); i++)
3636 if (likely_target_p (targets[i]))
3637 {
3638 if (likely_target)
3639 {
3640 likely_target = NULL;
3641 if (dump_file)
3642 fprintf (dump_file, "More than one likely target\n\n");
3643 nmultiple++;
3644 break;
3645 }
3646 likely_target = targets[i];
3647 }
3648 if (!likely_target)
3649 {
3650 bad_call_targets.add (cache_token);
3651 continue;
3652 }
3653 /* This is reached only when dumping; check if we agree or disagree
3654 with the speculation. */
3655 if (e->speculative)
3656 {
3657 struct cgraph_edge *e2;
3658 struct ipa_ref *ref;
3659 e->speculative_call_info (e2, e, ref);
3660 if (e2->callee->ultimate_alias_target ()
3661 == likely_target->ultimate_alias_target ())
3662 {
3663 fprintf (dump_file, "We agree with speculation\n\n");
3664 nok++;
3665 }
3666 else
3667 {
3668 fprintf (dump_file, "We disagree with speculation\n\n");
3669 nwrong++;
3670 }
3671 continue;
3672 }
3673 if (!likely_target->definition)
3674 {
3675 if (dump_file)
3676 fprintf (dump_file, "Target is not a definition\n\n");
3677 nnotdefined++;
3678 continue;
3679 }
3680 /* Do not introduce new references to external symbols. While we
3681 can handle these just well, it is common for programs to
3682 incorrectly with headers defining methods they are linked
3683 with. */
3684 if (DECL_EXTERNAL (likely_target->decl))
3685 {
3686 if (dump_file)
3687 fprintf (dump_file, "Target is external\n\n");
3688 nexternal++;
3689 continue;
3690 }
3691 /* Don't use an implicitly-declared destructor (c++/58678). */
3692 struct cgraph_node *non_thunk_target
3693 = likely_target->function_symbol ();
3694 if (DECL_ARTIFICIAL (non_thunk_target->decl))
3695 {
3696 if (dump_file)
3697 fprintf (dump_file, "Target is artificial\n\n");
3698 nartificial++;
3699 continue;
3700 }
3701 if (likely_target->get_availability () <= AVAIL_INTERPOSABLE
3702 && likely_target->can_be_discarded_p ())
3703 {
3704 if (dump_file)
3705 fprintf (dump_file, "Target is overwritable\n\n");
3706 noverwritable++;
3707 continue;
3708 }
3709 else if (dbg_cnt (devirt))
3710 {
3711 if (dump_enabled_p ())
3712 {
3713 location_t locus = gimple_location_safe (e->call_stmt);
3714 dump_printf_loc (MSG_OPTIMIZED_LOCATIONS, locus,
3715 "speculatively devirtualizing call "
3716 "in %s to %s\n",
3717 n->dump_name (),
3718 likely_target->dump_name ());
3719 }
3720 if (!likely_target->can_be_discarded_p ())
3721 {
3722 cgraph_node *alias;
3723 alias = dyn_cast<cgraph_node *> (likely_target->noninterposable_alias ());
3724 if (alias)
3725 likely_target = alias;
3726 }
3727 nconverted++;
3728 update = true;
3729 e->make_speculative
3730 (likely_target, e->count.apply_scale (8, 10));
3731 }
3732 }
3733 if (update)
3734 ipa_update_overall_fn_summary (n);
3735 }
3736 if (warn_suggest_final_methods || warn_suggest_final_types)
3737 {
3738 if (warn_suggest_final_types)
3739 {
3740 final_warning_records->type_warnings.qsort (type_warning_cmp);
3741 for (unsigned int i = 0;
3742 i < final_warning_records->type_warnings.length (); i++)
3743 if (final_warning_records->type_warnings[i].count)
3744 {
3745 tree type = final_warning_records->type_warnings[i].type;
3746 int count = final_warning_records->type_warnings[i].count;
3747 profile_count dyn_count
3748 = final_warning_records->type_warnings[i].dyn_count;
3749
3750 if (!(dyn_count > 0))
3751 warning_n (DECL_SOURCE_LOCATION (TYPE_NAME (type)),
3752 OPT_Wsuggest_final_types, count,
3753 "Declaring type %qD final "
3754 "would enable devirtualization of %i call",
3755 "Declaring type %qD final "
3756 "would enable devirtualization of %i calls",
3757 type,
3758 count);
3759 else
3760 warning_n (DECL_SOURCE_LOCATION (TYPE_NAME (type)),
3761 OPT_Wsuggest_final_types, count,
3762 "Declaring type %qD final "
3763 "would enable devirtualization of %i call "
3764 "executed %lli times",
3765 "Declaring type %qD final "
3766 "would enable devirtualization of %i calls "
3767 "executed %lli times",
3768 type,
3769 count,
3770 (long long) dyn_count.to_gcov_type ());
3771 }
3772 }
3773
3774 if (warn_suggest_final_methods)
3775 {
3776 auto_vec<const decl_warn_count*> decl_warnings_vec;
3777
3778 final_warning_records->decl_warnings.traverse
3779 <vec<const decl_warn_count *> *, add_decl_warning> (&decl_warnings_vec);
3780 decl_warnings_vec.qsort (decl_warning_cmp);
3781 for (unsigned int i = 0; i < decl_warnings_vec.length (); i++)
3782 {
3783 tree decl = decl_warnings_vec[i]->decl;
3784 int count = decl_warnings_vec[i]->count;
3785 profile_count dyn_count
3786 = decl_warnings_vec[i]->dyn_count;
3787
3788 if (!(dyn_count > 0))
3789 if (DECL_CXX_DESTRUCTOR_P (decl))
3790 warning_n (DECL_SOURCE_LOCATION (decl),
3791 OPT_Wsuggest_final_methods, count,
3792 "Declaring virtual destructor of %qD final "
3793 "would enable devirtualization of %i call",
3794 "Declaring virtual destructor of %qD final "
3795 "would enable devirtualization of %i calls",
3796 DECL_CONTEXT (decl), count);
3797 else
3798 warning_n (DECL_SOURCE_LOCATION (decl),
3799 OPT_Wsuggest_final_methods, count,
3800 "Declaring method %qD final "
3801 "would enable devirtualization of %i call",
3802 "Declaring method %qD final "
3803 "would enable devirtualization of %i calls",
3804 decl, count);
3805 else if (DECL_CXX_DESTRUCTOR_P (decl))
3806 warning_n (DECL_SOURCE_LOCATION (decl),
3807 OPT_Wsuggest_final_methods, count,
3808 "Declaring virtual destructor of %qD final "
3809 "would enable devirtualization of %i call "
3810 "executed %lli times",
3811 "Declaring virtual destructor of %qD final "
3812 "would enable devirtualization of %i calls "
3813 "executed %lli times",
3814 DECL_CONTEXT (decl), count,
3815 (long long)dyn_count.to_gcov_type ());
3816 else
3817 warning_n (DECL_SOURCE_LOCATION (decl),
3818 OPT_Wsuggest_final_methods, count,
3819 "Declaring method %qD final "
3820 "would enable devirtualization of %i call "
3821 "executed %lli times",
3822 "Declaring method %qD final "
3823 "would enable devirtualization of %i calls "
3824 "executed %lli times",
3825 decl, count,
3826 (long long)dyn_count.to_gcov_type ());
3827 }
3828 }
3829
3830 delete (final_warning_records);
3831 final_warning_records = 0;
3832 }
3833
3834 if (dump_file)
3835 fprintf (dump_file,
3836 "%i polymorphic calls, %i devirtualized,"
3837 " %i speculatively devirtualized, %i cold\n"
3838 "%i have multiple targets, %i overwritable,"
3839 " %i already speculated (%i agree, %i disagree),"
3840 " %i external, %i not defined, %i artificial, %i infos dropped\n",
3841 npolymorphic, ndevirtualized, nconverted, ncold,
3842 nmultiple, noverwritable, nspeculated, nok, nwrong,
3843 nexternal, nnotdefined, nartificial, ndropped);
3844 return ndevirtualized || ndropped ? TODO_remove_functions : 0;
3845}
3846
3847namespace {
3848
3849const pass_data pass_data_ipa_devirt =
3850{
3851 IPA_PASS, /* type */
3852 "devirt", /* name */
3853 OPTGROUP_NONE, /* optinfo_flags */
3854 TV_IPA_DEVIRT, /* tv_id */
3855 0, /* properties_required */
3856 0, /* properties_provided */
3857 0, /* properties_destroyed */
3858 0, /* todo_flags_start */
3859 ( TODO_dump_symtab ), /* todo_flags_finish */
3860};
3861
3862class pass_ipa_devirt : public ipa_opt_pass_d
3863{
3864public:
3865 pass_ipa_devirt (gcc::context *ctxt)
3866 : ipa_opt_pass_d (pass_data_ipa_devirt, ctxt,
3867 NULL, /* generate_summary */
3868 NULL, /* write_summary */
3869 NULL, /* read_summary */
3870 NULL, /* write_optimization_summary */
3871 NULL, /* read_optimization_summary */
3872 NULL, /* stmt_fixup */
3873 0, /* function_transform_todo_flags_start */
3874 NULL, /* function_transform */
3875 NULL) /* variable_transform */
3876 {}
3877
3878 /* opt_pass methods: */
3879 virtual bool gate (function *)
3880 {
3881 /* In LTO, always run the IPA passes and decide on function basis if the
3882 pass is enabled. */
3883 if (in_lto_p)
3884 return true;
3885 return (flag_devirtualize
3886 && (flag_devirtualize_speculatively
3887 || (warn_suggest_final_methods
3888 || warn_suggest_final_types))
3889 && optimize);
3890 }
3891
3892 virtual unsigned int execute (function *) { return ipa_devirt (); }
3893
3894}; // class pass_ipa_devirt
3895
3896} // anon namespace
3897
3898ipa_opt_pass_d *
3899make_pass_ipa_devirt (gcc::context *ctxt)
3900{
3901 return new pass_ipa_devirt (ctxt);
3902}
3903
3904#include "gt-ipa-devirt.h"
3905