[Demangler] [DO NOT SUBMIT] Initial patch for Microsoft demangler.

[ruiu]

Summary

This patch is not intended to be submitted as-is. I'm sending this out
now to get comments if there's anyone who has an opinion on the
implementation strategy.

So this is an initial patch for a Microsoft-style symbol demangler.
To give you an overview, I'll describe the code from 10,000 feet view.

• First of all, this demangler is not based on the exiting Itanium demangler which resides in the same directory. This is because the existing demangler seems too complicated to me and reported to be too slow.
  
  I designed this demangler with a goal to reduce the number of memory allocations as possible. This hasn't yet optimized hard, because I don't want to do that until the feature is complete, but I think you can see it from the code.
• Internally, all mangled symbols are converted to ASTs (or Types) and then converted to strings. This simplifies the code a lot. Particularly, constructing a string representing a C++ type is hard because you have to append new strings to both ends of an intermediate result. By using ASTs, you can eliminate that complexity.
  
  I also believe that this is faster than constructing strings directly.
• This demangler does not use any LLVM code. So, there's no use of StringRef, ArrayRef, etc. I had to write my own small String class, which is a bit silly, but this is intentional as this demangler is supposed to be used in other programs such as libcxxabi as well.

I don't ask you guys to do regular code review on this patch because the
patch is incomplete. Particularly, this patch

• does not provide a support for demanglign C++ special functions such as operator overloads, except the ctor and dtor, and
• does not provide a "proper" external function (whatever it means). The current microsoftDemangle function is provided just for testing.

I guess that this patch might be fun to read. Enjoy.

[majnemer]

llvm/lib/Demangle/MicrosoftDemangle.cpp

492–507

Isn't 'E' only for 64-bit?

600–619

These should be handled as normal structs and unions.

811

symbo -> symbol.

[eugene]

llvm/lib/Demangle/MicrosoftDemangle.cpp

190

Here a below a lot of function names violate LLVM's conventions (http://llvm.org/docs/CodingStandards.html#name-types-functions-variables-and-enumerators-properly)

Please let me know if that document is obsolete.

[ruiu]

llvm/lib/Demangle/MicrosoftDemangle.cpp

190

That's intentional. This file is intended to be used not only in LLVM but also in other projects. So this file does not use any LLVM functions and does not follow the LLVM coding style. I did not make that decision -- I just followed ItaniumDemangler.cpp which exists in the same directory.

[rnk]

llvm/lib/Demangle/MicrosoftDemangle.cpp

168

We will probably need to separate these for function templates.

[zturner]

More comments later when I have some time to look in more detail.

llvm/lib/Demangle/MicrosoftDemangle.cpp

96

What about vectorcall?

304–314

Can you add a similar comment above the parse() function that describes the high level grammar, similar to how you've done here with this one subsection?

332

What is the significance of 'A' and 'P'?

412–413

vectorcall is Q

419

s/structors/destructors/? Otherwise I'm not sure what this means.

429

Not all of these are valid for all types. For example, unaligned is not valid for functions. Do we care about this?

448–449

This is not quite right. After the F comes an additional storage class. For example, if it's simply unaligned, it will be FA. const __unaligned will be FB. const volatile __unaligned would be FD. etc.

450–451

Same is true here. You need to also consume the following character and or in the result until you get a terminating sequence

456

Can we have another grammar summary here?

492–505

This is not quite right. This A and B here corresponds to the storage class returned from read_storage_class(). So you need to be prepared to handle every PE + <any possible return value of read_storage_class()>, including the complex return values like FA and FIB, etc.

507

Same is true here.

[ruiu]

Zach,

You don't want to take a look into this patch in detail because this patch is incomplete. I know this has a lot of correctness issues, and I'm fixing all of them now. The point of sending this patch early is to get feedback for the design of this demangler, as this demangler is completely different from the existing Itanium demangler.

[rnk]

Broadly speaking, having a general Type or Node class that forms a tree seems like the right approach. I'm sure it'll grow in complexity over time. Pre-allocating enough of them to demangle most function prototypes without memory allocation is also great. I think this is the right direction.

It might be worth completely eliminating the STL dependency so that this can be run reliably without memory allocation in a crashing process, but it's probably not worth it for now.

[amccarth]

So the idea is to convert the mangled name to an AST and then convert the AST to a string. That makes sense. But is the string form of the result always enough? Will there ever be a need for a caller to get the AST or some other representation?

[compnerd]

llvm/lib/Demangle/MicrosoftDemangle.cpp

34

Isnt this effectively std::string_view or StringRef?

190

I think that we should adhere to the LLVM style. The itanium demangler was imported stock from libc++abi where it must adhere to the C++ ABI specification. I expect that over time it will move back to the LLVM style.

332

It is just the way that the numbers are encoded. 'A' = 0, 'P' = 15 (base 16-encoding).

[ruiu]

So the idea is to convert the mangled name to an AST and then convert the AST to a string. That makes sense. But is the string form of the result always enough? Will there ever be a need for a caller to get the AST or some other representation?

This is an interesting question. It could imagine that it might be useful, but honestly I don't come up with a use case in which you want to access internal ASTs.

llvm/lib/Demangle/MicrosoftDemangle.cpp

34

Yes it is. This file is designed to be usable outside LLVM.

[ruiu]

Over the last few days, I made a bunch of changes to the demanler to improve it.
It's not complete yet, but it started working really well. It can now demangle
complex C++ symbols as you can see in MicrosoftDemangleTest.cpp file.

Preliminary performance testing shows that this demangler is pretty fast.
I ran this and Microsoft's UnDecorateSymbolName for the test cases in
MicrosoftDemangleTest.cpp.

It showed that my demangler is 45% faster (or, finishs benchmark in 55% time)
than the Microsoft's demangler. This result seems very promising.

I think the remaining tasks are to add more types, add more tests and fix bugs.
I don't expect any major design changes. So if you want to review this, you can
do that now. I'm sending this out today because I'm on vacation next week, so
I'll address review comments in the week after next.

[zturner]

Will add more comments later.

llvm/lib/Demangle/MicrosoftDemangle.cpp

143

Missing vectorcall.

190

Agree with this. I would like it if we can adhere to LLVM style wherever possible.

318

isdigit(*input.p)

