Update gcc-50 to SVN version 221572
[dragonfly.git] / contrib / gcc-5.0 / gcc / ipa-devirt.c
1 /* Basic IPA utilities for type inheritance graph construction and
2    devirtualization.
3    Copyright (C) 2013-2015 Free Software Foundation, Inc.
4    Contributed by Jan Hubicka
5
6 This file is part of GCC.
7
8 GCC is free software; you can redistribute it and/or modify it under
9 the terms of the GNU General Public License as published by the Free
10 Software Foundation; either version 3, or (at your option) any later
11 version.
12
13 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
14 WARRANTY; without even the implied warranty of MERCHANTABILITY or
15 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
16 for more details.
17
18 You should have received a copy of the GNU General Public License
19 along with GCC; see the file COPYING3.  If not see
20 <http://www.gnu.org/licenses/>.  */
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 "tm.h"
112 #include "hash-set.h"
113 #include "machmode.h"
114 #include "hash-map.h"
115 #include "vec.h"
116 #include "double-int.h"
117 #include "input.h"
118 #include "alias.h"
119 #include "symtab.h"
120 #include "wide-int.h"
121 #include "inchash.h"
122 #include "tree.h"
123 #include "fold-const.h"
124 #include "print-tree.h"
125 #include "calls.h"
126 #include "predict.h"
127 #include "basic-block.h"
128 #include "is-a.h"
129 #include "plugin-api.h"
130 #include "hard-reg-set.h"
131 #include "function.h"
132 #include "ipa-ref.h"
133 #include "cgraph.h"
134 #include "hashtab.h"
135 #include "rtl.h"
136 #include "flags.h"
137 #include "statistics.h"
138 #include "real.h"
139 #include "fixed-value.h"
140 #include "insn-config.h"
141 #include "expmed.h"
142 #include "dojump.h"
143 #include "explow.h"
144 #include "emit-rtl.h"
145 #include "varasm.h"
146 #include "stmt.h"
147 #include "expr.h"
148 #include "tree-pass.h"
149 #include "target.h"
150 #include "hash-table.h"
151 #include "tree-pretty-print.h"
152 #include "ipa-utils.h"
153 #include "tree-ssa-alias.h"
154 #include "internal-fn.h"
155 #include "gimple-fold.h"
156 #include "gimple-expr.h"
157 #include "gimple.h"
158 #include "alloc-pool.h"
159 #include "symbol-summary.h"
160 #include "ipa-prop.h"
161 #include "ipa-inline.h"
162 #include "diagnostic.h"
163 #include "tree-dfa.h"
164 #include "demangle.h"
165 #include "dbgcnt.h"
166 #include "gimple-pretty-print.h"
167 #include "stor-layout.h"
168 #include "intl.h"
169
170 /* Hash based set of pairs of types.  */
171 typedef struct
172 {
173   tree first;
174   tree second;
175 } type_pair;
176
177 struct pair_traits : default_hashset_traits
178 {
179   static hashval_t
180   hash (type_pair p)
181   {
182     return TYPE_UID (p.first) ^ TYPE_UID (p.second);
183   }
184   static bool
185   is_empty (type_pair p)
186   {
187     return p.first == NULL;
188   }
189   static bool
190   is_deleted (type_pair p ATTRIBUTE_UNUSED)
191     {
192       return false;
193     }
194   static bool
195   equal (const type_pair &a, const type_pair &b)
196     {
197       return a.first==b.first && a.second == b.second;
198     }
199   static void
200   mark_empty (type_pair &e)
201     {
202       e.first = NULL;
203     }
204 };
205
206 static bool odr_types_equivalent_p (tree, tree, bool, bool *,
207                                     hash_set<type_pair,pair_traits> *);
208
209 static bool odr_violation_reported = false;
210
211
212 /* Pointer set of all call targets appearing in the cache.  */
213 static hash_set<cgraph_node *> *cached_polymorphic_call_targets;
214
215 /* The node of type inheritance graph.  For each type unique in
216    One Definition Rule (ODR) sense, we produce one node linking all
217    main variants of types equivalent to it, bases and derived types.  */
218
219 struct GTY(()) odr_type_d
220 {
221   /* leader type.  */
222   tree type;
223   /* All bases; built only for main variants of types.  */
224   vec<odr_type> GTY((skip)) bases;
225   /* All derived types with virtual methods seen in unit;
226      built only for main variants of types.  */
227   vec<odr_type> GTY((skip)) derived_types;
228
229   /* All equivalent types, if more than one.  */
230   vec<tree, va_gc> *types;
231   /* Set of all equivalent types, if NON-NULL.  */
232   hash_set<tree> * GTY((skip)) types_set;
233
234   /* Unique ID indexing the type in odr_types array.  */
235   int id;
236   /* Is it in anonymous namespace? */
237   bool anonymous_namespace;
238   /* Do we know about all derivations of given type?  */
239   bool all_derivations_known;
240   /* Did we report ODR violation here?  */
241   bool odr_violated;
242 };
243
244 /* Return TRUE if all derived types of T are known and thus
245    we may consider the walk of derived type complete.
246
247    This is typically true only for final anonymous namespace types and types
248    defined within functions (that may be COMDAT and thus shared across units,
249    but with the same set of derived types).  */
250
251 bool
252 type_all_derivations_known_p (const_tree t)
253 {
254   if (TYPE_FINAL_P (t))
255     return true;
256   if (flag_ltrans)
257     return false;
258   /* Non-C++ types may have IDENTIFIER_NODE here, do not crash.  */
259   if (!TYPE_NAME (t) || TREE_CODE (TYPE_NAME (t)) != TYPE_DECL)
260     return true;
261   if (type_in_anonymous_namespace_p (t))
262     return true;
263   return (decl_function_context (TYPE_NAME (t)) != NULL);
264 }
265
266 /* Return TRUE if type's constructors are all visible.  */
267
268 static bool
269 type_all_ctors_visible_p (tree t)
270 {
271   return !flag_ltrans
272          && symtab->state >= CONSTRUCTION
273          /* We can not always use type_all_derivations_known_p.
274             For function local types we must assume case where
275             the function is COMDAT and shared in between units.
276
277             TODO: These cases are quite easy to get, but we need
278             to keep track of C++ privatizing via -Wno-weak
279             as well as the  IPA privatizing.  */
280          && type_in_anonymous_namespace_p (t);
281 }
282
283 /* Return TRUE if type may have instance.  */
284
285 static bool
286 type_possibly_instantiated_p (tree t)
287 {
288   tree vtable;
289   varpool_node *vnode;
290
291   /* TODO: Add abstract types here.  */
292   if (!type_all_ctors_visible_p (t))
293     return true;
294
295   vtable = BINFO_VTABLE (TYPE_BINFO (t));
296   if (TREE_CODE (vtable) == POINTER_PLUS_EXPR)
297     vtable = TREE_OPERAND (TREE_OPERAND (vtable, 0), 0);
298   vnode = varpool_node::get (vtable);
299   return vnode && vnode->definition;
300 }
301
302 /* Hash used to unify ODR types based on their mangled name and for anonymous
303    namespace types.  */
304
305 struct odr_name_hasher
306 {
307   typedef odr_type_d value_type;
308   typedef union tree_node compare_type;
309   static inline hashval_t hash (const value_type *);
310   static inline bool equal (const value_type *, const compare_type *);
311   static inline void remove (value_type *);
312 };
313
314 /* Has used to unify ODR types based on their associated virtual table.
315    This hash is needed to keep -fno-lto-odr-type-merging to work and contains
316    only polymorphic types.  Types with mangled names are inserted to both.  */
317
318 struct odr_vtable_hasher:odr_name_hasher
319 {
320   static inline hashval_t hash (const value_type *);
321   static inline bool equal (const value_type *, const compare_type *);
322 };
323
324 /* Return type that was declared with T's name so that T is an
325    qualified variant of it.  */
326
327 static inline tree
328 main_odr_variant (const_tree t)
329 {
330   if (TYPE_NAME (t) && TREE_CODE (TYPE_NAME (t)) == TYPE_DECL)
331     return TREE_TYPE (TYPE_NAME (t));
332   /* Unnamed types and non-C++ produced types can be compared by variants.  */
333   else
334     return TYPE_MAIN_VARIANT (t);
335 }
336
337 static bool
338 can_be_name_hashed_p (tree t)
339 {
340   return (!in_lto_p || type_in_anonymous_namespace_p (t)
341           || (TYPE_NAME (t) && DECL_ASSEMBLER_NAME_SET_P (TYPE_NAME (t))));
342 }
343
344 /* Hash type by its ODR name.  */
345
346 static hashval_t
347 hash_odr_name (const_tree t)
348 {
349   gcc_checking_assert (main_odr_variant (t) == t);
350
351   /* If not in LTO, all main variants are unique, so we can do
352      pointer hash.  */
353   if (!in_lto_p)
354     return htab_hash_pointer (t);
355
356   /* Anonymous types are unique.  */
357   if (type_in_anonymous_namespace_p (t))
358     return htab_hash_pointer (t);
359
360   gcc_checking_assert (TYPE_NAME (t)
361                        && DECL_ASSEMBLER_NAME_SET_P (TYPE_NAME (t)));
362   return IDENTIFIER_HASH_VALUE (DECL_ASSEMBLER_NAME (TYPE_NAME (t)));
363 }
364
365 /* Return the computed hashcode for ODR_TYPE.  */
366
367 inline hashval_t
368 odr_name_hasher::hash (const value_type *odr_type)
369 {
370   return hash_odr_name (odr_type->type);
371 }
372
373 static bool
374 can_be_vtable_hashed_p (tree t)
375 {
376   /* vtable hashing can distinguish only main variants.  */
377   if (TYPE_MAIN_VARIANT (t) != t)
378     return false;
379   /* Anonymous namespace types are always handled by name hash.  */
380   if (type_in_anonymous_namespace_p (t))
381     return false;
382   return (TREE_CODE (t) == RECORD_TYPE
383           && TYPE_BINFO (t) && BINFO_VTABLE (TYPE_BINFO (t)));
384 }
385
386 /* Hash type by assembler name of its vtable.  */
387
388 static hashval_t
389 hash_odr_vtable (const_tree t)
390 {
391   tree v = BINFO_VTABLE (TYPE_BINFO (TYPE_MAIN_VARIANT (t)));
392   inchash::hash hstate;
393
394   gcc_checking_assert (in_lto_p);
395   gcc_checking_assert (!type_in_anonymous_namespace_p (t));
396   gcc_checking_assert (TREE_CODE (t) == RECORD_TYPE
397                        && TYPE_BINFO (t) && BINFO_VTABLE (TYPE_BINFO (t)));
398   gcc_checking_assert (main_odr_variant (t) == t);
399
400   if (TREE_CODE (v) == POINTER_PLUS_EXPR)
401     {
402       add_expr (TREE_OPERAND (v, 1), hstate);
403       v = TREE_OPERAND (TREE_OPERAND (v, 0), 0);
404     }
405
406   hstate.add_wide_int (IDENTIFIER_HASH_VALUE (DECL_ASSEMBLER_NAME (v)));
407   return hstate.end ();
408 }
409
410 /* Return the computed hashcode for ODR_TYPE.  */
411
412 inline hashval_t
413 odr_vtable_hasher::hash (const value_type *odr_type)
414 {
415   return hash_odr_vtable (odr_type->type);
416 }
417
418 /* For languages with One Definition Rule, work out if
419    types are the same based on their name.
420
421    This is non-trivial for LTO where minor differences in
422    the type representation may have prevented type merging
423    to merge two copies of otherwise equivalent type.
424
425    Until we start streaming mangled type names, this function works
426    only for polymorphic types.
427
428    When STRICT is true, we compare types by their names for purposes of
429    ODR violation warnings.  When strict is false, we consider variants
430    equivalent, becuase it is all that matters for devirtualization machinery.
431 */
432
433 bool
434 types_same_for_odr (const_tree type1, const_tree type2, bool strict)
435 {
436   gcc_checking_assert (TYPE_P (type1) && TYPE_P (type2));
437
438   type1 = main_odr_variant (type1);
439   type2 = main_odr_variant (type2);
440   if (!strict)
441     {
442       type1 = TYPE_MAIN_VARIANT (type1);
443       type2 = TYPE_MAIN_VARIANT (type2);
444     }
445
446   if (type1 == type2)
447     return true;
448
449   if (!in_lto_p)
450     return false;
451
452   /* Check for anonymous namespaces. Those have !TREE_PUBLIC
453      on the corresponding TYPE_STUB_DECL.  */
454   if (type_in_anonymous_namespace_p (type1)
455       || type_in_anonymous_namespace_p (type2))
456     return false;
457
458
459   /* ODR name of the type is set in DECL_ASSEMBLER_NAME of its TYPE_NAME.
460
461      Ideally we should never need types without ODR names here.  It can however
462      happen in two cases:
463
464        1) for builtin types that are not streamed but rebuilt in lto/lto-lang.c
465           Here testing for equivalence is safe, since their MAIN_VARIANTs are
466           unique.
467        2) for units streamed with -fno-lto-odr-type-merging.  Here we can't
468           establish precise ODR equivalency, but for correctness we care only
469           about equivalency on complete polymorphic types.  For these we can
470           compare assembler names of their virtual tables.  */
471   if ((!TYPE_NAME (type1) || !DECL_ASSEMBLER_NAME_SET_P (TYPE_NAME (type1)))
472       || (!TYPE_NAME (type2) || !DECL_ASSEMBLER_NAME_SET_P (TYPE_NAME (type2))))
473     {
474       /* See if types are obviously different (i.e. different codes
475          or polymorphic wrt non-polymorphic).  This is not strictly correct
476          for ODR violating programs, but we can't do better without streaming
477          ODR names.  */
478       if (TREE_CODE (type1) != TREE_CODE (type2))
479         return false;
480       if (TREE_CODE (type1) == RECORD_TYPE
481           && (TYPE_BINFO (type1) == NULL_TREE)
482               != (TYPE_BINFO (type1) == NULL_TREE))
483         return false;
484       if (TREE_CODE (type1) == RECORD_TYPE && TYPE_BINFO (type1)
485           && (BINFO_VTABLE (TYPE_BINFO (type1)) == NULL_TREE)
486              != (BINFO_VTABLE (TYPE_BINFO (type2)) == NULL_TREE))
487         return false;
488
489       /* At the moment we have no way to establish ODR equivalence at LTO
490          other than comparing virtual table pointers of polymorphic types.
491          Eventually we should start saving mangled names in TYPE_NAME.
492          Then this condition will become non-trivial.  */
493
494       if (TREE_CODE (type1) == RECORD_TYPE
495           && TYPE_BINFO (type1) && TYPE_BINFO (type2)
496           && BINFO_VTABLE (TYPE_BINFO (type1))
497           && BINFO_VTABLE (TYPE_BINFO (type2)))
498         {
499           tree v1 = BINFO_VTABLE (TYPE_BINFO (type1));
500           tree v2 = BINFO_VTABLE (TYPE_BINFO (type2));
501           gcc_assert (TREE_CODE (v1) == POINTER_PLUS_EXPR
502                       && TREE_CODE (v2) == POINTER_PLUS_EXPR);
503           return (operand_equal_p (TREE_OPERAND (v1, 1),
504                                    TREE_OPERAND (v2, 1), 0)
505                   && DECL_ASSEMBLER_NAME
506                          (TREE_OPERAND (TREE_OPERAND (v1, 0), 0))
507                      == DECL_ASSEMBLER_NAME
508                          (TREE_OPERAND (TREE_OPERAND (v2, 0), 0)));
509         }
510       gcc_unreachable ();
511     }
512   return (DECL_ASSEMBLER_NAME (TYPE_NAME (type1))
513           == DECL_ASSEMBLER_NAME (TYPE_NAME (type2)));
514 }
515
516 /* Return true if we can decide on ODR equivalency.
517
518    In non-LTO it is always decide, in LTO however it depends in the type has
519    ODR info attached.
520
521    When STRICT is false, compare main variants.  */
522
523 bool
524 types_odr_comparable (tree t1, tree t2, bool strict)
525 {
526   return (!in_lto_p
527           || (strict ? main_odr_variant (t1) == main_odr_variant (t2)
528               : TYPE_MAIN_VARIANT (t1) == TYPE_MAIN_VARIANT (t2))
529           || (odr_type_p (t1) && odr_type_p (t2))
530           || (TREE_CODE (t1) == RECORD_TYPE && TREE_CODE (t2) == RECORD_TYPE
531               && TYPE_BINFO (t1) && TYPE_BINFO (t2)
532               && polymorphic_type_binfo_p (TYPE_BINFO (t1))
533               && polymorphic_type_binfo_p (TYPE_BINFO (t2))));
534 }
535
536 /* Return true if T1 and T2 are ODR equivalent.  If ODR equivalency is not
537    known, be conservative and return false.  */
538
539 bool
540 types_must_be_same_for_odr (tree t1, tree t2)
541 {
542   if (types_odr_comparable (t1, t2))
543     return types_same_for_odr (t1, t2);
544   else
545     return TYPE_MAIN_VARIANT (t1) == TYPE_MAIN_VARIANT (t2);
546 }
547
548 /* Compare types T1 and T2 and return true if they are
549    equivalent.  */
550
551 inline bool
552 odr_name_hasher::equal (const value_type *o1, const compare_type *t2)
553 {
554   tree t1 = o1->type;
555
556   gcc_checking_assert (main_odr_variant (t2) == t2);
557   gcc_checking_assert (main_odr_variant (t1) == t1);
558   if (t1 == t2)
559     return true;
560   if (!in_lto_p)
561     return false;
562   /* Check for anonymous namespaces. Those have !TREE_PUBLIC
563      on the corresponding TYPE_STUB_DECL.  */
564   if (type_in_anonymous_namespace_p (t1)
565       || type_in_anonymous_namespace_p (t2))
566     return false;
567   gcc_checking_assert (DECL_ASSEMBLER_NAME (TYPE_NAME (t1)));
568   gcc_checking_assert (DECL_ASSEMBLER_NAME (TYPE_NAME (t2)));
569   return (DECL_ASSEMBLER_NAME (TYPE_NAME (t1))
570           == DECL_ASSEMBLER_NAME (TYPE_NAME (t2)));
571 }
572
573 /* Compare types T1 and T2 and return true if they are
574    equivalent.  */
575
576 inline bool
577 odr_vtable_hasher::equal (const value_type *o1, const compare_type *t2)
578 {
579   tree t1 = o1->type;
580
581   gcc_checking_assert (main_odr_variant (t2) == t2);
582   gcc_checking_assert (main_odr_variant (t1) == t1);
583   gcc_checking_assert (in_lto_p);
584   t1 = TYPE_MAIN_VARIANT (t1);
585   t2 = TYPE_MAIN_VARIANT (t2);
586   if (t1 == t2)
587     return true;
588   tree v1 = BINFO_VTABLE (TYPE_BINFO (t1));
589   tree v2 = BINFO_VTABLE (TYPE_BINFO (t2));
590   return (operand_equal_p (TREE_OPERAND (v1, 1),
591                            TREE_OPERAND (v2, 1), 0)
592           && DECL_ASSEMBLER_NAME
593                  (TREE_OPERAND (TREE_OPERAND (v1, 0), 0))
594              == DECL_ASSEMBLER_NAME
595                  (TREE_OPERAND (TREE_OPERAND (v2, 0), 0)));
596 }
597
598 /* Free ODR type V.  */
599
600 inline void
601 odr_name_hasher::remove (value_type *v)
602 {
603   v->bases.release ();
604   v->derived_types.release ();
605   if (v->types_set)
606     delete v->types_set;
607   ggc_free (v);
608 }
609
610 /* ODR type hash used to look up ODR type based on tree type node.  */
611
612 typedef hash_table<odr_name_hasher> odr_hash_type;
613 static odr_hash_type *odr_hash;
614 typedef hash_table<odr_vtable_hasher> odr_vtable_hash_type;
615 static odr_vtable_hash_type *odr_vtable_hash;
616
617 /* ODR types are also stored into ODR_TYPE vector to allow consistent
618    walking.  Bases appear before derived types.  Vector is garbage collected
619    so we won't end up visiting empty types.  */
620
621 static GTY(()) vec <odr_type, va_gc> *odr_types_ptr;
622 #define odr_types (*odr_types_ptr)
623
624 /* Set TYPE_BINFO of TYPE and its variants to BINFO.  */
625 void
626 set_type_binfo (tree type, tree binfo)
627 {
628   for (; type; type = TYPE_NEXT_VARIANT (type))
629     if (COMPLETE_TYPE_P (type))
630       TYPE_BINFO (type) = binfo;
631     else
632       gcc_assert (!TYPE_BINFO (type));
633 }
634
635 /* Compare T2 and T2 based on name or structure.  */
636
637 static bool
638 odr_subtypes_equivalent_p (tree t1, tree t2,
639                            hash_set<type_pair,pair_traits> *visited)
640 {
641   bool an1, an2;
642
643   /* This can happen in incomplete types that should be handled earlier.  */
644   gcc_assert (t1 && t2);
645
646   t1 = main_odr_variant (t1);
647   t2 = main_odr_variant (t2);
648   if (t1 == t2)
649     return true;
650
651   /* Anonymous namespace types must match exactly.  */
652   an1 = type_in_anonymous_namespace_p (t1);
653   an2 = type_in_anonymous_namespace_p (t2);
654   if (an1 != an2 || an1)
655     return false;
656
657   /* For ODR types be sure to compare their names.
658      To support -wno-odr-type-merging we allow one type to be non-ODR
659      and other ODR even though it is a violation.  */
660   if (types_odr_comparable (t1, t2, true))
661     {
662       if (!types_same_for_odr (t1, t2, true))
663         return false;
664       /* Limit recursion: If subtypes are ODR types and we know
665          that they are same, be happy.  */
666       if (!get_odr_type (t1, true)->odr_violated)
667         return true;
668     }
669
670   /* Component types, builtins and possibly violating ODR types
671      have to be compared structurally.  */
672   if (TREE_CODE (t1) != TREE_CODE (t2))
673     return false;
674   if ((TYPE_NAME (t1) == NULL_TREE) != (TYPE_NAME (t2) == NULL_TREE))
675     return false;
676   if (TYPE_NAME (t1) && DECL_NAME (TYPE_NAME (t1)) != DECL_NAME (TYPE_NAME (t2)))
677     return false;
678
679   type_pair pair={t1,t2};
680   if (TYPE_UID (t1) > TYPE_UID (t2))
681     {
682       pair.first = t2;
683       pair.second = t1;
684     }
685   if (visited->add (pair))
686     return true;
687   return odr_types_equivalent_p (t1, t2, false, NULL, visited);
688 }
689
690 /* Compare two virtual tables, PREVAILING and VTABLE and output ODR
691    violation warnings.  */
692
693 void
694 compare_virtual_tables (varpool_node *prevailing, varpool_node *vtable)
695 {
696   int n1, n2;
697   if (DECL_VIRTUAL_P (prevailing->decl) != DECL_VIRTUAL_P (vtable->decl))
698     {
699       odr_violation_reported = true;
700       if (DECL_VIRTUAL_P (prevailing->decl))
701         {
702           varpool_node *tmp = prevailing;
703           prevailing = vtable;
704           vtable = tmp;
705         }
706       if (warning_at (DECL_SOURCE_LOCATION
707                         (TYPE_NAME (DECL_CONTEXT (vtable->decl))),
708                       OPT_Wodr,
709                       "virtual table of type %qD violates one definition rule",
710                       DECL_CONTEXT (vtable->decl)))
711         inform (DECL_SOURCE_LOCATION (prevailing->decl),
712                 "variable of same assembler name as the virtual table is "
713                 "defined in another translation unit");
714       return;
715     }
716   if (!prevailing->definition || !vtable->definition)
717     return;
718   for (n1 = 0, n2 = 0; true; n1++, n2++)
719     {
720       struct ipa_ref *ref1, *ref2;
721       bool end1, end2;
722
723       end1 = !prevailing->iterate_reference (n1, ref1);
724       end2 = !vtable->iterate_reference (n2, ref2);
725
726       /* !DECL_VIRTUAL_P means RTTI entry;
727          We warn when RTTI is lost because non-RTTI previals; we silently
728          accept the other case.  */
729       while (!end2
730              && (end1
731                  || (DECL_ASSEMBLER_NAME (ref1->referred->decl)
732                      != DECL_ASSEMBLER_NAME (ref2->referred->decl)
733                      && DECL_VIRTUAL_P (ref1->referred->decl)))
734              && !DECL_VIRTUAL_P (ref2->referred->decl))
735         {
736           if (warning_at (DECL_SOURCE_LOCATION
737                             (TYPE_NAME (DECL_CONTEXT (vtable->decl))), 0,
738                           "virtual table of type %qD contains RTTI information",
739                           DECL_CONTEXT (vtable->decl)))
740             {
741               inform (DECL_SOURCE_LOCATION
742                         (TYPE_NAME (DECL_CONTEXT (prevailing->decl))),
743                       "but is prevailed by one without from other translation "
744                       "unit");
745               inform (DECL_SOURCE_LOCATION
746                         (TYPE_NAME (DECL_CONTEXT (prevailing->decl))),
747                       "RTTI will not work on this type");
748             }
749           n2++;
750           end2 = !vtable->iterate_reference (n2, ref2);
751         }
752       while (!end1
753              && (end2
754                  || (DECL_ASSEMBLER_NAME (ref2->referred->decl)
755                      != DECL_ASSEMBLER_NAME (ref1->referred->decl)
756                      && DECL_VIRTUAL_P (ref2->referred->decl)))
757              && !DECL_VIRTUAL_P (ref1->referred->decl))
758         {
759           n1++;
760           end1 = !vtable->iterate_reference (n1, ref1);
761         }
762
763       /* Finished?  */
764       if (end1 && end2)
765         {
766           /* Extra paranoia; compare the sizes.  We do not have information
767              about virtual inheritance offsets, so just be sure that these
768              match. 
769              Do this as very last check so the not very informative error
770              is not output too often.  */
771           if (DECL_SIZE (prevailing->decl) != DECL_SIZE (vtable->decl))
772             {
773               if (warning_at (DECL_SOURCE_LOCATION
774                                 (TYPE_NAME (DECL_CONTEXT (vtable->decl))), 0,
775                               "virtual table of type %qD violates "
776                               "one definition rule  ",
777                               DECL_CONTEXT (vtable->decl)))
778                 {
779                   inform (DECL_SOURCE_LOCATION
780                             (TYPE_NAME (DECL_CONTEXT (prevailing->decl))),
781                           "the conflicting type defined in another translation "
782                           "unit has virtual table of different size");
783                 }
784             }
785           return;
786         }
787
788       if (!end1 && !end2)
789         {
790           if (DECL_ASSEMBLER_NAME (ref1->referred->decl)
791               == DECL_ASSEMBLER_NAME (ref2->referred->decl))
792             continue;
793
794           /* If the loops above stopped on non-virtual pointer, we have
795              mismatch in RTTI information mangling.  */
796           if (!DECL_VIRTUAL_P (ref1->referred->decl)
797               && !DECL_VIRTUAL_P (ref2->referred->decl))
798             {
799               if (warning_at (DECL_SOURCE_LOCATION
800                                 (TYPE_NAME (DECL_CONTEXT (vtable->decl))), 0,
801                               "virtual table of type %qD violates "
802                               "one definition rule  ",
803                               DECL_CONTEXT (vtable->decl)))
804                 {
805                   inform (DECL_SOURCE_LOCATION
806                             (TYPE_NAME (DECL_CONTEXT (prevailing->decl))),
807                           "the conflicting type defined in another translation "
808                           "unit with different RTTI information");
809                 }
810               return;
811             }
812           /* At this point both REF1 and REF2 points either to virtual table
813              or virtual method.  If one points to virtual table and other to
814              method we can complain the same way as if one table was shorter
815              than other pointing out the extra method.  */
816           gcc_assert (DECL_VIRTUAL_P (ref1->referred->decl)
817                       && (TREE_CODE (ref1->referred->decl) == FUNCTION_DECL
818                           || TREE_CODE (ref1->referred->decl) == VAR_DECL));
819           gcc_assert (DECL_VIRTUAL_P (ref2->referred->decl)
820                       && (TREE_CODE (ref2->referred->decl) == FUNCTION_DECL
821                           || TREE_CODE (ref2->referred->decl) == VAR_DECL));
822           if (TREE_CODE (ref1->referred->decl)
823               != TREE_CODE (ref2->referred->decl))
824             {
825               if (TREE_CODE (ref1->referred->decl) == VAR_DECL)
826                 end1 = true;
827               else if (TREE_CODE (ref2->referred->decl) == VAR_DECL)
828                 end2 = true;
829             }
830         }
831
832       /* Complain about size mismatch.  Either we have too many virutal
833          functions or too many virtual table pointers.  */
834       if (end1 || end2)
835         {
836           if (end1)
837             {
838               varpool_node *tmp = prevailing;
839               prevailing = vtable;
840               vtable = tmp;
841               ref1 = ref2;
842             }
843           if (warning_at (DECL_SOURCE_LOCATION
844                             (TYPE_NAME (DECL_CONTEXT (vtable->decl))), 0,
845                           "virtual table of type %qD violates "
846                           "one definition rule",
847                           DECL_CONTEXT (vtable->decl)))
848             {
849               if (TREE_CODE (ref1->referring->decl) == FUNCTION_DECL)
850                 {
851                   inform (DECL_SOURCE_LOCATION
852                            (TYPE_NAME (DECL_CONTEXT (prevailing->decl))),
853                           "the conflicting type defined in another translation "
854                           "unit");
855                   inform (DECL_SOURCE_LOCATION
856                             (TYPE_NAME (DECL_CONTEXT (ref1->referring->decl))),
857                           "contains additional virtual method %qD",
858                           ref1->referred->decl);
859                 }
860               else
861                 {
862                   inform (DECL_SOURCE_LOCATION
863                            (TYPE_NAME (DECL_CONTEXT (prevailing->decl))),
864                           "the conflicting type defined in another translation "
865                           "unit has virtual table table with more entries");
866                 }
867             }
868           return;
869         }
870
871       /* And in the last case we have either mistmatch in between two virtual
872          methods or two virtual table pointers.  */
873       if (warning_at (DECL_SOURCE_LOCATION
874                         (TYPE_NAME (DECL_CONTEXT (vtable->decl))), 0,
875                       "virtual table of type %qD violates "
876                       "one definition rule  ",
877                       DECL_CONTEXT (vtable->decl)))
878         {
879           if (TREE_CODE (ref1->referred->decl) == FUNCTION_DECL)
880             {
881               inform (DECL_SOURCE_LOCATION
882                         (TYPE_NAME (DECL_CONTEXT (prevailing->decl))),
883                       "the conflicting type defined in another translation "
884                       "unit");
885               gcc_assert (TREE_CODE (ref2->referred->decl)
886                           == FUNCTION_DECL);
887               inform (DECL_SOURCE_LOCATION (ref1->referred->decl),
888                       "virtual method %qD", ref1->referred->decl);
889               inform (DECL_SOURCE_LOCATION (ref2->referred->decl),
890                       "ought to match virtual method %qD but does not",
891                       ref2->referred->decl);
892             }
893           else
894             inform (DECL_SOURCE_LOCATION
895                       (TYPE_NAME (DECL_CONTEXT (prevailing->decl))),
896                     "the conflicting type defined in another translation "
897                     "unit has virtual table table with different contents");
898           return;
899         }
900     }
901 }
902
903 /* Output ODR violation warning about T1 and T2 with REASON.
904    Display location of ST1 and ST2 if REASON speaks about field or
905    method of the type.
906    If WARN is false, do nothing. Set WARNED if warning was indeed
907    output.  */
908
909 void
910 warn_odr (tree t1, tree t2, tree st1, tree st2,
911           bool warn, bool *warned, const char *reason)
912 {
913   tree decl2 = TYPE_NAME (t2);
914   if (warned)
915     *warned = false;
916
917   if (!warn)
918     return;
919   if (!warning_at (DECL_SOURCE_LOCATION (TYPE_NAME (t1)), OPT_Wodr,
920                    "type %qT violates one definition rule",
921                    t1))
922     return;
923   if (!st1 && !st2)
924     ;
925   /* For FIELD_DECL support also case where one of fields is
926      NULL - this is used when the structures have mismatching number of
927      elements.  */
928   else if (!st1 || TREE_CODE (st1) == FIELD_DECL)
929     {
930       inform (DECL_SOURCE_LOCATION (decl2),
931               "a different type is defined in another translation unit");
932       if (!st1)
933         {
934           st1 = st2;
935           st2 = NULL;
936         }
937       inform (DECL_SOURCE_LOCATION (st1),
938               "the first difference of corresponding definitions is field %qD",
939               st1);
940       if (st2)
941         decl2 = st2;
942     }
943   else if (TREE_CODE (st1) == FUNCTION_DECL)
944     {
945       inform (DECL_SOURCE_LOCATION (decl2),
946               "a different type is defined in another translation unit");
947       inform (DECL_SOURCE_LOCATION (st1),
948               "the first difference of corresponding definitions is method %qD",
949               st1);
950       decl2 = st2;
951     }
952   else
953     return;
954   inform (DECL_SOURCE_LOCATION (decl2), reason);
955
956   if (warned)
957     *warned = true;
958 }
959
960 /* We already warned about ODR mismatch.  T1 and T2 ought to be equivalent
961    because they are used on same place in ODR matching types.
962    They are not; inform the user.  */
963
964 void
965 warn_types_mismatch (tree t1, tree t2)
966 {
967   if (!TYPE_NAME (t1) || !TYPE_NAME (t2))
968     return;
969   /* In Firefox it is a common bug to have same types but in
970      different namespaces.  Be a bit more informative on
971      this.  */
972   if (TYPE_CONTEXT (t1) && TYPE_CONTEXT (t2)
973       && (((TREE_CODE (TYPE_CONTEXT (t1)) == NAMESPACE_DECL)
974             != (TREE_CODE (TYPE_CONTEXT (t2)) == NAMESPACE_DECL))
975            || (TREE_CODE (TYPE_CONTEXT (t1)) == NAMESPACE_DECL
976                && (DECL_NAME (TYPE_CONTEXT (t1)) !=
977                    DECL_NAME (TYPE_CONTEXT (t2))))))
978     inform (DECL_SOURCE_LOCATION (TYPE_NAME (t1)),
979             "type %qT should match type %qT but is defined "
980             "in different namespace  ",
981             t1, t2);
982   else
983     inform (DECL_SOURCE_LOCATION (TYPE_NAME (t1)),
984             "type %qT should match type %qT",
985             t1, t2);
986   inform (DECL_SOURCE_LOCATION (TYPE_NAME (t2)),
987           "the incompatible type is defined here");
988 }
989
990 /* Compare T1 and T2, report ODR violations if WARN is true and set
991    WARNED to true if anything is reported.  Return true if types match.
992    If true is returned, the types are also compatible in the sense of
993    gimple_canonical_types_compatible_p.  */
994
995 static bool
996 odr_types_equivalent_p (tree t1, tree t2, bool warn, bool *warned,
997                         hash_set<type_pair,pair_traits> *visited)
998 {
999   /* Check first for the obvious case of pointer identity.  */
1000   if (t1 == t2)
1001     return true;
1002   gcc_assert (!type_in_anonymous_namespace_p (t1));
1003   gcc_assert (!type_in_anonymous_namespace_p (t2));
1004
1005   /* Can't be the same type if the types don't have the same code.  */
1006   if (TREE_CODE (t1) != TREE_CODE (t2))
1007     {
1008       warn_odr (t1, t2, NULL, NULL, warn, warned,
1009                 G_("a different type is defined in another translation unit"));
1010       return false;
1011     }
1012
1013   if (TYPE_QUALS (t1) != TYPE_QUALS (t2))
1014     {
1015       warn_odr (t1, t2, NULL, NULL, warn, warned,
1016                 G_("a type with different qualifiers is defined in another "
1017                    "translation unit"));
1018       return false;
1019     }
1020
1021   if (comp_type_attributes (t1, t2) != 1)
1022     {
1023       warn_odr (t1, t2, NULL, NULL, warn, warned,
1024                 G_("a type with attributes "
1025                    "is defined in another translation unit"));
1026       return false;
1027     }
1028
1029   if (TREE_CODE (t1) == ENUMERAL_TYPE
1030       && TYPE_VALUES (t1) && TYPE_VALUES (t2))
1031     {
1032       tree v1, v2;
1033       for (v1 = TYPE_VALUES (t1), v2 = TYPE_VALUES (t2);
1034            v1 && v2 ; v1 = TREE_CHAIN (v1), v2 = TREE_CHAIN (v2))
1035         {
1036           if (TREE_PURPOSE (v1) != TREE_PURPOSE (v2))
1037             {
1038               warn_odr (t1, t2, NULL, NULL, warn, warned,
1039                         G_("an enum with different value name"
1040                            " is defined in another translation unit"));
1041               return false;
1042             }
1043           if (TREE_VALUE (v1) != TREE_VALUE (v2)
1044               && !operand_equal_p (DECL_INITIAL (TREE_VALUE (v1)),
1045                                    DECL_INITIAL (TREE_VALUE (v2)), 0))
1046             {
1047               warn_odr (t1, t2, NULL, NULL, warn, warned,
1048                         G_("an enum with different values is defined"
1049                            " in another translation unit"));
1050               return false;
1051             }
1052         }
1053       if (v1 || v2)
1054         {
1055           warn_odr (t1, t2, NULL, NULL, warn, warned,
1056                     G_("an enum with mismatching number of values "
1057                        "is defined in another translation unit"));
1058           return false;
1059         }
1060     }
1061
1062   /* Non-aggregate types can be handled cheaply.  */
1063   if (INTEGRAL_TYPE_P (t1)
1064       || SCALAR_FLOAT_TYPE_P (t1)
1065       || FIXED_POINT_TYPE_P (t1)
1066       || TREE_CODE (t1) == VECTOR_TYPE
1067       || TREE_CODE (t1) == COMPLEX_TYPE
1068       || TREE_CODE (t1) == OFFSET_TYPE
1069       || POINTER_TYPE_P (t1))
1070     {
1071       if (TYPE_PRECISION (t1) != TYPE_PRECISION (t2))
1072         {
1073           warn_odr (t1, t2, NULL, NULL, warn, warned,
1074                     G_("a type with different precision is defined "
1075                        "in another translation unit"));
1076           return false;
1077         }
1078       if (TYPE_UNSIGNED (t1) != TYPE_UNSIGNED (t2))
1079         {
1080           warn_odr (t1, t2, NULL, NULL, warn, warned,
1081                     G_("a type with different signedness is defined "
1082                        "in another translation unit"));
1083           return false;
1084         }
1085
1086       if (TREE_CODE (t1) == INTEGER_TYPE
1087           && TYPE_STRING_FLAG (t1) != TYPE_STRING_FLAG (t2))
1088         {
1089           /* char WRT uint_8?  */
1090           warn_odr (t1, t2, NULL, NULL, warn, warned,
1091                     G_("a different type is defined in another "
1092                        "translation unit"));
1093           return false;
1094         }
1095
1096       /* For canonical type comparisons we do not want to build SCCs
1097          so we cannot compare pointed-to types.  But we can, for now,
1098          require the same pointed-to type kind and match what
1099          useless_type_conversion_p would do.  */
1100       if (POINTER_TYPE_P (t1))
1101         {
1102           if (TYPE_ADDR_SPACE (TREE_TYPE (t1))
1103               != TYPE_ADDR_SPACE (TREE_TYPE (t2)))
1104             {
1105               warn_odr (t1, t2, NULL, NULL, warn, warned,
1106                         G_("it is defined as a pointer in different address "
1107                            "space in another translation unit"));
1108               return false;
1109             }
1110
1111           if (!odr_subtypes_equivalent_p (TREE_TYPE (t1), TREE_TYPE (t2), visited))
1112             {
1113               warn_odr (t1, t2, NULL, NULL, warn, warned,
1114                         G_("it is defined as a pointer to different type "
1115                            "in another translation unit"));
1116               if (warn && warned)
1117                 warn_types_mismatch (TREE_TYPE (t1), TREE_TYPE (t2));
1118               return false;
1119             }
1120         }
1121
1122       if ((TREE_CODE (t1) == VECTOR_TYPE || TREE_CODE (t1) == COMPLEX_TYPE)
1123           && !odr_subtypes_equivalent_p (TREE_TYPE (t1), TREE_TYPE (t2), visited))
1124         {
1125           /* Probably specific enough.  */
1126           warn_odr (t1, t2, NULL, NULL, warn, warned,
1127                     G_("a different type is defined "
1128                        "in another translation unit"));
1129           if (warn && warned)
1130             warn_types_mismatch (TREE_TYPE (t1), TREE_TYPE (t2));
1131           return false;
1132         }
1133     }
1134   /* Do type-specific comparisons.  */
1135   else switch (TREE_CODE (t1))
1136     {
1137     case ARRAY_TYPE:
1138       {
1139         /* Array types are the same if the element types are the same and
1140            the number of elements are the same.  */
1141         if (!odr_subtypes_equivalent_p (TREE_TYPE (t1), TREE_TYPE (t2), visited))
1142           {
1143             warn_odr (t1, t2, NULL, NULL, warn, warned,
1144                       G_("a different type is defined in another "
1145                          "translation unit"));
1146             if (warn && warned)
1147               warn_types_mismatch (TREE_TYPE (t1), TREE_TYPE (t2));
1148           }
1149         gcc_assert (TYPE_STRING_FLAG (t1) == TYPE_STRING_FLAG (t2));
1150         gcc_assert (TYPE_NONALIASED_COMPONENT (t1)
1151                     == TYPE_NONALIASED_COMPONENT (t2));
1152
1153         tree i1 = TYPE_DOMAIN (t1);
1154         tree i2 = TYPE_DOMAIN (t2);
1155
1156         /* For an incomplete external array, the type domain can be
1157            NULL_TREE.  Check this condition also.  */
1158         if (i1 == NULL_TREE || i2 == NULL_TREE)
1159           return true;
1160
1161         tree min1 = TYPE_MIN_VALUE (i1);
1162         tree min2 = TYPE_MIN_VALUE (i2);
1163         tree max1 = TYPE_MAX_VALUE (i1);
1164         tree max2 = TYPE_MAX_VALUE (i2);
1165
1166         /* In C++, minimums should be always 0.  */
1167         gcc_assert (min1 == min2);
1168         if (!operand_equal_p (max1, max2, 0))
1169           {
1170             warn_odr (t1, t2, NULL, NULL, warn, warned,
1171                       G_("an array of different size is defined "
1172                          "in another translation unit"));
1173             return false;
1174           }
1175       }
1176     break;
1177
1178     case METHOD_TYPE:
1179     case FUNCTION_TYPE:
1180       /* Function types are the same if the return type and arguments types
1181          are the same.  */
1182       if (!odr_subtypes_equivalent_p (TREE_TYPE (t1), TREE_TYPE (t2), visited))
1183         {
1184           warn_odr (t1, t2, NULL, NULL, warn, warned,
1185                     G_("has different return value "
1186                        "in another translation unit"));
1187           if (warn && warned)
1188             warn_types_mismatch (TREE_TYPE (t1), TREE_TYPE (t2));
1189           return false;
1190         }
1191
1192       if (TYPE_ARG_TYPES (t1) == TYPE_ARG_TYPES (t2))
1193         return true;
1194       else
1195         {
1196           tree parms1, parms2;
1197
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             {
1202               if (!odr_subtypes_equivalent_p
1203                      (TREE_VALUE (parms1), TREE_VALUE (parms2), visited))
1204                 {
1205                   warn_odr (t1, t2, NULL, NULL, warn, warned,
1206                             G_("has different parameters in another "
1207                                "translation unit"));
1208                   if (warn && warned)
1209                     warn_types_mismatch (TREE_VALUE (parms1),
1210                                          TREE_VALUE (parms2));
1211                   return false;
1212                 }
1213             }
1214
1215           if (parms1 || parms2)
1216             {
1217               warn_odr (t1, t2, NULL, NULL, warn, warned,
1218                         G_("has different parameters "
1219                            "in another translation unit"));
1220               return false;
1221             }
1222
1223           return true;
1224         }
1225
1226     case RECORD_TYPE:
1227     case UNION_TYPE:
1228     case QUAL_UNION_TYPE:
1229       {
1230         tree f1, f2;
1231
1232         /* For aggregate types, all the fields must be the same.  */
1233         if (COMPLETE_TYPE_P (t1) && COMPLETE_TYPE_P (t2))
1234           {
1235             for (f1 = TYPE_FIELDS (t1), f2 = TYPE_FIELDS (t2);
1236                  f1 || f2;
1237                  f1 = TREE_CHAIN (f1), f2 = TREE_CHAIN (f2))
1238               {
1239                 /* Skip non-fields.  */
1240                 while (f1 && TREE_CODE (f1) != FIELD_DECL)
1241                   f1 = TREE_CHAIN (f1);
1242                 while (f2 && TREE_CODE (f2) != FIELD_DECL)
1243                   f2 = TREE_CHAIN (f2);
1244                 if (!f1 || !f2)
1245                   break;
1246                 if (DECL_VIRTUAL_P (f1) != DECL_VIRTUAL_P (f2))
1247                   {
1248                     warn_odr (t1, t2, NULL, NULL, warn, warned,
1249                               G_("a type with different virtual table pointers"
1250                                  " is defined in another translation unit"));
1251                     return false;
1252                   }
1253                 if (DECL_ARTIFICIAL (f1) != DECL_ARTIFICIAL (f2))
1254                   {
1255                     warn_odr (t1, t2, NULL, NULL, warn, warned,
1256                               G_("a type with different bases is defined "
1257                                  "in another translation unit"));
1258                     return false;
1259                   }
1260                 if (DECL_NAME (f1) != DECL_NAME (f2)
1261                     && !DECL_ARTIFICIAL (f1))
1262                   {
1263                     warn_odr (t1, t2, f1, f2, warn, warned,
1264                               G_("a field with different name is defined "
1265                                  "in another translation unit"));
1266                     return false;
1267                   }
1268                 if (!odr_subtypes_equivalent_p (TREE_TYPE (f1),
1269                                                 TREE_TYPE (f2), visited))
1270                   {
1271                     /* Do not warn about artificial fields and just go into
1272                        generic field mismatch warning.  */
1273                     if (DECL_ARTIFICIAL (f1))
1274                       break;
1275
1276                     warn_odr (t1, t2, f1, f2, warn, warned,
1277                               G_("a field of same name but different type "
1278                                  "is defined in another translation unit"));
1279                     if (warn && warned)
1280                       warn_types_mismatch (TREE_TYPE (f1), TREE_TYPE (f2));
1281                     return false;
1282                   }
1283                 if (!gimple_compare_field_offset (f1, f2))
1284                   {
1285                     /* Do not warn about artificial fields and just go into
1286                        generic field mismatch warning.  */
1287                     if (DECL_ARTIFICIAL (f1))
1288                       break;
1289                     warn_odr (t1, t2, f1, f2, warn, warned,
1290                               G_("fields has different layout "
1291                                  "in another translation unit"));
1292                     return false;
1293                   }
1294                 gcc_assert (DECL_NONADDRESSABLE_P (f1)
1295                             == DECL_NONADDRESSABLE_P (f2));
1296               }
1297
1298             /* If one aggregate has more fields than the other, they
1299                are not the same.  */
1300             if (f1 || f2)
1301               {
1302                 if ((f1 && DECL_VIRTUAL_P (f1)) || (f2 && DECL_VIRTUAL_P (f2)))
1303                   warn_odr (t1, t2, NULL, NULL, warn, warned,
1304                             G_("a type with different virtual table pointers"
1305                                " is defined in another translation unit"));
1306                 if ((f1 && DECL_ARTIFICIAL (f1))
1307                     || (f2 && DECL_ARTIFICIAL (f2)))
1308                   warn_odr (t1, t2, NULL, NULL, warn, warned,
1309                             G_("a type with different bases is defined "
1310                                "in another translation unit"));
1311                 else
1312                   warn_odr (t1, t2, f1, f2, warn, warned,
1313                             G_("a type with different number of fields "
1314                                "is defined in another translation unit"));
1315                 
1316                 return false;
1317               }
1318             if ((TYPE_MAIN_VARIANT (t1) == t1 || TYPE_MAIN_VARIANT (t2) == t2)
1319                 && (TYPE_METHODS (TYPE_MAIN_VARIANT (t1))
1320                     != TYPE_METHODS (TYPE_MAIN_VARIANT (t2))))
1321               {
1322                 for (f1 = TYPE_METHODS (TYPE_MAIN_VARIANT (t1)),
1323                      f2 = TYPE_METHODS (TYPE_MAIN_VARIANT (t2));
1324                      f1 && f2 ; f1 = DECL_CHAIN (f1), f2 = DECL_CHAIN (f2))
1325                   {
1326                     if (DECL_ASSEMBLER_NAME (f1) != DECL_ASSEMBLER_NAME (f2))
1327                       {
1328                         warn_odr (t1, t2, f1, f2, warn, warned,
1329                                   G_("a different method of same type "
1330                                      "is defined in another translation unit"));
1331                         return false;
1332                       }
1333                     if (DECL_VIRTUAL_P (f1) != DECL_VIRTUAL_P (f2))
1334                       {
1335                         warn_odr (t1, t2, f1, f2, warn, warned,
1336                                   G_("s definition that differs by virtual "
1337                                      "keyword in another translation unit"));
1338                         return false;
1339                       }
1340                     if (DECL_VINDEX (f1) != DECL_VINDEX (f2))
1341                       {
1342                         warn_odr (t1, t2, f1, f2, warn, warned,
1343                                   G_("virtual table layout differs in another "
1344                                      "translation unit"));
1345                         return false;
1346                       }
1347                     if (odr_subtypes_equivalent_p (TREE_TYPE (f1), TREE_TYPE (f2), visited))
1348                       {
1349                         warn_odr (t1, t2, f1, f2, warn, warned,
1350                                   G_("method with incompatible type is defined "
1351                                      "in another translation unit"));
1352                         return false;
1353                       }
1354                   }
1355                 if (f1 || f2)
1356                   {
1357                     warn_odr (t1, t2, NULL, NULL, warn, warned,
1358                               G_("a type with different number of methods "
1359                                  "is defined in another translation unit"));
1360                     return false;
1361                   }
1362               }
1363           }
1364         break;
1365       }
1366     case VOID_TYPE:
1367       break;
1368
1369     default:
1370       debug_tree (t1);
1371       gcc_unreachable ();
1372     }
1373
1374   /* Those are better to come last as they are utterly uninformative.  */
1375   if (TYPE_SIZE (t1) && TYPE_SIZE (t2)
1376       && !operand_equal_p (TYPE_SIZE (t1), TYPE_SIZE (t2), 0))
1377     {
1378       warn_odr (t1, t2, NULL, NULL, warn, warned,
1379                 G_("a type with different size "
1380                    "is defined in another translation unit"));
1381       return false;
1382     }
1383   if (COMPLETE_TYPE_P (t1) && COMPLETE_TYPE_P (t2)
1384       && TYPE_ALIGN (t1) != TYPE_ALIGN (t2))
1385     {
1386       warn_odr (t1, t2, NULL, NULL, warn, warned,
1387                 G_("a type with different alignment "
1388                    "is defined in another translation unit"));
1389       return false;
1390     }
1391   gcc_assert (!TYPE_SIZE_UNIT (t1) || !TYPE_SIZE_UNIT (t2)
1392               || operand_equal_p (TYPE_SIZE_UNIT (t1),
1393                                   TYPE_SIZE_UNIT (t2), 0));
1394   return true;
1395 }
1396
1397 /* TYPE is equivalent to VAL by ODR, but its tree representation differs
1398    from VAL->type.  This may happen in LTO where tree merging did not merge
1399    all variants of the same type or due to ODR violation.
1400
1401    Analyze and report ODR violations and add type to duplicate list.
1402    If TYPE is more specified than VAL->type, prevail VAL->type.  Also if
1403    this is first time we see definition of a class return true so the
1404    base types are analyzed.  */
1405
1406 static bool
1407 add_type_duplicate (odr_type val, tree type)
1408 {
1409   bool build_bases = false;
1410   bool prevail = false;
1411
1412   if (!val->types_set)
1413     val->types_set = new hash_set<tree>;
1414
1415   /* Chose polymorphic type as leader (this happens only in case of ODR
1416      violations.  */
1417   if ((TREE_CODE (type) == RECORD_TYPE && TYPE_BINFO (type)
1418        && polymorphic_type_binfo_p (TYPE_BINFO (type)))
1419       && (TREE_CODE (val->type) != RECORD_TYPE || !TYPE_BINFO (val->type)
1420           || !polymorphic_type_binfo_p (TYPE_BINFO (val->type))))
1421     {
1422       prevail = true;
1423       build_bases = true;
1424     }
1425   /* Always prefer complete type to be the leader.  */
1426   else if (!COMPLETE_TYPE_P (val->type) && COMPLETE_TYPE_P (type))
1427     {
1428       prevail = true;
1429       build_bases = TYPE_BINFO (type);
1430     }
1431   else if (COMPLETE_TYPE_P (val->type) && !COMPLETE_TYPE_P (type))
1432     ;
1433   else if (TREE_CODE (val->type) == ENUMERAL_TYPE
1434            && TREE_CODE (type) == ENUMERAL_TYPE
1435            && !TYPE_VALUES (val->type) && TYPE_VALUES (type))
1436     prevail = true;
1437   else if (TREE_CODE (val->type) == RECORD_TYPE
1438            && TREE_CODE (type) == RECORD_TYPE
1439            && TYPE_BINFO (type) && !TYPE_BINFO (val->type))
1440     {
1441       gcc_assert (!val->bases.length ());
1442       build_bases = true;
1443       prevail = true;
1444     }
1445
1446   if (prevail)
1447     {
1448       tree tmp = type;
1449
1450       type = val->type;
1451       val->type = tmp;
1452     }
1453
1454   val->types_set->add (type);
1455
1456   /* If we now have a mangled name, be sure to record it to val->type
1457      so ODR hash can work.  */
1458
1459   if (can_be_name_hashed_p (type) && !can_be_name_hashed_p (val->type))
1460     SET_DECL_ASSEMBLER_NAME (TYPE_NAME (val->type),
1461                              DECL_ASSEMBLER_NAME (TYPE_NAME (type)));
1462
1463   bool merge = true;
1464   bool base_mismatch = false;
1465   unsigned int i;
1466   bool warned = false;
1467   hash_set<type_pair,pair_traits> visited;
1468
1469   gcc_assert (in_lto_p);
1470   vec_safe_push (val->types, type);
1471
1472   /* First we compare memory layout.  */
1473   if (!odr_types_equivalent_p (val->type, type,
1474                                !flag_ltrans && !val->odr_violated,
1475                                &warned, &visited))
1476     {
1477       merge = false;
1478       odr_violation_reported = true;
1479       val->odr_violated = true;
1480       if (symtab->dump_file)
1481         {
1482           fprintf (symtab->dump_file, "ODR violation\n");
1483
1484           print_node (symtab->dump_file, "", val->type, 0);
1485           putc ('\n',symtab->dump_file);
1486           print_node (symtab->dump_file, "", type, 0);
1487           putc ('\n',symtab->dump_file);
1488         }
1489     }
1490
1491   /* Next sanity check that bases are the same.  If not, we will end
1492      up producing wrong answers.  */
1493   if (COMPLETE_TYPE_P (type) && COMPLETE_TYPE_P (val->type)
1494       && TREE_CODE (val->type) == RECORD_TYPE
1495       && TREE_CODE (type) == RECORD_TYPE
1496       && TYPE_BINFO (val->type) && TYPE_BINFO (type))
1497     {
1498       if (BINFO_N_BASE_BINFOS (TYPE_BINFO (type))
1499           != BINFO_N_BASE_BINFOS (TYPE_BINFO (val->type)))
1500         {
1501           if (!warned && !val->odr_violated)
1502             {
1503               tree extra_base;
1504               warn_odr (type, val->type, NULL, NULL, !warned, &warned,
1505                         "a type with the same name but different "
1506                         "number of polymorphic bases is "
1507                         "defined in another translation unit");
1508               if (BINFO_N_BASE_BINFOS (TYPE_BINFO (type))
1509                   > BINFO_N_BASE_BINFOS (TYPE_BINFO (val->type)))
1510                 extra_base = BINFO_BASE_BINFO
1511                              (TYPE_BINFO (type),
1512                               BINFO_N_BASE_BINFOS (TYPE_BINFO (val->type)));
1513               else
1514                 extra_base = BINFO_BASE_BINFO
1515                              (TYPE_BINFO (val->type),
1516                               BINFO_N_BASE_BINFOS (TYPE_BINFO (type)));
1517               tree extra_base_type = BINFO_TYPE (extra_base);
1518               inform (DECL_SOURCE_LOCATION (TYPE_NAME (extra_base_type)),
1519                       "the extra base is defined here");
1520             }
1521           base_mismatch = true;
1522         }
1523       else
1524         for (i = 0; i < BINFO_N_BASE_BINFOS (TYPE_BINFO (type)); i++)
1525           {
1526             tree base1 = BINFO_BASE_BINFO (TYPE_BINFO (type), i);
1527             tree base2 = BINFO_BASE_BINFO (TYPE_BINFO (val->type), i);
1528             tree type1 = BINFO_TYPE (base1);
1529             tree type2 = BINFO_TYPE (base2);
1530
1531             if (types_odr_comparable (type1, type2))
1532               {
1533                 if (!types_same_for_odr (type1, type2))
1534                   base_mismatch = true;
1535               }
1536             else
1537               {
1538                 hash_set<type_pair,pair_traits> visited;
1539                 if (!odr_types_equivalent_p (type1, type2, false, NULL,
1540                                              &visited))
1541                   base_mismatch = true;
1542               }
1543             if (base_mismatch)
1544               {
1545                 if (!warned && !val->odr_violated)
1546                   {
1547                     warn_odr (type, val->type, NULL, NULL,
1548                               !warned, &warned,
1549                               "a type with the same name but different base "
1550                               "type is defined in another translation unit");
1551                     if (warned)
1552                       warn_types_mismatch (type1, type2);
1553                   }
1554                 break;
1555               }
1556             if (BINFO_OFFSET (base1) != BINFO_OFFSET (base2))
1557               {
1558                 base_mismatch = true;
1559                 if (!warned && !val->odr_violated)
1560                   warn_odr (type, val->type, NULL, NULL,
1561                             !warned, &warned,
1562                             "a type with the same name but different base "
1563                             "layout is defined in another translation unit");
1564                 break;
1565               }
1566             /* One of bases is not of complete type.  */
1567             if (!TYPE_BINFO (type1) != !TYPE_BINFO (type2))
1568               {
1569                 /* If we have a polymorphic type info specified for TYPE1
1570                    but not for TYPE2 we possibly missed a base when recording
1571                    VAL->type earlier.
1572                    Be sure this does not happen.  */
1573                 gcc_assert (TYPE_BINFO (type2)
1574                             || !polymorphic_type_binfo_p (TYPE_BINFO (type1))
1575                             || build_bases
1576                             || val->odr_violated);
1577                 break;
1578               }
1579             /* One base is polymorphic and the other not.
1580                This ought to be diagnosed earlier, but do not ICE in the
1581                checking bellow.  */
1582             else if (TYPE_BINFO (type1)
1583                      && polymorphic_type_binfo_p (TYPE_BINFO (type1))
1584                         != polymorphic_type_binfo_p (TYPE_BINFO (type2)))
1585               {
1586                 gcc_assert (val->odr_violated);
1587                 base_mismatch = true;
1588                 break;
1589               }
1590           }
1591 #ifdef ENABLE_CHECKING
1592       /* Sanity check that all bases will be build same way again.  */
1593       if (!base_mismatch && val->bases.length ())
1594         {
1595           unsigned int num_poly_bases = 0;
1596           unsigned int j;
1597
1598           for (i = 0; i < BINFO_N_BASE_BINFOS (TYPE_BINFO (type)); i++)
1599             if (polymorphic_type_binfo_p (BINFO_BASE_BINFO
1600                                              (TYPE_BINFO (type), i)))
1601               num_poly_bases++;
1602           gcc_assert (num_poly_bases == val->bases.length ());
1603           for (j = 0, i = 0; i < BINFO_N_BASE_BINFOS (TYPE_BINFO (type));
1604                i++)
1605             if (polymorphic_type_binfo_p (BINFO_BASE_BINFO
1606                                            (TYPE_BINFO (type), i)))
1607               {
1608                 odr_type base = get_odr_type
1609                                    (BINFO_TYPE
1610                                       (BINFO_BASE_BINFO (TYPE_BINFO (type),
1611                                                          i)),
1612                                     true);
1613                 gcc_assert (val->bases[j] == base);
1614                 j++;
1615               }
1616         }
1617 #endif
1618       if (base_mismatch)
1619         {
1620           merge = false;
1621           odr_violation_reported = true;
1622           val->odr_violated = true;
1623
1624           if (symtab->dump_file)
1625             {
1626               fprintf (symtab->dump_file, "ODR base violation\n");
1627             
1628               print_node (symtab->dump_file, "", val->type, 0);
1629               putc ('\n',symtab->dump_file);
1630               print_node (symtab->dump_file, "", type, 0);
1631               putc ('\n',symtab->dump_file);
1632             }
1633         }
1634     }
1635
1636   /* Regularize things a little.  During LTO same types may come with
1637      different BINFOs.  Either because their virtual table was
1638      not merged by tree merging and only later at decl merging or
1639      because one type comes with external vtable, while other
1640      with internal.  We want to merge equivalent binfos to conserve
1641      memory and streaming overhead.
1642
1643      The external vtables are more harmful: they contain references
1644      to external declarations of methods that may be defined in the
1645      merged LTO unit.  For this reason we absolutely need to remove
1646      them and replace by internal variants. Not doing so will lead
1647      to incomplete answers from possible_polymorphic_call_targets.
1648
1649      FIXME: disable for now; because ODR types are now build during
1650      streaming in, the variants do not need to be linked to the type,
1651      yet.  We need to do the merging in cleanup pass to be implemented
1652      soon.  */
1653   if (!flag_ltrans && merge
1654       && 0
1655       && TREE_CODE (val->type) == RECORD_TYPE
1656       && TREE_CODE (type) == RECORD_TYPE
1657       && TYPE_BINFO (val->type) && TYPE_BINFO (type)
1658       && TYPE_MAIN_VARIANT (type) == type
1659       && TYPE_MAIN_VARIANT (val->type) == val->type
1660       && BINFO_VTABLE (TYPE_BINFO (val->type))
1661       && BINFO_VTABLE (TYPE_BINFO (type)))
1662     {
1663       tree master_binfo = TYPE_BINFO (val->type);
1664       tree v1 = BINFO_VTABLE (master_binfo);
1665       tree v2 = BINFO_VTABLE (TYPE_BINFO (type));
1666
1667       if (TREE_CODE (v1) == POINTER_PLUS_EXPR)
1668         {
1669           gcc_assert (TREE_CODE (v2) == POINTER_PLUS_EXPR
1670                       && operand_equal_p (TREE_OPERAND (v1, 1),
1671                                           TREE_OPERAND (v2, 1), 0));
1672           v1 = TREE_OPERAND (TREE_OPERAND (v1, 0), 0);
1673           v2 = TREE_OPERAND (TREE_OPERAND (v2, 0), 0);
1674         }
1675       gcc_assert (DECL_ASSEMBLER_NAME (v1)
1676                   == DECL_ASSEMBLER_NAME (v2));
1677
1678       if (DECL_EXTERNAL (v1) && !DECL_EXTERNAL (v2))
1679         {
1680           unsigned int i;
1681
1682           set_type_binfo (val->type, TYPE_BINFO (type));
1683           for (i = 0; i < val->types->length (); i++)
1684             {
1685               if (TYPE_BINFO ((*val->types)[i])
1686                   == master_binfo)
1687                 set_type_binfo ((*val->types)[i], TYPE_BINFO (type));
1688             }
1689           BINFO_TYPE (TYPE_BINFO (type)) = val->type;
1690         }
1691       else
1692         set_type_binfo (type, master_binfo);
1693     }
1694   return build_bases;
1695 }
1696
1697 /* Get ODR type hash entry for TYPE.  If INSERT is true, create
1698    possibly new entry.  */
1699
1700 odr_type
1701 get_odr_type (tree type, bool insert)
1702 {
1703   odr_type_d **slot = NULL;
1704   odr_type_d **vtable_slot = NULL;
1705   odr_type val = NULL;
1706   hashval_t hash;
1707   bool build_bases = false;
1708   bool insert_to_odr_array = false;
1709   int base_id = -1;
1710
1711   type = main_odr_variant (type);
1712
1713   gcc_checking_assert (can_be_name_hashed_p (type)
1714                        || can_be_vtable_hashed_p (type));
1715
1716   /* Lookup entry, first try name hash, fallback to vtable hash.  */
1717   if (can_be_name_hashed_p (type))
1718     {
1719       hash = hash_odr_name (type);
1720       slot = odr_hash->find_slot_with_hash (type, hash,
1721                                             insert ? INSERT : NO_INSERT);
1722     }
1723   if ((!slot || !*slot) && in_lto_p && can_be_vtable_hashed_p (type))
1724     {
1725       hash = hash_odr_vtable (type);
1726       vtable_slot = odr_vtable_hash->find_slot_with_hash (type, hash,
1727                                                    insert ? INSERT : NO_INSERT);
1728     }
1729
1730   if (!slot && !vtable_slot)
1731     return NULL;
1732
1733   /* See if we already have entry for type.  */
1734   if ((slot && *slot) || (vtable_slot && *vtable_slot))
1735     {
1736       if (slot && *slot)
1737         {
1738           val = *slot;
1739 #ifdef ENABLE_CHECKING
1740           if (in_lto_p && can_be_vtable_hashed_p (type))
1741             {
1742               hash = hash_odr_vtable (type);
1743               vtable_slot = odr_vtable_hash->find_slot_with_hash (type, hash,
1744                                                                   NO_INSERT);
1745               gcc_assert (!vtable_slot || *vtable_slot == *slot);
1746               vtable_slot = NULL;
1747             }
1748 #endif
1749         }
1750       else if (*vtable_slot)
1751         val = *vtable_slot;
1752
1753       if (val->type != type
1754           && (!val->types_set || !val->types_set->add (type)))
1755         {
1756           gcc_assert (insert);
1757           /* We have type duplicate, but it may introduce vtable name or
1758              mangled name; be sure to keep hashes in sync.  */
1759           if (in_lto_p && can_be_vtable_hashed_p (type)
1760               && (!vtable_slot || !*vtable_slot))
1761             {
1762               if (!vtable_slot)
1763                 {
1764                   hash = hash_odr_vtable (type);
1765                   vtable_slot = odr_vtable_hash->find_slot_with_hash
1766                              (type, hash, INSERT);
1767                   gcc_checking_assert (!*vtable_slot || *vtable_slot == val);
1768                 }
1769               *vtable_slot = val;
1770             }
1771           if (slot && !*slot)
1772             *slot = val;
1773           build_bases = add_type_duplicate (val, type);
1774         }
1775     }
1776   else
1777     {
1778       val = ggc_cleared_alloc<odr_type_d> ();
1779       val->type = type;
1780       val->bases = vNULL;
1781       val->derived_types = vNULL;
1782       val->anonymous_namespace = type_in_anonymous_namespace_p (type);
1783       build_bases = COMPLETE_TYPE_P (val->type);
1784       insert_to_odr_array = true;
1785       if (slot)
1786         *slot = val;
1787       if (vtable_slot)
1788         *vtable_slot = val;
1789     }
1790
1791   if (build_bases && TREE_CODE (type) == RECORD_TYPE && TYPE_BINFO (type)
1792       && type == TYPE_MAIN_VARIANT (type))
1793     {
1794       tree binfo = TYPE_BINFO (type);
1795       unsigned int i;
1796
1797       gcc_assert (BINFO_TYPE (TYPE_BINFO (val->type)) = type);
1798   
1799       val->all_derivations_known = type_all_derivations_known_p (type);
1800       for (i = 0; i < BINFO_N_BASE_BINFOS (binfo); i++)
1801         /* For now record only polymorphic types. other are
1802            pointless for devirtualization and we can not precisely
1803            determine ODR equivalency of these during LTO.  */
1804         if (polymorphic_type_binfo_p (BINFO_BASE_BINFO (binfo, i)))
1805           {
1806             odr_type base = get_odr_type (BINFO_TYPE (BINFO_BASE_BINFO (binfo,
1807                                                                         i)),
1808                                           true);
1809             gcc_assert (TYPE_MAIN_VARIANT (base->type) == base->type);
1810             base->derived_types.safe_push (val);
1811             val->bases.safe_push (base);
1812             if (base->id > base_id)
1813               base_id = base->id;
1814           }
1815       }
1816   /* Ensure that type always appears after bases.  */
1817   if (insert_to_odr_array)
1818     {
1819       if (odr_types_ptr)
1820         val->id = odr_types.length ();
1821       vec_safe_push (odr_types_ptr, val);
1822     }
1823   else if (base_id > val->id)
1824     {
1825       odr_types[val->id] = 0;
1826       /* Be sure we did not recorded any derived types; these may need
1827          renumbering too.  */
1828       gcc_assert (val->derived_types.length() == 0);
1829       if (odr_types_ptr)
1830         val->id = odr_types.length ();
1831       vec_safe_push (odr_types_ptr, val);
1832     }
1833   return val;
1834 }
1835
1836 /* Add TYPE od ODR type hash.  */
1837
1838 void
1839 register_odr_type (tree type)
1840 {
1841   if (!odr_hash)
1842     {
1843       odr_hash = new odr_hash_type (23);
1844       if (in_lto_p)
1845         odr_vtable_hash = new odr_vtable_hash_type (23);
1846     }
1847   /* Arrange things to be nicer and insert main variants first.  */
1848   if (odr_type_p (TYPE_MAIN_VARIANT (type)))
1849     get_odr_type (TYPE_MAIN_VARIANT (type), true);
1850   if (TYPE_MAIN_VARIANT (type) != type)
1851     get_odr_type (type, true);
1852 }
1853
1854 /* Return true if type is known to have no derivations.  */
1855
1856 bool
1857 type_known_to_have_no_deriavations_p (tree t)
1858 {
1859   return (type_all_derivations_known_p (t)
1860           && (TYPE_FINAL_P (t)
1861               || (odr_hash
1862                   && !get_odr_type (t, true)->derived_types.length())));
1863 }
1864
1865 /* Dump ODR type T and all its derived types.  INDENT specifies indentation for
1866    recursive printing.  */
1867
1868 static void
1869 dump_odr_type (FILE *f, odr_type t, int indent=0)
1870 {
1871   unsigned int i;
1872   fprintf (f, "%*s type %i: ", indent * 2, "", t->id);
1873   print_generic_expr (f, t->type, TDF_SLIM);
1874   fprintf (f, "%s", t->anonymous_namespace ? " (anonymous namespace)":"");
1875   fprintf (f, "%s\n", t->all_derivations_known ? " (derivations known)":"");
1876   if (TYPE_NAME (t->type))
1877     {
1878       /*fprintf (f, "%*s defined at: %s:%i\n", indent * 2, "",
1879                DECL_SOURCE_FILE (TYPE_NAME (t->type)),
1880                DECL_SOURCE_LINE (TYPE_NAME (t->type)));*/
1881       if (DECL_ASSEMBLER_NAME_SET_P (TYPE_NAME (t->type)))
1882         fprintf (f, "%*s mangled name: %s\n", indent * 2, "",
1883                  IDENTIFIER_POINTER
1884                    (DECL_ASSEMBLER_NAME (TYPE_NAME (t->type))));
1885     }
1886   if (t->bases.length ())
1887     {
1888       fprintf (f, "%*s base odr type ids: ", indent * 2, "");
1889       for (i = 0; i < t->bases.length (); i++)
1890         fprintf (f, " %i", t->bases[i]->id);
1891       fprintf (f, "\n");
1892     }
1893   if (t->derived_types.length ())
1894     {
1895       fprintf (f, "%*s derived types:\n", indent * 2, "");
1896       for (i = 0; i < t->derived_types.length (); i++)
1897         dump_odr_type (f, t->derived_types[i], indent + 1);
1898     }
1899   fprintf (f, "\n");
1900 }
1901
1902 /* Dump the type inheritance graph.  */
1903
1904 static void
1905 dump_type_inheritance_graph (FILE *f)
1906 {
1907   unsigned int i;
1908   if (!odr_types_ptr)
1909     return;
1910   fprintf (f, "\n\nType inheritance graph:\n");
1911   for (i = 0; i < odr_types.length (); i++)
1912     {
1913       if (odr_types[i] && odr_types[i]->bases.length () == 0)
1914         dump_odr_type (f, odr_types[i]);
1915     }
1916   for (i = 0; i < odr_types.length (); i++)
1917     {
1918       if (odr_types[i] && odr_types[i]->types && odr_types[i]->types->length ())
1919         {
1920           unsigned int j;
1921           fprintf (f, "Duplicate tree types for odr type %i\n", i);
1922           print_node (f, "", odr_types[i]->type, 0);
1923           for (j = 0; j < odr_types[i]->types->length (); j++)
1924             {
1925               tree t;
1926               fprintf (f, "duplicate #%i\n", j);
1927               print_node (f, "", (*odr_types[i]->types)[j], 0);
1928               t = (*odr_types[i]->types)[j];
1929               while (TYPE_P (t) && TYPE_CONTEXT (t))
1930                 {
1931                   t = TYPE_CONTEXT (t);
1932                   print_node (f, "", t, 0);
1933                 }
1934               putc ('\n',f);
1935             }
1936         }
1937     }
1938 }
1939
1940 /* Given method type T, return type of class it belongs to.
1941    Look up this pointer and get its type.    */
1942
1943 tree
1944 method_class_type (const_tree t)
1945 {
1946   tree first_parm_type = TREE_VALUE (TYPE_ARG_TYPES (t));
1947   gcc_assert (TREE_CODE (t) == METHOD_TYPE);
1948
1949   return TREE_TYPE (first_parm_type);
1950 }
1951
1952 /* Initialize IPA devirt and build inheritance tree graph.  */
1953
1954 void
1955 build_type_inheritance_graph (void)
1956 {
1957   struct symtab_node *n;
1958   FILE *inheritance_dump_file;
1959   int flags;
1960
1961   if (odr_hash)
1962     return;
1963   timevar_push (TV_IPA_INHERITANCE);
1964   inheritance_dump_file = dump_begin (TDI_inheritance, &flags);
1965   odr_hash = new odr_hash_type (23);
1966   if (in_lto_p)
1967     odr_vtable_hash = new odr_vtable_hash_type (23);
1968
1969   /* We reconstruct the graph starting of types of all methods seen in the
1970      the unit.  */
1971   FOR_EACH_SYMBOL (n)
1972     if (is_a <cgraph_node *> (n)
1973         && DECL_VIRTUAL_P (n->decl)
1974         && n->real_symbol_p ())
1975       get_odr_type (TYPE_MAIN_VARIANT (method_class_type (TREE_TYPE (n->decl))),
1976                     true);
1977
1978     /* Look also for virtual tables of types that do not define any methods.
1979  
1980        We need it in a case where class B has virtual base of class A
1981        re-defining its virtual method and there is class C with no virtual
1982        methods with B as virtual base.
1983
1984        Here we output B's virtual method in two variant - for non-virtual
1985        and virtual inheritance.  B's virtual table has non-virtual version,
1986        while C's has virtual.
1987
1988        For this reason we need to know about C in order to include both
1989        variants of B.  More correctly, record_target_from_binfo should
1990        add both variants of the method when walking B, but we have no
1991        link in between them.
1992
1993        We rely on fact that either the method is exported and thus we
1994        assume it is called externally or C is in anonymous namespace and
1995        thus we will see the vtable.  */
1996
1997     else if (is_a <varpool_node *> (n)
1998              && DECL_VIRTUAL_P (n->decl)
1999              && TREE_CODE (DECL_CONTEXT (n->decl)) == RECORD_TYPE
2000              && TYPE_BINFO (DECL_CONTEXT (n->decl))
2001              && polymorphic_type_binfo_p (TYPE_BINFO (DECL_CONTEXT (n->decl))))
2002       get_odr_type (TYPE_MAIN_VARIANT (DECL_CONTEXT (n->decl)), true);
2003   if (inheritance_dump_file)
2004     {
2005       dump_type_inheritance_graph (inheritance_dump_file);
2006       dump_end (TDI_inheritance, inheritance_dump_file);
2007     }
2008   timevar_pop (TV_IPA_INHERITANCE);
2009 }
2010
2011 /* Return true if N has reference from live virtual table
2012    (and thus can be a destination of polymorphic call). 
2013    Be conservatively correct when callgraph is not built or
2014    if the method may be referred externally.  */
2015
2016 static bool
2017 referenced_from_vtable_p (struct cgraph_node *node)
2018 {
2019   int i;
2020   struct ipa_ref *ref;
2021   bool found = false;
2022
2023   if (node->externally_visible
2024       || DECL_EXTERNAL (node->decl)
2025       || node->used_from_other_partition)
2026     return true;
2027
2028   /* Keep this test constant time.
2029      It is unlikely this can happen except for the case where speculative
2030      devirtualization introduced many speculative edges to this node. 
2031      In this case the target is very likely alive anyway.  */
2032   if (node->ref_list.referring.length () > 100)
2033     return true;
2034
2035   /* We need references built.  */
2036   if (symtab->state <= CONSTRUCTION)
2037     return true;
2038
2039   for (i = 0; node->iterate_referring (i, ref); i++)
2040     if ((ref->use == IPA_REF_ALIAS
2041          && referenced_from_vtable_p (dyn_cast<cgraph_node *> (ref->referring)))
2042         || (ref->use == IPA_REF_ADDR
2043             && TREE_CODE (ref->referring->decl) == VAR_DECL
2044             && DECL_VIRTUAL_P (ref->referring->decl)))
2045       {
2046         found = true;
2047         break;
2048       }
2049   return found;
2050 }
2051
2052 /* If TARGET has associated node, record it in the NODES array.
2053    CAN_REFER specify if program can refer to the target directly.
2054    if TARGET is unknown (NULL) or it can not be inserted (for example because
2055    its body was already removed and there is no way to refer to it), clear
2056    COMPLETEP.  */
2057
2058 static void
2059 maybe_record_node (vec <cgraph_node *> &nodes,
2060                    tree target, hash_set<tree> *inserted,
2061                    bool can_refer,
2062                    bool *completep)
2063 {
2064   struct cgraph_node *target_node, *alias_target;
2065   enum availability avail;
2066
2067   /* cxa_pure_virtual and __builtin_unreachable do not need to be added into
2068      list of targets; the runtime effect of calling them is undefined.
2069      Only "real" virtual methods should be accounted.  */
2070   if (target && TREE_CODE (TREE_TYPE (target)) != METHOD_TYPE)
2071     return;
2072
2073   if (!can_refer)
2074     {
2075       /* The only case when method of anonymous namespace becomes unreferable
2076          is when we completely optimized it out.  */
2077       if (flag_ltrans
2078           || !target 
2079           || !type_in_anonymous_namespace_p (DECL_CONTEXT (target)))
2080         *completep = false;
2081       return;
2082     }
2083
2084   if (!target)
2085     return;
2086
2087   target_node = cgraph_node::get (target);
2088
2089   /* Prefer alias target over aliases, so we do not get confused by
2090      fake duplicates.  */
2091   if (target_node)
2092     {
2093       alias_target = target_node->ultimate_alias_target (&avail);
2094       if (target_node != alias_target
2095           && avail >= AVAIL_AVAILABLE
2096           && target_node->get_availability ())
2097         target_node = alias_target;
2098     }
2099
2100   /* Method can only be called by polymorphic call if any
2101      of vtables referring to it are alive. 
2102
2103      While this holds for non-anonymous functions, too, there are
2104      cases where we want to keep them in the list; for example
2105      inline functions with -fno-weak are static, but we still
2106      may devirtualize them when instance comes from other unit.
2107      The same holds for LTO.
2108
2109      Currently we ignore these functions in speculative devirtualization.
2110      ??? Maybe it would make sense to be more aggressive for LTO even
2111      elsewhere.  */
2112   if (!flag_ltrans
2113       && type_in_anonymous_namespace_p (DECL_CONTEXT (target))
2114       && (!target_node
2115           || !referenced_from_vtable_p (target_node)))
2116     ;
2117   /* See if TARGET is useful function we can deal with.  */
2118   else if (target_node != NULL
2119            && (TREE_PUBLIC (target)
2120                || DECL_EXTERNAL (target)
2121                || target_node->definition)
2122            && target_node->real_symbol_p ())
2123     {
2124       gcc_assert (!target_node->global.inlined_to);
2125       gcc_assert (target_node->real_symbol_p ());
2126       if (!inserted->add (target))
2127         {
2128           cached_polymorphic_call_targets->add (target_node);
2129           nodes.safe_push (target_node);
2130         }
2131     }
2132   else if (completep
2133            && (!type_in_anonymous_namespace_p
2134                  (DECL_CONTEXT (target))
2135                || flag_ltrans))
2136     *completep = false;
2137 }
2138
2139 /* See if BINFO's type matches OUTER_TYPE.  If so, look up 
2140    BINFO of subtype of OTR_TYPE at OFFSET and in that BINFO find
2141    method in vtable and insert method to NODES array
2142    or BASES_TO_CONSIDER if this array is non-NULL.
2143    Otherwise recurse to base BINFOs.
2144    This matches what get_binfo_at_offset does, but with offset
2145    being unknown.
2146
2147    TYPE_BINFOS is a stack of BINFOS of types with defined
2148    virtual table seen on way from class type to BINFO.
2149
2150    MATCHED_VTABLES tracks virtual tables we already did lookup
2151    for virtual function in. INSERTED tracks nodes we already
2152    inserted.
2153
2154    ANONYMOUS is true if BINFO is part of anonymous namespace.
2155
2156    Clear COMPLETEP when we hit unreferable target.
2157   */
2158
2159 static void
2160 record_target_from_binfo (vec <cgraph_node *> &nodes,
2161                           vec <tree> *bases_to_consider,
2162                           tree binfo,
2163                           tree otr_type,
2164                           vec <tree> &type_binfos,
2165                           HOST_WIDE_INT otr_token,
2166                           tree outer_type,
2167                           HOST_WIDE_INT offset,
2168                           hash_set<tree> *inserted,
2169                           hash_set<tree> *matched_vtables,
2170                           bool anonymous,
2171                           bool *completep)
2172 {
2173   tree type = BINFO_TYPE (binfo);
2174   int i;
2175   tree base_binfo;
2176
2177
2178   if (BINFO_VTABLE (binfo))
2179     type_binfos.safe_push (binfo);
2180   if (types_same_for_odr (type, outer_type))
2181     {
2182       int i;
2183       tree type_binfo = NULL;
2184
2185       /* Look up BINFO with virtual table.  For normal types it is always last
2186          binfo on stack.  */
2187       for (i = type_binfos.length () - 1; i >= 0; i--)
2188         if (BINFO_OFFSET (type_binfos[i]) == BINFO_OFFSET (binfo))
2189           {
2190             type_binfo = type_binfos[i];
2191             break;
2192           }
2193       if (BINFO_VTABLE (binfo))
2194         type_binfos.pop ();
2195       /* If this is duplicated BINFO for base shared by virtual inheritance,
2196          we may not have its associated vtable.  This is not a problem, since
2197          we will walk it on the other path.  */
2198       if (!type_binfo)
2199         return;
2200       tree inner_binfo = get_binfo_at_offset (type_binfo,
2201                                               offset, otr_type);
2202       if (!inner_binfo)
2203         {
2204           gcc_assert (odr_violation_reported);
2205           return;
2206         }
2207       /* For types in anonymous namespace first check if the respective vtable
2208          is alive. If not, we know the type can't be called.  */
2209       if (!flag_ltrans && anonymous)
2210         {
2211           tree vtable = BINFO_VTABLE (inner_binfo);
2212           varpool_node *vnode;
2213
2214           if (TREE_CODE (vtable) == POINTER_PLUS_EXPR)
2215             vtable = TREE_OPERAND (TREE_OPERAND (vtable, 0), 0);
2216           vnode = varpool_node::get (vtable);
2217           if (!vnode || !vnode->definition)
2218             return;
2219         }
2220       gcc_assert (inner_binfo);
2221       if (bases_to_consider
2222           ? !matched_vtables->contains (BINFO_VTABLE (inner_binfo))
2223           : !matched_vtables->add (BINFO_VTABLE (inner_binfo)))
2224         {
2225           bool can_refer;
2226           tree target = gimple_get_virt_method_for_binfo (otr_token,
2227                                                           inner_binfo,
2228                                                           &can_refer);
2229           if (!bases_to_consider)
2230             maybe_record_node (nodes, target, inserted, can_refer, completep);
2231           /* Destructors are never called via construction vtables.  */
2232           else if (!target || !DECL_CXX_DESTRUCTOR_P (target))
2233             bases_to_consider->safe_push (target);
2234         }
2235       return;
2236     }
2237
2238   /* Walk bases.  */
2239   for (i = 0; BINFO_BASE_ITERATE (binfo, i, base_binfo); i++)
2240     /* Walking bases that have no virtual method is pointless exercise.  */
2241     if (polymorphic_type_binfo_p (base_binfo))
2242       record_target_from_binfo (nodes, bases_to_consider, base_binfo, otr_type,
2243                                 type_binfos, 
2244                                 otr_token, outer_type, offset, inserted,
2245                                 matched_vtables, anonymous, completep);
2246   if (BINFO_VTABLE (binfo))
2247     type_binfos.pop ();
2248 }
2249      
2250 /* Look up virtual methods matching OTR_TYPE (with OFFSET and OTR_TOKEN)
2251    of TYPE, insert them to NODES, recurse into derived nodes. 
2252    INSERTED is used to avoid duplicate insertions of methods into NODES.
2253    MATCHED_VTABLES are used to avoid duplicate walking vtables.
2254    Clear COMPLETEP if unreferable target is found.
2255  
2256    If CONSIDER_CONSTRUCTION is true, record to BASES_TO_CONSIDER
2257    all cases where BASE_SKIPPED is true (because the base is abstract
2258    class).  */
2259
2260 static void
2261 possible_polymorphic_call_targets_1 (vec <cgraph_node *> &nodes,
2262                                      hash_set<tree> *inserted,
2263                                      hash_set<tree> *matched_vtables,
2264                                      tree otr_type,
2265                                      odr_type type,
2266                                      HOST_WIDE_INT otr_token,
2267                                      tree outer_type,
2268                                      HOST_WIDE_INT offset,
2269                                      bool *completep,
2270                                      vec <tree> &bases_to_consider,
2271                                      bool consider_construction)
2272 {
2273   tree binfo = TYPE_BINFO (type->type);
2274   unsigned int i;
2275   auto_vec <tree, 8> type_binfos;
2276   bool possibly_instantiated = type_possibly_instantiated_p (type->type);
2277
2278   /* We may need to consider types w/o instances because of possible derived
2279      types using their methods either directly or via construction vtables.
2280      We are safe to skip them when all derivations are known, since we will
2281      handle them later.
2282      This is done by recording them to BASES_TO_CONSIDER array.  */
2283   if (possibly_instantiated || consider_construction)
2284     {
2285       record_target_from_binfo (nodes,
2286                                 (!possibly_instantiated
2287                                  && type_all_derivations_known_p (type->type))
2288                                 ? &bases_to_consider : NULL,
2289                                 binfo, otr_type, type_binfos, otr_token,
2290                                 outer_type, offset,
2291                                 inserted, matched_vtables,
2292                                 type->anonymous_namespace, completep);
2293     }
2294   for (i = 0; i < type->derived_types.length (); i++)
2295     possible_polymorphic_call_targets_1 (nodes, inserted, 
2296                                          matched_vtables,
2297                                          otr_type,
2298                                          type->derived_types[i],
2299                                          otr_token, outer_type, offset, completep,
2300                                          bases_to_consider, consider_construction);
2301 }
2302
2303 /* Cache of queries for polymorphic call targets.
2304
2305    Enumerating all call targets may get expensive when there are many
2306    polymorphic calls in the program, so we memoize all the previous
2307    queries and avoid duplicated work.  */
2308
2309 struct polymorphic_call_target_d
2310 {
2311   HOST_WIDE_INT otr_token;
2312   ipa_polymorphic_call_context context;
2313   odr_type type;
2314   vec <cgraph_node *> targets;
2315   tree decl_warning;
2316   int type_warning;
2317   bool complete;
2318   bool speculative;
2319 };
2320
2321 /* Polymorphic call target cache helpers.  */
2322
2323 struct polymorphic_call_target_hasher 
2324 {
2325   typedef polymorphic_call_target_d value_type;
2326   typedef polymorphic_call_target_d compare_type;
2327   static inline hashval_t hash (const value_type *);
2328   static inline bool equal (const value_type *, const compare_type *);
2329   static inline void remove (value_type *);
2330 };
2331
2332 /* Return the computed hashcode for ODR_QUERY.  */
2333
2334 inline hashval_t
2335 polymorphic_call_target_hasher::hash (const value_type *odr_query)
2336 {
2337   inchash::hash hstate (odr_query->otr_token);
2338
2339   hstate.add_wide_int (odr_query->type->id);
2340   hstate.merge_hash (TYPE_UID (odr_query->context.outer_type));
2341   hstate.add_wide_int (odr_query->context.offset);
2342
2343   if (odr_query->context.speculative_outer_type)
2344     {
2345       hstate.merge_hash (TYPE_UID (odr_query->context.speculative_outer_type));
2346       hstate.add_wide_int (odr_query->context.speculative_offset);
2347     }
2348   hstate.add_flag (odr_query->speculative);
2349   hstate.add_flag (odr_query->context.maybe_in_construction);
2350   hstate.add_flag (odr_query->context.maybe_derived_type);
2351   hstate.add_flag (odr_query->context.speculative_maybe_derived_type);
2352   hstate.commit_flag ();
2353   return hstate.end ();
2354 }
2355
2356 /* Compare cache entries T1 and T2.  */
2357
2358 inline bool
2359 polymorphic_call_target_hasher::equal (const value_type *t1,
2360                                        const compare_type *t2)
2361 {
2362   return (t1->type == t2->type && t1->otr_token == t2->otr_token
2363           && t1->speculative == t2->speculative
2364           && t1->context.offset == t2->context.offset
2365           && t1->context.speculative_offset == t2->context.speculative_offset
2366           && t1->context.outer_type == t2->context.outer_type
2367           && t1->context.speculative_outer_type == t2->context.speculative_outer_type
2368           && t1->context.maybe_in_construction
2369               == t2->context.maybe_in_construction
2370           && t1->context.maybe_derived_type == t2->context.maybe_derived_type
2371           && (t1->context.speculative_maybe_derived_type
2372               == t2->context.speculative_maybe_derived_type));
2373 }
2374
2375 /* Remove entry in polymorphic call target cache hash.  */
2376
2377 inline void
2378 polymorphic_call_target_hasher::remove (value_type *v)
2379 {
2380   v->targets.release ();
2381   free (v);
2382 }
2383
2384 /* Polymorphic call target query cache.  */
2385
2386 typedef hash_table<polymorphic_call_target_hasher>
2387    polymorphic_call_target_hash_type;
2388 static polymorphic_call_target_hash_type *polymorphic_call_target_hash;
2389
2390 /* Destroy polymorphic call target query cache.  */
2391
2392 static void
2393 free_polymorphic_call_targets_hash ()
2394 {
2395   if (cached_polymorphic_call_targets)
2396     {
2397       delete polymorphic_call_target_hash;
2398       polymorphic_call_target_hash = NULL;
2399       delete cached_polymorphic_call_targets;
2400       cached_polymorphic_call_targets = NULL;
2401     }
2402 }
2403
2404 /* When virtual function is removed, we may need to flush the cache.  */
2405
2406 static void
2407 devirt_node_removal_hook (struct cgraph_node *n, void *d ATTRIBUTE_UNUSED)
2408 {
2409   if (cached_polymorphic_call_targets
2410       && cached_polymorphic_call_targets->contains (n))
2411     free_polymorphic_call_targets_hash ();
2412 }
2413
2414 /* Look up base of BINFO that has virtual table VTABLE with OFFSET.  */
2415
2416 tree
2417 subbinfo_with_vtable_at_offset (tree binfo, unsigned HOST_WIDE_INT offset,
2418                                 tree vtable)
2419 {
2420   tree v = BINFO_VTABLE (binfo);
2421   int i;
2422   tree base_binfo;
2423   unsigned HOST_WIDE_INT this_offset;
2424
2425   if (v)
2426     {
2427       if (!vtable_pointer_value_to_vtable (v, &v, &this_offset))
2428         gcc_unreachable ();
2429
2430       if (offset == this_offset
2431           && DECL_ASSEMBLER_NAME (v) == DECL_ASSEMBLER_NAME (vtable))
2432         return binfo;
2433     }
2434   
2435   for (i = 0; BINFO_BASE_ITERATE (binfo, i, base_binfo); i++)
2436     if (polymorphic_type_binfo_p (base_binfo))
2437       {
2438         base_binfo = subbinfo_with_vtable_at_offset (base_binfo, offset, vtable);
2439         if (base_binfo)
2440           return base_binfo;
2441       }
2442   return NULL;
2443 }
2444
2445 /* T is known constant value of virtual table pointer.
2446    Store virtual table to V and its offset to OFFSET. 
2447    Return false if T does not look like virtual table reference.  */
2448
2449 bool
2450 vtable_pointer_value_to_vtable (const_tree t, tree *v,
2451                                 unsigned HOST_WIDE_INT *offset)
2452 {
2453   /* We expect &MEM[(void *)&virtual_table + 16B].
2454      We obtain object's BINFO from the context of the virtual table. 
2455      This one contains pointer to virtual table represented via
2456      POINTER_PLUS_EXPR.  Verify that this pointer matches what
2457      we propagated through.
2458
2459      In the case of virtual inheritance, the virtual tables may
2460      be nested, i.e. the offset may be different from 16 and we may
2461      need to dive into the type representation.  */
2462   if (TREE_CODE (t) == ADDR_EXPR
2463       && TREE_CODE (TREE_OPERAND (t, 0)) == MEM_REF
2464       && TREE_CODE (TREE_OPERAND (TREE_OPERAND (t, 0), 0)) == ADDR_EXPR
2465       && TREE_CODE (TREE_OPERAND (TREE_OPERAND (t, 0), 1)) == INTEGER_CST
2466       && (TREE_CODE (TREE_OPERAND (TREE_OPERAND (TREE_OPERAND (t, 0), 0), 0))
2467           == VAR_DECL)
2468       && DECL_VIRTUAL_P (TREE_OPERAND (TREE_OPERAND
2469                                          (TREE_OPERAND (t, 0), 0), 0)))
2470     {
2471       *v = TREE_OPERAND (TREE_OPERAND (TREE_OPERAND (t, 0), 0), 0);
2472       *offset = tree_to_uhwi (TREE_OPERAND (TREE_OPERAND (t, 0), 1));
2473       return true;
2474     }
2475
2476   /* Alternative representation, used by C++ frontend is POINTER_PLUS_EXPR.
2477      We need to handle it when T comes from static variable initializer or
2478      BINFO. */
2479   if (TREE_CODE (t) == POINTER_PLUS_EXPR)
2480     {
2481       *offset = tree_to_uhwi (TREE_OPERAND (t, 1));
2482       t = TREE_OPERAND (t, 0);
2483     }
2484   else
2485     *offset = 0;
2486
2487   if (TREE_CODE (t) != ADDR_EXPR)
2488     return false;
2489   *v = TREE_OPERAND (t, 0);
2490   return true;
2491 }
2492
2493 /* T is known constant value of virtual table pointer.  Return BINFO of the
2494    instance type.  */
2495
2496 tree
2497 vtable_pointer_value_to_binfo (const_tree t)
2498 {
2499   tree vtable;
2500   unsigned HOST_WIDE_INT offset;
2501
2502   if (!vtable_pointer_value_to_vtable (t, &vtable, &offset))
2503     return NULL_TREE;
2504
2505   /* FIXME: for stores of construction vtables we return NULL,
2506      because we do not have BINFO for those. Eventually we should fix
2507      our representation to allow this case to be handled, too.
2508      In the case we see store of BINFO we however may assume
2509      that standard folding will be able to cope with it.  */
2510   return subbinfo_with_vtable_at_offset (TYPE_BINFO (DECL_CONTEXT (vtable)),
2511                                          offset, vtable);
2512 }
2513
2514 /* Walk bases of OUTER_TYPE that contain OTR_TYPE at OFFSET.
2515    Look up their respective virtual methods for OTR_TOKEN and OTR_TYPE
2516    and insert them in NODES.
2517
2518    MATCHED_VTABLES and INSERTED is used to avoid duplicated work.  */
2519
2520 static void
2521 record_targets_from_bases (tree otr_type,
2522                            HOST_WIDE_INT otr_token,
2523                            tree outer_type,
2524                            HOST_WIDE_INT offset,
2525                            vec <cgraph_node *> &nodes,
2526                            hash_set<tree> *inserted,
2527                            hash_set<tree> *matched_vtables,
2528                            bool *completep)
2529 {
2530   while (true)
2531     {
2532       HOST_WIDE_INT pos, size;
2533       tree base_binfo;
2534       tree fld;
2535
2536       if (types_same_for_odr (outer_type, otr_type))
2537         return;
2538
2539       for (fld = TYPE_FIELDS (outer_type); fld; fld = DECL_CHAIN (fld))
2540         {
2541           if (TREE_CODE (fld) != FIELD_DECL)
2542             continue;
2543
2544           pos = int_bit_position (fld);
2545           size = tree_to_shwi (DECL_SIZE (fld));
2546           if (pos <= offset && (pos + size) > offset
2547               /* Do not get confused by zero sized bases.  */
2548               && polymorphic_type_binfo_p (TYPE_BINFO (TREE_TYPE (fld))))
2549             break;
2550         }
2551       /* Within a class type we should always find corresponding fields.  */
2552       gcc_assert (fld && TREE_CODE (TREE_TYPE (fld)) == RECORD_TYPE);
2553
2554       /* Nonbase types should have been stripped by outer_class_type.  */
2555       gcc_assert (DECL_ARTIFICIAL (fld));
2556
2557       outer_type = TREE_TYPE (fld);
2558       offset -= pos;
2559
2560       base_binfo = get_binfo_at_offset (TYPE_BINFO (outer_type),
2561                                         offset, otr_type);
2562       if (!base_binfo)
2563         {
2564           gcc_assert (odr_violation_reported);
2565           return;
2566         }
2567       gcc_assert (base_binfo);
2568       if (!matched_vtables->add (BINFO_VTABLE (base_binfo)))
2569         {
2570           bool can_refer;
2571           tree target = gimple_get_virt_method_for_binfo (otr_token,
2572                                                           base_binfo,
2573                                                           &can_refer);
2574           if (!target || ! DECL_CXX_DESTRUCTOR_P (target))
2575             maybe_record_node (nodes, target, inserted, can_refer, completep);
2576           matched_vtables->add (BINFO_VTABLE (base_binfo));
2577         }
2578     }
2579 }
2580
2581 /* When virtual table is removed, we may need to flush the cache.  */
2582
2583 static void
2584 devirt_variable_node_removal_hook (varpool_node *n,
2585                                    void *d ATTRIBUTE_UNUSED)
2586 {
2587   if (cached_polymorphic_call_targets
2588       && DECL_VIRTUAL_P (n->decl)
2589       && type_in_anonymous_namespace_p (DECL_CONTEXT (n->decl)))
2590     free_polymorphic_call_targets_hash ();
2591 }
2592
2593 /* Record about how many calls would benefit from given type to be final.  */
2594
2595 struct odr_type_warn_count
2596 {
2597   tree type;
2598   int count;
2599   gcov_type dyn_count;
2600 };
2601
2602 /* Record about how many calls would benefit from given method to be final.  */
2603
2604 struct decl_warn_count
2605 {
2606   tree decl;
2607   int count;
2608   gcov_type dyn_count;
2609 };
2610
2611 /* Information about type and decl warnings.  */
2612
2613 struct final_warning_record
2614 {
2615   gcov_type dyn_count;
2616   vec<odr_type_warn_count> type_warnings;
2617   hash_map<tree, decl_warn_count> decl_warnings;
2618 };
2619 struct final_warning_record *final_warning_records;
2620
2621 /* Return vector containing possible targets of polymorphic call of type
2622    OTR_TYPE calling method OTR_TOKEN within type of OTR_OUTER_TYPE and OFFSET.
2623    If INCLUDE_BASES is true, walk also base types of OUTER_TYPES containing
2624    OTR_TYPE and include their virtual method.  This is useful for types
2625    possibly in construction or destruction where the virtual table may
2626    temporarily change to one of base types.  INCLUDE_DERIVER_TYPES make
2627    us to walk the inheritance graph for all derivations.
2628
2629    If COMPLETEP is non-NULL, store true if the list is complete. 
2630    CACHE_TOKEN (if non-NULL) will get stored to an unique ID of entry
2631    in the target cache.  If user needs to visit every target list
2632    just once, it can memoize them.
2633
2634    If SPECULATIVE is set, the list will not contain targets that
2635    are not speculatively taken.
2636
2637    Returned vector is placed into cache.  It is NOT caller's responsibility
2638    to free it.  The vector can be freed on cgraph_remove_node call if
2639    the particular node is a virtual function present in the cache.  */
2640
2641 vec <cgraph_node *>
2642 possible_polymorphic_call_targets (tree otr_type,
2643                                    HOST_WIDE_INT otr_token,
2644                                    ipa_polymorphic_call_context context,
2645                                    bool *completep,
2646                                    void **cache_token,
2647                                    bool speculative)
2648 {
2649   static struct cgraph_node_hook_list *node_removal_hook_holder;
2650   vec <cgraph_node *> nodes = vNULL;
2651   auto_vec <tree, 8> bases_to_consider;
2652   odr_type type, outer_type;
2653   polymorphic_call_target_d key;
2654   polymorphic_call_target_d **slot;
2655   unsigned int i;
2656   tree binfo, target;
2657   bool complete;
2658   bool can_refer = false;
2659   bool skipped = false;
2660
2661   otr_type = TYPE_MAIN_VARIANT (otr_type);
2662
2663   /* If ODR is not initialized or the context is invalid, return empty
2664      incomplete list.  */
2665   if (!odr_hash || context.invalid || !TYPE_BINFO (otr_type))
2666     {
2667       if (completep)
2668         *completep = context.invalid;
2669       if (cache_token)
2670         *cache_token = NULL;
2671       return nodes;
2672     }
2673
2674   /* Do not bother to compute speculative info when user do not asks for it.  */
2675   if (!speculative || !context.speculative_outer_type)
2676     context.clear_speculation ();
2677
2678   type = get_odr_type (otr_type, true);
2679
2680   /* Recording type variants would waste results cache.  */
2681   gcc_assert (!context.outer_type
2682               || TYPE_MAIN_VARIANT (context.outer_type) == context.outer_type);
2683
2684   /* Look up the outer class type we want to walk.
2685      If we fail to do so, the context is invalid.  */
2686   if ((context.outer_type || context.speculative_outer_type)
2687       && !context.restrict_to_inner_class (otr_type))
2688     {
2689       if (completep)
2690         *completep = true;
2691       if (cache_token)
2692         *cache_token = NULL;
2693       return nodes;
2694     }
2695   gcc_assert (!context.invalid);
2696
2697   /* Check that restrict_to_inner_class kept the main variant.  */
2698   gcc_assert (!context.outer_type
2699               || TYPE_MAIN_VARIANT (context.outer_type) == context.outer_type);
2700
2701   /* We canonicalize our query, so we do not need extra hashtable entries.  */
2702
2703   /* Without outer type, we have no use for offset.  Just do the
2704      basic search from inner type.  */
2705   if (!context.outer_type)
2706     context.clear_outer_type (otr_type);
2707   /* We need to update our hierarchy if the type does not exist.  */
2708   outer_type = get_odr_type (context.outer_type, true);
2709   /* If the type is complete, there are no derivations.  */
2710   if (TYPE_FINAL_P (outer_type->type))
2711     context.maybe_derived_type = false;
2712
2713   /* Initialize query cache.  */
2714   if (!cached_polymorphic_call_targets)
2715     {
2716       cached_polymorphic_call_targets = new hash_set<cgraph_node *>;
2717       polymorphic_call_target_hash
2718         = new polymorphic_call_target_hash_type (23);
2719       if (!node_removal_hook_holder)
2720         {
2721           node_removal_hook_holder =
2722             symtab->add_cgraph_removal_hook (&devirt_node_removal_hook, NULL);
2723           symtab->add_varpool_removal_hook (&devirt_variable_node_removal_hook,
2724                                          NULL);
2725         }
2726     }
2727
2728   if (in_lto_p)
2729     {
2730       if (context.outer_type != otr_type)
2731         context.outer_type
2732           = get_odr_type (context.outer_type, true)->type;
2733       if (context.speculative_outer_type)
2734         context.speculative_outer_type
2735           = get_odr_type (context.speculative_outer_type, true)->type;
2736     }
2737
2738   /* Look up cached answer.  */
2739   key.type = type;
2740   key.otr_token = otr_token;
2741   key.speculative = speculative;
2742   key.context = context;
2743   slot = polymorphic_call_target_hash->find_slot (&key, INSERT);
2744   if (cache_token)
2745    *cache_token = (void *)*slot;
2746   if (*slot)
2747     {
2748       if (completep)
2749         *completep = (*slot)->complete;
2750       if ((*slot)->type_warning && final_warning_records)
2751         {
2752           final_warning_records->type_warnings[(*slot)->type_warning - 1].count++;
2753           final_warning_records->type_warnings[(*slot)->type_warning - 1].dyn_count
2754             += final_warning_records->dyn_count;
2755         }
2756       if (!speculative && (*slot)->decl_warning && final_warning_records)
2757         {
2758           struct decl_warn_count *c =
2759              final_warning_records->decl_warnings.get ((*slot)->decl_warning);
2760           c->count++;
2761           c->dyn_count += final_warning_records->dyn_count;
2762         }
2763       return (*slot)->targets;
2764     }
2765
2766   complete = true;
2767
2768   /* Do actual search.  */
2769   timevar_push (TV_IPA_VIRTUAL_CALL);
2770   *slot = XCNEW (polymorphic_call_target_d);
2771   if (cache_token)
2772     *cache_token = (void *)*slot;
2773   (*slot)->type = type;
2774   (*slot)->otr_token = otr_token;
2775   (*slot)->context = context;
2776   (*slot)->speculative = speculative;
2777
2778   hash_set<tree> inserted;
2779   hash_set<tree> matched_vtables;
2780
2781   /* First insert targets we speculatively identified as likely.  */
2782   if (context.speculative_outer_type)
2783     {
2784       odr_type speculative_outer_type;
2785       bool speculation_complete = true;
2786
2787       /* First insert target from type itself and check if it may have
2788          derived types.  */
2789       speculative_outer_type = get_odr_type (context.speculative_outer_type, true);
2790       if (TYPE_FINAL_P (speculative_outer_type->type))
2791         context.speculative_maybe_derived_type = false;
2792       binfo = get_binfo_at_offset (TYPE_BINFO (speculative_outer_type->type),
2793                                    context.speculative_offset, otr_type);
2794       if (binfo)
2795         target = gimple_get_virt_method_for_binfo (otr_token, binfo,
2796                                                    &can_refer);
2797       else
2798         target = NULL;
2799
2800       /* In the case we get complete method, we don't need 
2801          to walk derivations.  */
2802       if (target && DECL_FINAL_P (target))
2803         context.speculative_maybe_derived_type = false;
2804       if (type_possibly_instantiated_p (speculative_outer_type->type))
2805         maybe_record_node (nodes, target, &inserted, can_refer, &speculation_complete);
2806       if (binfo)
2807         matched_vtables.add (BINFO_VTABLE (binfo));
2808
2809
2810       /* Next walk recursively all derived types.  */
2811       if (context.speculative_maybe_derived_type)
2812         for (i = 0; i < speculative_outer_type->derived_types.length(); i++)
2813           possible_polymorphic_call_targets_1 (nodes, &inserted,
2814                                                &matched_vtables,
2815                                                otr_type,
2816                                                speculative_outer_type->derived_types[i],
2817                                                otr_token, speculative_outer_type->type,
2818                                                context.speculative_offset,
2819                                                &speculation_complete,
2820                                                bases_to_consider,
2821                                                false);
2822     }
2823
2824   if (!speculative || !nodes.length ())
2825     {
2826       /* First see virtual method of type itself.  */
2827       binfo = get_binfo_at_offset (TYPE_BINFO (outer_type->type),
2828                                    context.offset, otr_type);
2829       if (binfo)
2830         target = gimple_get_virt_method_for_binfo (otr_token, binfo,
2831                                                    &can_refer);
2832       else
2833         {
2834           gcc_assert (odr_violation_reported);
2835           target = NULL;
2836         }
2837
2838       /* Destructors are never called through construction virtual tables,
2839          because the type is always known.  */
2840       if (target && DECL_CXX_DESTRUCTOR_P (target))
2841         context.maybe_in_construction = false;
2842
2843       if (target)
2844         {
2845           /* In the case we get complete method, we don't need 
2846              to walk derivations.  */
2847           if (DECL_FINAL_P (target))
2848             context.maybe_derived_type = false;
2849         }
2850
2851       /* If OUTER_TYPE is abstract, we know we are not seeing its instance.  */
2852       if (type_possibly_instantiated_p (outer_type->type))
2853         maybe_record_node (nodes, target, &inserted, can_refer, &complete);
2854       else
2855         skipped = true;
2856
2857       if (binfo)
2858         matched_vtables.add (BINFO_VTABLE (binfo));
2859
2860       /* Next walk recursively all derived types.  */
2861       if (context.maybe_derived_type)
2862         {
2863           for (i = 0; i < outer_type->derived_types.length(); i++)
2864             possible_polymorphic_call_targets_1 (nodes, &inserted,
2865                                                  &matched_vtables,
2866                                                  otr_type,
2867                                                  outer_type->derived_types[i],
2868                                                  otr_token, outer_type->type,
2869                                                  context.offset, &complete,
2870                                                  bases_to_consider,
2871                                                  context.maybe_in_construction);
2872
2873           if (!outer_type->all_derivations_known)
2874             {
2875               if (!speculative && final_warning_records)
2876                 {
2877                   if (complete
2878                       && nodes.length () == 1
2879                       && warn_suggest_final_types
2880                       && !outer_type->derived_types.length ())
2881                     {
2882                       if (outer_type->id >= (int)final_warning_records->type_warnings.length ())
2883                         final_warning_records->type_warnings.safe_grow_cleared
2884                           (odr_types.length ());
2885                       final_warning_records->type_warnings[outer_type->id].count++;
2886                       final_warning_records->type_warnings[outer_type->id].dyn_count
2887                         += final_warning_records->dyn_count;
2888                       final_warning_records->type_warnings[outer_type->id].type
2889                         = outer_type->type;
2890                       (*slot)->type_warning = outer_type->id + 1;
2891                     }
2892                   if (complete
2893                       && warn_suggest_final_methods
2894                       && nodes.length () == 1
2895                       && types_same_for_odr (DECL_CONTEXT (nodes[0]->decl),
2896                                              outer_type->type))
2897                     {
2898                       bool existed;
2899                       struct decl_warn_count &c =
2900                          final_warning_records->decl_warnings.get_or_insert
2901                             (nodes[0]->decl, &existed);
2902
2903                       if (existed)
2904                         {
2905                           c.count++;
2906                           c.dyn_count += final_warning_records->dyn_count;
2907                         }
2908                       else
2909                         {
2910                           c.count = 1;
2911                           c.dyn_count = final_warning_records->dyn_count;
2912                           c.decl = nodes[0]->decl;
2913                         }
2914                       (*slot)->decl_warning = nodes[0]->decl;
2915                     }
2916                 }
2917               complete = false;
2918             }
2919         }
2920
2921       if (!speculative)
2922         {
2923           /* Destructors are never called through construction virtual tables,
2924              because the type is always known.  One of entries may be
2925              cxa_pure_virtual so look to at least two of them.  */
2926           if (context.maybe_in_construction)
2927             for (i =0 ; i < MIN (nodes.length (), 2); i++)
2928               if (DECL_CXX_DESTRUCTOR_P (nodes[i]->decl))
2929                 context.maybe_in_construction = false;
2930           if (context.maybe_in_construction)
2931             {
2932               if (type != outer_type
2933                   && (!skipped
2934                       || (context.maybe_derived_type
2935                           && !type_all_derivations_known_p (outer_type->type))))
2936                 record_targets_from_bases (otr_type, otr_token, outer_type->type,
2937                                            context.offset, nodes, &inserted,
2938                                            &matched_vtables, &complete);
2939               if (skipped)
2940                 maybe_record_node (nodes, target, &inserted, can_refer, &complete);
2941               for (i = 0; i < bases_to_consider.length(); i++)
2942                 maybe_record_node (nodes, bases_to_consider[i], &inserted, can_refer, &complete);
2943             }
2944         }
2945     }
2946
2947   (*slot)->targets = nodes;
2948   (*slot)->complete = complete;
2949   if (completep)
2950     *completep = complete;
2951
2952   timevar_pop (TV_IPA_VIRTUAL_CALL);
2953   return nodes;
2954 }
2955
2956 bool
2957 add_decl_warning (const tree &key ATTRIBUTE_UNUSED, const decl_warn_count &value,
2958                   vec<const decl_warn_count*> *vec)
2959 {
2960   vec->safe_push (&value);
2961   return true;
2962 }
2963
2964 /* Dump target list TARGETS into FILE.  */
2965
2966 static void
2967 dump_targets (FILE *f, vec <cgraph_node *> targets)
2968 {
2969   unsigned int i;
2970
2971   for (i = 0; i < targets.length (); i++)
2972     {
2973       char *name = NULL;
2974       if (in_lto_p)
2975         name = cplus_demangle_v3 (targets[i]->asm_name (), 0);
2976       fprintf (f, " %s/%i", name ? name : targets[i]->name (), targets[i]->order);
2977       if (in_lto_p)
2978         free (name);
2979       if (!targets[i]->definition)
2980         fprintf (f, " (no definition%s)",
2981                  DECL_DECLARED_INLINE_P (targets[i]->decl)
2982                  ? " inline" : "");
2983     }
2984   fprintf (f, "\n");
2985 }
2986
2987 /* Dump all possible targets of a polymorphic call.  */
2988
2989 void
2990 dump_possible_polymorphic_call_targets (FILE *f,
2991                                         tree otr_type,
2992                                         HOST_WIDE_INT otr_token,
2993                                         const ipa_polymorphic_call_context &ctx)
2994 {
2995   vec <cgraph_node *> targets;
2996   bool final;
2997   odr_type type = get_odr_type (TYPE_MAIN_VARIANT (otr_type), false);
2998   unsigned int len;
2999
3000   if (!type)
3001     return;
3002   targets = possible_polymorphic_call_targets (otr_type, otr_token,
3003                                                ctx,
3004                                                &final, NULL, false);
3005   fprintf (f, "  Targets of polymorphic call of type %i:", type->id);
3006   print_generic_expr (f, type->type, TDF_SLIM);
3007   fprintf (f, " token %i\n", (int)otr_token);
3008
3009   ctx.dump (f);
3010
3011   fprintf (f, "    %s%s%s%s\n      ",
3012            final ? "This is a complete list." :
3013            "This is partial list; extra targets may be defined in other units.",
3014            ctx.maybe_in_construction ? " (base types included)" : "",
3015            ctx.maybe_derived_type ? " (derived types included)" : "",
3016            ctx.speculative_maybe_derived_type ? " (speculative derived types included)" : "");
3017   len = targets.length ();
3018   dump_targets (f, targets);
3019
3020   targets = possible_polymorphic_call_targets (otr_type, otr_token,
3021                                                ctx,
3022                                                &final, NULL, true);
3023   if (targets.length () != len)
3024     {
3025       fprintf (f, "  Speculative targets:");
3026       dump_targets (f, targets);
3027     }
3028   gcc_assert (targets.length () <= len);
3029   fprintf (f, "\n");
3030 }
3031
3032
3033 /* Return true if N can be possibly target of a polymorphic call of
3034    OTR_TYPE/OTR_TOKEN.  */
3035
3036 bool
3037 possible_polymorphic_call_target_p (tree otr_type,
3038                                     HOST_WIDE_INT otr_token,
3039                                     const ipa_polymorphic_call_context &ctx,
3040                                     struct cgraph_node *n)
3041 {
3042   vec <cgraph_node *> targets;
3043   unsigned int i;
3044   enum built_in_function fcode;
3045   bool final;
3046
3047   if (TREE_CODE (TREE_TYPE (n->decl)) == FUNCTION_TYPE
3048       && ((fcode = DECL_FUNCTION_CODE (n->decl))
3049           == BUILT_IN_UNREACHABLE
3050           || fcode == BUILT_IN_TRAP))
3051     return true;
3052
3053   if (!odr_hash)
3054     return true;
3055   targets = possible_polymorphic_call_targets (otr_type, otr_token, ctx, &final);
3056   for (i = 0; i < targets.length (); i++)
3057     if (n->semantically_equivalent_p (targets[i]))
3058       return true;
3059
3060   /* At a moment we allow middle end to dig out new external declarations
3061      as a targets of polymorphic calls.  */
3062   if (!final && !n->definition)
3063     return true;
3064   return false;
3065 }
3066
3067
3068
3069 /* Return true if N can be possibly target of a polymorphic call of
3070    OBJ_TYPE_REF expression REF in STMT.  */
3071
3072 bool
3073 possible_polymorphic_call_target_p (tree ref,
3074                                     gimple stmt,
3075                                     struct cgraph_node *n)
3076 {
3077   ipa_polymorphic_call_context context (current_function_decl, ref, stmt);
3078   tree call_fn = gimple_call_fn (stmt);
3079
3080   return possible_polymorphic_call_target_p (obj_type_ref_class (call_fn),
3081                                              tree_to_uhwi
3082                                                (OBJ_TYPE_REF_TOKEN (call_fn)),
3083                                              context,
3084                                              n);
3085 }
3086
3087
3088 /* After callgraph construction new external nodes may appear.
3089    Add them into the graph.  */
3090
3091 void
3092 update_type_inheritance_graph (void)
3093 {
3094   struct cgraph_node *n;
3095
3096   if (!odr_hash)
3097     return;
3098   free_polymorphic_call_targets_hash ();
3099   timevar_push (TV_IPA_INHERITANCE);
3100   /* We reconstruct the graph starting from types of all methods seen in the
3101      the unit.  */
3102   FOR_EACH_FUNCTION (n)
3103     if (DECL_VIRTUAL_P (n->decl)
3104         && !n->definition
3105         && n->real_symbol_p ())
3106       get_odr_type (method_class_type (TYPE_MAIN_VARIANT (TREE_TYPE (n->decl))),
3107                                        true);
3108   timevar_pop (TV_IPA_INHERITANCE);
3109 }
3110
3111
3112 /* Return true if N looks like likely target of a polymorphic call.
3113    Rule out cxa_pure_virtual, noreturns, function declared cold and
3114    other obvious cases.  */
3115
3116 bool
3117 likely_target_p (struct cgraph_node *n)
3118 {
3119   int flags;
3120   /* cxa_pure_virtual and similar things are not likely.  */
3121   if (TREE_CODE (TREE_TYPE (n->decl)) != METHOD_TYPE)
3122     return false;
3123   flags = flags_from_decl_or_type (n->decl);
3124   if (flags & ECF_NORETURN)
3125     return false;
3126   if (lookup_attribute ("cold",
3127                         DECL_ATTRIBUTES (n->decl)))
3128     return false;
3129   if (n->frequency < NODE_FREQUENCY_NORMAL)
3130     return false;
3131   /* If there are no live virtual tables referring the target,
3132      the only way the target can be called is an instance coming from other
3133      compilation unit; speculative devirtualization is built around an
3134      assumption that won't happen.  */
3135   if (!referenced_from_vtable_p (n))
3136     return false;
3137   return true;
3138 }
3139
3140 /* Compare type warning records P1 and P2 and choose one with larger count;
3141    helper for qsort.  */
3142
3143 int
3144 type_warning_cmp (const void *p1, const void *p2)
3145 {
3146   const odr_type_warn_count *t1 = (const odr_type_warn_count *)p1;
3147   const odr_type_warn_count *t2 = (const odr_type_warn_count *)p2;
3148
3149   if (t1->dyn_count < t2->dyn_count)
3150    return 1;
3151   if (t1->dyn_count > t2->dyn_count)
3152    return -1;
3153   return t2->count - t1->count;
3154 }
3155
3156 /* Compare decl warning records P1 and P2 and choose one with larger count;
3157    helper for qsort.  */
3158
3159 int
3160 decl_warning_cmp (const void *p1, const void *p2)
3161 {
3162   const decl_warn_count *t1 = *(const decl_warn_count * const *)p1;
3163   const decl_warn_count *t2 = *(const decl_warn_count * const *)p2;
3164
3165   if (t1->dyn_count < t2->dyn_count)
3166    return 1;
3167   if (t1->dyn_count > t2->dyn_count)
3168    return -1;
3169   return t2->count - t1->count;
3170 }
3171
3172
3173 /* Try to speculatively devirtualize call to OTR_TYPE with OTR_TOKEN with
3174    context CTX.  */
3175
3176 struct cgraph_node *
3177 try_speculative_devirtualization (tree otr_type, HOST_WIDE_INT otr_token,
3178                                   ipa_polymorphic_call_context ctx)
3179 {
3180   vec <cgraph_node *>targets
3181      = possible_polymorphic_call_targets
3182           (otr_type, otr_token, ctx, NULL, NULL, true);
3183   unsigned int i;
3184   struct cgraph_node *likely_target = NULL;
3185
3186   for (i = 0; i < targets.length (); i++)
3187     if (likely_target_p (targets[i]))
3188       {
3189         if (likely_target)
3190           return NULL;
3191         likely_target = targets[i];
3192       }
3193   if (!likely_target
3194       ||!likely_target->definition
3195       || DECL_EXTERNAL (likely_target->decl))
3196     return NULL;
3197
3198   /* Don't use an implicitly-declared destructor (c++/58678).  */
3199   struct cgraph_node *non_thunk_target
3200     = likely_target->function_symbol ();
3201   if (DECL_ARTIFICIAL (non_thunk_target->decl))
3202     return NULL;
3203   if (likely_target->get_availability () <= AVAIL_INTERPOSABLE
3204       && likely_target->can_be_discarded_p ())
3205     return NULL;
3206   return likely_target;
3207 }
3208
3209 /* The ipa-devirt pass.
3210    When polymorphic call has only one likely target in the unit,
3211    turn it into a speculative call.  */
3212
3213 static unsigned int
3214 ipa_devirt (void)
3215 {
3216   struct cgraph_node *n;
3217   hash_set<void *> bad_call_targets;
3218   struct cgraph_edge *e;
3219
3220   int npolymorphic = 0, nspeculated = 0, nconverted = 0, ncold = 0;
3221   int nmultiple = 0, noverwritable = 0, ndevirtualized = 0, nnotdefined = 0;
3222   int nwrong = 0, nok = 0, nexternal = 0, nartificial = 0;
3223   int ndropped = 0;
3224
3225   if (!odr_types_ptr)
3226     return 0;
3227
3228   if (dump_file)
3229     dump_type_inheritance_graph (dump_file);
3230
3231   /* We can output -Wsuggest-final-methods and -Wsuggest-final-types warnings.
3232      This is implemented by setting up final_warning_records that are updated
3233      by get_polymorphic_call_targets.
3234      We need to clear cache in this case to trigger recomputation of all
3235      entries.  */
3236   if (warn_suggest_final_methods || warn_suggest_final_types)
3237     {
3238       final_warning_records = new (final_warning_record);
3239       final_warning_records->type_warnings = vNULL;
3240       final_warning_records->type_warnings.safe_grow_cleared (odr_types.length ());
3241       free_polymorphic_call_targets_hash ();
3242     }
3243
3244   FOR_EACH_DEFINED_FUNCTION (n)
3245     {   
3246       bool update = false;
3247       if (!opt_for_fn (n->decl, flag_devirtualize))
3248         continue;
3249       if (dump_file && n->indirect_calls)
3250         fprintf (dump_file, "\n\nProcesing function %s/%i\n",
3251                  n->name (), n->order);
3252       for (e = n->indirect_calls; e; e = e->next_callee)
3253         if (e->indirect_info->polymorphic)
3254           {
3255             struct cgraph_node *likely_target = NULL;
3256             void *cache_token;
3257             bool final;
3258
3259             if (final_warning_records)
3260               final_warning_records->dyn_count = e->count;
3261
3262             vec <cgraph_node *>targets
3263                = possible_polymorphic_call_targets
3264                     (e, &final, &cache_token, true);
3265             unsigned int i;
3266
3267             /* Trigger warnings by calculating non-speculative targets.  */
3268             if (warn_suggest_final_methods || warn_suggest_final_types)
3269               possible_polymorphic_call_targets (e);
3270
3271             if (dump_file)
3272               dump_possible_polymorphic_call_targets 
3273                 (dump_file, e);
3274
3275             npolymorphic++;
3276
3277             /* See if the call can be devirtualized by means of ipa-prop's
3278                polymorphic call context propagation.  If not, we can just
3279                forget about this call being polymorphic and avoid some heavy
3280                lifting in remove_unreachable_nodes that will otherwise try to
3281                keep all possible targets alive until inlining and in the inliner
3282                itself.
3283
3284                This may need to be revisited once we add further ways to use
3285                the may edges, but it is a resonable thing to do right now.  */
3286
3287             if ((e->indirect_info->param_index == -1
3288                 || (!opt_for_fn (n->decl, flag_devirtualize_speculatively)
3289                     && e->indirect_info->vptr_changed))
3290                 && !flag_ltrans_devirtualize)
3291               {
3292                 e->indirect_info->polymorphic = false;
3293                 ndropped++;
3294                 if (dump_file)
3295                   fprintf (dump_file, "Dropping polymorphic call info;"
3296                            " it can not be used by ipa-prop\n");
3297               }
3298
3299             if (!opt_for_fn (n->decl, flag_devirtualize_speculatively))
3300               continue;
3301
3302             if (!e->maybe_hot_p ())
3303               {
3304                 if (dump_file)
3305                   fprintf (dump_file, "Call is cold\n\n");
3306                 ncold++;
3307                 continue;
3308               }
3309             if (e->speculative)
3310               {
3311                 if (dump_file)
3312                   fprintf (dump_file, "Call is already speculated\n\n");
3313                 nspeculated++;
3314
3315                 /* When dumping see if we agree with speculation.  */
3316                 if (!dump_file)
3317                   continue;
3318               }
3319             if (bad_call_targets.contains (cache_token))
3320               {
3321                 if (dump_file)
3322                   fprintf (dump_file, "Target list is known to be useless\n\n");
3323                 nmultiple++;
3324                 continue;
3325               }
3326             for (i = 0; i < targets.length (); i++)
3327               if (likely_target_p (targets[i]))
3328                 {
3329                   if (likely_target)
3330                     {
3331                       likely_target = NULL;
3332                       if (dump_file)
3333                         fprintf (dump_file, "More than one likely target\n\n");
3334                       nmultiple++;
3335                       break;
3336                     }
3337                   likely_target = targets[i];
3338                 }
3339             if (!likely_target)
3340               {
3341                 bad_call_targets.add (cache_token);
3342                 continue;
3343               }
3344             /* This is reached only when dumping; check if we agree or disagree
3345                with the speculation.  */
3346             if (e->speculative)
3347               {
3348                 struct cgraph_edge *e2;
3349                 struct ipa_ref *ref;
3350                 e->speculative_call_info (e2, e, ref);
3351                 if (e2->callee->ultimate_alias_target ()
3352                     == likely_target->ultimate_alias_target ())
3353                   {
3354                     fprintf (dump_file, "We agree with speculation\n\n");
3355                     nok++;
3356                   }
3357                 else
3358                   {
3359                     fprintf (dump_file, "We disagree with speculation\n\n");
3360                     nwrong++;
3361                   }
3362                 continue;
3363               }
3364             if (!likely_target->definition)
3365               {
3366                 if (dump_file)
3367                   fprintf (dump_file, "Target is not a definition\n\n");
3368                 nnotdefined++;
3369                 continue;
3370               }
3371             /* Do not introduce new references to external symbols.  While we
3372                can handle these just well, it is common for programs to
3373                incorrectly with headers defining methods they are linked
3374                with.  */
3375             if (DECL_EXTERNAL (likely_target->decl))
3376               {
3377                 if (dump_file)
3378                   fprintf (dump_file, "Target is external\n\n");
3379                 nexternal++;
3380                 continue;
3381               }
3382             /* Don't use an implicitly-declared destructor (c++/58678).  */
3383             struct cgraph_node *non_thunk_target
3384               = likely_target->function_symbol ();
3385             if (DECL_ARTIFICIAL (non_thunk_target->decl))
3386               {
3387                 if (dump_file)
3388                   fprintf (dump_file, "Target is artificial\n\n");
3389                 nartificial++;
3390                 continue;
3391               }
3392             if (likely_target->get_availability () <= AVAIL_INTERPOSABLE
3393                 && likely_target->can_be_discarded_p ())
3394               {
3395                 if (dump_file)
3396                   fprintf (dump_file, "Target is overwritable\n\n");
3397                 noverwritable++;
3398                 continue;
3399               }
3400             else if (dbg_cnt (devirt))
3401               {
3402                 if (dump_enabled_p ())
3403                   {
3404                     location_t locus = gimple_location_safe (e->call_stmt);
3405                     dump_printf_loc (MSG_OPTIMIZED_LOCATIONS, locus,
3406                                      "speculatively devirtualizing call in %s/%i to %s/%i\n",
3407                                      n->name (), n->order,
3408                                      likely_target->name (),
3409                                      likely_target->order);
3410                   }
3411                 if (!likely_target->can_be_discarded_p ())
3412                   {
3413                     cgraph_node *alias;
3414                     alias = dyn_cast<cgraph_node *> (likely_target->noninterposable_alias ());
3415                     if (alias)
3416                       likely_target = alias;
3417                   }
3418                 nconverted++;
3419                 update = true;
3420                 e->make_speculative
3421                   (likely_target, e->count * 8 / 10, e->frequency * 8 / 10);
3422               }
3423           }
3424       if (update)
3425         inline_update_overall_summary (n);
3426     }
3427   if (warn_suggest_final_methods || warn_suggest_final_types)
3428     {
3429       if (warn_suggest_final_types)
3430         {
3431           final_warning_records->type_warnings.qsort (type_warning_cmp);
3432           for (unsigned int i = 0;
3433                i < final_warning_records->type_warnings.length (); i++)
3434             if (final_warning_records->type_warnings[i].count)
3435               {
3436                 tree type = final_warning_records->type_warnings[i].type;
3437                 int count = final_warning_records->type_warnings[i].count;
3438                 long long dyn_count
3439                   = final_warning_records->type_warnings[i].dyn_count;
3440
3441                 if (!dyn_count)
3442                   warning_n (DECL_SOURCE_LOCATION (TYPE_NAME (type)),
3443                              OPT_Wsuggest_final_types, count,
3444                              "Declaring type %qD final "
3445                              "would enable devirtualization of %i call",
3446                              "Declaring type %qD final "
3447                              "would enable devirtualization of %i calls",
3448                              type,
3449                              count);
3450                 else
3451                   warning_n (DECL_SOURCE_LOCATION (TYPE_NAME (type)),
3452                              OPT_Wsuggest_final_types, count,
3453                              "Declaring type %qD final "
3454                              "would enable devirtualization of %i call "
3455                              "executed %lli times",
3456                              "Declaring type %qD final "
3457                              "would enable devirtualization of %i calls "
3458                              "executed %lli times",
3459                              type,
3460                              count,
3461                              dyn_count);
3462               }
3463         }
3464
3465       if (warn_suggest_final_methods)
3466         {
3467           vec<const decl_warn_count*> decl_warnings_vec = vNULL;
3468
3469           final_warning_records->decl_warnings.traverse
3470             <vec<const decl_warn_count *> *, add_decl_warning> (&decl_warnings_vec);
3471           decl_warnings_vec.qsort (decl_warning_cmp);
3472           for (unsigned int i = 0; i < decl_warnings_vec.length (); i++)
3473             {
3474               tree decl = decl_warnings_vec[i]->decl;
3475               int count = decl_warnings_vec[i]->count;
3476               long long dyn_count = decl_warnings_vec[i]->dyn_count;
3477
3478               if (!dyn_count)
3479                 if (DECL_CXX_DESTRUCTOR_P (decl))
3480                   warning_n (DECL_SOURCE_LOCATION (decl),
3481                               OPT_Wsuggest_final_methods, count,
3482                               "Declaring virtual destructor of %qD final "
3483                               "would enable devirtualization of %i call",
3484                               "Declaring virtual destructor of %qD final "
3485                               "would enable devirtualization of %i calls",
3486                               DECL_CONTEXT (decl), count);
3487                 else
3488                   warning_n (DECL_SOURCE_LOCATION (decl),
3489                               OPT_Wsuggest_final_methods, count,
3490                               "Declaring method %qD final "
3491                               "would enable devirtualization of %i call",
3492                               "Declaring method %qD final "
3493                               "would enable devirtualization of %i calls",
3494                               decl, count);
3495                else if (DECL_CXX_DESTRUCTOR_P (decl))
3496                   warning_n (DECL_SOURCE_LOCATION (decl),
3497                               OPT_Wsuggest_final_methods, count,
3498                               "Declaring virtual destructor of %qD final "
3499                               "would enable devirtualization of %i call "
3500                               "executed %lli times",
3501                               "Declaring virtual destructor of %qD final "
3502                               "would enable devirtualization of %i calls "
3503                               "executed %lli times",
3504                               DECL_CONTEXT (decl), count, dyn_count);
3505                 else
3506                   warning_n (DECL_SOURCE_LOCATION (decl),
3507                               OPT_Wsuggest_final_methods, count,
3508                               "Declaring method %qD final "
3509                               "would enable devirtualization of %i call "
3510                               "executed %lli times",
3511                               "Declaring method %qD final "
3512                               "would enable devirtualization of %i calls "
3513                               "executed %lli times",
3514                               decl, count, dyn_count);
3515             }
3516         }
3517         
3518       delete (final_warning_records);
3519       final_warning_records = 0;
3520     }
3521
3522   if (dump_file)
3523     fprintf (dump_file,
3524              "%i polymorphic calls, %i devirtualized,"
3525              " %i speculatively devirtualized, %i cold\n"
3526              "%i have multiple targets, %i overwritable,"
3527              " %i already speculated (%i agree, %i disagree),"
3528              " %i external, %i not defined, %i artificial, %i infos dropped\n",
3529              npolymorphic, ndevirtualized, nconverted, ncold,
3530              nmultiple, noverwritable, nspeculated, nok, nwrong,
3531              nexternal, nnotdefined, nartificial, ndropped);
3532   return ndevirtualized || ndropped ? TODO_remove_functions : 0;
3533 }
3534
3535 namespace {
3536
3537 const pass_data pass_data_ipa_devirt =
3538 {
3539   IPA_PASS, /* type */
3540   "devirt", /* name */
3541   OPTGROUP_NONE, /* optinfo_flags */
3542   TV_IPA_DEVIRT, /* tv_id */
3543   0, /* properties_required */
3544   0, /* properties_provided */
3545   0, /* properties_destroyed */
3546   0, /* todo_flags_start */
3547   ( TODO_dump_symtab ), /* todo_flags_finish */
3548 };
3549
3550 class pass_ipa_devirt : public ipa_opt_pass_d
3551 {
3552 public:
3553   pass_ipa_devirt (gcc::context *ctxt)
3554     : ipa_opt_pass_d (pass_data_ipa_devirt, ctxt,
3555                       NULL, /* generate_summary */
3556                       NULL, /* write_summary */
3557                       NULL, /* read_summary */
3558                       NULL, /* write_optimization_summary */
3559                       NULL, /* read_optimization_summary */
3560                       NULL, /* stmt_fixup */
3561                       0, /* function_transform_todo_flags_start */
3562                       NULL, /* function_transform */
3563                       NULL) /* variable_transform */
3564   {}
3565
3566   /* opt_pass methods: */
3567   virtual bool gate (function *)
3568     {
3569       /* In LTO, always run the IPA passes and decide on function basis if the
3570          pass is enabled.  */
3571       if (in_lto_p)
3572         return true;
3573       return (flag_devirtualize
3574               && (flag_devirtualize_speculatively
3575                   || (warn_suggest_final_methods
3576                       || warn_suggest_final_types))
3577               && optimize);
3578     }
3579
3580   virtual unsigned int execute (function *) { return ipa_devirt (); }
3581
3582 }; // class pass_ipa_devirt
3583
3584 } // anon namespace
3585
3586 ipa_opt_pass_d *
3587 make_pass_ipa_devirt (gcc::context *ctxt)
3588 {
3589   return new pass_ipa_devirt (ctxt);
3590 }
3591
3592 #include "gt-ipa-devirt.h"