gcc/ipa-devirt.c

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