319

Why are we adding 1? If *input.p == '0' then wouldn't we want to return the number 0?

357

The comment here mentions that this is only for 64-bit, but we expect it always. Won't this generate an error in non-x86?

382

What's the +1 for?

394

You can save 2 lines if you invert this conditional and break on the negation. You can drop the curly braces as well as the continue statement.

532–537

Why not use read_storage_class() here? This misses all the cases like unaligned and restrict, and it also treats C and D as equivalent, which doesn't seem right. C is just volatile, while D is const volatile. Regardless, I think you can just say ty.sclass = read_storage_class();

544

You should also handle 3A6, which is a reference to a function.

559

Should this be Private | Static | FFar?

561

Should this be Private | Virtual | Far?

562

Are G and H not used?

605

vectorcall is Q

656

Can we have comments above every read_xxx function that describes the grammar of what is being read?

657

If you write this code:

nullptr_t NullPtr;

Then this is mangled as ?NullPtr@@3$$TA. Because of the 3 it makes it into this function, but nothing in this function handles a $$. In fact, the only place in the entire demangler that handles $$ is in the processing of an array, and it expects $$C. So this looks to be missing.

703

Can you sort this list in alphabetical order?

720

case 'S': return Char16;
case 'U': return Char32;

737

The same problem here as mentioned earlier. For 32-bit, it's A.

Note that both can theoretically appear in the same mangled name, for example: void foo(int * __ptr32 PA, int * __ptr64 PB);

[zturner]

Also, I think most (all?) of the original comments I had still apply.

[zturner]

llvm/lib/Demangle/MicrosoftDemangle.cpp

631

Support for restrict and unaligned got removed, it seems like? See original comments about how to correctly support those.

666

Here's a few more.

3A6  Reference to function
3P6   Rvalue Reference to Function
3P8  Pointer to Member Function
3AEAP8 Reference to Member Function Pointer
3$$QEAP8  Rvalue reference to member function pointer  (wtf?)

This is the second time I've seen this 3$$, so we should probably figure out what it means (it occurred in the variable of type nullptr_t also.

[zturner]

llvm/lib/Demangle/MicrosoftDemangle.cpp

663–666

Ok, I think I get it. Here's some pointers to member functions:

Ok I think I get it. Here's some pointers to member functions:

PtrMemberFunction@@3P8TheClass@@EAAXXZEQ1
PtrPtrMemberFunction@@3PEAP8TheClass@@EAAXXZEA
PtrPtrPtrMemberFunction@@3PEAPEAP8TheClass@@EAAXXZEA

