gcc/cp/mangle.c

   1 /* Name mangling for the 3.0 C++ ABI.
   2    Copyright (C) 2000-2013 Free Software Foundation, Inc.
   3    Written by Alex Samuel <samuel@codesourcery.com>
   4
   5    This file is part of GCC.
   6
   7    GCC is free software; you can redistribute it and/or modify it
   8    under the terms of the GNU General Public License as published by
   9    the Free Software Foundation; either version 3, or (at your option)
  10    any later version.
  11
  12    GCC is distributed in the hope that it will be useful, but
  13    WITHOUT ANY WARRANTY; without even the implied warranty of
  14    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  15    General Public License for more details.
  16
  17 You should have received a copy of the GNU General Public License
  18 along with GCC; see the file COPYING3.  If not see
  19 <http://www.gnu.org/licenses/>.  */
  20
  21 /* This file implements mangling of C++ names according to the IA64
  22    C++ ABI specification.  A mangled name encodes a function or
  23    variable's name, scope, type, and/or template arguments into a text
  24    identifier.  This identifier is used as the function's or
  25    variable's linkage name, to preserve compatibility between C++'s
  26    language features (templates, scoping, and overloading) and C
  27    linkers.
  28
  29    Additionally, g++ uses mangled names internally.  To support this,
  30    mangling of types is allowed, even though the mangled name of a
  31    type should not appear by itself as an exported name.  Ditto for
  32    uninstantiated templates.
  33
  34    The primary entry point for this module is mangle_decl, which
  35    returns an identifier containing the mangled name for a decl.
  36    Additional entry points are provided to build mangled names of
  37    particular constructs when the appropriate decl for that construct
  38    is not available.  These are:
  39
  40      mangle_typeinfo_for_type:          typeinfo data
  41      mangle_typeinfo_string_for_type:   typeinfo type name
  42      mangle_vtbl_for_type:              virtual table data
  43      mangle_vtt_for_type:               VTT data
  44      mangle_ctor_vtbl_for_type:         `C-in-B' constructor virtual table data
  45      mangle_thunk:                      thunk function or entry  */
  46
  47 #include "config.h"
  48 #include "system.h"
  49 #include "coretypes.h"
  50 #include "tm.h"
  51 #include "tree.h"
  52 #include "tm_p.h"
  53 #include "cp-tree.h"
  54 #include "obstack.h"
  55 #include "flags.h"
  56 #include "target.h"
  57 #include "cgraph.h"
  58
  59 /* Debugging support.  */
  60
  61 /* Define DEBUG_MANGLE to enable very verbose trace messages.  */
  62 #ifndef DEBUG_MANGLE
  63 #define DEBUG_MANGLE 0
  64 #endif
  65
  66 /* Macros for tracing the write_* functions.  */
  67 #if DEBUG_MANGLE
  68 # define MANGLE_TRACE(FN, INPUT) \
  69   fprintf (stderr, "  %-24s: %-24s\n", (FN), (INPUT))
  70 # define MANGLE_TRACE_TREE(FN, NODE) \
  71   fprintf (stderr, "  %-24s: %-24s (%p)\n", \
  72            (FN), tree_code_name[TREE_CODE (NODE)], (void *) (NODE))
  73 #else
  74 # define MANGLE_TRACE(FN, INPUT)
  75 # define MANGLE_TRACE_TREE(FN, NODE)
  76 #endif
  77
  78 /* Nonzero if NODE is a class template-id.  We can't rely on
  79    CLASSTYPE_USE_TEMPLATE here because of tricky bugs in the parser
  80    that hard to distinguish A<T> from A, where A<T> is the type as
  81    instantiated outside of the template, and A is the type used
  82    without parameters inside the template.  */
  83 #define CLASSTYPE_TEMPLATE_ID_P(NODE)                                   \
  84   (TYPE_LANG_SPECIFIC (NODE) != NULL                                    \
  85    && (TREE_CODE (NODE) == BOUND_TEMPLATE_TEMPLATE_PARM                 \
  86        || (CLASSTYPE_TEMPLATE_INFO (NODE) != NULL                       \
  87            && (PRIMARY_TEMPLATE_P (CLASSTYPE_TI_TEMPLATE (NODE))))))
  88
  89 /* Things we only need one of.  This module is not reentrant.  */
  90 typedef struct GTY(()) globals {
  91   /* An array of the current substitution candidates, in the order
  92      we've seen them.  */
  93   vec<tree, va_gc> *substitutions;
  94
  95   /* The entity that is being mangled.  */
  96   tree GTY ((skip)) entity;
  97
  98   /* How many parameter scopes we are inside.  */
  99   int parm_depth;
 100
 101   /* True if the mangling will be different in a future version of the
 102      ABI.  */
 103   bool need_abi_warning;
 104 } globals;
 105
 106 static GTY (()) globals G;
 107
 108 /* The obstack on which we build mangled names.  */
 109 static struct obstack *mangle_obstack;
 110
 111 /* The obstack on which we build mangled names that are not going to
 112    be IDENTIFIER_NODEs.  */
 113 static struct obstack name_obstack;
 114
 115 /* The first object on the name_obstack; we use this to free memory
 116    allocated on the name_obstack.  */
 117 static void *name_base;
 118
 119 /* Indices into subst_identifiers.  These are identifiers used in
 120    special substitution rules.  */
 121 typedef enum
 122 {
 123   SUBID_ALLOCATOR,
 124   SUBID_BASIC_STRING,
 125   SUBID_CHAR_TRAITS,
 126   SUBID_BASIC_ISTREAM,
 127   SUBID_BASIC_OSTREAM,
 128   SUBID_BASIC_IOSTREAM,
 129   SUBID_MAX
 130 }
 131 substitution_identifier_index_t;
 132
 133 /* For quick substitution checks, look up these common identifiers
 134    once only.  */
 135 static GTY(()) tree subst_identifiers[SUBID_MAX];
 136
 137 /* Single-letter codes for builtin integer types, defined in
 138    <builtin-type>.  These are indexed by integer_type_kind values.  */
 139 static const char
 140 integer_type_codes[itk_none] =
 141 {
 142   'c',  /* itk_char */
 143   'a',  /* itk_signed_char */
 144   'h',  /* itk_unsigned_char */
 145   's',  /* itk_short */
 146   't',  /* itk_unsigned_short */
 147   'i',  /* itk_int */
 148   'j',  /* itk_unsigned_int */
 149   'l',  /* itk_long */
 150   'm',  /* itk_unsigned_long */
 151   'x',  /* itk_long_long */
 152   'y',  /* itk_unsigned_long_long */
 153   'n',  /* itk_int128 */
 154   'o',  /* itk_unsigned_int128  */
 155 };
 156
 157 static int decl_is_template_id (const tree, tree* const);
 158
 159 /* Functions for handling substitutions.  */
 160
 161 static inline tree canonicalize_for_substitution (tree);
 162 static void add_substitution (tree);
 163 static inline int is_std_substitution (const tree,
 164                                        const substitution_identifier_index_t);
 165 static inline int is_std_substitution_char (const tree,
 166                                             const substitution_identifier_index_t);
 167 static int find_substitution (tree);
 168 static void mangle_call_offset (const tree, const tree);
 169
 170 /* Functions for emitting mangled representations of things.  */
 171
 172 static void write_mangled_name (const tree, bool);
 173 static void write_encoding (const tree);
 174 static void write_name (tree, const int);
 175 static void write_abi_tags (tree);
 176 static void write_unscoped_name (const tree);
 177 static void write_unscoped_template_name (const tree);
 178 static void write_nested_name (const tree);
 179 static void write_prefix (const tree);
 180 static void write_template_prefix (const tree);
 181 static void write_unqualified_name (const tree);
 182 static void write_conversion_operator_name (const tree);
 183 static void write_source_name (tree);
 184 static void write_literal_operator_name (tree);
 185 static void write_unnamed_type_name (const tree);
 186 static void write_closure_type_name (const tree);
 187 static int hwint_to_ascii (unsigned HOST_WIDE_INT, const unsigned int, char *,
 188                            const unsigned int);
 189 static void write_number (unsigned HOST_WIDE_INT, const int,
 190                           const unsigned int);
 191 static void write_compact_number (int num);
 192 static void write_integer_cst (const tree);
 193 static void write_real_cst (const tree);
 194 static void write_identifier (const char *);
 195 static void write_special_name_constructor (const tree);
 196 static void write_special_name_destructor (const tree);
 197 static void write_type (tree);
 198 static int write_CV_qualifiers_for_type (const tree);
 199 static void write_builtin_type (tree);
 200 static void write_function_type (const tree);
 201 static void write_bare_function_type (const tree, const int, const tree);
 202 static void write_method_parms (tree, const int, const tree);
 203 static void write_class_enum_type (const tree);
 204 static void write_template_args (tree);
 205 static void write_expression (tree);
 206 static void write_template_arg_literal (const tree);
 207 static void write_template_arg (tree);
 208 static void write_template_template_arg (const tree);
 209 static void write_array_type (const tree);
 210 static void write_pointer_to_member_type (const tree);
 211 static void write_template_param (const tree);
 212 static void write_template_template_param (const tree);
 213 static void write_substitution (const int);
 214 static int discriminator_for_local_entity (tree);
 215 static int discriminator_for_string_literal (tree, tree);
 216 static void write_discriminator (const int);
 217 static void write_local_name (tree, const tree, const tree);
 218 static void dump_substitution_candidates (void);
 219 static tree mangle_decl_string (const tree);
 220 static int local_class_index (tree);
 221
 222 /* Control functions.  */
 223
 224 static inline void start_mangling (const tree);
 225 static inline const char *finish_mangling (const bool);
 226 static tree mangle_special_for_type (const tree, const char *);
 227
 228 /* Foreign language functions.  */
 229
 230 static void write_java_integer_type_codes (const tree);
 231
 232 /* Append a single character to the end of the mangled
 233    representation.  */
 234 #define write_char(CHAR)                                                \
 235   obstack_1grow (mangle_obstack, (CHAR))
 236
 237 /* Append a sized buffer to the end of the mangled representation.  */
 238 #define write_chars(CHAR, LEN)                                          \
 239   obstack_grow (mangle_obstack, (CHAR), (LEN))
 240
 241 /* Append a NUL-terminated string to the end of the mangled
 242    representation.  */
 243 #define write_string(STRING)                                            \
 244   obstack_grow (mangle_obstack, (STRING), strlen (STRING))
 245
 246 /* Nonzero if NODE1 and NODE2 are both TREE_LIST nodes and have the
 247    same purpose (context, which may be a type) and value (template
 248    decl).  See write_template_prefix for more information on what this
 249    is used for.  */
 250 #define NESTED_TEMPLATE_MATCH(NODE1, NODE2)                             \
 251   (TREE_CODE (NODE1) == TREE_LIST                                       \
 252    && TREE_CODE (NODE2) == TREE_LIST                                    \
 253    && ((TYPE_P (TREE_PURPOSE (NODE1))                                   \
 254         && same_type_p (TREE_PURPOSE (NODE1), TREE_PURPOSE (NODE2)))    \
 255        || TREE_PURPOSE (NODE1) == TREE_PURPOSE (NODE2))                 \
 256    && TREE_VALUE (NODE1) == TREE_VALUE (NODE2))
 257
 258 /* Write out an unsigned quantity in base 10.  */
 259 #define write_unsigned_number(NUMBER)                                   \
 260   write_number ((NUMBER), /*unsigned_p=*/1, 10)
 261
 262 /* If DECL is a template instance, return nonzero and, if
 263    TEMPLATE_INFO is non-NULL, set *TEMPLATE_INFO to its template info.
 264    Otherwise return zero.  */
 265
 266 static int
 267 decl_is_template_id (const tree decl, tree* const template_info)
 268 {
 269   if (TREE_CODE (decl) == TYPE_DECL)
 270     {
 271       /* TYPE_DECLs are handled specially.  Look at its type to decide
 272          if this is a template instantiation.  */
 273       const tree type = TREE_TYPE (decl);
 274
 275       if (CLASS_TYPE_P (type) && CLASSTYPE_TEMPLATE_ID_P (type))
 276         {
 277           if (template_info != NULL)
 278             /* For a templated TYPE_DECL, the template info is hanging
 279                off the type.  */
 280             *template_info = TYPE_TEMPLATE_INFO (type);
 281           return 1;
 282         }
 283     }
 284   else
 285     {
 286       /* Check if this is a primary template.  */
 287       if (DECL_LANG_SPECIFIC (decl) != NULL
 288           && DECL_USE_TEMPLATE (decl)
 289           && PRIMARY_TEMPLATE_P (DECL_TI_TEMPLATE (decl))
 290           && TREE_CODE (decl) != TEMPLATE_DECL)
 291         {
 292           if (template_info != NULL)
 293             /* For most templated decls, the template info is hanging
 294                off the decl.  */
 295             *template_info = DECL_TEMPLATE_INFO (decl);
 296           return 1;
 297         }
 298     }
 299
 300   /* It's not a template id.  */
 301   return 0;
 302 }
 303
 304 /* Produce debugging output of current substitution candidates.  */
 305
 306 static void
 307 dump_substitution_candidates (void)
 308 {
 309   unsigned i;
 310   tree el;
 311
 312   fprintf (stderr, "  ++ substitutions  ");
 313   FOR_EACH_VEC_ELT (*G.substitutions, i, el)
 314     {
 315       const char *name = "???";
 316
 317       if (i > 0)
 318         fprintf (stderr, "                    ");
 319       if (DECL_P (el))
 320         name = IDENTIFIER_POINTER (DECL_NAME (el));
 321       else if (TREE_CODE (el) == TREE_LIST)
 322         name = IDENTIFIER_POINTER (DECL_NAME (TREE_VALUE (el)));
 323       else if (TYPE_NAME (el))
 324         name = IDENTIFIER_POINTER (DECL_NAME (TYPE_NAME (el)));
 325       fprintf (stderr, " S%d_ = ", i - 1);
 326       if (TYPE_P (el) &&
 327           (CP_TYPE_RESTRICT_P (el)
 328            || CP_TYPE_VOLATILE_P (el)
 329            || CP_TYPE_CONST_P (el)))
 330         fprintf (stderr, "CV-");
 331       fprintf (stderr, "%s (%s at %p)\n",
 332                name, tree_code_name[TREE_CODE (el)], (void *) el);
 333     }
 334 }
 335
 336 /* Both decls and types can be substitution candidates, but sometimes
 337    they refer to the same thing.  For instance, a TYPE_DECL and
 338    RECORD_TYPE for the same class refer to the same thing, and should
 339    be treated accordingly in substitutions.  This function returns a
 340    canonicalized tree node representing NODE that is used when adding
 341    and substitution candidates and finding matches.  */
 342
 343 static inline tree
 344 canonicalize_for_substitution (tree node)
 345 {
 346   /* For a TYPE_DECL, use the type instead.  */
 347   if (TREE_CODE (node) == TYPE_DECL)
 348     node = TREE_TYPE (node);
 349   if (TYPE_P (node)
 350       && TYPE_CANONICAL (node) != node
 351       && TYPE_MAIN_VARIANT (node) != node)
 352     {
 353       tree orig = node;
 354       /* Here we want to strip the topmost typedef only.
 355          We need to do that so is_std_substitution can do proper
 356          name matching.  */
 357       if (TREE_CODE (node) == FUNCTION_TYPE)
 358         /* Use build_qualified_type and TYPE_QUALS here to preserve
 359            the old buggy mangling of attribute noreturn with abi<5.  */
 360         node = build_qualified_type (TYPE_MAIN_VARIANT (node),
 361                                      TYPE_QUALS (node));
 362       else
 363         node = cp_build_qualified_type (TYPE_MAIN_VARIANT (node),
 364                                         cp_type_quals (node));
 365       if (TREE_CODE (node) == FUNCTION_TYPE
 366           || TREE_CODE (node) == METHOD_TYPE)
 367         node = build_ref_qualified_type (node, type_memfn_rqual (orig));
 368     }
 369   return node;
 370 }
 371
 372 /* Add NODE as a substitution candidate.  NODE must not already be on
 373    the list of candidates.  */
 374
 375 static void
 376 add_substitution (tree node)
 377 {
 378   tree c;
 379
 380   if (DEBUG_MANGLE)
 381     fprintf (stderr, "  ++ add_substitution (%s at %10p)\n",
 382              tree_code_name[TREE_CODE (node)], (void *) node);
 383
 384   /* Get the canonicalized substitution candidate for NODE.  */
 385   c = canonicalize_for_substitution (node);
 386   if (DEBUG_MANGLE && c != node)
 387     fprintf (stderr, "  ++ using candidate (%s at %10p)\n",
 388              tree_code_name[TREE_CODE (node)], (void *) node);
 389   node = c;
 390
 391 #if ENABLE_CHECKING
 392   /* Make sure NODE isn't already a candidate.  */
 393   {
 394     int i;
 395     tree candidate;
 396
 397     FOR_EACH_VEC_SAFE_ELT (G.substitutions, i, candidate)
 398       {
 399         gcc_assert (!(DECL_P (node) && node == candidate));
 400         gcc_assert (!(TYPE_P (node) && TYPE_P (candidate)
 401                       && same_type_p (node, candidate)));
 402       }
 403   }
 404 #endif /* ENABLE_CHECKING */
 405
 406   /* Put the decl onto the varray of substitution candidates.  */
 407   vec_safe_push (G.substitutions, node);
 408
 409   if (DEBUG_MANGLE)
 410     dump_substitution_candidates ();
 411 }
 412
 413 /* Helper function for find_substitution.  Returns nonzero if NODE,
 414    which may be a decl or a CLASS_TYPE, is a template-id with template
 415    name of substitution_index[INDEX] in the ::std namespace.  */
 416
 417 static inline int
 418 is_std_substitution (const tree node,
 419                      const substitution_identifier_index_t index)
 420 {
 421   tree type = NULL;
 422   tree decl = NULL;
 423
 424   if (DECL_P (node))
 425     {
 426       type = TREE_TYPE (node);
 427       decl = node;
 428     }
 429   else if (CLASS_TYPE_P (node))
 430     {
 431       type = node;
 432       decl = TYPE_NAME (node);
 433     }
 434   else
 435     /* These are not the droids you're looking for.  */
 436     return 0;
 437
 438   return (DECL_NAMESPACE_STD_P (CP_DECL_CONTEXT (decl))
 439           && TYPE_LANG_SPECIFIC (type)
 440           && TYPE_TEMPLATE_INFO (type)
 441           && (DECL_NAME (TYPE_TI_TEMPLATE (type))
 442               == subst_identifiers[index]));
 443 }
 444
 445 /* Helper function for find_substitution.  Returns nonzero if NODE,
 446    which may be a decl or a CLASS_TYPE, is the template-id
 447    ::std::identifier<char>, where identifier is
 448    substitution_index[INDEX].  */
 449
 450 static inline int
 451 is_std_substitution_char (const tree node,
 452                           const substitution_identifier_index_t index)
 453 {
 454   tree args;
 455   /* Check NODE's name is ::std::identifier.  */
 456   if (!is_std_substitution (node, index))
 457     return 0;
 458   /* Figure out its template args.  */
 459   if (DECL_P (node))
 460     args = DECL_TI_ARGS (node);
 461   else if (CLASS_TYPE_P (node))
 462     args = CLASSTYPE_TI_ARGS (node);
 463   else
 464     /* Oops, not a template.  */
 465     return 0;
 466   /* NODE's template arg list should be <char>.  */
 467   return
 468     TREE_VEC_LENGTH (args) == 1
 469     && TREE_VEC_ELT (args, 0) == char_type_node;
 470 }
 471
 472 /* Check whether a substitution should be used to represent NODE in
 473    the mangling.
 474
 475    First, check standard special-case substitutions.
 476
 477      <substitution> ::= St
 478          # ::std
 479
 480                     ::= Sa
 481          # ::std::allocator
 482
 483                     ::= Sb
 484          # ::std::basic_string
 485
 486                     ::= Ss
 487          # ::std::basic_string<char,
 488                                ::std::char_traits<char>,
 489                                ::std::allocator<char> >
 490
 491                     ::= Si
 492          # ::std::basic_istream<char, ::std::char_traits<char> >
 493
 494                     ::= So
 495          # ::std::basic_ostream<char, ::std::char_traits<char> >
 496
 497                     ::= Sd
 498          # ::std::basic_iostream<char, ::std::char_traits<char> >
 499
 500    Then examine the stack of currently available substitution
 501    candidates for entities appearing earlier in the same mangling
 502
 503    If a substitution is found, write its mangled representation and
 504    return nonzero.  If none is found, just return zero.  */
 505
 506 static int
 507 find_substitution (tree node)
 508 {
 509   int i;
 510   const int size = vec_safe_length (G.substitutions);
 511   tree decl;
 512   tree type;
 513
 514   if (DEBUG_MANGLE)
 515     fprintf (stderr, "  ++ find_substitution (%s at %p)\n",
 516              tree_code_name[TREE_CODE (node)], (void *) node);
 517
 518   /* Obtain the canonicalized substitution representation for NODE.
 519      This is what we'll compare against.  */
 520   node = canonicalize_for_substitution (node);
 521
 522   /* Check for builtin substitutions.  */
 523
 524   decl = TYPE_P (node) ? TYPE_NAME (node) : node;
 525   type = TYPE_P (node) ? node : TREE_TYPE (node);
 526
 527   /* Check for std::allocator.  */
 528   if (decl
 529       && is_std_substitution (decl, SUBID_ALLOCATOR)
 530       && !CLASSTYPE_USE_TEMPLATE (TREE_TYPE (decl)))
 531     {
 532       write_string ("Sa");
 533       return 1;
 534     }
 535
 536   /* Check for std::basic_string.  */
 537   if (decl && is_std_substitution (decl, SUBID_BASIC_STRING))
 538     {
 539       if (TYPE_P (node))
 540         {
 541           /* If this is a type (i.e. a fully-qualified template-id),
 542              check for
 543                  std::basic_string <char,
 544                                     std::char_traits<char>,
 545                                     std::allocator<char> > .  */
 546           if (cp_type_quals (type) == TYPE_UNQUALIFIED
 547               && CLASSTYPE_USE_TEMPLATE (type))
 548             {
 549               tree args = CLASSTYPE_TI_ARGS (type);
 550               if (TREE_VEC_LENGTH (args) == 3
 551                   && same_type_p (TREE_VEC_ELT (args, 0), char_type_node)
 552                   && is_std_substitution_char (TREE_VEC_ELT (args, 1),
 553                                                SUBID_CHAR_TRAITS)
 554                   && is_std_substitution_char (TREE_VEC_ELT (args, 2),
 555                                                SUBID_ALLOCATOR))
 556                 {
 557                   write_string ("Ss");
 558                   return 1;
 559                 }
 560             }
 561         }
 562       else
 563         /* Substitute for the template name only if this isn't a type.  */
 564         {
 565           write_string ("Sb");
 566           return 1;
 567         }
 568     }
 569
 570   /* Check for basic_{i,o,io}stream.  */
 571   if (TYPE_P (node)
 572       && cp_type_quals (type) == TYPE_UNQUALIFIED
 573       && CLASS_TYPE_P (type)
 574       && CLASSTYPE_USE_TEMPLATE (type)
 575       && CLASSTYPE_TEMPLATE_INFO (type) != NULL)
 576     {
 577       /* First, check for the template
 578          args <char, std::char_traits<char> > .  */
 579       tree args = CLASSTYPE_TI_ARGS (type);
 580       if (TREE_VEC_LENGTH (args) == 2
 581           && TYPE_P (TREE_VEC_ELT (args, 0))
 582           && same_type_p (TREE_VEC_ELT (args, 0), char_type_node)
 583           && is_std_substitution_char (TREE_VEC_ELT (args, 1),
 584                                        SUBID_CHAR_TRAITS))
 585         {
 586           /* Got them.  Is this basic_istream?  */
 587           if (is_std_substitution (decl, SUBID_BASIC_ISTREAM))
 588             {
 589               write_string ("Si");
 590               return 1;
 591             }
 592           /* Or basic_ostream?  */
 593           else if (is_std_substitution (decl, SUBID_BASIC_OSTREAM))
 594             {
 595               write_string ("So");
 596               return 1;
 597             }
 598           /* Or basic_iostream?  */
 599           else if (is_std_substitution (decl, SUBID_BASIC_IOSTREAM))
 600             {
 601               write_string ("Sd");
 602               return 1;
 603             }
 604         }
 605     }
 606
 607   /* Check for namespace std.  */
 608   if (decl && DECL_NAMESPACE_STD_P (decl))
 609     {
 610       write_string ("St");
 611       return 1;
 612     }
 613
 614   /* Now check the list of available substitutions for this mangling
 615      operation.  */
 616   for (i = 0; i < size; ++i)
 617     {
 618       tree candidate = (*G.substitutions)[i];
 619       /* NODE is a matched to a candidate if it's the same decl node or
 620          if it's the same type.  */
 621       if (decl == candidate
 622           || (TYPE_P (candidate) && type && TYPE_P (node)
 623               && same_type_p (type, candidate))
 624           || NESTED_TEMPLATE_MATCH (node, candidate))
 625         {
 626           write_substitution (i);
 627           return 1;
 628         }
 629     }
 630
 631   /* No substitution found.  */
 632   return 0;
 633 }
 634
 635
 636 /* TOP_LEVEL is true, if this is being called at outermost level of
 637   mangling. It should be false when mangling a decl appearing in an
 638   expression within some other mangling.
 639
 640   <mangled-name>      ::= _Z <encoding>  */
 641
 642 static void
 643 write_mangled_name (const tree decl, bool top_level)
 644 {
 645   MANGLE_TRACE_TREE ("mangled-name", decl);
 646
 647   if (/* The names of `extern "C"' functions are not mangled.  */
 648       DECL_EXTERN_C_FUNCTION_P (decl)
 649       /* But overloaded operator names *are* mangled.  */
 650       && !DECL_OVERLOADED_OPERATOR_P (decl))
 651     {
 652     unmangled_name:;
 653
 654       if (top_level)
 655         write_string (IDENTIFIER_POINTER (DECL_NAME (decl)));
 656       else
 657         {
 658           /* The standard notes: "The <encoding> of an extern "C"
 659              function is treated like global-scope data, i.e. as its
 660              <source-name> without a type."  We cannot write
 661              overloaded operators that way though, because it contains
 662              characters invalid in assembler.  */
 663           if (abi_version_at_least (2))
 664             write_string ("_Z");
 665           else
 666             G.need_abi_warning = true;
 667           write_source_name (DECL_NAME (decl));
 668         }
 669     }
 670   else if (VAR_P (decl)
 671            /* The names of non-static global variables aren't mangled.  */
 672            && DECL_EXTERNAL_LINKAGE_P (decl)
 673            && (CP_DECL_CONTEXT (decl) == global_namespace
 674                /* And neither are `extern "C"' variables.  */
 675                || DECL_EXTERN_C_P (decl)))
 676     {
 677       if (top_level || abi_version_at_least (2))
 678         goto unmangled_name;
 679       else
 680         {
 681           G.need_abi_warning = true;
 682           goto mangled_name;
 683         }
 684     }
 685   else
 686     {
 687     mangled_name:;
 688       write_string ("_Z");
 689       write_encoding (decl);
 690       if (DECL_LANG_SPECIFIC (decl)
 691           && (DECL_MAYBE_IN_CHARGE_DESTRUCTOR_P (decl)
 692               || DECL_MAYBE_IN_CHARGE_CONSTRUCTOR_P (decl)))
 693         /* We need a distinct mangled name for these entities, but
 694            we should never actually output it.  So, we append some
 695            characters the assembler won't like.  */
 696         write_string (" *INTERNAL* ");
 697     }
 698 }
 699
 700 /*   <encoding>         ::= <function name> <bare-function-type>
 701                         ::= <data name>  */
 702
 703 static void
 704 write_encoding (const tree decl)
 705 {
 706   MANGLE_TRACE_TREE ("encoding", decl);
 707
 708   if (DECL_LANG_SPECIFIC (decl) && DECL_EXTERN_C_FUNCTION_P (decl))
 709     {
 710       /* For overloaded operators write just the mangled name
 711          without arguments.  */
 712       if (DECL_OVERLOADED_OPERATOR_P (decl))
 713         write_name (decl, /*ignore_local_scope=*/0);
 714       else
 715         write_source_name (DECL_NAME (decl));
 716       return;
 717     }
 718
 719   write_name (decl, /*ignore_local_scope=*/0);
 720   if (TREE_CODE (decl) == FUNCTION_DECL)
 721     {
 722       tree fn_type;
 723       tree d;
 724
 725       if (decl_is_template_id (decl, NULL))
 726         {
 727           fn_type = get_mostly_instantiated_function_type (decl);
 728           /* FN_TYPE will not have parameter types for in-charge or
 729              VTT parameters.  Therefore, we pass NULL_TREE to
 730              write_bare_function_type -- otherwise, it will get
 731              confused about which artificial parameters to skip.  */
 732           d = NULL_TREE;
 733         }
 734       else
 735         {
 736           fn_type = TREE_TYPE (decl);
 737           d = decl;
 738         }
 739
 740       write_bare_function_type (fn_type,
 741                                 (!DECL_CONSTRUCTOR_P (decl)
 742                                  && !DECL_DESTRUCTOR_P (decl)
 743                                  && !DECL_CONV_FN_P (decl)
 744                                  && decl_is_template_id (decl, NULL)),
 745                                 d);
 746     }
 747 }
 748
 749 /* Lambdas can have a bit more context for mangling, specifically VAR_DECL
 750    or PARM_DECL context, which doesn't belong in DECL_CONTEXT.  */
 751
 752 static tree
 753 decl_mangling_context (tree decl)
 754 {
 755   tree tcontext = targetm.cxx.decl_mangling_context (decl);
 756
 757   if (tcontext != NULL_TREE)
 758     return tcontext;
 759
 760   if (TREE_CODE (decl) == TYPE_DECL
 761       && LAMBDA_TYPE_P (TREE_TYPE (decl)))
 762     {
 763       tree extra = LAMBDA_TYPE_EXTRA_SCOPE (TREE_TYPE (decl));
 764       if (extra)
 765         return extra;
 766     }
 767     else if (TREE_CODE (decl) == TYPE_DECL
 768              && TREE_CODE (TREE_TYPE (decl)) == TEMPLATE_TYPE_PARM)
 769      /* template type parms have no mangling context.  */
 770       return NULL_TREE;
 771   return CP_DECL_CONTEXT (decl);
 772 }
 773
 774 /* <name> ::= <unscoped-name>
 775           ::= <unscoped-template-name> <template-args>
 776           ::= <nested-name>
 777           ::= <local-name>
 778
 779    If IGNORE_LOCAL_SCOPE is nonzero, this production of <name> is
 780    called from <local-name>, which mangles the enclosing scope
 781    elsewhere and then uses this function to mangle just the part
 782    underneath the function scope.  So don't use the <local-name>
 783    production, to avoid an infinite recursion.  */
 784
 785 static void
 786 write_name (tree decl, const int ignore_local_scope)
 787 {
 788   tree context;
 789
 790   MANGLE_TRACE_TREE ("name", decl);
 791
 792   if (TREE_CODE (decl) == TYPE_DECL)
 793     {
 794       /* In case this is a typedef, fish out the corresponding
 795          TYPE_DECL for the main variant.  */
 796       decl = TYPE_NAME (TYPE_MAIN_VARIANT (TREE_TYPE (decl)));
 797     }
 798
 799   context = decl_mangling_context (decl);
 800
 801   /* A decl in :: or ::std scope is treated specially.  The former is
 802      mangled using <unscoped-name> or <unscoped-template-name>, the
 803      latter with a special substitution.  Also, a name that is
 804      directly in a local function scope is also mangled with
 805      <unscoped-name> rather than a full <nested-name>.  */
 806   if (context == NULL
 807       || context == global_namespace
 808       || DECL_NAMESPACE_STD_P (context)
 809       || (ignore_local_scope
 810           && (TREE_CODE (context) == FUNCTION_DECL
 811               || (abi_version_at_least (7)
 812                   && TREE_CODE (context) == PARM_DECL))))
 813     {
 814       tree template_info;
 815       /* Is this a template instance?  */
 816       if (decl_is_template_id (decl, &template_info))
 817         {
 818           /* Yes: use <unscoped-template-name>.  */
 819           write_unscoped_template_name (TI_TEMPLATE (template_info));
 820           write_template_args (TI_ARGS (template_info));
 821         }
 822       else
 823         /* Everything else gets an <unqualified-name>.  */
 824         write_unscoped_name (decl);
 825     }
 826   else
 827     {
 828       /* Handle local names, unless we asked not to (that is, invoked
 829          under <local-name>, to handle only the part of the name under
 830          the local scope).  */
 831       if (!ignore_local_scope)
 832         {
 833           /* Scan up the list of scope context, looking for a
 834              function.  If we find one, this entity is in local
 835              function scope.  local_entity tracks context one scope
 836              level down, so it will contain the element that's
 837              directly in that function's scope, either decl or one of
 838              its enclosing scopes.  */
 839           tree local_entity = decl;
 840           while (context != NULL && context != global_namespace)
 841             {
 842               /* Make sure we're always dealing with decls.  */
 843               if (context != NULL && TYPE_P (context))
 844                 context = TYPE_NAME (context);
 845               /* Is this a function?  */
 846               if (TREE_CODE (context) == FUNCTION_DECL
 847                   || TREE_CODE (context) == PARM_DECL)
 848                 {
 849                   /* Yes, we have local scope.  Use the <local-name>
 850                      production for the innermost function scope.  */
 851                   write_local_name (context, local_entity, decl);
 852                   return;
 853                 }
 854               /* Up one scope level.  */
 855               local_entity = context;
 856               context = decl_mangling_context (context);
 857             }
 858
 859           /* No local scope found?  Fall through to <nested-name>.  */
 860         }
 861
 862       /* Other decls get a <nested-name> to encode their scope.  */
 863       write_nested_name (decl);
 864     }
 865 }
 866
 867 /* <unscoped-name> ::= <unqualified-name>
 868                    ::= St <unqualified-name>   # ::std::  */
 869
 870 static void
 871 write_unscoped_name (const tree decl)
 872 {
 873   tree context = decl_mangling_context (decl);
 874
 875   MANGLE_TRACE_TREE ("unscoped-name", decl);
 876
 877   /* Is DECL in ::std?  */
 878   if (DECL_NAMESPACE_STD_P (context))
 879     {
 880       write_string ("St");
 881       write_unqualified_name (decl);
 882     }
 883   else
 884     {
 885       /* If not, it should be either in the global namespace, or directly
 886          in a local function scope.  */
 887       gcc_assert (context == global_namespace
 888                   || context != NULL
 889                   || TREE_CODE (context) == FUNCTION_DECL);
 890
 891       write_unqualified_name (decl);
 892     }
 893 }
 894
 895 /* <unscoped-template-name> ::= <unscoped-name>
 896                             ::= <substitution>  */
 897
 898 static void
 899 write_unscoped_template_name (const tree decl)
 900 {
 901   MANGLE_TRACE_TREE ("unscoped-template-name", decl);
 902
 903   if (find_substitution (decl))
 904     return;
 905   write_unscoped_name (decl);
 906   add_substitution (decl);
 907 }
 908
 909 /* Write the nested name, including CV-qualifiers, of DECL.
 910
 911    <nested-name> ::= N [<CV-qualifiers>] [<ref-qualifier>] <prefix> <unqualified-name> E
 912                  ::= N [<CV-qualifiers>] [<ref-qualifier>] <template-prefix> <template-args> E
 913
 914    <ref-qualifier> ::= R # & ref-qualifier
 915                    ::= O # && ref-qualifier
 916    <CV-qualifiers> ::= [r] [V] [K]  */
 917
 918 static void
 919 write_nested_name (const tree decl)
 920 {
 921   tree template_info;
 922
 923   MANGLE_TRACE_TREE ("nested-name", decl);
 924
 925   write_char ('N');
 926
 927   /* Write CV-qualifiers, if this is a member function.  */
 928   if (TREE_CODE (decl) == FUNCTION_DECL
 929       && DECL_NONSTATIC_MEMBER_FUNCTION_P (decl))
 930     {
 931       if (DECL_VOLATILE_MEMFUNC_P (decl))
 932         write_char ('V');
 933       if (DECL_CONST_MEMFUNC_P (decl))
 934         write_char ('K');
 935       if (FUNCTION_REF_QUALIFIED (TREE_TYPE (decl)))
 936         {
 937           if (FUNCTION_RVALUE_QUALIFIED (TREE_TYPE (decl)))
 938             write_char ('O');
 939           else
 940             write_char ('R');
 941         }
 942     }
 943
 944   /* Is this a template instance?  */
 945   if (decl_is_template_id (decl, &template_info))
 946     {
 947       /* Yes, use <template-prefix>.  */
 948       write_template_prefix (decl);
 949       write_template_args (TI_ARGS (template_info));
 950     }
 951   else if (TREE_CODE (TREE_TYPE (decl)) == TYPENAME_TYPE)
 952     {
 953       tree name = TYPENAME_TYPE_FULLNAME (TREE_TYPE (decl));
 954       if (TREE_CODE (name) == TEMPLATE_ID_EXPR)
 955         {
 956           write_template_prefix (decl);
 957           write_template_args (TREE_OPERAND (name, 1));
 958         }
 959       else
 960         {
 961           write_prefix (decl_mangling_context (decl));
 962           write_unqualified_name (decl);
 963         }
 964     }
 965   else
 966     {
 967       /* No, just use <prefix>  */
 968       write_prefix (decl_mangling_context (decl));
 969       write_unqualified_name (decl);
 970     }
 971   write_char ('E');
 972 }
 973
 974 /* <prefix> ::= <prefix> <unqualified-name>
 975             ::= <template-param>
 976             ::= <template-prefix> <template-args>
 977             ::= <decltype>
 978             ::= # empty
 979             ::= <substitution>  */
 980
 981 static void
 982 write_prefix (const tree node)
 983 {
 984   tree decl;
 985   /* Non-NULL if NODE represents a template-id.  */
 986   tree template_info = NULL;
 987
 988   if (node == NULL
 989       || node == global_namespace)
 990     return;
 991
 992   MANGLE_TRACE_TREE ("prefix", node);
 993
 994   if (TREE_CODE (node) == DECLTYPE_TYPE)
 995     {
 996       write_type (node);
 997       return;
 998     }
 999
1000   if (find_substitution (node))
1001     return;
1002
1003   if (DECL_P (node))
1004     {
1005       /* If this is a function or parm decl, that means we've hit function
1006          scope, so this prefix must be for a local name.  In this
1007          case, we're under the <local-name> production, which encodes
1008          the enclosing function scope elsewhere.  So don't continue
1009          here.  */
1010       if (TREE_CODE (node) == FUNCTION_DECL
1011           || TREE_CODE (node) == PARM_DECL)
1012         return;
1013
1014       decl = node;
1015       decl_is_template_id (decl, &template_info);
1016     }
1017   else
1018     {
1019       /* Node is a type.  */
1020       decl = TYPE_NAME (node);
1021       if (CLASSTYPE_TEMPLATE_ID_P (node))
1022         template_info = TYPE_TEMPLATE_INFO (node);
1023     }
1024
1025   /* In G++ 3.2, the name of the template parameter was used.  */
1026   if (TREE_CODE (node) == TEMPLATE_TYPE_PARM
1027       && !abi_version_at_least (2))
1028     G.need_abi_warning = true;
1029
1030   if (TREE_CODE (node) == TEMPLATE_TYPE_PARM
1031       && abi_version_at_least (2))
1032     write_template_param (node);
1033   else if (template_info != NULL)
1034     /* Templated.  */
1035     {
1036       write_template_prefix (decl);
1037       write_template_args (TI_ARGS (template_info));
1038     }
1039   else if (TREE_CODE (TREE_TYPE (decl)) == TYPENAME_TYPE)
1040     {
1041       tree name = TYPENAME_TYPE_FULLNAME (TREE_TYPE (decl));
1042       if (TREE_CODE (name) == TEMPLATE_ID_EXPR)
1043         {
1044           write_template_prefix (decl);
1045           write_template_args (TREE_OPERAND (name, 1));
1046         }
1047       else
1048         {
1049           write_prefix (decl_mangling_context (decl));
1050           write_unqualified_name (decl);
1051         }
1052     }
1053   else
1054     /* Not templated.  */
1055     {
1056       write_prefix (decl_mangling_context (decl));
1057       write_unqualified_name (decl);
1058       if (VAR_P (decl)
1059           || TREE_CODE (decl) == FIELD_DECL)
1060         {
1061           /* <data-member-prefix> := <member source-name> M */
1062           write_char ('M');
1063           return;
1064         }
1065     }
1066
1067   add_substitution (node);
1068 }
1069
1070 /* <template-prefix> ::= <prefix> <template component>
1071                      ::= <template-param>
1072                      ::= <substitution>  */
1073
1074 static void
1075 write_template_prefix (const tree node)
1076 {
1077   tree decl = DECL_P (node) ? node : TYPE_NAME (node);
1078   tree type = DECL_P (node) ? TREE_TYPE (node) : node;
1079   tree context = decl_mangling_context (decl);
1080   tree template_info;
1081   tree templ;
1082   tree substitution;
1083
1084   MANGLE_TRACE_TREE ("template-prefix", node);
1085
1086   /* Find the template decl.  */
1087   if (decl_is_template_id (decl, &template_info))
1088     templ = TI_TEMPLATE (template_info);
1089   else if (TREE_CODE (type) == TYPENAME_TYPE)
1090     /* For a typename type, all we have is the name.  */
1091     templ = DECL_NAME (decl);
1092   else
1093     {
1094       gcc_assert (CLASSTYPE_TEMPLATE_ID_P (type));
1095
1096       templ = TYPE_TI_TEMPLATE (type);
1097     }
1098
1099   /* For a member template, though, the template name for the
1100      innermost name must have all the outer template levels
1101      instantiated.  For instance, consider
1102
1103        template<typename T> struct Outer {
1104          template<typename U> struct Inner {};
1105        };
1106
1107      The template name for `Inner' in `Outer<int>::Inner<float>' is
1108      `Outer<int>::Inner<U>'.  In g++, we don't instantiate the template
1109      levels separately, so there's no TEMPLATE_DECL available for this
1110      (there's only `Outer<T>::Inner<U>').
1111
1112      In order to get the substitutions right, we create a special
1113      TREE_LIST to represent the substitution candidate for a nested
1114      template.  The TREE_PURPOSE is the template's context, fully
1115      instantiated, and the TREE_VALUE is the TEMPLATE_DECL for the inner
1116      template.
1117
1118      So, for the example above, `Outer<int>::Inner' is represented as a
1119      substitution candidate by a TREE_LIST whose purpose is `Outer<int>'
1120      and whose value is `Outer<T>::Inner<U>'.  */
1121   if (TYPE_P (context))
1122     substitution = build_tree_list (context, templ);
1123   else
1124     substitution = templ;
1125
1126   if (find_substitution (substitution))
1127     return;
1128
1129   /* In G++ 3.2, the name of the template template parameter was used.  */
1130   if (TREE_TYPE (templ)
1131       && TREE_CODE (TREE_TYPE (templ)) == TEMPLATE_TEMPLATE_PARM
1132       && !abi_version_at_least (2))
1133     G.need_abi_warning = true;
1134
1135   if (TREE_TYPE (templ)
1136       && TREE_CODE (TREE_TYPE (templ)) == TEMPLATE_TEMPLATE_PARM
1137       && abi_version_at_least (2))
1138     write_template_param (TREE_TYPE (templ));
1139   else
1140     {
1141       write_prefix (context);
1142       write_unqualified_name (decl);
1143     }
1144
1145   add_substitution (substitution);
1146 }
1147
1148 /* We don't need to handle thunks, vtables, or VTTs here.  Those are
1149    mangled through special entry points.
1150
1151     <unqualified-name>  ::= <operator-name>
1152                         ::= <special-name>
1153                         ::= <source-name>
1154                         ::= <unnamed-type-name>
1155                         ::= <local-source-name>
1156
1157     <local-source-name> ::= L <source-name> <discriminator> */
1158
1159 static void
1160 write_unqualified_id (tree identifier)
1161 {
1162   if (IDENTIFIER_TYPENAME_P (identifier))
1163     write_conversion_operator_name (TREE_TYPE (identifier));
1164   else if (IDENTIFIER_OPNAME_P (identifier))
1165     {
1166       int i;
1167       const char *mangled_name = NULL;
1168
1169       /* Unfortunately, there is no easy way to go from the
1170          name of the operator back to the corresponding tree
1171          code.  */
1172       for (i = 0; i < MAX_TREE_CODES; ++i)
1173         if (operator_name_info[i].identifier == identifier)
1174           {
1175             /* The ABI says that we prefer binary operator
1176                names to unary operator names.  */
1177             if (operator_name_info[i].arity == 2)
1178               {
1179                 mangled_name = operator_name_info[i].mangled_name;
1180                 break;
1181               }
1182             else if (!mangled_name)
1183               mangled_name = operator_name_info[i].mangled_name;
1184           }
1185         else if (assignment_operator_name_info[i].identifier
1186                  == identifier)
1187           {
1188             mangled_name
1189               = assignment_operator_name_info[i].mangled_name;
1190             break;
1191           }
1192       write_string (mangled_name);
1193     }
1194   else if (UDLIT_OPER_P (identifier))
1195     write_literal_operator_name (identifier);
1196   else
1197     write_source_name (identifier);
1198 }
1199
1200 static void
1201 write_unqualified_name (const tree decl)
1202 {
1203   MANGLE_TRACE_TREE ("unqualified-name", decl);
1204
1205   if (identifier_p (decl))
1206     {
1207       write_unqualified_id (decl);
1208       return;
1209     }
1210
1211   bool found = false;
1212
1213   if (DECL_NAME (decl) == NULL_TREE)
1214     {
1215       found = true;
1216       gcc_assert (DECL_ASSEMBLER_NAME_SET_P (decl));
1217       write_source_name (DECL_ASSEMBLER_NAME (decl));
1218     }
1219   else if (DECL_DECLARES_FUNCTION_P (decl))
1220     {
1221       found = true;
1222       if (DECL_CONSTRUCTOR_P (decl))
1223         write_special_name_constructor (decl);
1224       else if (DECL_DESTRUCTOR_P (decl))
1225         write_special_name_destructor (decl);
1226       else if (DECL_CONV_FN_P (decl))
1227         {
1228           /* Conversion operator. Handle it right here.
1229              <operator> ::= cv <type>  */
1230           tree type;
1231           if (decl_is_template_id (decl, NULL))
1232             {
1233               tree fn_type;
1234               fn_type = get_mostly_instantiated_function_type (decl);
1235               type = TREE_TYPE (fn_type);
1236             }
1237           else
1238             type = DECL_CONV_FN_TYPE (decl);
1239           write_conversion_operator_name (type);
1240         }
1241       else if (DECL_OVERLOADED_OPERATOR_P (decl))
1242         {
1243           operator_name_info_t *oni;
1244           if (DECL_ASSIGNMENT_OPERATOR_P (decl))
1245             oni = assignment_operator_name_info;
1246           else
1247             oni = operator_name_info;
1248
1249           write_string (oni[DECL_OVERLOADED_OPERATOR_P (decl)].mangled_name);
1250         }
1251       else if (UDLIT_OPER_P (DECL_NAME (decl)))
1252         write_literal_operator_name (DECL_NAME (decl));
1253       else
1254         found = false;
1255     }
1256
1257   if (found)
1258     /* OK */;
1259   else if (VAR_OR_FUNCTION_DECL_P (decl) && ! TREE_PUBLIC (decl)
1260            && DECL_NAMESPACE_SCOPE_P (decl)
1261            && decl_linkage (decl) == lk_internal)
1262     {
1263       MANGLE_TRACE_TREE ("local-source-name", decl);
1264       write_char ('L');
1265       write_source_name (DECL_NAME (decl));
1266       /* The default discriminator is 1, and that's all we ever use,
1267          so there's no code to output one here.  */
1268     }
1269   else
1270     {
1271       tree type = TREE_TYPE (decl);
1272
1273       if (TREE_CODE (decl) == TYPE_DECL
1274           && TYPE_ANONYMOUS_P (type))
1275         write_unnamed_type_name (type);
1276       else if (TREE_CODE (decl) == TYPE_DECL
1277                && LAMBDA_TYPE_P (type))
1278         write_closure_type_name (type);
1279       else
1280         write_source_name (DECL_NAME (decl));
1281     }
1282
1283   tree attrs = (TREE_CODE (decl) == TYPE_DECL
1284                 ? TYPE_ATTRIBUTES (TREE_TYPE (decl))
1285                 : DECL_ATTRIBUTES (decl));
1286   write_abi_tags (lookup_attribute ("abi_tag", attrs));
1287 }
1288
1289 /* Write the unqualified-name for a conversion operator to TYPE.  */
1290
1291 static void
1292 write_conversion_operator_name (const tree type)
1293 {
1294   write_string ("cv");
1295   write_type (type);
1296 }
1297
1298 /* Non-terminal <source-name>.  IDENTIFIER is an IDENTIFIER_NODE.
1299
1300      <source-name> ::= </length/ number> <identifier>  */
1301
1302 static void
1303 write_source_name (tree identifier)
1304 {
1305   MANGLE_TRACE_TREE ("source-name", identifier);
1306
1307   /* Never write the whole template-id name including the template
1308      arguments; we only want the template name.  */
1309   if (IDENTIFIER_TEMPLATE (identifier))
1310     identifier = IDENTIFIER_TEMPLATE (identifier);
1311
1312   write_unsigned_number (IDENTIFIER_LENGTH (identifier));
1313   write_identifier (IDENTIFIER_POINTER (identifier));
1314 }
1315
1316 /* Compare two TREE_STRINGs like strcmp.  */
1317
1318 int
1319 tree_string_cmp (const void *p1, const void *p2)
1320 {
1321   if (p1 == p2)
1322     return 0;
1323   tree s1 = *(const tree*)p1;
1324   tree s2 = *(const tree*)p2;
1325   return strcmp (TREE_STRING_POINTER (s1),
1326                  TREE_STRING_POINTER (s2));
1327 }
1328
1329 /* ID is the name of a function or type with abi_tags attribute TAGS.
1330    Write out the name, suitably decorated.  */
1331
1332 static void
1333 write_abi_tags (tree tags)
1334 {
1335   if (tags == NULL_TREE)
1336     return;
1337
1338   tags = TREE_VALUE (tags);
1339
1340   vec<tree, va_gc> * vec = make_tree_vector();
1341
1342   for (tree t = tags; t; t = TREE_CHAIN (t))
1343     {
1344       tree str = TREE_VALUE (t);
1345       vec_safe_push (vec, str);
1346     }
1347
1348   vec->qsort (tree_string_cmp);
1349
1350   unsigned i; tree str;
1351   FOR_EACH_VEC_ELT (*vec, i, str)
1352     {
1353       write_string ("B");
1354       write_unsigned_number (TREE_STRING_LENGTH (str) - 1);
1355       write_identifier (TREE_STRING_POINTER (str));
1356     }
1357
1358   release_tree_vector (vec);
1359 }
1360
1361 /* Write a user-defined literal operator.
1362           ::= li <source-name>    # "" <source-name>
1363    IDENTIFIER is an LITERAL_IDENTIFIER_NODE.  */
1364
1365 static void
1366 write_literal_operator_name (tree identifier)
1367 {
1368   const char* suffix = UDLIT_OP_SUFFIX (identifier);
1369   write_identifier (UDLIT_OP_MANGLED_PREFIX);
1370   write_unsigned_number (strlen (suffix));
1371   write_identifier (suffix);
1372 }
1373
1374 /* Encode 0 as _, and 1+ as n-1_.  */
1375
1376 static void
1377 write_compact_number (int num)
1378 {
1379   if (num > 0)
1380     write_unsigned_number (num - 1);
1381   write_char ('_');
1382 }
1383
1384 /* Return how many unnamed types precede TYPE in its enclosing class.  */
1385
1386 static int
1387 nested_anon_class_index (tree type)
1388 {
1389   int index = 0;
1390   tree member = TYPE_FIELDS (TYPE_CONTEXT (type));
1391   for (; member; member = DECL_CHAIN (member))
1392     if (DECL_IMPLICIT_TYPEDEF_P (member))
1393       {
1394         tree memtype = TREE_TYPE (member);
1395         if (memtype == type)
1396           return index;
1397         else if (TYPE_ANONYMOUS_P (memtype))
1398           ++index;
1399       }
1400
1401   gcc_unreachable ();
1402 }
1403
1404 /* <unnamed-type-name> ::= Ut [ <nonnegative number> ] _ */
1405
1406 static void
1407 write_unnamed_type_name (const tree type)
1408 {
1409   int discriminator;
1410   MANGLE_TRACE_TREE ("unnamed-type-name", type);
1411
1412   if (TYPE_FUNCTION_SCOPE_P (type))
1413     discriminator = local_class_index (type);
1414   else if (TYPE_CLASS_SCOPE_P (type))
1415     discriminator = nested_anon_class_index (type);
1416   else
1417     {
1418       gcc_assert (no_linkage_check (type, /*relaxed_p=*/true));
1419       /* Just use the old mangling at namespace scope.  */
1420       write_source_name (TYPE_IDENTIFIER (type));
1421       return;
1422     }
1423
1424   write_string ("Ut");
1425   write_compact_number (discriminator);
1426 }
1427
1428 /* <closure-type-name> ::= Ul <lambda-sig> E [ <nonnegative number> ] _
1429    <lambda-sig> ::= <parameter type>+  # Parameter types or "v" if the lambda has no parameters */
1430
1431 static void
1432 write_closure_type_name (const tree type)
1433 {
1434   tree fn = lambda_function (type);
1435   tree lambda = CLASSTYPE_LAMBDA_EXPR (type);
1436   tree parms = TYPE_ARG_TYPES (TREE_TYPE (fn));
1437
1438   MANGLE_TRACE_TREE ("closure-type-name", type);
1439
1440   write_string ("Ul");
1441   write_method_parms (parms, /*method_p=*/1, fn);
1442   write_char ('E');
1443   write_compact_number (LAMBDA_EXPR_DISCRIMINATOR (lambda));
1444 }
1445
1446 /* Convert NUMBER to ascii using base BASE and generating at least
1447    MIN_DIGITS characters. BUFFER points to the _end_ of the buffer
1448    into which to store the characters. Returns the number of
1449    characters generated (these will be laid out in advance of where
1450    BUFFER points).  */
1451
1452 static int
1453 hwint_to_ascii (unsigned HOST_WIDE_INT number, const unsigned int base,
1454                 char *buffer, const unsigned int min_digits)
1455 {
1456   static const char base_digits[] = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ";
1457   unsigned digits = 0;
1458
1459   while (number)
1460     {
1461       unsigned HOST_WIDE_INT d = number / base;
1462
1463       *--buffer = base_digits[number - d * base];
1464       digits++;
1465       number = d;
1466     }
1467   while (digits < min_digits)
1468     {
1469       *--buffer = base_digits[0];
1470       digits++;
1471     }
1472   return digits;
1473 }
1474
1475 /* Non-terminal <number>.
1476
1477      <number> ::= [n] </decimal integer/>  */
1478
1479 static void
1480 write_number (unsigned HOST_WIDE_INT number, const int unsigned_p,
1481               const unsigned int base)
1482 {
1483   char buffer[sizeof (HOST_WIDE_INT) * 8];
1484   unsigned count = 0;
1485
1486   if (!unsigned_p && (HOST_WIDE_INT) number < 0)
1487     {
1488       write_char ('n');
1489       number = -((HOST_WIDE_INT) number);
1490     }
1491   count = hwint_to_ascii (number, base, buffer + sizeof (buffer), 1);
1492   write_chars (buffer + sizeof (buffer) - count, count);
1493 }
1494
1495 /* Write out an integral CST in decimal. Most numbers are small, and
1496    representable in a HOST_WIDE_INT. Occasionally we'll have numbers
1497    bigger than that, which we must deal with.  */
1498
1499 static inline void
1500 write_integer_cst (const tree cst)
1501 {
1502   int sign = tree_int_cst_sgn (cst);
1503
1504   if (TREE_INT_CST_HIGH (cst) + (sign < 0))
1505     {
1506       /* A bignum. We do this in chunks, each of which fits in a
1507          HOST_WIDE_INT.  */
1508       char buffer[sizeof (HOST_WIDE_INT) * 8 * 2];
1509       unsigned HOST_WIDE_INT chunk;
1510       unsigned chunk_digits;
1511       char *ptr = buffer + sizeof (buffer);
1512       unsigned count = 0;
1513       tree n, base, type;
1514       int done;
1515
1516       /* HOST_WIDE_INT must be at least 32 bits, so 10^9 is
1517          representable.  */
1518       chunk = 1000000000;
1519       chunk_digits = 9;
1520
1521       if (sizeof (HOST_WIDE_INT) >= 8)
1522         {
1523           /* It is at least 64 bits, so 10^18 is representable.  */
1524           chunk_digits = 18;
1525           chunk *= chunk;
1526         }
1527
1528       type = c_common_signed_or_unsigned_type (1, TREE_TYPE (cst));
1529       base = build_int_cstu (type, chunk);
1530       n = build_int_cst_wide (type,
1531                               TREE_INT_CST_LOW (cst), TREE_INT_CST_HIGH (cst));
1532
1533       if (sign < 0)
1534         {
1535           write_char ('n');
1536           n = fold_build1_loc (input_location, NEGATE_EXPR, type, n);
1537         }
1538       do
1539         {
1540           tree d = fold_build2_loc (input_location, FLOOR_DIV_EXPR, type, n, base);
1541           tree tmp = fold_build2_loc (input_location, MULT_EXPR, type, d, base);
1542           unsigned c;
1543
1544           done = integer_zerop (d);
1545           tmp = fold_build2_loc (input_location, MINUS_EXPR, type, n, tmp);
1546           c = hwint_to_ascii (TREE_INT_CST_LOW (tmp), 10, ptr,
1547                               done ? 1 : chunk_digits);
1548           ptr -= c;
1549           count += c;
1550           n = d;
1551         }
1552       while (!done);
1553       write_chars (ptr, count);
1554     }
1555   else
1556     {
1557       /* A small num.  */
1558       unsigned HOST_WIDE_INT low = TREE_INT_CST_LOW (cst);
1559
1560       if (sign < 0)
1561         {
1562           write_char ('n');
1563           low = -low;
1564         }
1565       write_unsigned_number (low);
1566     }
1567 }
1568
1569 /* Write out a floating-point literal.
1570
1571     "Floating-point literals are encoded using the bit pattern of the
1572     target processor's internal representation of that number, as a
1573     fixed-length lowercase hexadecimal string, high-order bytes first
1574     (even if the target processor would store low-order bytes first).
1575     The "n" prefix is not used for floating-point literals; the sign
1576     bit is encoded with the rest of the number.
1577
1578     Here are some examples, assuming the IEEE standard representation
1579     for floating point numbers.  (Spaces are for readability, not
1580     part of the encoding.)
1581
1582         1.0f                    Lf 3f80 0000 E
1583        -1.0f                    Lf bf80 0000 E
1584         1.17549435e-38f         Lf 0080 0000 E
1585         1.40129846e-45f         Lf 0000 0001 E
1586         0.0f                    Lf 0000 0000 E"
1587
1588    Caller is responsible for the Lx and the E.  */
1589 static void
1590 write_real_cst (const tree value)
1591 {
1592   if (abi_version_at_least (2))
1593     {
1594       long target_real[4];  /* largest supported float */
1595       char buffer[9];       /* eight hex digits in a 32-bit number */
1596       int i, limit, dir;
1597
1598       tree type = TREE_TYPE (value);
1599       int words = GET_MODE_BITSIZE (TYPE_MODE (type)) / 32;
1600
1601       real_to_target (target_real, &TREE_REAL_CST (value),
1602                       TYPE_MODE (type));
1603
1604       /* The value in target_real is in the target word order,
1605          so we must write it out backward if that happens to be
1606          little-endian.  write_number cannot be used, it will
1607          produce uppercase.  */
1608       if (FLOAT_WORDS_BIG_ENDIAN)
1609         i = 0, limit = words, dir = 1;
1610       else
1611         i = words - 1, limit = -1, dir = -1;
1612
1613       for (; i != limit; i += dir)
1614         {
1615           sprintf (buffer, "%08lx", (unsigned long) target_real[i]);
1616           write_chars (buffer, 8);
1617         }
1618     }
1619   else
1620     {
1621       /* In G++ 3.3 and before the REAL_VALUE_TYPE was written out
1622          literally.  Note that compatibility with 3.2 is impossible,
1623          because the old floating-point emulator used a different
1624          format for REAL_VALUE_TYPE.  */
1625       size_t i;
1626       for (i = 0; i < sizeof (TREE_REAL_CST (value)); ++i)
1627         write_number (((unsigned char *) &TREE_REAL_CST (value))[i],
1628                       /*unsigned_p*/ 1,
1629                       /*base*/ 16);
1630       G.need_abi_warning = 1;
1631     }
1632 }
1633
1634 /* Non-terminal <identifier>.
1635
1636      <identifier> ::= </unqualified source code identifier>  */
1637
1638 static void
1639 write_identifier (const char *identifier)
1640 {
1641   MANGLE_TRACE ("identifier", identifier);
1642   write_string (identifier);
1643 }
1644
1645 /* Handle constructor productions of non-terminal <special-name>.
1646    CTOR is a constructor FUNCTION_DECL.
1647
1648      <special-name> ::= C1   # complete object constructor
1649                     ::= C2   # base object constructor
1650                     ::= C3   # complete object allocating constructor
1651
1652    Currently, allocating constructors are never used.
1653
1654    We also need to provide mangled names for the maybe-in-charge
1655    constructor, so we treat it here too.  mangle_decl_string will
1656    append *INTERNAL* to that, to make sure we never emit it.  */
1657
1658 static void
1659 write_special_name_constructor (const tree ctor)
1660 {
1661   if (DECL_BASE_CONSTRUCTOR_P (ctor))
1662     write_string ("C2");
1663   else
1664     {
1665       gcc_assert (DECL_COMPLETE_CONSTRUCTOR_P (ctor)
1666                   /* Even though we don't ever emit a definition of
1667                      the old-style destructor, we still have to
1668                      consider entities (like static variables) nested
1669                      inside it.  */
1670                   || DECL_MAYBE_IN_CHARGE_CONSTRUCTOR_P (ctor));
1671       write_string ("C1");
1672     }
1673 }
1674
1675 /* Handle destructor productions of non-terminal <special-name>.
1676    DTOR is a destructor FUNCTION_DECL.
1677
1678      <special-name> ::= D0 # deleting (in-charge) destructor
1679                     ::= D1 # complete object (in-charge) destructor
1680                     ::= D2 # base object (not-in-charge) destructor
1681
1682    We also need to provide mangled names for the maybe-incharge
1683    destructor, so we treat it here too.  mangle_decl_string will
1684    append *INTERNAL* to that, to make sure we never emit it.  */
1685
1686 static void
1687 write_special_name_destructor (const tree dtor)
1688 {
1689   if (DECL_DELETING_DESTRUCTOR_P (dtor))
1690     write_string ("D0");
1691   else if (DECL_BASE_DESTRUCTOR_P (dtor))
1692     write_string ("D2");
1693   else
1694     {
1695       gcc_assert (DECL_COMPLETE_DESTRUCTOR_P (dtor)
1696                   /* Even though we don't ever emit a definition of
1697                      the old-style destructor, we still have to
1698                      consider entities (like static variables) nested
1699                      inside it.  */
1700                   || DECL_MAYBE_IN_CHARGE_DESTRUCTOR_P (dtor));
1701       write_string ("D1");
1702     }
1703 }
1704
1705 /* Scan the vector of local classes and return how many others with the
1706    same name (or same no name) and context precede ENTITY.  */
1707
1708 static int
1709 local_class_index (tree entity)
1710 {
1711   int ix, discriminator = 0;
1712   tree name = (TYPE_ANONYMOUS_P (entity) ? NULL_TREE
1713                : TYPE_IDENTIFIER (entity));
1714   tree ctx = TYPE_CONTEXT (entity);
1715   for (ix = 0; ; ix++)
1716     {
1717       tree type = (*local_classes)[ix];
1718       if (type == entity)
1719         return discriminator;
1720       if (TYPE_CONTEXT (type) == ctx
1721           && (name ? TYPE_IDENTIFIER (type) == name
1722               : TYPE_ANONYMOUS_P (type)))
1723         ++discriminator;
1724     }
1725   gcc_unreachable ();
1726 }
1727
1728 /* Return the discriminator for ENTITY appearing inside
1729    FUNCTION.  The discriminator is the lexical ordinal of VAR among
1730    entities with the same name in the same FUNCTION.  */
1731
1732 static int
1733 discriminator_for_local_entity (tree entity)
1734 {
1735   if (DECL_DISCRIMINATOR_P (entity))
1736     {
1737       if (DECL_DISCRIMINATOR_SET_P (entity))
1738         return DECL_DISCRIMINATOR (entity);
1739       else
1740         /* The first entity with a particular name doesn't get
1741            DECL_DISCRIMINATOR set up.  */
1742         return 0;
1743     }
1744   else if (TREE_CODE (entity) == TYPE_DECL)
1745     {
1746       /* Scan the list of local classes.  */
1747       entity = TREE_TYPE (entity);
1748
1749       /* Lambdas and unnamed types have their own discriminators.  */
1750       if (LAMBDA_TYPE_P (entity) || TYPE_ANONYMOUS_P (entity))
1751         return 0;
1752
1753       return local_class_index (entity);
1754     }
1755   else
1756     gcc_unreachable ();
1757 }
1758
1759 /* Return the discriminator for STRING, a string literal used inside
1760    FUNCTION.  The discriminator is the lexical ordinal of STRING among
1761    string literals used in FUNCTION.  */
1762
1763 static int
1764 discriminator_for_string_literal (tree /*function*/,
1765                                   tree /*string*/)
1766 {
1767   /* For now, we don't discriminate amongst string literals.  */
1768   return 0;
1769 }
1770
1771 /*   <discriminator> := _ <number>
1772
1773    The discriminator is used only for the second and later occurrences
1774    of the same name within a single function. In this case <number> is
1775    n - 2, if this is the nth occurrence, in lexical order.  */
1776
1777 static void
1778 write_discriminator (const int discriminator)
1779 {
1780   /* If discriminator is zero, don't write anything.  Otherwise...  */
1781   if (discriminator > 0)
1782     {
1783       write_char ('_');
1784       write_unsigned_number (discriminator - 1);
1785     }
1786 }
1787
1788 /* Mangle the name of a function-scope entity.  FUNCTION is the
1789    FUNCTION_DECL for the enclosing function, or a PARM_DECL for lambdas in
1790    default argument scope.  ENTITY is the decl for the entity itself.
1791    LOCAL_ENTITY is the entity that's directly scoped in FUNCTION_DECL,
1792    either ENTITY itself or an enclosing scope of ENTITY.
1793
1794      <local-name> := Z <function encoding> E <entity name> [<discriminator>]
1795                   := Z <function encoding> E s [<discriminator>]
1796                   := Z <function encoding> Ed [ <parameter number> ] _ <entity name> */
1797
1798 static void
1799 write_local_name (tree function, const tree local_entity,
1800                   const tree entity)
1801 {
1802   tree parm = NULL_TREE;
1803
1804   MANGLE_TRACE_TREE ("local-name", entity);
1805
1806   if (TREE_CODE (function) == PARM_DECL)
1807     {
1808       parm = function;
1809       function = DECL_CONTEXT (parm);
1810     }
1811
1812   write_char ('Z');
1813   write_encoding (function);
1814   write_char ('E');
1815
1816   /* For this purpose, parameters are numbered from right-to-left.  */
1817   if (parm)
1818     {
1819       tree t;
1820       int i = 0;
1821       for (t = DECL_ARGUMENTS (function); t; t = DECL_CHAIN (t))
1822         {
1823           if (t == parm)
1824             i = 1;
1825           else if (i)
1826             ++i;
1827         }
1828       write_char ('d');
1829       write_compact_number (i - 1);
1830     }
1831
1832   if (TREE_CODE (entity) == STRING_CST)
1833     {
1834       write_char ('s');
1835       write_discriminator (discriminator_for_string_literal (function,
1836                                                              entity));
1837     }
1838   else
1839     {
1840       /* Now the <entity name>.  Let write_name know its being called
1841          from <local-name>, so it doesn't try to process the enclosing
1842          function scope again.  */
1843       write_name (entity, /*ignore_local_scope=*/1);
1844       write_discriminator (discriminator_for_local_entity (local_entity));
1845     }
1846 }
1847
1848 /* Non-terminals <type> and <CV-qualifier>.
1849
1850      <type> ::= <builtin-type>
1851             ::= <function-type>
1852             ::= <class-enum-type>
1853             ::= <array-type>
1854             ::= <pointer-to-member-type>
1855             ::= <template-param>
1856             ::= <substitution>
1857             ::= <CV-qualifier>
1858             ::= P <type>    # pointer-to
1859             ::= R <type>    # reference-to
1860             ::= C <type>    # complex pair (C 2000)
1861             ::= G <type>    # imaginary (C 2000)     [not supported]
1862             ::= U <source-name> <type>   # vendor extended type qualifier
1863
1864    C++0x extensions
1865
1866      <type> ::= RR <type>   # rvalue reference-to
1867      <type> ::= Dt <expression> # decltype of an id-expression or
1868                                 # class member access
1869      <type> ::= DT <expression> # decltype of an expression
1870      <type> ::= Dn              # decltype of nullptr
1871
1872    TYPE is a type node.  */
1873
1874 static void
1875 write_type (tree type)
1876 {
1877   /* This gets set to nonzero if TYPE turns out to be a (possibly
1878      CV-qualified) builtin type.  */
1879   int is_builtin_type = 0;
1880
1881   MANGLE_TRACE_TREE ("type", type);
1882
1883   if (type == error_mark_node)
1884     return;
1885
1886   type = canonicalize_for_substitution (type);
1887   if (find_substitution (type))
1888     return;
1889
1890
1891   if (write_CV_qualifiers_for_type (type) > 0)
1892     /* If TYPE was CV-qualified, we just wrote the qualifiers; now
1893        mangle the unqualified type.  The recursive call is needed here
1894        since both the qualified and unqualified types are substitution
1895        candidates.  */
1896     {
1897       tree t = TYPE_MAIN_VARIANT (type);
1898       if (TREE_CODE (t) == FUNCTION_TYPE
1899           || TREE_CODE (t) == METHOD_TYPE)
1900         {
1901           t = build_ref_qualified_type (t, type_memfn_rqual (type));
1902           if (abi_version_at_least (8))
1903             /* Avoid adding the unqualified function type as a substitution.  */
1904             write_function_type (t);
1905           else
1906             write_type (t);
1907         }
1908       else
1909         write_type (t);
1910     }
1911   else if (TREE_CODE (type) == ARRAY_TYPE)
1912     /* It is important not to use the TYPE_MAIN_VARIANT of TYPE here
1913        so that the cv-qualification of the element type is available
1914        in write_array_type.  */
1915     write_array_type (type);
1916   else
1917     {
1918       tree type_orig = type;
1919
1920       /* See through any typedefs.  */
1921       type = TYPE_MAIN_VARIANT (type);
1922       if (TREE_CODE (type) == FUNCTION_TYPE
1923           || TREE_CODE (type) == METHOD_TYPE)
1924         type = build_ref_qualified_type (type, type_memfn_rqual (type_orig));
1925
1926       /* According to the C++ ABI, some library classes are passed the
1927          same as the scalar type of their single member and use the same
1928          mangling.  */
1929       if (TREE_CODE (type) == RECORD_TYPE && TYPE_TRANSPARENT_AGGR (type))
1930         type = TREE_TYPE (first_field (type));
1931
1932       if (TYPE_PTRDATAMEM_P (type))
1933         write_pointer_to_member_type (type);
1934       else
1935         {
1936           /* Handle any target-specific fundamental types.  */
1937           const char *target_mangling
1938             = targetm.mangle_type (type_orig);
1939
1940           if (target_mangling)
1941             {
1942               write_string (target_mangling);
1943               /* Add substitutions for types other than fundamental
1944                  types.  */
1945               if (!VOID_TYPE_P (type)
1946                   && TREE_CODE (type) != INTEGER_TYPE
1947                   && TREE_CODE (type) != REAL_TYPE
1948                   && TREE_CODE (type) != BOOLEAN_TYPE)
1949                 add_substitution (type);
1950               return;
1951             }
1952
1953           switch (TREE_CODE (type))
1954             {
1955             case VOID_TYPE:
1956             case BOOLEAN_TYPE:
1957             case INTEGER_TYPE:  /* Includes wchar_t.  */
1958             case REAL_TYPE:
1959             case FIXED_POINT_TYPE:
1960               {
1961                 /* If this is a typedef, TYPE may not be one of
1962                    the standard builtin type nodes, but an alias of one.  Use
1963                    TYPE_MAIN_VARIANT to get to the underlying builtin type.  */
1964                 write_builtin_type (TYPE_MAIN_VARIANT (type));
1965                 ++is_builtin_type;
1966               }
1967               break;
1968
1969             case COMPLEX_TYPE:
1970               write_char ('C');
1971               write_type (TREE_TYPE (type));
1972               break;
1973
1974             case FUNCTION_TYPE:
1975             case METHOD_TYPE:
1976               write_function_type (type);
1977               break;
1978
1979             case UNION_TYPE:
1980             case RECORD_TYPE:
1981             case ENUMERAL_TYPE:
1982               /* A pointer-to-member function is represented as a special
1983                  RECORD_TYPE, so check for this first.  */
1984               if (TYPE_PTRMEMFUNC_P (type))
1985                 write_pointer_to_member_type (type);
1986               else
1987                 write_class_enum_type (type);
1988               break;
1989
1990             case TYPENAME_TYPE:
1991             case UNBOUND_CLASS_TEMPLATE:
1992               /* We handle TYPENAME_TYPEs and UNBOUND_CLASS_TEMPLATEs like
1993                  ordinary nested names.  */
1994               write_nested_name (TYPE_STUB_DECL (type));
1995               break;
1996
1997             case POINTER_TYPE:
1998             case REFERENCE_TYPE:
1999               if (TYPE_PTR_P (type))
2000                 write_char ('P');
2001               else if (TYPE_REF_IS_RVALUE (type))
2002                 write_char ('O');
2003               else
2004                 write_char ('R');
2005               {
2006                 tree target = TREE_TYPE (type);
2007                 /* Attribute const/noreturn are not reflected in mangling.
2008                    We strip them here rather than at a lower level because
2009                    a typedef or template argument can have function type
2010                    with function-cv-quals (that use the same representation),
2011                    but you can't have a pointer/reference to such a type.  */
2012                 if (abi_version_at_least (5)
2013                     && TREE_CODE (target) == FUNCTION_TYPE)
2014                   target = build_qualified_type (target, TYPE_UNQUALIFIED);
2015                 write_type (target);
2016               }
2017               break;
2018
2019             case TEMPLATE_TYPE_PARM:
2020               if (is_auto (type))
2021                 {
2022                   if (AUTO_IS_DECLTYPE (type))
2023                     write_identifier ("Dc");
2024                   else
2025                     write_identifier ("Da");
2026                   ++is_builtin_type;
2027                   break;
2028                 }
2029               /* else fall through.  */
2030             case TEMPLATE_PARM_INDEX:
2031               write_template_param (type);
2032               break;
2033
2034             case TEMPLATE_TEMPLATE_PARM:
2035               write_template_template_param (type);
2036               break;
2037
2038             case BOUND_TEMPLATE_TEMPLATE_PARM:
2039               write_template_template_param (type);
2040               write_template_args
2041                 (TI_ARGS (TEMPLATE_TEMPLATE_PARM_TEMPLATE_INFO (type)));
2042               break;
2043
2044             case VECTOR_TYPE:
2045               if (abi_version_at_least (4))
2046                 {
2047                   write_string ("Dv");
2048                   /* Non-constant vector size would be encoded with
2049                      _ expression, but we don't support that yet.  */
2050                   write_unsigned_number (TYPE_VECTOR_SUBPARTS (type));
2051                   write_char ('_');
2052                 }
2053               else
2054                 {
2055                   G.need_abi_warning = 1;
2056                   write_string ("U8__vector");
2057                 }
2058               write_type (TREE_TYPE (type));
2059               break;
2060
2061             case TYPE_PACK_EXPANSION:
2062               write_string ("Dp");
2063               write_type (PACK_EXPANSION_PATTERN (type));
2064               break;
2065
2066             case DECLTYPE_TYPE:
2067               /* These shouldn't make it into mangling.  */
2068               gcc_assert (!DECLTYPE_FOR_LAMBDA_CAPTURE (type)
2069                           && !DECLTYPE_FOR_LAMBDA_PROXY (type));
2070
2071               /* In ABI <5, we stripped decltype of a plain decl.  */
2072               if (!abi_version_at_least (5)
2073                   && DECLTYPE_TYPE_ID_EXPR_OR_MEMBER_ACCESS_P (type))
2074                 {
2075                   tree expr = DECLTYPE_TYPE_EXPR (type);
2076                   tree etype = NULL_TREE;
2077                   switch (TREE_CODE (expr))
2078                     {
2079                     case VAR_DECL:
2080                     case PARM_DECL:
2081                     case RESULT_DECL:
2082                     case FUNCTION_DECL:
2083                     case CONST_DECL:
2084                     case TEMPLATE_PARM_INDEX:
2085                       etype = TREE_TYPE (expr);
2086                       break;
2087
2088                     default:
2089                       break;
2090                     }
2091
2092                   if (etype && !type_uses_auto (etype))
2093                     {
2094                       G.need_abi_warning = 1;
2095                       write_type (etype);
2096                       return;
2097                     }
2098                 }
2099
2100               write_char ('D');
2101               if (DECLTYPE_TYPE_ID_EXPR_OR_MEMBER_ACCESS_P (type))
2102                 write_char ('t');
2103               else
2104                 write_char ('T');
2105               ++cp_unevaluated_operand;
2106               write_expression (DECLTYPE_TYPE_EXPR (type));
2107               --cp_unevaluated_operand;
2108               write_char ('E');
2109               break;
2110
2111             case NULLPTR_TYPE:
2112               write_string ("Dn");
2113               if (abi_version_at_least (7))
2114                 ++is_builtin_type;
2115               break;
2116
2117             case TYPEOF_TYPE:
2118               sorry ("mangling typeof, use decltype instead");
2119               break;
2120
2121             case UNDERLYING_TYPE:
2122               sorry ("mangling __underlying_type");
2123               break;
2124
2125             case LANG_TYPE:
2126               /* fall through.  */
2127
2128             default:
2129               gcc_unreachable ();
2130             }
2131         }
2132     }
2133
2134   /* Types other than builtin types are substitution candidates.  */
2135   if (!is_builtin_type)
2136     add_substitution (type);
2137 }
2138
2139 /* Non-terminal <CV-qualifiers> for type nodes.  Returns the number of
2140    CV-qualifiers written for TYPE.
2141
2142      <CV-qualifiers> ::= [r] [V] [K]  */
2143
2144 static int
2145 write_CV_qualifiers_for_type (const tree type)
2146 {
2147   int num_qualifiers = 0;
2148
2149   /* The order is specified by:
2150
2151        "In cases where multiple order-insensitive qualifiers are
2152        present, they should be ordered 'K' (closest to the base type),
2153        'V', 'r', and 'U' (farthest from the base type) ..."
2154
2155      Note that we do not use cp_type_quals below; given "const
2156      int[3]", the "const" is emitted with the "int", not with the
2157      array.  */
2158   cp_cv_quals quals = TYPE_QUALS (type);
2159
2160   if (quals & TYPE_QUAL_RESTRICT)
2161     {
2162       write_char ('r');
2163       ++num_qualifiers;
2164     }
2165   if (quals & TYPE_QUAL_VOLATILE)
2166     {
2167       write_char ('V');
2168       ++num_qualifiers;
2169     }
2170   if (quals & TYPE_QUAL_CONST)
2171     {
2172       write_char ('K');
2173       ++num_qualifiers;
2174     }
2175
2176   return num_qualifiers;
2177 }
2178
2179 /* Non-terminal <builtin-type>.
2180
2181      <builtin-type> ::= v   # void
2182                     ::= b   # bool
2183                     ::= w   # wchar_t
2184                     ::= c   # char
2185                     ::= a   # signed char
2186                     ::= h   # unsigned char
2187                     ::= s   # short
2188                     ::= t   # unsigned short
2189                     ::= i   # int
2190                     ::= j   # unsigned int
2191                     ::= l   # long
2192                     ::= m   # unsigned long
2193                     ::= x   # long long, __int64
2194                     ::= y   # unsigned long long, __int64
2195                     ::= n   # __int128
2196                     ::= o   # unsigned __int128
2197                     ::= f   # float
2198                     ::= d   # double
2199                     ::= e   # long double, __float80
2200                     ::= g   # __float128          [not supported]
2201                     ::= u <source-name>  # vendor extended type */
2202
2203 static void
2204 write_builtin_type (tree type)
2205 {
2206   if (TYPE_CANONICAL (type))
2207     type = TYPE_CANONICAL (type);
2208
2209   switch (TREE_CODE (type))
2210     {
2211     case VOID_TYPE:
2212       write_char ('v');
2213       break;
2214
2215     case BOOLEAN_TYPE:
2216       write_char ('b');
2217       break;
2218
2219     case INTEGER_TYPE:
2220       /* TYPE may still be wchar_t, char16_t, or char32_t, since that
2221          isn't in integer_type_nodes.  */
2222       if (type == wchar_type_node)
2223         write_char ('w');
2224       else if (type == char16_type_node)
2225         write_string ("Ds");
2226       else if (type == char32_type_node)
2227         write_string ("Di");
2228       else if (TYPE_FOR_JAVA (type))
2229         write_java_integer_type_codes (type);
2230       else
2231         {
2232           size_t itk;
2233           /* Assume TYPE is one of the shared integer type nodes.  Find
2234              it in the array of these nodes.  */
2235         iagain:
2236           for (itk = 0; itk < itk_none; ++itk)
2237             if (integer_types[itk] != NULL_TREE
2238                 && type == integer_types[itk])
2239               {
2240                 /* Print the corresponding single-letter code.  */
2241                 write_char (integer_type_codes[itk]);
2242                 break;
2243               }
2244
2245           if (itk == itk_none)
2246             {
2247               tree t = c_common_type_for_mode (TYPE_MODE (type),
2248                                                TYPE_UNSIGNED (type));
2249               if (type != t)
2250                 {
2251                   type = t;
2252                   goto iagain;
2253                 }
2254
2255               if (TYPE_PRECISION (type) == 128)
2256                 write_char (TYPE_UNSIGNED (type) ? 'o' : 'n');
2257               else
2258                 {
2259                   /* Allow for cases where TYPE is not one of the shared
2260                      integer type nodes and write a "vendor extended builtin
2261                      type" with a name the form intN or uintN, respectively.
2262                      Situations like this can happen if you have an
2263                      __attribute__((__mode__(__SI__))) type and use exotic
2264                      switches like '-mint8' on AVR.  Of course, this is
2265                      undefined by the C++ ABI (and '-mint8' is not even
2266                      Standard C conforming), but when using such special
2267                      options you're pretty much in nowhere land anyway.  */
2268                   const char *prefix;
2269                   char prec[11];        /* up to ten digits for an unsigned */
2270
2271                   prefix = TYPE_UNSIGNED (type) ? "uint" : "int";
2272                   sprintf (prec, "%u", (unsigned) TYPE_PRECISION (type));
2273                   write_char ('u');     /* "vendor extended builtin type" */
2274                   write_unsigned_number (strlen (prefix) + strlen (prec));
2275                   write_string (prefix);
2276                   write_string (prec);
2277                 }
2278             }
2279         }
2280       break;
2281
2282     case REAL_TYPE:
2283       if (type == float_type_node
2284           || type == java_float_type_node)
2285         write_char ('f');
2286       else if (type == double_type_node
2287                || type == java_double_type_node)
2288         write_char ('d');
2289       else if (type == long_double_type_node)
2290         write_char ('e');
2291       else if (type == dfloat32_type_node)
2292         write_string ("Df");
2293       else if (type == dfloat64_type_node)
2294         write_string ("Dd");
2295       else if (type == dfloat128_type_node)
2296         write_string ("De");
2297       else
2298         gcc_unreachable ();
2299       break;
2300
2301     case FIXED_POINT_TYPE:
2302       write_string ("DF");
2303       if (GET_MODE_IBIT (TYPE_MODE (type)) > 0)
2304         write_unsigned_number (GET_MODE_IBIT (TYPE_MODE (type)));
2305       if (type == fract_type_node
2306           || type == sat_fract_type_node
2307           || type == accum_type_node
2308           || type == sat_accum_type_node)
2309         write_char ('i');
2310       else if (type == unsigned_fract_type_node
2311                || type == sat_unsigned_fract_type_node
2312                || type == unsigned_accum_type_node
2313                || type == sat_unsigned_accum_type_node)
2314         write_char ('j');
2315       else if (type == short_fract_type_node
2316                || type == sat_short_fract_type_node
2317                || type == short_accum_type_node
2318                || type == sat_short_accum_type_node)
2319         write_char ('s');
2320       else if (type == unsigned_short_fract_type_node
2321                || type == sat_unsigned_short_fract_type_node
2322                || type == unsigned_short_accum_type_node
2323                || type == sat_unsigned_short_accum_type_node)
2324         write_char ('t');
2325       else if (type == long_fract_type_node
2326                || type == sat_long_fract_type_node
2327                || type == long_accum_type_node
2328                || type == sat_long_accum_type_node)
2329         write_char ('l');
2330       else if (type == unsigned_long_fract_type_node
2331                || type == sat_unsigned_long_fract_type_node
2332                || type == unsigned_long_accum_type_node
2333                || type == sat_unsigned_long_accum_type_node)
2334         write_char ('m');
2335       else if (type == long_long_fract_type_node
2336                || type == sat_long_long_fract_type_node
2337                || type == long_long_accum_type_node
2338                || type == sat_long_long_accum_type_node)
2339         write_char ('x');
2340       else if (type == unsigned_long_long_fract_type_node
2341                || type == sat_unsigned_long_long_fract_type_node
2342                || type == unsigned_long_long_accum_type_node
2343                || type == sat_unsigned_long_long_accum_type_node)
2344         write_char ('y');
2345       else
2346         sorry ("mangling unknown fixed point type");
2347       write_unsigned_number (GET_MODE_FBIT (TYPE_MODE (type)));
2348       if (TYPE_SATURATING (type))
2349         write_char ('s');
2350       else
2351         write_char ('n');
2352       break;
2353
2354     default:
2355       gcc_unreachable ();
2356     }
2357 }
2358
2359 /* Non-terminal <function-type>.  NODE is a FUNCTION_TYPE or
2360    METHOD_TYPE.  The return type is mangled before the parameter
2361    types.
2362
2363      <function-type> ::= F [Y] <bare-function-type> [<ref-qualifier>] E   */
2364
2365 static void
2366 write_function_type (const tree type)
2367 {
2368   MANGLE_TRACE_TREE ("function-type", type);
2369
2370   /* For a pointer to member function, the function type may have
2371      cv-qualifiers, indicating the quals for the artificial 'this'
2372      parameter.  */
2373   if (TREE_CODE (type) == METHOD_TYPE)
2374     {
2375       /* The first parameter must be a POINTER_TYPE pointing to the
2376          `this' parameter.  */
2377       tree this_type = class_of_this_parm (type);
2378       write_CV_qualifiers_for_type (this_type);
2379     }
2380
2381   write_char ('F');
2382   /* We don't track whether or not a type is `extern "C"'.  Note that
2383      you can have an `extern "C"' function that does not have
2384      `extern "C"' type, and vice versa:
2385
2386        extern "C" typedef void function_t();
2387        function_t f; // f has C++ linkage, but its type is
2388                      // `extern "C"'
2389
2390        typedef void function_t();
2391        extern "C" function_t f; // Vice versa.
2392
2393      See [dcl.link].  */
2394   write_bare_function_type (type, /*include_return_type_p=*/1,
2395                             /*decl=*/NULL);
2396   if (FUNCTION_REF_QUALIFIED (type))
2397     {
2398       if (FUNCTION_RVALUE_QUALIFIED (type))
2399         write_char ('O');
2400       else
2401         write_char ('R');
2402     }
2403   write_char ('E');
2404 }
2405
2406 /* Non-terminal <bare-function-type>.  TYPE is a FUNCTION_TYPE or
2407    METHOD_TYPE.  If INCLUDE_RETURN_TYPE is nonzero, the return value
2408    is mangled before the parameter types.  If non-NULL, DECL is
2409    FUNCTION_DECL for the function whose type is being emitted.
2410
2411    If DECL is a member of a Java type, then a literal 'J'
2412    is output and the return type is mangled as if INCLUDE_RETURN_TYPE
2413    were nonzero.
2414
2415      <bare-function-type> ::= [J]</signature/ type>+  */
2416
2417 static void
2418 write_bare_function_type (const tree type, const int include_return_type_p,
2419                           const tree decl)
2420 {
2421   int java_method_p;
2422
2423   MANGLE_TRACE_TREE ("bare-function-type", type);
2424
2425   /* Detect Java methods and emit special encoding.  */
2426   if (decl != NULL
2427       && DECL_FUNCTION_MEMBER_P (decl)
2428       && TYPE_FOR_JAVA (DECL_CONTEXT (decl))
2429       && !DECL_CONSTRUCTOR_P (decl)
2430       && !DECL_DESTRUCTOR_P (decl)
2431       && !DECL_CONV_FN_P (decl))
2432     {
2433       java_method_p = 1;
2434       write_char ('J');
2435     }
2436   else
2437     {
2438       java_method_p = 0;
2439     }
2440
2441   /* Mangle the return type, if requested.  */
2442   if (include_return_type_p || java_method_p)
2443     write_type (TREE_TYPE (type));
2444
2445   /* Now mangle the types of the arguments.  */
2446   ++G.parm_depth;
2447   write_method_parms (TYPE_ARG_TYPES (type),
2448                       TREE_CODE (type) == METHOD_TYPE,
2449                       decl);
2450   --G.parm_depth;
2451 }
2452
2453 /* Write the mangled representation of a method parameter list of
2454    types given in PARM_TYPES.  If METHOD_P is nonzero, the function is
2455    considered a non-static method, and the this parameter is omitted.
2456    If non-NULL, DECL is the FUNCTION_DECL for the function whose
2457    parameters are being emitted.  */
2458
2459 static void
2460 write_method_parms (tree parm_types, const int method_p, const tree decl)
2461 {
2462   tree first_parm_type;
2463   tree parm_decl = decl ? DECL_ARGUMENTS (decl) : NULL_TREE;
2464
2465   /* Assume this parameter type list is variable-length.  If it ends
2466      with a void type, then it's not.  */
2467   int varargs_p = 1;
2468
2469   /* If this is a member function, skip the first arg, which is the
2470      this pointer.
2471        "Member functions do not encode the type of their implicit this
2472        parameter."
2473
2474      Similarly, there's no need to mangle artificial parameters, like
2475      the VTT parameters for constructors and destructors.  */
2476   if (method_p)
2477     {
2478       parm_types = TREE_CHAIN (parm_types);
2479       parm_decl = parm_decl ? DECL_CHAIN (parm_decl) : NULL_TREE;
2480
2481       while (parm_decl && DECL_ARTIFICIAL (parm_decl))
2482         {
2483           parm_types = TREE_CHAIN (parm_types);
2484           parm_decl = DECL_CHAIN (parm_decl);
2485         }
2486     }
2487
2488   for (first_parm_type = parm_types;
2489        parm_types;
2490        parm_types = TREE_CHAIN (parm_types))
2491     {
2492       tree parm = TREE_VALUE (parm_types);
2493       if (parm == void_type_node)
2494         {
2495           /* "Empty parameter lists, whether declared as () or
2496              conventionally as (void), are encoded with a void parameter
2497              (v)."  */
2498           if (parm_types == first_parm_type)
2499             write_type (parm);
2500           /* If the parm list is terminated with a void type, it's
2501              fixed-length.  */
2502           varargs_p = 0;
2503           /* A void type better be the last one.  */
2504           gcc_assert (TREE_CHAIN (parm_types) == NULL);
2505         }
2506       else
2507         write_type (parm);
2508     }
2509
2510   if (varargs_p)
2511     /* <builtin-type> ::= z  # ellipsis  */
2512     write_char ('z');
2513 }
2514
2515 /* <class-enum-type> ::= <name>  */
2516
2517 static void
2518 write_class_enum_type (const tree type)
2519 {
2520   write_name (TYPE_NAME (type), /*ignore_local_scope=*/0);
2521 }
2522
2523 /* Non-terminal <template-args>.  ARGS is a TREE_VEC of template
2524    arguments.
2525
2526      <template-args> ::= I <template-arg>* E  */
2527
2528 static void
2529 write_template_args (tree args)
2530 {
2531   int i;
2532   int length = 0;
2533
2534   MANGLE_TRACE_TREE ("template-args", args);
2535
2536   write_char ('I');
2537
2538   if (args)
2539     length = TREE_VEC_LENGTH (args);
2540
2541   if (args && TREE_CODE (TREE_VEC_ELT (args, 0)) == TREE_VEC)
2542     {
2543       /* We have nested template args.  We want the innermost template
2544          argument list.  */
2545       args = TREE_VEC_ELT (args, length - 1);
2546       length = TREE_VEC_LENGTH (args);
2547     }
2548   for (i = 0; i < length; ++i)
2549     write_template_arg (TREE_VEC_ELT (args, i));
2550
2551   write_char ('E');
2552 }
2553
2554 /* Write out the
2555    <unqualified-name>
2556    <unqualified-name> <template-args>
2557    part of SCOPE_REF or COMPONENT_REF mangling.  */
2558
2559 static void
2560 write_member_name (tree member)
2561 {
2562   if (identifier_p (member))
2563     write_unqualified_id (member);
2564   else if (DECL_P (member))
2565     write_unqualified_name (member);
2566   else if (TREE_CODE (member) == TEMPLATE_ID_EXPR)
2567     {
2568       tree name = TREE_OPERAND (member, 0);
2569       if (TREE_CODE (name) == OVERLOAD)
2570         name = OVL_FUNCTION (name);
2571       write_member_name (name);
2572       write_template_args (TREE_OPERAND (member, 1));
2573     }
2574   else
2575     write_expression (member);
2576 }
2577
2578 /* <expression> ::= <unary operator-name> <expression>
2579                 ::= <binary operator-name> <expression> <expression>
2580                 ::= <expr-primary>
2581
2582    <expr-primary> ::= <template-param>
2583                   ::= L <type> <value number> E         # literal
2584                   ::= L <mangled-name> E                # external name
2585                   ::= st <type>                         # sizeof
2586                   ::= sr <type> <unqualified-name>      # dependent name
2587                   ::= sr <type> <unqualified-name> <template-args> */
2588
2589 static void
2590 write_expression (tree expr)
2591 {
2592   enum tree_code code = TREE_CODE (expr);
2593
2594   /* Skip NOP_EXPRs.  They can occur when (say) a pointer argument
2595      is converted (via qualification conversions) to another
2596      type.  */
2597   while (TREE_CODE (expr) == NOP_EXPR
2598          /* Parentheses aren't mangled.  */
2599          || code == PAREN_EXPR
2600          || TREE_CODE (expr) == NON_LVALUE_EXPR)
2601     {
2602       expr = TREE_OPERAND (expr, 0);
2603       code = TREE_CODE (expr);
2604     }
2605
2606   if (code == BASELINK
2607       && (!type_unknown_p (expr)
2608           || !BASELINK_QUALIFIED_P (expr)))
2609     {
2610       expr = BASELINK_FUNCTIONS (expr);
2611       code = TREE_CODE (expr);
2612     }
2613
2614   /* Handle pointers-to-members by making them look like expression
2615      nodes.  */
2616   if (code == PTRMEM_CST)
2617     {
2618       expr = build_nt (ADDR_EXPR,
2619                        build_qualified_name (/*type=*/NULL_TREE,
2620                                              PTRMEM_CST_CLASS (expr),
2621                                              PTRMEM_CST_MEMBER (expr),
2622                                              /*template_p=*/false));
2623       code = TREE_CODE (expr);
2624     }
2625
2626   /* Handle template parameters.  */
2627   if (code == TEMPLATE_TYPE_PARM
2628       || code == TEMPLATE_TEMPLATE_PARM
2629       || code == BOUND_TEMPLATE_TEMPLATE_PARM
2630       || code == TEMPLATE_PARM_INDEX)
2631     write_template_param (expr);
2632   /* Handle literals.  */
2633   else if (TREE_CODE_CLASS (code) == tcc_constant
2634            || (abi_version_at_least (2) && code == CONST_DECL))
2635     write_template_arg_literal (expr);
2636   else if (code == PARM_DECL && DECL_ARTIFICIAL (expr))
2637     {
2638       gcc_assert (!strcmp ("this", IDENTIFIER_POINTER (DECL_NAME (expr))));
2639       write_string ("fpT");
2640     }
2641   else if (code == PARM_DECL)
2642     {
2643       /* A function parameter used in a late-specified return type.  */
2644       int index = DECL_PARM_INDEX (expr);
2645       int level = DECL_PARM_LEVEL (expr);
2646       int delta = G.parm_depth - level + 1;
2647       gcc_assert (index >= 1);
2648       write_char ('f');
2649       if (delta != 0)
2650         {
2651           if (abi_version_at_least (5))
2652             {
2653               /* Let L be the number of function prototype scopes from the
2654                  innermost one (in which the parameter reference occurs) up
2655                  to (and including) the one containing the declaration of
2656                  the referenced parameter.  If the parameter declaration
2657                  clause of the innermost function prototype scope has been
2658                  completely seen, it is not counted (in that case -- which
2659                  is perhaps the most common -- L can be zero).  */
2660               write_char ('L');
2661               write_unsigned_number (delta - 1);
2662             }
2663           else
2664             G.need_abi_warning = true;
2665         }
2666       write_char ('p');
2667       write_compact_number (index - 1);
2668     }
2669   else if (DECL_P (expr))
2670     {
2671       /* G++ 3.2 incorrectly mangled non-type template arguments of
2672          enumeration type using their names.  */
2673       if (code == CONST_DECL)
2674         G.need_abi_warning = 1;
2675       write_char ('L');
2676       write_mangled_name (expr, false);
2677       write_char ('E');
2678     }
2679   else if (TREE_CODE (expr) == SIZEOF_EXPR
2680            && SIZEOF_EXPR_TYPE_P (expr))
2681     {
2682       write_string ("st");
2683       write_type (TREE_TYPE (TREE_OPERAND (expr, 0)));
2684     }
2685   else if (TREE_CODE (expr) == SIZEOF_EXPR
2686            && TYPE_P (TREE_OPERAND (expr, 0)))
2687     {
2688       write_string ("st");
2689       write_type (TREE_OPERAND (expr, 0));
2690     }
2691   else if (TREE_CODE (expr) == ALIGNOF_EXPR
2692            && TYPE_P (TREE_OPERAND (expr, 0)))
2693     {
2694       write_string ("at");
2695       write_type (TREE_OPERAND (expr, 0));
2696     }
2697   else if (code == SCOPE_REF
2698            || code == BASELINK)
2699     {
2700       tree scope, member;
2701       if (code == SCOPE_REF)
2702         {
2703           scope = TREE_OPERAND (expr, 0);
2704           member = TREE_OPERAND (expr, 1);
2705         }
2706       else
2707         {
2708           scope = BINFO_TYPE (BASELINK_ACCESS_BINFO (expr));
2709           member = BASELINK_FUNCTIONS (expr);
2710         }
2711
2712       if (!abi_version_at_least (2) && DECL_P (member))
2713         {
2714           write_string ("sr");
2715           write_type (scope);
2716           /* G++ 3.2 incorrectly put out both the "sr" code and
2717              the nested name of the qualified name.  */
2718           G.need_abi_warning = 1;
2719           write_encoding (member);
2720         }
2721
2722       /* If the MEMBER is a real declaration, then the qualifying
2723          scope was not dependent.  Ideally, we would not have a
2724          SCOPE_REF in those cases, but sometimes we do.  If the second
2725          argument is a DECL, then the name must not have been
2726          dependent.  */
2727       else if (DECL_P (member))
2728         write_expression (member);
2729       else
2730         {
2731           write_string ("sr");
2732           write_type (scope);
2733           write_member_name (member);
2734         }
2735     }
2736   else if (INDIRECT_REF_P (expr)
2737            && TREE_TYPE (TREE_OPERAND (expr, 0))
2738            && TREE_CODE (TREE_TYPE (TREE_OPERAND (expr, 0))) == REFERENCE_TYPE)
2739     {
2740       write_expression (TREE_OPERAND (expr, 0));
2741     }
2742   else if (identifier_p (expr))
2743     {
2744       /* An operator name appearing as a dependent name needs to be
2745          specially marked to disambiguate between a use of the operator
2746          name and a use of the operator in an expression.  */
2747       if (IDENTIFIER_OPNAME_P (expr))
2748         write_string ("on");
2749       write_unqualified_id (expr);
2750     }
2751   else if (TREE_CODE (expr) == TEMPLATE_ID_EXPR)
2752     {
2753       tree fn = TREE_OPERAND (expr, 0);
2754       if (is_overloaded_fn (fn))
2755         fn = DECL_NAME (get_first_fn (fn));
2756       if (IDENTIFIER_OPNAME_P (fn))
2757         write_string ("on");
2758       write_unqualified_id (fn);
2759       write_template_args (TREE_OPERAND (expr, 1));
2760     }
2761   else if (TREE_CODE (expr) == MODOP_EXPR)
2762     {
2763       enum tree_code subop = TREE_CODE (TREE_OPERAND (expr, 1));
2764       const char *name = (assignment_operator_name_info[(int) subop]
2765                           .mangled_name);
2766       write_string (name);
2767       write_expression (TREE_OPERAND (expr, 0));
2768       write_expression (TREE_OPERAND (expr, 2));
2769     }
2770   else if (code == NEW_EXPR || code == VEC_NEW_EXPR)
2771     {
2772       /* ::= [gs] nw <expression>* _ <type> E
2773          ::= [gs] nw <expression>* _ <type> <initializer>
2774          ::= [gs] na <expression>* _ <type> E
2775          ::= [gs] na <expression>* _ <type> <initializer>
2776          <initializer> ::= pi <expression>* E  */
2777       tree placement = TREE_OPERAND (expr, 0);
2778       tree type = TREE_OPERAND (expr, 1);
2779       tree nelts = TREE_OPERAND (expr, 2);
2780       tree init = TREE_OPERAND (expr, 3);
2781       tree t;
2782
2783       gcc_assert (code == NEW_EXPR);
2784       if (TREE_OPERAND (expr, 2))
2785         code = VEC_NEW_EXPR;
2786
2787       if (NEW_EXPR_USE_GLOBAL (expr))
2788         write_string ("gs");
2789
2790       write_string (operator_name_info[(int) code].mangled_name);
2791
2792       for (t = placement; t; t = TREE_CHAIN (t))
2793         write_expression (TREE_VALUE (t));
2794
2795       write_char ('_');
2796
2797       if (nelts)
2798         {
2799           tree domain;
2800           ++processing_template_decl;
2801           domain = compute_array_index_type (NULL_TREE, nelts,
2802                                              tf_warning_or_error);
2803           type = build_cplus_array_type (type, domain);
2804           --processing_template_decl;
2805         }
2806       write_type (type);
2807
2808       if (init && TREE_CODE (init) == TREE_LIST
2809           && TREE_CODE (TREE_VALUE (init)) == CONSTRUCTOR
2810           && CONSTRUCTOR_IS_DIRECT_INIT (TREE_VALUE (init)))
2811         write_expression (TREE_VALUE (init));
2812       else
2813         {
2814           if (init)
2815             write_string ("pi");
2816           if (init && init != void_zero_node)
2817             for (t = init; t; t = TREE_CHAIN (t))
2818               write_expression (TREE_VALUE (t));
2819           write_char ('E');
2820         }
2821     }
2822   else if (code == DELETE_EXPR || code == VEC_DELETE_EXPR)
2823     {
2824       gcc_assert (code == DELETE_EXPR);
2825       if (DELETE_EXPR_USE_VEC (expr))
2826         code = VEC_DELETE_EXPR;
2827
2828       if (DELETE_EXPR_USE_GLOBAL (expr))
2829         write_string ("gs");
2830
2831       write_string (operator_name_info[(int) code].mangled_name);
2832
2833       write_expression (TREE_OPERAND (expr, 0));
2834     }
2835   else if (code == THROW_EXPR)
2836     {
2837       tree op = TREE_OPERAND (expr, 0);
2838       if (op)
2839         {
2840           write_string ("tw");
2841           write_expression (op);
2842         }
2843       else
2844         write_string ("tr");
2845     }
2846   else if (code == CONSTRUCTOR)
2847     {
2848       vec<constructor_elt, va_gc> *elts = CONSTRUCTOR_ELTS (expr);
2849       unsigned i; tree val;
2850
2851       if (BRACE_ENCLOSED_INITIALIZER_P (expr))
2852         write_string ("il");
2853       else
2854         {
2855           write_string ("tl");
2856           write_type (TREE_TYPE (expr));
2857         }
2858       FOR_EACH_CONSTRUCTOR_VALUE (elts, i, val)
2859         write_expression (val);
2860       write_char ('E');
2861     }
2862   else if (dependent_name (expr))
2863     {
2864       write_unqualified_id (dependent_name (expr));
2865     }
2866   else
2867     {
2868       int i, len;
2869       const char *name;
2870
2871       /* When we bind a variable or function to a non-type template
2872          argument with reference type, we create an ADDR_EXPR to show
2873          the fact that the entity's address has been taken.  But, we
2874          don't actually want to output a mangling code for the `&'.  */
2875       if (TREE_CODE (expr) == ADDR_EXPR
2876           && TREE_TYPE (expr)
2877           && TREE_CODE (TREE_TYPE (expr)) == REFERENCE_TYPE)
2878         {
2879           expr = TREE_OPERAND (expr, 0);
2880           if (DECL_P (expr))
2881             {
2882               write_expression (expr);
2883               return;
2884             }
2885
2886           code = TREE_CODE (expr);
2887         }
2888
2889       if (code == COMPONENT_REF)
2890         {
2891           tree ob = TREE_OPERAND (expr, 0);
2892
2893           if (TREE_CODE (ob) == ARROW_EXPR)
2894             {
2895               write_string (operator_name_info[(int)code].mangled_name);
2896               ob = TREE_OPERAND (ob, 0);
2897             }
2898           else
2899             write_string ("dt");
2900
2901           write_expression (ob);
2902           write_member_name (TREE_OPERAND (expr, 1));
2903           return;
2904         }
2905
2906       /* If it wasn't any of those, recursively expand the expression.  */
2907       name = operator_name_info[(int) code].mangled_name;
2908
2909       /* We used to mangle const_cast and static_cast like a C cast.  */
2910       if (!abi_version_at_least (6)
2911           && (code == CONST_CAST_EXPR
2912               || code == STATIC_CAST_EXPR))
2913         {
2914           name = operator_name_info[CAST_EXPR].mangled_name;
2915           G.need_abi_warning = 1;
2916         }
2917
2918       if (name == NULL)
2919         {
2920           switch (code)
2921             {
2922             case TRAIT_EXPR:
2923               error ("use of built-in trait %qE in function signature; "
2924                      "use library traits instead", expr);
2925               break;
2926
2927             default:
2928               sorry ("mangling %C", code);
2929               break;
2930             }
2931           return;
2932         }
2933       else
2934         write_string (name);
2935
2936       switch (code)
2937         {
2938         case CALL_EXPR:
2939           {
2940             tree fn = CALL_EXPR_FN (expr);
2941
2942             if (TREE_CODE (fn) == ADDR_EXPR)
2943               fn = TREE_OPERAND (fn, 0);
2944
2945             /* Mangle a dependent name as the name, not whatever happens to
2946                be the first function in the overload set.  */
2947             if ((TREE_CODE (fn) == FUNCTION_DECL
2948                  || TREE_CODE (fn) == OVERLOAD)
2949                 && type_dependent_expression_p_push (expr))
2950               fn = DECL_NAME (get_first_fn (fn));
2951
2952             write_expression (fn);
2953           }
2954
2955           for (i = 0; i < call_expr_nargs (expr); ++i)
2956             write_expression (CALL_EXPR_ARG (expr, i));
2957           write_char ('E');
2958           break;
2959
2960         case CAST_EXPR:
2961           write_type (TREE_TYPE (expr));
2962           if (list_length (TREE_OPERAND (expr, 0)) == 1)
2963             write_expression (TREE_VALUE (TREE_OPERAND (expr, 0)));
2964           else
2965             {
2966               tree args = TREE_OPERAND (expr, 0);
2967               write_char ('_');
2968               for (; args; args = TREE_CHAIN (args))
2969                 write_expression (TREE_VALUE (args));
2970               write_char ('E');
2971             }
2972           break;
2973
2974         case DYNAMIC_CAST_EXPR:
2975         case REINTERPRET_CAST_EXPR:
2976         case STATIC_CAST_EXPR:
2977         case CONST_CAST_EXPR:
2978           write_type (TREE_TYPE (expr));
2979           write_expression (TREE_OPERAND (expr, 0));
2980           break;
2981
2982         case PREINCREMENT_EXPR:
2983         case PREDECREMENT_EXPR:
2984           if (abi_version_at_least (6))
2985             write_char ('_');
2986           else
2987             G.need_abi_warning = 1;
2988           /* Fall through.  */
2989
2990         default:
2991           /* In the middle-end, some expressions have more operands than
2992              they do in templates (and mangling).  */
2993           len = cp_tree_operand_length (expr);
2994
2995           for (i = 0; i < len; ++i)
2996             {
2997               tree operand = TREE_OPERAND (expr, i);
2998               /* As a GNU extension, the middle operand of a
2999                  conditional may be omitted.  Since expression
3000                  manglings are supposed to represent the input token
3001                  stream, there's no good way to mangle such an
3002                  expression without extending the C++ ABI.  */
3003               if (code == COND_EXPR && i == 1 && !operand)
3004                 {
3005                   error ("omitted middle operand to %<?:%> operand "
3006                          "cannot be mangled");
3007                   continue;
3008                 }
3009               write_expression (operand);
3010             }
3011         }
3012     }
3013 }
3014
3015 /* Literal subcase of non-terminal <template-arg>.
3016
3017      "Literal arguments, e.g. "A<42L>", are encoded with their type
3018      and value. Negative integer values are preceded with "n"; for
3019      example, "A<-42L>" becomes "1AILln42EE". The bool value false is
3020      encoded as 0, true as 1."  */
3021
3022 static void
3023 write_template_arg_literal (const tree value)
3024 {
3025   write_char ('L');
3026   write_type (TREE_TYPE (value));
3027
3028   /* Write a null member pointer value as (type)0, regardless of its
3029      real representation.  */
3030   if (null_member_pointer_value_p (value))
3031     write_integer_cst (integer_zero_node);
3032   else
3033     switch (TREE_CODE (value))
3034       {
3035       case CONST_DECL:
3036         write_integer_cst (DECL_INITIAL (value));
3037         break;
3038
3039       case INTEGER_CST:
3040         gcc_assert (!same_type_p (TREE_TYPE (value), boolean_type_node)
3041                     || integer_zerop (value) || integer_onep (value));
3042         write_integer_cst (value);
3043         break;
3044
3045       case REAL_CST:
3046         write_real_cst (value);
3047         break;
3048
3049       case COMPLEX_CST:
3050         if (TREE_CODE (TREE_REALPART (value)) == INTEGER_CST
3051             && TREE_CODE (TREE_IMAGPART (value)) == INTEGER_CST)
3052           {
3053             write_integer_cst (TREE_REALPART (value));
3054             write_char ('_');
3055             write_integer_cst (TREE_IMAGPART (value));
3056           }
3057         else if (TREE_CODE (TREE_REALPART (value)) == REAL_CST
3058                  && TREE_CODE (TREE_IMAGPART (value)) == REAL_CST)
3059           {
3060             write_real_cst (TREE_REALPART (value));
3061             write_char ('_');
3062             write_real_cst (TREE_IMAGPART (value));
3063           }
3064         else
3065           gcc_unreachable ();
3066         break;
3067
3068       case STRING_CST:
3069         sorry ("string literal in function template signature");
3070         break;
3071
3072       default:
3073         gcc_unreachable ();
3074       }
3075
3076   write_char ('E');
3077 }
3078
3079 /* Non-terminal <template-arg>.
3080
3081      <template-arg> ::= <type>                          # type
3082                     ::= L <type> </value/ number> E     # literal
3083                     ::= LZ <name> E                     # external name
3084                     ::= X <expression> E                # expression  */
3085
3086 static void
3087 write_template_arg (tree node)
3088 {
3089   enum tree_code code = TREE_CODE (node);
3090
3091   MANGLE_TRACE_TREE ("template-arg", node);
3092
3093   /* A template template parameter's argument list contains TREE_LIST
3094      nodes of which the value field is the actual argument.  */
3095   if (code == TREE_LIST)
3096     {
3097       node = TREE_VALUE (node);
3098       /* If it's a decl, deal with its type instead.  */
3099       if (DECL_P (node))
3100         {
3101           node = TREE_TYPE (node);
3102           code = TREE_CODE (node);
3103         }
3104     }
3105
3106   if (TREE_CODE (node) == NOP_EXPR
3107       && TREE_CODE (TREE_TYPE (node)) == REFERENCE_TYPE)
3108     {
3109       /* Template parameters can be of reference type. To maintain
3110          internal consistency, such arguments use a conversion from
3111          address of object to reference type.  */
3112       gcc_assert (TREE_CODE (TREE_OPERAND (node, 0)) == ADDR_EXPR);
3113       if (abi_version_at_least (2))
3114         node = TREE_OPERAND (TREE_OPERAND (node, 0), 0);
3115       else
3116         G.need_abi_warning = 1;
3117     }
3118
3119   if (TREE_CODE (node) == BASELINK
3120       && !type_unknown_p (node))
3121     {
3122       if (abi_version_at_least (6))
3123         node = BASELINK_FUNCTIONS (node);
3124       else
3125         /* We wrongly wrapped a class-scope function in X/E.  */
3126         G.need_abi_warning = 1;
3127     }
3128
3129   if (ARGUMENT_PACK_P (node))
3130     {
3131       /* Expand the template argument pack. */
3132       tree args = ARGUMENT_PACK_ARGS (node);
3133       int i, length = TREE_VEC_LENGTH (args);
3134       if (abi_version_at_least (6))
3135         write_char ('J');
3136       else
3137         {
3138           write_char ('I');
3139           G.need_abi_warning = 1;
3140         }
3141       for (i = 0; i < length; ++i)
3142         write_template_arg (TREE_VEC_ELT (args, i));
3143       write_char ('E');
3144     }
3145   else if (TYPE_P (node))
3146     write_type (node);
3147   else if (code == TEMPLATE_DECL)
3148     /* A template appearing as a template arg is a template template arg.  */
3149     write_template_template_arg (node);
3150   else if ((TREE_CODE_CLASS (code) == tcc_constant && code != PTRMEM_CST)
3151            || (abi_version_at_least (2) && code == CONST_DECL)
3152            || null_member_pointer_value_p (node))
3153     write_template_arg_literal (node);
3154   else if (DECL_P (node))
3155     {
3156       /* Until ABI version 2, non-type template arguments of
3157          enumeration type were mangled using their names.  */
3158       if (code == CONST_DECL && !abi_version_at_least (2))
3159         G.need_abi_warning = 1;
3160       write_char ('L');
3161       /* Until ABI version 3, the underscore before the mangled name
3162          was incorrectly omitted.  */
3163       if (!abi_version_at_least (3))
3164         {
3165           G.need_abi_warning = 1;
3166           write_char ('Z');
3167         }
3168       else
3169         write_string ("_Z");
3170       write_encoding (node);
3171       write_char ('E');
3172     }
3173   else
3174     {
3175       /* Template arguments may be expressions.  */
3176       write_char ('X');
3177       write_expression (node);
3178       write_char ('E');
3179     }
3180 }
3181
3182 /*  <template-template-arg>
3183                         ::= <name>
3184                         ::= <substitution>  */
3185
3186 static void
3187 write_template_template_arg (const tree decl)
3188 {
3189   MANGLE_TRACE_TREE ("template-template-arg", decl);
3190
3191   if (find_substitution (decl))
3192     return;
3193   write_name (decl, /*ignore_local_scope=*/0);
3194   add_substitution (decl);
3195 }
3196
3197
3198 /* Non-terminal <array-type>.  TYPE is an ARRAY_TYPE.
3199
3200      <array-type> ::= A [</dimension/ number>] _ </element/ type>
3201                   ::= A <expression> _ </element/ type>
3202
3203      "Array types encode the dimension (number of elements) and the
3204      element type. For variable length arrays, the dimension (but not
3205      the '_' separator) is omitted."  */
3206
3207 static void
3208 write_array_type (const tree type)
3209 {
3210   write_char ('A');
3211   if (TYPE_DOMAIN (type))
3212     {
3213       tree index_type;
3214       tree max;
3215
3216       index_type = TYPE_DOMAIN (type);
3217       /* The INDEX_TYPE gives the upper and lower bounds of the
3218          array.  */
3219       max = TYPE_MAX_VALUE (index_type);
3220       if (TREE_CODE (max) == INTEGER_CST)
3221         {
3222           /* The ABI specifies that we should mangle the number of
3223              elements in the array, not the largest allowed index.  */
3224           double_int dmax = tree_to_double_int (max) + double_int_one;
3225           /* Truncate the result - this will mangle [0, SIZE_INT_MAX]
3226              number of elements as zero.  */
3227           dmax = dmax.zext (TYPE_PRECISION (TREE_TYPE (max)));
3228           gcc_assert (dmax.fits_uhwi ());
3229           write_unsigned_number (dmax.low);
3230         }
3231       else
3232         {
3233           max = TREE_OPERAND (max, 0);
3234           if (!abi_version_at_least (2))
3235             {
3236               /* value_dependent_expression_p presumes nothing is
3237                  dependent when PROCESSING_TEMPLATE_DECL is zero.  */
3238               ++processing_template_decl;
3239               if (!value_dependent_expression_p (max))
3240                 G.need_abi_warning = 1;
3241               --processing_template_decl;
3242             }
3243           write_expression (max);
3244         }
3245
3246     }
3247   write_char ('_');
3248   write_type (TREE_TYPE (type));
3249 }
3250
3251 /* Non-terminal <pointer-to-member-type> for pointer-to-member
3252    variables.  TYPE is a pointer-to-member POINTER_TYPE.
3253
3254      <pointer-to-member-type> ::= M </class/ type> </member/ type>  */
3255
3256 static void
3257 write_pointer_to_member_type (const tree type)
3258 {
3259   write_char ('M');
3260   write_type (TYPE_PTRMEM_CLASS_TYPE (type));
3261   write_type (TYPE_PTRMEM_POINTED_TO_TYPE (type));
3262 }
3263
3264 /* Non-terminal <template-param>.  PARM is a TEMPLATE_TYPE_PARM,
3265    TEMPLATE_TEMPLATE_PARM, BOUND_TEMPLATE_TEMPLATE_PARM or a
3266    TEMPLATE_PARM_INDEX.
3267
3268      <template-param> ::= T </parameter/ number> _  */
3269
3270 static void
3271 write_template_param (const tree parm)
3272 {
3273   int parm_index;
3274
3275   MANGLE_TRACE_TREE ("template-parm", parm);
3276
3277   switch (TREE_CODE (parm))
3278     {
3279     case TEMPLATE_TYPE_PARM:
3280     case TEMPLATE_TEMPLATE_PARM:
3281     case BOUND_TEMPLATE_TEMPLATE_PARM:
3282       parm_index = TEMPLATE_TYPE_IDX (parm);
3283       break;
3284
3285     case TEMPLATE_PARM_INDEX:
3286       parm_index = TEMPLATE_PARM_IDX (parm);
3287       break;
3288
3289     default:
3290       gcc_unreachable ();
3291     }
3292
3293   write_char ('T');
3294   /* NUMBER as it appears in the mangling is (-1)-indexed, with the
3295      earliest template param denoted by `_'.  */
3296   write_compact_number (parm_index);
3297 }
3298
3299 /*  <template-template-param>
3300                         ::= <template-param>
3301                         ::= <substitution>  */
3302
3303 static void
3304 write_template_template_param (const tree parm)
3305 {
3306   tree templ = NULL_TREE;
3307
3308   /* PARM, a TEMPLATE_TEMPLATE_PARM, is an instantiation of the
3309      template template parameter.  The substitution candidate here is
3310      only the template.  */
3311   if (TREE_CODE (parm) == BOUND_TEMPLATE_TEMPLATE_PARM)
3312     {
3313       templ
3314         = TI_TEMPLATE (TEMPLATE_TEMPLATE_PARM_TEMPLATE_INFO (parm));
3315       if (find_substitution (templ))
3316         return;
3317     }
3318
3319   /* <template-param> encodes only the template parameter position,
3320      not its template arguments, which is fine here.  */
3321   write_template_param (parm);
3322   if (templ)
3323     add_substitution (templ);
3324 }
3325
3326 /* Non-terminal <substitution>.
3327
3328       <substitution> ::= S <seq-id> _
3329                      ::= S_  */
3330
3331 static void
3332 write_substitution (const int seq_id)
3333 {
3334   MANGLE_TRACE ("substitution", "");
3335
3336   write_char ('S');
3337   if (seq_id > 0)
3338     write_number (seq_id - 1, /*unsigned=*/1, 36);
3339   write_char ('_');
3340 }
3341
3342 /* Start mangling ENTITY.  */
3343
3344 static inline void
3345 start_mangling (const tree entity)
3346 {
3347   G.entity = entity;
3348   G.need_abi_warning = false;
3349   obstack_free (&name_obstack, name_base);
3350   mangle_obstack = &name_obstack;
3351   name_base = obstack_alloc (&name_obstack, 0);
3352 }
3353
3354 /* Done with mangling. If WARN is true, and the name of G.entity will
3355    be mangled differently in a future version of the ABI, issue a
3356    warning.  */
3357
3358 static void
3359 finish_mangling_internal (const bool warn)
3360 {
3361   if (warn_abi && warn && G.need_abi_warning)
3362     warning (OPT_Wabi, "the mangled name of %qD will change in a future "
3363              "version of GCC",
3364              G.entity);
3365
3366   /* Clear all the substitutions.  */
3367   vec_safe_truncate (G.substitutions, 0);
3368
3369   /* Null-terminate the string.  */
3370   write_char ('\0');
3371 }
3372
3373
3374 /* Like finish_mangling_internal, but return the mangled string.  */
3375
3376 static inline const char *
3377 finish_mangling (const bool warn)
3378 {
3379   finish_mangling_internal (warn);
3380   return (const char *) obstack_finish (mangle_obstack);
3381 }
3382
3383 /* Like finish_mangling_internal, but return an identifier.  */
3384
3385 static tree
3386 finish_mangling_get_identifier (const bool warn)
3387 {
3388   finish_mangling_internal (warn);
3389   /* Don't obstack_finish here, and the next start_mangling will
3390      remove the identifier.  */
3391   return get_identifier ((const char *) obstack_base (mangle_obstack));
3392 }
3393
3394 /* Initialize data structures for mangling.  */
3395
3396 void
3397 init_mangle (void)
3398 {
3399   gcc_obstack_init (&name_obstack);
3400   name_base = obstack_alloc (&name_obstack, 0);
3401   vec_alloc (G.substitutions, 0);
3402
3403   /* Cache these identifiers for quick comparison when checking for
3404      standard substitutions.  */
3405   subst_identifiers[SUBID_ALLOCATOR] = get_identifier ("allocator");
3406   subst_identifiers[SUBID_BASIC_STRING] = get_identifier ("basic_string");
3407   subst_identifiers[SUBID_CHAR_TRAITS] = get_identifier ("char_traits");
3408   subst_identifiers[SUBID_BASIC_ISTREAM] = get_identifier ("basic_istream");
3409   subst_identifiers[SUBID_BASIC_OSTREAM] = get_identifier ("basic_ostream");
3410   subst_identifiers[SUBID_BASIC_IOSTREAM] = get_identifier ("basic_iostream");
3411 }
3412
3413 /* Generate the mangled name of DECL.  */
3414
3415 static tree
3416 mangle_decl_string (const tree decl)
3417 {
3418   tree result;
3419   location_t saved_loc = input_location;
3420   tree saved_fn = NULL_TREE;
3421   bool template_p = false;
3422
3423   /* We shouldn't be trying to mangle an uninstantiated template.  */
3424   gcc_assert (!type_dependent_expression_p (decl));
3425
3426   if (DECL_LANG_SPECIFIC (decl) && DECL_USE_TEMPLATE (decl))
3427     {
3428       struct tinst_level *tl = current_instantiation ();
3429       if ((!tl || tl->decl != decl)
3430           && push_tinst_level (decl))
3431         {
3432           template_p = true;
3433           saved_fn = current_function_decl;
3434           current_function_decl = NULL_TREE;
3435         }
3436     }
3437   input_location = DECL_SOURCE_LOCATION (decl);
3438
3439   start_mangling (decl);
3440
3441   if (TREE_CODE (decl) == TYPE_DECL)
3442     write_type (TREE_TYPE (decl));
3443   else
3444     write_mangled_name (decl, true);
3445
3446   result = finish_mangling_get_identifier (/*warn=*/true);
3447   if (DEBUG_MANGLE)
3448     fprintf (stderr, "mangle_decl_string = '%s'\n\n",
3449              IDENTIFIER_POINTER (result));
3450
3451   if (template_p)
3452     {
3453       pop_tinst_level ();
3454       current_function_decl = saved_fn;
3455     }
3456   input_location = saved_loc;
3457
3458   return result;
3459 }
3460
3461 /* Return an identifier for the external mangled name of DECL.  */
3462
3463 static tree
3464 get_mangled_id (tree decl)
3465 {
3466   tree id = mangle_decl_string (decl);
3467   return targetm.mangle_decl_assembler_name (decl, id);
3468 }
3469
3470 /* Create an identifier for the external mangled name of DECL.  */
3471
3472 void
3473 mangle_decl (const tree decl)
3474 {
3475   tree id;
3476   bool dep;
3477
3478   /* Don't bother mangling uninstantiated templates.  */
3479   ++processing_template_decl;
3480   if (TREE_CODE (decl) == TYPE_DECL)
3481     dep = dependent_type_p (TREE_TYPE (decl));
3482   else
3483     dep = (DECL_LANG_SPECIFIC (decl) && DECL_TEMPLATE_INFO (decl)
3484            && any_dependent_template_arguments_p (DECL_TI_ARGS (decl)));
3485   --processing_template_decl;
3486   if (dep)
3487     return;
3488
3489   id = get_mangled_id (decl);
3490   SET_DECL_ASSEMBLER_NAME (decl, id);
3491
3492   if (G.need_abi_warning
3493       /* Don't do this for a fake symbol we aren't going to emit anyway.  */
3494       && !DECL_MAYBE_IN_CHARGE_CONSTRUCTOR_P (decl)
3495       && !DECL_MAYBE_IN_CHARGE_DESTRUCTOR_P (decl))
3496     {
3497 #ifdef ASM_OUTPUT_DEF
3498       /* If the mangling will change in the future, emit an alias with the
3499          future mangled name for forward-compatibility.  */
3500       int save_ver;
3501       tree id2, alias;
3502 #endif
3503
3504       SET_IDENTIFIER_GLOBAL_VALUE (id, decl);
3505       if (IDENTIFIER_GLOBAL_VALUE (id) != decl)
3506         inform (DECL_SOURCE_LOCATION (decl), "-fabi-version=6 (or =0) "
3507                 "avoids this error with a change in mangling");
3508
3509 #ifdef ASM_OUTPUT_DEF
3510       save_ver = flag_abi_version;
3511       flag_abi_version = 0;
3512       id2 = mangle_decl_string (decl);
3513       id2 = targetm.mangle_decl_assembler_name (decl, id2);
3514       flag_abi_version = save_ver;
3515
3516       alias = make_alias_for (decl, id2);
3517       DECL_IGNORED_P (alias) = 1;
3518       TREE_PUBLIC (alias) = TREE_PUBLIC (decl);
3519       DECL_VISIBILITY (alias) = DECL_VISIBILITY (decl);
3520       if (vague_linkage_p (decl))
3521         DECL_WEAK (alias) = 1;
3522       if (TREE_CODE (decl) == FUNCTION_DECL)
3523         cgraph_same_body_alias (cgraph_get_create_node (decl), alias, decl);
3524       else
3525         varpool_extra_name_alias (alias, decl);
3526 #endif
3527     }
3528 }
3529
3530 /* Generate the mangled representation of TYPE.  */
3531
3532 const char *
3533 mangle_type_string (const tree type)
3534 {
3535   const char *result;
3536
3537   start_mangling (type);
3538   write_type (type);
3539   result = finish_mangling (/*warn=*/false);
3540   if (DEBUG_MANGLE)
3541     fprintf (stderr, "mangle_type_string = '%s'\n\n", result);
3542   return result;
3543 }
3544
3545 /* Create an identifier for the mangled name of a special component
3546    for belonging to TYPE.  CODE is the ABI-specified code for this
3547    component.  */
3548
3549 static tree
3550 mangle_special_for_type (const tree type, const char *code)
3551 {
3552   tree result;
3553
3554   /* We don't have an actual decl here for the special component, so
3555      we can't just process the <encoded-name>.  Instead, fake it.  */
3556   start_mangling (type);
3557
3558   /* Start the mangling.  */
3559   write_string ("_Z");
3560   write_string (code);
3561
3562   /* Add the type.  */
3563   write_type (type);
3564   result = finish_mangling_get_identifier (/*warn=*/false);
3565
3566   if (DEBUG_MANGLE)
3567     fprintf (stderr, "mangle_special_for_type = %s\n\n",
3568              IDENTIFIER_POINTER (result));
3569
3570   return result;
3571 }
3572
3573 /* Create an identifier for the mangled representation of the typeinfo
3574    structure for TYPE.  */
3575
3576 tree
3577 mangle_typeinfo_for_type (const tree type)
3578 {
3579   return mangle_special_for_type (type, "TI");
3580 }
3581
3582 /* Create an identifier for the mangled name of the NTBS containing
3583    the mangled name of TYPE.  */
3584
3585 tree
3586 mangle_typeinfo_string_for_type (const tree type)
3587 {
3588   return mangle_special_for_type (type, "TS");
3589 }
3590
3591 /* Create an identifier for the mangled name of the vtable for TYPE.  */
3592
3593 tree
3594 mangle_vtbl_for_type (const tree type)
3595 {
3596   return mangle_special_for_type (type, "TV");
3597 }
3598
3599 /* Returns an identifier for the mangled name of the VTT for TYPE.  */
3600
3601 tree
3602 mangle_vtt_for_type (const tree type)
3603 {
3604   return mangle_special_for_type (type, "TT");
3605 }
3606
3607 /* Return an identifier for a construction vtable group.  TYPE is
3608    the most derived class in the hierarchy; BINFO is the base
3609    subobject for which this construction vtable group will be used.
3610
3611    This mangling isn't part of the ABI specification; in the ABI
3612    specification, the vtable group is dumped in the same COMDAT as the
3613    main vtable, and is referenced only from that vtable, so it doesn't
3614    need an external name.  For binary formats without COMDAT sections,
3615    though, we need external names for the vtable groups.
3616
3617    We use the production
3618
3619     <special-name> ::= CT <type> <offset number> _ <base type>  */
3620
3621 tree
3622 mangle_ctor_vtbl_for_type (const tree type, const tree binfo)
3623 {
3624   tree result;
3625
3626   start_mangling (type);
3627
3628   write_string ("_Z");
3629   write_string ("TC");
3630   write_type (type);
3631   write_integer_cst (BINFO_OFFSET (binfo));
3632   write_char ('_');
3633   write_type (BINFO_TYPE (binfo));
3634
3635   result = finish_mangling_get_identifier (/*warn=*/false);
3636   if (DEBUG_MANGLE)
3637     fprintf (stderr, "mangle_ctor_vtbl_for_type = %s\n\n",
3638              IDENTIFIER_POINTER (result));
3639   return result;
3640 }
3641
3642 /* Mangle a this pointer or result pointer adjustment.
3643
3644    <call-offset> ::= h <fixed offset number> _
3645                  ::= v <fixed offset number> _ <virtual offset number> _ */
3646
3647 static void
3648 mangle_call_offset (const tree fixed_offset, const tree virtual_offset)
3649 {
3650   write_char (virtual_offset ? 'v' : 'h');
3651
3652   /* For either flavor, write the fixed offset.  */
3653   write_integer_cst (fixed_offset);
3654   write_char ('_');
3655
3656   /* For a virtual thunk, add the virtual offset.  */
3657   if (virtual_offset)
3658     {
3659       write_integer_cst (virtual_offset);
3660       write_char ('_');
3661     }
3662 }
3663
3664 /* Return an identifier for the mangled name of a this-adjusting or
3665    covariant thunk to FN_DECL.  FIXED_OFFSET is the initial adjustment
3666    to this used to find the vptr.  If VIRTUAL_OFFSET is non-NULL, this
3667    is a virtual thunk, and it is the vtbl offset in
3668    bytes. THIS_ADJUSTING is nonzero for a this adjusting thunk and
3669    zero for a covariant thunk. Note, that FN_DECL might be a covariant
3670    thunk itself. A covariant thunk name always includes the adjustment
3671    for the this pointer, even if there is none.
3672
3673    <special-name> ::= T <call-offset> <base encoding>
3674                   ::= Tc <this_adjust call-offset> <result_adjust call-offset>
3675                                         <base encoding>  */
3676
3677 tree
3678 mangle_thunk (tree fn_decl, const int this_adjusting, tree fixed_offset,
3679               tree virtual_offset)
3680 {
3681   tree result;
3682
3683   start_mangling (fn_decl);
3684
3685   write_string ("_Z");
3686   write_char ('T');
3687
3688   if (!this_adjusting)
3689     {
3690       /* Covariant thunk with no this adjustment */
3691       write_char ('c');
3692       mangle_call_offset (integer_zero_node, NULL_TREE);
3693       mangle_call_offset (fixed_offset, virtual_offset);
3694     }
3695   else if (!DECL_THUNK_P (fn_decl))
3696     /* Plain this adjusting thunk.  */
3697     mangle_call_offset (fixed_offset, virtual_offset);
3698   else
3699     {
3700       /* This adjusting thunk to covariant thunk.  */
3701       write_char ('c');
3702       mangle_call_offset (fixed_offset, virtual_offset);
3703       fixed_offset = ssize_int (THUNK_FIXED_OFFSET (fn_decl));
3704       virtual_offset = THUNK_VIRTUAL_OFFSET (fn_decl);
3705       if (virtual_offset)
3706         virtual_offset = BINFO_VPTR_FIELD (virtual_offset);
3707       mangle_call_offset (fixed_offset, virtual_offset);
3708       fn_decl = THUNK_TARGET (fn_decl);
3709     }
3710
3711   /* Scoped name.  */
3712   write_encoding (fn_decl);
3713
3714   result = finish_mangling_get_identifier (/*warn=*/false);
3715   if (DEBUG_MANGLE)
3716     fprintf (stderr, "mangle_thunk = %s\n\n", IDENTIFIER_POINTER (result));
3717   return result;
3718 }
3719
3720 /* This hash table maps TYPEs to the IDENTIFIER for a conversion
3721    operator to TYPE.  The nodes are IDENTIFIERs whose TREE_TYPE is the
3722    TYPE.  */
3723
3724 static GTY ((param_is (union tree_node))) htab_t conv_type_names;
3725
3726 /* Hash a node (VAL1) in the table.  */
3727
3728 static hashval_t
3729 hash_type (const void *val)
3730 {
3731   return (hashval_t) TYPE_UID (TREE_TYPE ((const_tree) val));
3732 }
3733
3734 /* Compare VAL1 (a node in the table) with VAL2 (a TYPE).  */
3735
3736 static int
3737 compare_type (const void *val1, const void *val2)
3738 {
3739   return TREE_TYPE ((const_tree) val1) == (const_tree) val2;
3740 }
3741
3742 /* Return an identifier for the mangled unqualified name for a
3743    conversion operator to TYPE.  This mangling is not specified by the
3744    ABI spec; it is only used internally.  */
3745
3746 tree
3747 mangle_conv_op_name_for_type (const tree type)
3748 {
3749   void **slot;
3750   tree identifier;
3751
3752   if (type == error_mark_node)
3753     return error_mark_node;
3754
3755   if (conv_type_names == NULL)
3756     conv_type_names = htab_create_ggc (31, &hash_type, &compare_type, NULL);
3757
3758   slot = htab_find_slot_with_hash (conv_type_names, type,
3759                                    (hashval_t) TYPE_UID (type), INSERT);
3760   identifier = (tree)*slot;
3761   if (!identifier)
3762     {
3763       char buffer[64];
3764
3765        /* Create a unique name corresponding to TYPE.  */
3766       sprintf (buffer, "operator %lu",
3767                (unsigned long) htab_elements (conv_type_names));
3768       identifier = get_identifier (buffer);
3769       *slot = identifier;
3770
3771       /* Hang TYPE off the identifier so it can be found easily later
3772          when performing conversions.  */
3773       TREE_TYPE (identifier) = type;
3774
3775       /* Set bits on the identifier so we know later it's a conversion.  */
3776       IDENTIFIER_OPNAME_P (identifier) = 1;
3777       IDENTIFIER_TYPENAME_P (identifier) = 1;
3778     }
3779
3780   return identifier;
3781 }
3782
3783 /* Write out the appropriate string for this variable when generating
3784    another mangled name based on this one.  */
3785
3786 static void
3787 write_guarded_var_name (const tree variable)
3788 {
3789   if (strncmp (IDENTIFIER_POINTER (DECL_NAME (variable)), "_ZGR", 4) == 0)
3790     /* The name of a guard variable for a reference temporary should refer
3791        to the reference, not the temporary.  */
3792     write_string (IDENTIFIER_POINTER (DECL_NAME (variable)) + 4);
3793   else
3794     write_name (variable, /*ignore_local_scope=*/0);
3795 }
3796
3797 /* Return an identifier for the name of an initialization guard
3798    variable for indicated VARIABLE.  */
3799
3800 tree
3801 mangle_guard_variable (const tree variable)
3802 {
3803   start_mangling (variable);
3804   write_string ("_ZGV");
3805   write_guarded_var_name (variable);
3806   return finish_mangling_get_identifier (/*warn=*/false);
3807 }
3808
3809 /* Return an identifier for the name of a thread_local initialization
3810    function for VARIABLE.  */
3811
3812 tree
3813 mangle_tls_init_fn (const tree variable)
3814 {
3815   start_mangling (variable);
3816   write_string ("_ZTH");
3817   write_guarded_var_name (variable);
3818   return finish_mangling_get_identifier (/*warn=*/false);
3819 }
3820
3821 /* Return an identifier for the name of a thread_local wrapper
3822    function for VARIABLE.  */
3823
3824 #define TLS_WRAPPER_PREFIX "_ZTW"
3825
3826 tree
3827 mangle_tls_wrapper_fn (const tree variable)
3828 {
3829   start_mangling (variable);
3830   write_string (TLS_WRAPPER_PREFIX);
3831   write_guarded_var_name (variable);
3832   return finish_mangling_get_identifier (/*warn=*/false);
3833 }
3834
3835 /* Return true iff FN is a thread_local wrapper function.  */
3836
3837 bool
3838 decl_tls_wrapper_p (const tree fn)
3839 {
3840   if (TREE_CODE (fn) != FUNCTION_DECL)
3841     return false;
3842   tree name = DECL_NAME (fn);
3843   return strncmp (IDENTIFIER_POINTER (name), TLS_WRAPPER_PREFIX,
3844                   strlen (TLS_WRAPPER_PREFIX)) == 0;
3845 }
3846
3847 /* Return an identifier for the name of a temporary variable used to
3848    initialize a static reference.  This isn't part of the ABI, but we might
3849    as well call them something readable.  */
3850
3851 static GTY(()) int temp_count;
3852
3853 tree
3854 mangle_ref_init_variable (const tree variable)
3855 {
3856   start_mangling (variable);
3857   write_string ("_ZGR");
3858   write_name (variable, /*ignore_local_scope=*/0);
3859   /* Avoid name clashes with aggregate initialization of multiple
3860      references at once.  */
3861   write_unsigned_number (temp_count++);
3862   return finish_mangling_get_identifier (/*warn=*/false);
3863 }
3864 \f
3865
3866 /* Foreign language type mangling section.  */
3867
3868 /* How to write the type codes for the integer Java type.  */
3869
3870 static void
3871 write_java_integer_type_codes (const tree type)
3872 {
3873   if (type == java_int_type_node)
3874     write_char ('i');
3875   else if (type == java_short_type_node)
3876     write_char ('s');
3877   else if (type == java_byte_type_node)
3878     write_char ('c');
3879   else if (type == java_char_type_node)
3880     write_char ('w');
3881   else if (type == java_long_type_node)
3882     write_char ('x');
3883   else if (type == java_boolean_type_node)
3884     write_char ('b');
3885   else
3886     gcc_unreachable ();
3887 }
3888
3889 #include "gt-cp-mangle.h"