The key observation here is that the 8 (8 here means member function pointer, as opposed to 6 in the case you've handled) doesn't necessarily come after the P. So this logic will not work here. I think you need to sink this conditional into the read_pointee function below. First you read the P, then you call read_pointee, which sees E (64-bit, and indicates that the storage class needs to be read), then storage class A (no storage class), then indirect recursion back into read_var_type(). It sees P again (pointer), then calls read_pointee again, this time there is no E (64-bit) or A (32-bit), but instead there is the number 8 (member function).

The same would apply to non-member functions, and the algorithm handles constness, reference, etc as well. So this should handle the general case.

[pcc]

I've been using https://github.com/rui314/msvc-demangler which I understand is basically the same code as this.

Here are a few names which it was unable to demangle:

$ undname '??1B@@UAE@XZ'
E expected, but got AE@XZ
$ undname '?foo@B@@UAEXXZ'
E expected, but got AEXXZ
$ undname '?foo@B@@$4PPPPPPPM@A@AEXXZ'
unknown func class: $4PPPPPPPM@A@AEXXZ

They were all derived from the IR from the clang test case clang/test/CodeGenCXX/microsoft-abi-virtual-inheritance.cpp.

llvm/include/llvm/Demangle/Demangle.h

 //===--- Demangle.h ---------------------------------------------*- C++ -*-===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 
 #include <cstddef>
+#include <string>
 
 namespace llvm {
 /// This is a llvm local version of __cxa_demangle. Other than the name and
 /// being in the llvm namespace it is identical.
 ///
 /// The mangled_name is demangled into buf and returned. If the buffer is not
 /// large enough, realloc is used to expand it.
 ///
 /// The *status will be set to
 ///   unknown_error: -4
 ///   invalid_args:  -3
 ///   invalid_mangled_name: -2
 ///   memory_alloc_failure: -1
 ///   success: 0
 
 char *itaniumDemangle(const char *mangled_name, char *buf, size_t *n,
                       int *status);
+
+// This is an experimental function to demangle MSVC-style symbols.
+std::string microsoftDemangle(const std::string &mangled_name,
+                              std::string error);
 }

llvm/lib/Demangle/CMakeLists.txt

 add_llvm_library(LLVMDemangle
   ItaniumDemangle.cpp
+  MicrosoftDemangle.cpp
 )

llvm/lib/Demangle/MicrosoftDemangle.cpp

+//===- MicrosoftDemangle.cpp ----------------------------------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is dual licensed under the MIT and the University of Illinois Open
+// Source Licenses. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This file defines a demangler for MSVC-style mangled symbols.
+//
+// This file has no dependencies on the rest of LLVM so that it can be
+// easily reused in other programs such as libcxxabi.
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/Demangle/Demangle.h"
+#include <algorithm>
+#include <cassert>
+#include <cctype>
+#include <cstdlib>
+#include <cstring>
+#include <iostream>
+#include <memory>
+#include <numeric>
+#include <sstream>
+#include <string>
+#include <utility>
+#include <vector>
+
+// A string class that does not own its contents.
+// This class provides a few utility functions for string manipulations.
+class String {
+public:
+  String() = default;
+  String(const String &) = default;
+  String(const std::string &s) : p(s.data()), len(s.size()) {}
+  String(const char *p) : p(p), len(strlen(p)) {}
+  String(const char *p, size_t len) : p(p), len(len) {}
+  template <size_t N> String(const char (&p)[N]) : p(p), len(N - 1) {}
+
+  std::string str() const { return {p, p + len}; }
+
+  bool empty() const { return len == 0; }
+
+  bool startswith(char c) const { return len > 0 && *p == c; }
+
+  bool startswith(const std::string &s) const {
+    return s.size() <= len && strncmp(p, s.data(), s.size()) == 0;
+  }
+
+  bool startswith_digit() const {
+    return 0 < len && '0' <= p[0] && p[0] <= '9';
+  }
+
+  String substr(size_t off) const { return {p + off, len - off}; }
+  String substr(size_t off, size_t length) const { return {p + off, length}; }
+
+  bool operator==(const String s) const {
+    return len == s.len && memcmp(p, s.p, len) == 0;
+  }
+
+  void trim(size_t n) {
+    assert(n <= len);
+    p += n;
+    len -= n;
+  }
+
+  int get() {
+    if (len == 0)
+      return -1;
+    len--;
+    return *p++;
+  }
+
+  void unget(int c) {
+    if (c == -1)
+      return;
+    p--;
+    len++;
+  }
+
+  const char *p = nullptr;
+  size_t len = 0;
+};
+
+std::ostream &operator<<(std::ostream &os, const String s) {
+  os.write(s.p, s.len);
+  return os;
+}
+
+// This memory allocator is extremely fast, but it doesn't call dtors
+// for allocated objects. That means you can't use STL containers
+// (such as std::vector) with this allocator. But it pays off --
+// the demangler is 3x faster with this allocator compared to one with
+// STL containers.
+namespace {
+class Arena {
+public:
+  void *alloc(size_t size) {
+    assert(size < unit);
+
+    uint8_t *p = buf + nused;
+    nused += size;
+    if (nused < unit)
+      return p;
+
+    buf = new uint8_t[Arena::unit];
+    buf2.emplace_back(buf);
+    nused = size;
+    return buf;
+  }
+
+private:
+  static constexpr size_t unit = 4096;
+
+  uint8_t *buf = init_buf;
+  alignas(sizeof(void *)) uint8_t init_buf[unit];
+  size_t nused = 0;
+  std::vector<std::unique_ptr<uint8_t[]>> buf2;
+};
+}
+
+void *operator new(size_t size, Arena &a) { return a.alloc(size); }
+
+// Storage classes
+enum {
+  Const = 1 << 0,
+  Volatile = 1 << 1,
+  Far = 1 << 2,
+  Huge = 1 << 3,
+  Unaligned = 1 << 4,
+  Restrict = 1 << 5,
+};
+
+// Calling conventions
+enum CallingConv : uint8_t {
+  Cdecl,
+  Pascal,
+  Thiscall,
+  Stdcall,
+  Fastcall,
+  Regcall,
+};
+
+// Types
+enum PrimTy : uint8_t {
+  Unknown,
+  None,
+  Function,
+  Ptr,
+  Ref,
+  Array,
+
+  Struct,
+  Union,
+  Class,
+  Enum,
+
+  Void,
+  Bool,
+  Char,
+  Schar,
+  Uchar,
+  Short,
+  Ushort,
+  Int,
+  Uint,
+  Long,
+  Ulong,
+  Int64,
+  Uint64,
+  Wchar,
+  Float,
+  Double,
+  Ldouble,
+};
+
+// Function classes
+enum FuncClass : uint8_t {
+  Public = 1 << 0,
+  Protected = 1 << 1,
+  Private = 1 << 2,
+  Global = 1 << 3,
+  Static = 1 << 4,
+  Virtual = 1 << 5,
+  FFar = 1 << 6,
+};
+
+namespace {
+struct Type;
+
+// Represents an identifier which may be a template.
+struct Name {
+  // Name read from an input string.
+  String str;
+
+  // Overloaded operators are represented as special names in mangled symbols.
+  // If this is an operator name, "op" has an operator name (e.g. ">>").
+  // Otherwise, empty.
+  String op;
+
+  // Template parameters. Null if not a template.
+  Type *params = nullptr;
+
+  // Nested names (e.g. "A::B::C") are represented as a linked list.
+  Name *next = nullptr;
+};
+
+// The type class. Mangled symbols are first parsed and converted to
+// this type and then converted to string.
+struct Type {
+  // Primitive type such as Int.
+  PrimTy prim;
+
+  // Represents a type X in "a pointer to X", "a reference to X",
+  // "an array of X", or "a function returning X".
+  Type *ptr = nullptr;
+
+  uint8_t sclass = 0;  // storage class
+  CallingConv calling_conv;
+  FuncClass func_class;
+
+  uint32_t len; // valid if prim == Array
+
+  // Valid if prim is one of (Struct, Union, Class, Enum).
+  Name *name = nullptr;
+
+  // Function parameters.
+  Type *params = nullptr;
+
+  // Lists of types (e.g. function parameters) are represented as linked lists.
+  Type *next = nullptr;
+};
+
+// Demangler class takes the main role in demangling symbols.
+// It has a set of functions to parse mangled symbols into Type instnaces.
+// It also has a set of functions to cnovert Type instances to strings.
+class Demangler {
+public:
+  Demangler(String s) : input(s) {}
+
+  // You are supposed to call parse() first and then check if error is
+  // still empty. After that, call str() to get a result.
+  void parse();
+  std::string str();
+
+  // Error string. Empty if there's no error.
+  std::string error;
+
+private:
+  // Parser functions. This is a recursive-descendent parser.
+  void read_var_type(Type &ty);
+  void read_member_func_type(Type &ty);
+
+  int read_number();
+  String read_string(bool memorize);
+  void memorize_string(String s);
+  Name *read_name();
+  void read_func_ptr(Type &ty);
+  void read_operator(Name *);
+  String read_operator_name();
+  String read_until(const std::string &s);
+  PrimTy read_prim_type();
+  int read_func_class();
+  int8_t read_func_access_class();
+  CallingConv read_calling_conv();
+  void read_func_return_type(Type &ty);
+  int8_t read_storage_class();
+  int8_t read_storage_class_for_return();
+
+  void read_class(Type &ty, PrimTy prim);
+  void read_pointee(Type &ty, PrimTy prim);
+  void read_array(Type &ty);
+  Type *read_params();
+
+  int peek() { return (input.len == 0) ? -1 : input.p[0]; }
+
+  bool consume(const std::string &s) {
+    if (!input.startswith(s))
+      return false;
+    input.trim(s.size());
+    return true;
+  }
+
+  void expect(const std::string &s) {
+    if (!consume(s) && error.empty())
+      error = s + " expected, but got " + input.str();
+  }
+
+  // Mangled symbol. read_* functions shorten this string
+  // as they parse it.
+  String input;
+
+  // A parsed mangled symbol.
+  Type type;
+
+  // The main symbol name. (e.g. "ns::foo" in "int ns::foo()".)
+  Name *symbol = nullptr;
+
+  // Memory allocator.
+  Arena arena;
+
+  // The first 10 names in a mangled name can be back-referenced by
+  // special name @[0-9]. This is a storage for the first 10 names.
+  String names[10];
+  size_t num_names = 0;
+
+  // Functions to convert Type to String.
+  void write_pre(Type &ty);
+  void write_post(Type &ty);
+  void write_class(Name *name, String s);
+  void write_params(Type *ty);
+  void write_name(Name *name);
+  void write_tmpl_params(Name *name);
+  void write_operator(Name *name);
+  void write_space();
+
+  // The result is written to this stream.
+  std::stringstream os;
+};
+} // namespace
+
+// Parser entry point.
+void Demangler::parse() {
+  // MSVC-style mangled symbols must start with '?'.
+  if (!consume("?")) {
+    symbol = new (arena) Name;
+    symbol->str = input;
+    type.prim = Unknown;
+  }
+
+  // What follows is a main symbol name. This may include
+  // namespaces or class names.
+  symbol = read_name();
+
+  // Read a variable.
+  if (consume("3")) {
+    read_var_type(type);
+    return;
+  }
+
+  // Read a non-member function.
+  if (consume("Y")) {
+    type.prim = Function;
+    type.calling_conv = read_calling_conv();
+    type.ptr = new (arena) Type;
+    type.ptr->sclass = read_storage_class_for_return();
+    read_var_type(*type.ptr);
+    type.params = read_params();
+    return;
+  }
+
+  // Read a member function.
+  type.prim = Function;
+  type.func_class = (FuncClass)read_func_class();
+  expect("E"); // if 64 bit
+  type.sclass = read_func_access_class();
+  type.calling_conv = read_calling_conv();
+
+  type.ptr = new (arena) Type;
+  type.ptr->sclass = read_storage_class_for_return();
+  read_func_return_type(*type.ptr);
+  type.params = read_params();
+}
+
+// Sometimes numbers are encoded in mangled symbols. For example,
+// "int (*x)[20]" is a valid C type (x is a pointer to an array of
+// length 20), so we need some way to embed numbers as part of symbols.
+// This function parses it.
+//
+// <number>               ::= [?] <non-negative integer>
+//
+// <non-negative integer> ::= <decimal digit> # when 1 <= Number <= 10
+//                        ::= <hex digit>+ @  # when Numbrer == 0 or >= 10
+//
+// <hex-digit>            ::= [A-P]           # A = 0, B = 1, ...
+int Demangler::read_number() {
+  bool neg = consume("?");
+
+  if (input.startswith_digit()) {
+    int32_t ret = *input.p - '0' + 1;
+    input.trim(1);
+    return neg ? -ret : ret;
+  }
+
+  int ret = 0;
+  for (size_t i = 0; i < input.len; ++i) {
+    char c = input.p[i];
+    if (c == '@') {
+      input.trim(i + 1);
+      return neg ? -ret : ret;
+    }
+    if ('A' <= c && c <= 'P') {
+      ret = (ret << 4) + (c - 'A');
+      continue;
+    }
+    break;
+  }
+
+  if (error.empty())
+    error = "bad number: " + input.str();
+  return 0;
+}
+
+// Read until the next '@'.
+String Demangler::read_string(bool memorize) {
+  for (size_t i = 0; i < input.len; ++i) {
+    if (input.p[i] != '@')
+      continue;
+    String ret = input.substr(0, i);
+    input.trim(i + 1);
+
+    if (memorize)
+      memorize_string(ret);
+    return ret;
+  }
+
+  if (error.empty())
+    error = "read_string: missing '@': " + input.str();
+  return "";
+}
+
+// First 10 strings can be referenced by special names ?0, ?1, ..., ?9.
+// Memorize it.
+void Demangler::memorize_string(String s) {
+  if (num_names >= sizeof(names) / sizeof(*names))
+    return;
+  for (size_t i = 0; i < num_names; ++i)
+    if (s == names[i])
+      return;
+  names[num_names++] = s;
+}
+
+// Parses a name in the form of A@B@C@@ which represents C::B::A.
+Name *Demangler::read_name() {
+  Name *head = nullptr;
+
+  while (!consume("@")) {
+    Name *elem = new (arena) Name;
+
+    if (input.startswith_digit()) {
+      size_t i = input.p[0] - '0';
+      if (i >= num_names) {
+        if (error.empty())
+          error = "name reference too large: " + input.str();
+        return {};
+      }
+      input.trim(1);
+      elem->str = names[i];
+    } else if (consume("?$")) {
+      // Class template.
+      elem->str = read_string(false);
+      elem->params = read_params();
+      expect("@");
+    } else if (consume("?")) {
+      // Overloaded operator.
+      read_operator(elem);
+    } else {
+      // Non-template functions or classes.
+      elem->str = read_string(true);
+    }
+
+    elem->next = head;
+    head = elem;
+  }
+
+  return head;
+}
+
+void Demangler::read_func_ptr(Type &ty) {
+  Type *tp = new (arena) Type;
+  tp->prim = Function;
+  tp->ptr = new (arena) Type;
+  read_var_type(*tp->ptr);
+  tp->params = read_params();
+
+  ty.prim = Ptr;
+  ty.ptr = tp;
+
+  if (input.startswith("@Z"))
+    input.trim(2);
+  else if (input.startswith("Z"))
+    input.trim(1);
+}
+
+void Demangler::read_operator(Name *name) {
+  name->op = read_operator_name();
+  if (error.empty() && peek() != '@')
+    name->str = read_string(true);
+}
+
+String Demangler::read_operator_name() {
+  String orig = input;
+
+  switch (input.get()) {
+  case '0': return "ctor";
+  case '1': return "dtor";
+  case '2': return " new";
+  case '3': return " delete";
+  case '4': return "=";
+  case '5': return ">>";
+  case '6': return "<<";
+  case '7': return "!";
+  case '8': return "==";
+  case '9': return "!=";
+  case 'A': return "[]";
+  case 'C': return "->";
+  case 'D': return "*";
+  case 'E': return "++";
+  case 'F': return "--";
+  case 'G': return "-";
+  case 'H': return "+";
+  case 'I': return "&";
+  case 'J': return "->*";
+  case 'K': return "/";
+  case 'L': return "%";
+  case 'M': return "<";
+  case 'N': return "<=";
+  case 'O': return ">";
+  case 'P': return ">=";
+  case 'Q': return ",";
+  case 'R': return "()";
+  case 'S': return "~";
+  case 'T': return "^";
+  case 'U': return "|";
+  case 'V': return "&&";
+  case 'W': return "||";
+  case 'X': return "*=";
+  case 'Y': return "+=";
+  case 'Z': return "-=";
+  case '_':
+    switch (input.get()) {
+    case '0': return "/=";
+    case '1': return "%=";
+    case '2': return ">>=";
+    case '3': return "<<=";
+    case '4': return "&=";
+    case '5': return "|=";
+    case '6': return "^=";
+    case 'U': return " new[]";
+    case 'V': return " delete[]";
+    case '_':
+      if (consume("L"))
+        return " co_await";
+    }
+  }
+
+  if (error.empty())
+    error = "unknown operator name: " + orig.str();
+  return "";
+}
+
+int Demangler::read_func_class() {
+  switch (int c = input.get()) {
+  case 'A': return Private;
+  case 'B': return Private | FFar;
+  case 'C': return Private | Static;
+  case 'D': return Private | Static;
+  case 'E': return Private | Virtual;
+  case 'F': return Private | Virtual;
+  case 'I': return Protected;
+  case 'J': return Protected | FFar;
+  case 'K': return Protected | Static;
+  case 'L': return Protected | Static | FFar;
+  case 'M': return Protected | Virtual;
+  case 'N': return Protected | Virtual | FFar;
+  case 'Q': return Public;
+  case 'R': return Public | FFar;
+  case 'S': return Public | Static;
+  case 'T': return Public | Static | FFar;
+  case 'U': return Public | Virtual;
+  case 'V': return Public | Virtual | FFar;
+  case 'Y': return Global;
+  case 'Z': return Global | FFar;
+  default:
+    input.unget(c);
+    if (error.empty())
+      error = "unknown func class: " + input.str();
+    return 0;
+  }
+}
+
+int8_t Demangler::read_func_access_class() {
+  switch (int c = input.get()) {
+  case 'A': return 0;
+  case 'B': return Const;
+  case 'C': return Volatile;
+  case 'D': return Const | Volatile;
+  default:
+    input.unget(c);
+    return 0;
+  }
+}
+
+CallingConv Demangler::read_calling_conv() {
+  String orig = input;
+
+  switch (input.get()) {
+  case 'A': return Cdecl;
+  case 'B': return Cdecl;
+  case 'C': return Pascal;
+  case 'E': return Thiscall;
+  case 'G': return Stdcall;
+  case 'I': return Fastcall;
+  default:
+    if (error.empty())
+      error = "unknown calling convention: " + orig.str();
+    return Cdecl;
+  }
+};
+
+// <return-type> ::= <type>
+//               ::= @ # structors (they have no declared return type)
+void Demangler::read_func_return_type(Type &ty) {
+  if (consume("@"))
+    ty.prim = None;
+  else
+    read_var_type(ty);
+}
+
+int8_t Demangler::read_storage_class() {
+  switch (int c = input.get()) {
+  case 'A': return 0;
+  case 'B': return Const;
+  case 'C': return Volatile;
+  case 'D': return Const | Volatile;
+  case 'E': return Far;
+  case 'F': return Const | Far;
+  case 'G': return Volatile | Far;
+  case 'H': return Const | Volatile | Far;
+  default:
+    input.unget(c);
+    return 0;
+  }
+}
+
+int8_t Demangler::read_storage_class_for_return() {
+  if (!consume("?"))
+    return 0;
+  String orig = input;
+
+  switch (input.get()) {
+  case 'A': return 0;
+  case 'B': return Const;
+  case 'C': return Volatile;
+  case 'D': return Const | Volatile;
+  default:
+    if (error.empty())
+      error = "unknown storage class: " + orig.str();
+    return 0;
+  }
+}
+
+// Reads a variable type.
+void Demangler::read_var_type(Type &ty) {
+  if (consume("W4")) {
+    ty.prim = Enum;
+    ty.name = read_name();
+    return;
+  }
+
+  if (consume("P6A")) {
+    read_func_ptr(ty);
+    return;
+  }
+
+  switch (int c = input.get()) {
+  case 'T':
+    read_class(ty, Union);
+    return;
+  case 'U':
+    read_class(ty, Struct);
+    return;
+  case 'V':
+    read_class(ty, Class);
+    return;
+  case 'A':
+    read_pointee(ty, Ref);
+    return;
+  case 'P':
+    read_pointee(ty, Ptr);
+    return;
+  case 'Q':
+    read_pointee(ty, Ptr);
+    ty.sclass = Const;
+    return;
+  case 'Y':
+    read_array(ty);
+    return;
+  default:
+    input.unget(c);
+    ty.prim = read_prim_type();
+    return;
+  }
+}
+
+// Reads a primitive type.
+PrimTy Demangler::read_prim_type() {
+  String orig = input;
+
+  switch (input.get()) {
+  case 'X': return Void;
+  case 'D': return Char;
+  case 'C': return Schar;
+  case 'E': return Uchar;
+  case 'F': return Short;
+  case 'G': return Ushort;
+  case 'H': return Int;
+  case 'I': return Uint;
+  case 'J': return Long;
+  case 'K': return Ulong;
+  case 'M': return Float;
+  case 'N': return Double;
+  case 'O': return Ldouble;
+  case '_':
+    switch (input.get()) {
+    case 'N': return Bool;
+    case 'J': return Int64;
+    case 'K': return Uint64;
+    case 'W': return Wchar;
+    }
+  }
+
+  if (error.empty())
+    error = "unknown primitive type: " + orig.str();
+  return Unknown;
+}
+
+void Demangler::read_class(Type &ty, PrimTy prim) {
+  ty.prim = prim;
+  ty.name = read_name();
+}
+
+void Demangler::read_pointee(Type &ty, PrimTy prim) {
+  ty.prim = prim;
+  expect("E"); // if 64 bit
+  ty.ptr = new (arena) Type;
+  ty.ptr->sclass = read_storage_class();
+  read_var_type(*ty.ptr);
+}
+
+void Demangler::read_array(Type &ty) {
+  int dimension = read_number();
+  if (dimension <= 0) {
+    if (error.empty())
+      error = "invalid array dimension: " + std::to_string(dimension);
+    return;
+  }
+
+  Type *tp = &ty;
+  for (int i = 0; i < dimension; ++i) {
+    tp->prim = Array;
+    tp->len = read_number();
+    tp->ptr = new (arena) Type;
+    tp = tp->ptr;
+  }
+
+  if (consume("$$C")) {
+    if (consume("B"))
+      ty.sclass = Const;
+    else if (consume("C") || consume("D"))
+      ty.sclass = Const | Volatile;
+    else if (!consume("A") && error.empty())
+      error = "unkonwn storage class: " + input.str();
+  }
+
+  read_var_type(*tp);
+}
+
+// Reads a function or a template parameters.
+Type * Demangler::read_params() {
+  // Within the same parameter list, you can backreference the first 10 types.
+  Type *backref[10];
+  int idx = 0;
+
+  Type *head = nullptr;
+  Type **tp = &head;
+  while (error.empty() && !input.startswith('@') && !input.startswith('Z')) {
+    if (input.startswith_digit()) {
+      int n = input.p[0] - '0';
+      if (n >= idx) {
+        if (error.empty())
+          error = "invalid backreference: " + input.str();
+        return nullptr;
+      }
+      input.trim(1);
+
+      *tp = new (arena) Type(*backref[n]);
+      (*tp)->next = nullptr;
+      tp = &(*tp)->next;
+      continue;
+    }
+
+    size_t len = input.len;
+
+    *tp = new (arena) Type;
+    read_var_type(**tp);
+
+    // Single-letter types are ignored for backreferences because
+    // memorizing them doesn't save anything.
+    if (idx <= 9 && len - input.len > 1)
+      backref[idx++] = *tp;
+    tp = &(*tp)->next;
+  }
+  return head;
+}
+
+// Converts an AST to a string.
+//
+// Converting an AST representing a C++ type to a string is tricky due
+// to the bad grammar of the C++ declaration inherited from C. You have
+// to construct a string from inside to outside. For example, if a type
+// X is a pointer to a function returning int, the order you create a
+// string becomes something like this:
+//
+//   (1) X is a pointer: *X
+//   (2) (1) is a function returning int: int (*X)()
+//
+// So you cannot construct a result just by appending strings to a result.
+//
+// To deal with this, we split the function into two. write_pre() writes
+// the "first half" of type declaration, and write_post() writes the
+// "second half". For example, write_pre() writes a return type for a
+// function and write_post() writes an parameter list.
+std::string Demangler::str() {
+  write_pre(type);
+  write_name(symbol);
+  write_post(type);
+  return os.str();
+}
+
+// Write the "first half" of a given type.
+void Demangler::write_pre(Type &ty) {
+  switch (ty.prim) {
+  case Unknown:
+  case None:
+    break;
+  case Function:
+    write_pre(*ty.ptr);
+    return;
+  case Ptr:
+  case Ref:
+    write_pre(*ty.ptr);
+
+    // "[]" and "()" (for function parameters) take precedence over "*",
+    // so "int *x(int)" means "x is a function returning int *". We need
+    // parentheses to supercede the default precedence. (e.g. we want to
+    // emit something like "int (*x)(int)".)
+    if (ty.ptr->prim == Function || ty.ptr->prim == Array)
+      os << "(";
+
+    if (ty.prim == Ptr)
+      os << "*";
+    else
+      os << "&";
+    break;
+  case Array:
+    write_pre(*ty.ptr);
+    break;
+
+  case Struct: write_class(ty.name, "struct"); break;
+  case Union:  write_class(ty.name, "union"); break;
+  case Class:  write_class(ty.name, "class"); break;
+  case Enum:   write_class(ty.name, "enum"); break;
+  case Void:    os << "void"; break;
+  case Bool:    os << "bool"; break;
+  case Char:    os << "char"; break;
+  case Schar:   os << "signed char"; break;
+  case Uchar:   os << "unsigned char"; break;
+  case Short:   os << "short"; break;
+  case Ushort:  os << "unsigned short"; break;
+  case Int:     os << "int"; break;
+  case Uint:    os << "unsigned int"; break;
+  case Long:    os << "long"; break;
+  case Ulong:   os << "unsigned long"; break;
+  case Int64:   os << "int64_t"; break;
+  case Uint64:  os << "uint64_t"; break;
+  case Wchar:   os << "wchar_t"; break;
+  case Float:   os << "float"; break;
+  case Double:  os << "double"; break;
+  case Ldouble: os << "long double"; break;
+  }
+
+  if (ty.sclass & Const) {
+    write_space();
+    os << "const";
+  }
+}
+
+// Write the "second half" of a given type.
+void Demangler::write_post(Type &ty) {
+  if (ty.prim == Function) {
+    os << "(";
+    write_params(ty.params);
+    os << ")";
+    if (ty.sclass & Const)
+      os << "const";
+    return;
+  }
+
+  if (ty.prim == Ptr || ty.prim == Ref) {
+    if (ty.ptr->prim == Function || ty.ptr->prim == Array)
+      os << ")";
+    write_post(*ty.ptr);
+    return;
+  }
+
+  if (ty.prim == Array) {
+    os << "[" << ty.len << "]";
+    write_post(*ty.ptr);
+  }
+}
+
+// Write a function or template parameter list.
+void Demangler::write_params(Type *params) {
+  for (Type *tp = params; tp; tp = tp->next) {
+    if (tp != params)
+      os << ",";
+    write_pre(*tp);
+    write_post(*tp);
+  }
+}
+
+void Demangler::write_class(Name *name, String s) {
+  os << s << " ";
+  write_name(name);
+}
+
+// Write a name read by read_name().
+void Demangler::write_name(Name *name) {
+  if (!name)
+    return;
+  write_space();
+
+  // Print out namespaces or outer class names.
+  for (; name->next; name = name->next) {
+    os << name->str;
+    write_tmpl_params(name);
+    os << "::";
+  }
+
+  // Print out a regular name.
+  if (name->op.empty()) {
+    os << name->str;
+    write_tmpl_params(name);
+    return;
+  }
+
+  // Print out ctor or dtor.
+  if (name->op == "ctor" || name->op == "dtor") {
+    os << name->str;
+    write_params(name->params);
+    os << "::";
+    if (name->op == "dtor")
+      os << "~";
+    os << name->str;
+    return;
+  }
+
+  // Print out an overloaded operator.
+  if (!name->str.empty())
+    os << name->str << "::";
+  os << "operator" << name->op;
+}
+
+void Demangler::write_tmpl_params(Name *name) {
+  if (!name->params)
+    return;
+  os << "<";
+  write_params(name->params);
+  os << ">";
+}
+
+// Writes a space if the last token does not end with a punctuation.
+void Demangler::write_space() {
+  std::string s = os.str();
+  if (!s.empty() && isalpha(s.back()))
+    os << " ";
+}
+
+std::string llvm::microsoftDemangle(const std::string &mangled_name,
+                                    std::string error) {
+  Demangler d(mangled_name);
+  d.parse();
+  if (!d.error.empty()) {
+    error = d.error;
+    return "";
+  }
+  return d.str();
+}

llvm/unittests/CMakeLists.txt

 add_custom_target(UnitTests)
 set_target_properties(UnitTests PROPERTIES FOLDER "Tests")
 
 function(add_llvm_unittest test_dirname)
   add_unittest(UnitTests ${test_dirname} ${ARGN})
 endfunction()
 
 add_subdirectory(ADT)
 add_subdirectory(Analysis)
 add_subdirectory(AsmParser)
 add_subdirectory(Bitcode)
 add_subdirectory(CodeGen)
 add_subdirectory(DebugInfo)
+add_subdirectory(Demangle)
 add_subdirectory(ExecutionEngine)
 add_subdirectory(IR)
 add_subdirectory(LineEditor)
 add_subdirectory(Linker)
 add_subdirectory(MC)
 add_subdirectory(MI)
 add_subdirectory(Object)
 add_subdirectory(BinaryFormat)
 add_subdirectory(ObjectYAML)
 add_subdirectory(Option)
 add_subdirectory(ProfileData)
 add_subdirectory(Support)
 add_subdirectory(Target)
 add_subdirectory(Transforms)
 add_subdirectory(XRay)

llvm/unittests/Demangle/CMakeLists.txt

+set(LLVM_LINK_COMPONENTS
+  Demangle
+  )
+
+add_llvm_unittest(DemangleTests
+  MicrosoftDemangleTest.cpp
+  )

llvm/unittests/Demangle/MicrosoftDemangleTest.cpp

+//===- llvm/unittest/Demangle/MicrosoftDemangleTest.cpp -------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/Demangle/Demangle.h"
+#include "gtest/gtest.h"
+
+using namespace llvm;
+
+namespace {
+
+TEST(MicrosoftDemanglerTest, Basic) {
+  auto Demangle = [&](const std::string &S) {
+    std::string Err;
+    std::string Ret = microsoftDemangle(S, Err);
+    EXPECT_EQ("", Err);
+    return Ret;
+  };
+
+  EXPECT_EQ("int x", Demangle("?x@@3HA"));
+  EXPECT_EQ("int*x", Demangle("?x@@3PEAHEA"));
+  EXPECT_EQ("int**x", Demangle("?x@@3PEAPEAHEA"));
+  EXPECT_EQ("int(*x)[3]", Demangle("?x@@3PEAY02HEA"));
+  EXPECT_EQ("int(*x)[3][5]", Demangle("?x@@3PEAY124HEA"));
+  EXPECT_EQ("int const(*x)[3]", Demangle("?x@@3PEAY02$$CBHEA"));
+  EXPECT_EQ("unsigned char*x", Demangle("?x@@3PEAEEA"));
+  EXPECT_EQ("int(*x)[3500][6]", Demangle("?x@@3PEAY1NKM@5HEA"));
+  EXPECT_EQ("void x(float,int)", Demangle("?x@@YAXMH@Z"));
+  EXPECT_EQ("void x(float,int)", Demangle("?x@@YAXMH@Z"));
+  EXPECT_EQ("int(*x)(float,double,int)", Demangle("?x@@3P6AHMNH@ZEA"));
+  EXPECT_EQ("int(*x)(int(*)(float),double)", Demangle("?x@@3P6AHP6AHM@ZN@ZEA"));
+  EXPECT_EQ("int(*x)(int(*)(float),int(*)(float))",
+            Demangle("?x@@3P6AHP6AHM@Z0@ZEA"));
+
+  EXPECT_EQ("int ns::x", Demangle("?x@ns@@3HA"));
+
+  // Microsoft"s undname returns "int const * const x" for this symbol.
+  // I believe it"s their bug.
+  EXPECT_EQ("int const*x", Demangle("?x@@3PEBHEB"));
+
+  EXPECT_EQ("int*const x", Demangle("?x@@3QEAHEB"));
+  EXPECT_EQ("int const*const x", Demangle("?x@@3QEBHEB"));
+
+  EXPECT_EQ("int const&x", Demangle("?x@@3AEBHEB"));
+
+  EXPECT_EQ("struct ty*x", Demangle("?x@@3PEAUty@@EA"));
+  EXPECT_EQ("union ty*x", Demangle("?x@@3PEATty@@EA"));
+  EXPECT_EQ("struct ty*x", Demangle("?x@@3PEAUty@@EA"));
+  EXPECT_EQ("enum ty*x", Demangle("?x@@3PEAW4ty@@EA"));
+  EXPECT_EQ("class ty*x", Demangle("?x@@3PEAVty@@EA"));
+
+  EXPECT_EQ("class tmpl<int>*x", Demangle("?x@@3PEAV?$tmpl@H@@EA"));
+  EXPECT_EQ("struct tmpl<int>*x", Demangle("?x@@3PEAU?$tmpl@H@@EA"));
+  EXPECT_EQ("union tmpl<int>*x", Demangle("?x@@3PEAT?$tmpl@H@@EA"));
+  EXPECT_EQ("class klass instance", Demangle("?instance@@3Vklass@@A"));
+  EXPECT_EQ("void(*instance$initializer$)(void)",
+            Demangle("?instance$initializer$@@3P6AXXZEA"));
+  EXPECT_EQ("klass::klass(void)", Demangle("??0klass@@QEAA@XZ"));
+  EXPECT_EQ("klass::~klass(void)", Demangle("??1klass@@QEAA@XZ"));
+  EXPECT_EQ("int x(class klass*,class klass&)",
+            Demangle("?x@@YAHPEAVklass@@AEAV1@@Z"));
+  EXPECT_EQ("class ns::klass<int,int>*ns::x",
+            Demangle("?x@ns@@3PEAV?$klass@HH@1@EA"));
+  EXPECT_EQ("unsigned int ns::klass<int>::fn(void)const",
+            Demangle("?fn@?$klass@H@ns@@QEBAIXZ"));
+
+  EXPECT_EQ("class klass const&klass::operator=(class klass const&)",
+            Demangle("??4klass@@QEAAAEBV0@AEBV0@@Z"));
+  EXPECT_EQ("bool klass::operator!(void)", Demangle("??7klass@@QEAA_NXZ"));
+  EXPECT_EQ("bool klass::operator==(class klass const&)",
+            Demangle("??8klass@@QEAA_NAEBV0@@Z"));
+  EXPECT_EQ("bool klass::operator!=(class klass const&)",
+            Demangle("??9klass@@QEAA_NAEBV0@@Z"));
+  EXPECT_EQ("int klass::operator[](uint64_t)", Demangle("??Aklass@@QEAAH_K@Z"));
+  EXPECT_EQ("int klass::operator->(void)", Demangle("??Cklass@@QEAAHXZ"));
+  EXPECT_EQ("int klass::operator*(void)", Demangle("??Dklass@@QEAAHXZ"));
+  EXPECT_EQ("int klass::operator++(void)", Demangle("??Eklass@@QEAAHXZ"));
+  EXPECT_EQ("int klass::operator++(int)", Demangle("??Eklass@@QEAAHH@Z"));
+  EXPECT_EQ("int klass::operator--(void)", Demangle("??Fklass@@QEAAHXZ"));
+  EXPECT_EQ("int klass::operator--(int)", Demangle("??Fklass@@QEAAHH@Z"));
+  EXPECT_EQ("int klass::operator+(int)", Demangle("??Hklass@@QEAAHH@Z"));
+  EXPECT_EQ("int klass::operator-(int)", Demangle("??Gklass@@QEAAHH@Z"));
+  EXPECT_EQ("int klass::operator&(int)", Demangle("??Iklass@@QEAAHH@Z"));
+  EXPECT_EQ("int klass::operator->*(int)", Demangle("??Jklass@@QEAAHH@Z"));
+  EXPECT_EQ("int klass::operator/(int)", Demangle("??Kklass@@QEAAHH@Z"));
+  EXPECT_EQ("int klass::operator<(int)", Demangle("??Mklass@@QEAAHH@Z"));
+  EXPECT_EQ("int klass::operator<=(int)", Demangle("??Nklass@@QEAAHH@Z"));
+  EXPECT_EQ("int klass::operator>(int)", Demangle("??Oklass@@QEAAHH@Z"));
+  EXPECT_EQ("int klass::operator>=(int)", Demangle("??Pklass@@QEAAHH@Z"));
+  EXPECT_EQ("int klass::operator,(int)", Demangle("??Qklass@@QEAAHH@Z"));
+  EXPECT_EQ("int klass::operator()(int)", Demangle("??Rklass@@QEAAHH@Z"));
+  EXPECT_EQ("int klass::operator~(void)", Demangle("??Sklass@@QEAAHXZ"));
+  EXPECT_EQ("int klass::operator^(int)", Demangle("??Tklass@@QEAAHH@Z"));
+  EXPECT_EQ("int klass::operator|(int)", Demangle("??Uklass@@QEAAHH@Z"));
+  EXPECT_EQ("int klass::operator&&(int)", Demangle("??Vklass@@QEAAHH@Z"));
+  EXPECT_EQ("int klass::operator||(int)", Demangle("??Wklass@@QEAAHH@Z"));
+  EXPECT_EQ("int klass::operator*=(int)", Demangle("??Xklass@@QEAAHH@Z"));
+  EXPECT_EQ("int klass::operator+=(int)", Demangle("??Yklass@@QEAAHH@Z"));
+  EXPECT_EQ("int klass::operator-=(int)", Demangle("??Zklass@@QEAAHH@Z"));
+  EXPECT_EQ("int klass::operator/=(int)", Demangle("??_0klass@@QEAAHH@Z"));
+  EXPECT_EQ("int klass::operator%=(int)", Demangle("??_1klass@@QEAAHH@Z"));
+  EXPECT_EQ("int klass::operator>>=(int)", Demangle("??_2klass@@QEAAHH@Z"));
+  EXPECT_EQ("int klass::operator<<=(int)", Demangle("??_3klass@@QEAAHH@Z"));
+  EXPECT_EQ("int klass::operator^=(int)", Demangle("??_6klass@@QEAAHH@Z"));
+  EXPECT_EQ("class klass const&operator<<(class klass const&,int)",
+            Demangle("??6@YAAEBVklass@@AEBV0@H@Z"));
+  EXPECT_EQ("class klass const&operator>>(class klass const&,uint64_t)",
+            Demangle("??5@YAAEBVklass@@AEBV0@_K@Z"));
+  EXPECT_EQ("void*operator new(uint64_t,class klass&)",
+            Demangle("??2@YAPEAX_KAEAVklass@@@Z"));
+  EXPECT_EQ("void*operator new[](uint64_t,class klass&)",
+            Demangle("??_U@YAPEAX_KAEAVklass@@@Z"));
+  EXPECT_EQ("void operator delete(void*,class klass&)",
+            Demangle("??3@YAXPEAXAEAVklass@@@Z"));
+  EXPECT_EQ("void operator delete[](void*,class klass&)",
+            Demangle("??_V@YAXPEAXAEAVklass@@@Z"));
+}
+
+} // end namespace