[WIP][NOT FOR COMMIT][PROTOTYPE] clang-scan-deps: dependency scanning tool rough prototype

[arphaman]

Oops, this is a wrong patch. Sorry for the noise.

include/llvm/Demangle/Canonicalize.h

+//===--- Canonicalize.h -----------------------------------------*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_DEMANGLE_CANONICALIZE_H
+#define LLVM_DEMANGLE_CANONICALIZE_H
+
+#include "llvm/ADT/StringRef.h"
+
+#include <cstddef>
+
+namespace llvm {
+/// Canonicalizer for mangled names.
+///
+/// This class allows specifying a list of "equivalent" manglings. For example,
+/// you can specify that Ss is equivalent to
+///   NSt3__112basic_stringIcNS_11char_traitsIcEENS_9allocatorIcEEEE
+/// and then manglings that refer to libstdc++'s 'std::string' will be
+/// considered equivalent to manglings that are the same except that they refer
+/// to libc++'s 'std::string'.
+///
+/// This can be used when data (eg, profiling data) is available for a version
+/// of a program built in a different configuration, with correspondingly
+/// different manglings.
+class ItaniumManglingCanonicalizer {
+public:
+  ItaniumManglingCanonicalizer();
+  ItaniumManglingCanonicalizer(const ItaniumManglingCanonicalizer &) = delete;
+  void operator=(const ItaniumManglingCanonicalizer &) = delete;
+  ~ItaniumManglingCanonicalizer();
+
+  enum class EquivalenceError {
+    Success,
+
+    /// Both the equivalent manglings have already been used as components of
+    /// some other mangling we've looked at. It's too late to add this
+    /// equivalence.
+    ManglingAlreadyUsed,
+
+    /// The first equivalent mangling is invalid.
+    InvalidFirstMangling,
+
+    /// The second equivalent mangling is invalid.
+    InvalidSecondMangling,
+  };
+
+  enum class FragmentKind {
+    /// The mangling fragment is a <name> (or a predefined <substitution>).
+    Name,
+    /// The mangling fragment is a <type>.
+    Type,
+    /// The mangling fragment is an <encoding>.
+    Encoding,
+  };
+
+  /// Add an equivalence between \p First and \p Second. Both manglings must
+  /// live at least as long as the canonicalizer.
+  EquivalenceError addEquivalence(FragmentKind Kind, StringRef First,
+                                  StringRef Second);
+
+  using Key = uintptr_t;
+
+  /// Form a canonical key for the specified mangling. They key will be the
+  /// same for all equivalent manglings, and different for any two
+  /// non-equivalent manglings, but is otherwise unspecified.
+  ///
+  /// Returns Key() if (and only if) the mangling is not a valid Itanium C++
+  /// ABI mangling.
+  ///
+  /// The string denoted by Mangling must live as long as the canonicalizer.
+  Key canonicalize(StringRef Mangling);
+
+  /// Find a canonical key for the specified mangling, if one has already been
+  /// formed. Otherwise returns Key().
+  Key lookup(StringRef Mangling);
+
+private:
+  struct Impl;
+  Impl *P;
+};
+} // namespace llvm
+
+#endif

include/llvm/LTO/Config.h

struct Config {
 
   /// Setting this field will replace unspecified target triples in input files
   /// with this triple.
   std::string DefaultTriple;
 
   /// Sample PGO profile path.
   std::string SampleProfile;
 
+  /// Name remapping file for profile data.
+  std::string ProfileRemapping;
+
   /// The directory to store .dwo files.
   std::string DwoDir;
 
   /// The path to write a .dwo file to. This should generally only be used when
   /// running an individual backend directly via thinBackend(), as otherwise
   /// all .dwo files will be written to the same path.
   std::string DwoPath;
 

include/llvm/Passes/PassBuilder.h

 class StringRef;
 class AAManager;
 class TargetMachine;
 class ModuleSummaryIndex;
 
 /// A struct capturing PGO tunables.
 struct PGOOptions {
   PGOOptions(std::string ProfileGenFile = "", std::string ProfileUseFile = "",
-             std::string SampleProfileFile = "", bool RunProfileGen = false,
-             bool SamplePGOSupport = false)
+             std::string SampleProfileFile = "",
+             std::string ProfileRemappingFile = "",
+             bool RunProfileGen = false, bool SamplePGOSupport = false)
       : ProfileGenFile(ProfileGenFile), ProfileUseFile(ProfileUseFile),
-        SampleProfileFile(SampleProfileFile), RunProfileGen(RunProfileGen),
+        SampleProfileFile(SampleProfileFile),
+        ProfileRemappingFile(ProfileRemappingFile),
+        RunProfileGen(RunProfileGen),
         SamplePGOSupport(SamplePGOSupport || !SampleProfileFile.empty()) {
     assert((RunProfileGen ||
             !SampleProfileFile.empty() ||
             !ProfileUseFile.empty() ||
             SamplePGOSupport) && "Illegal PGOOptions.");
   }
   std::string ProfileGenFile;
   std::string ProfileUseFile;
   std::string SampleProfileFile;
+  std::string ProfileRemappingFile;
   bool RunProfileGen;
   bool SamplePGOSupport;
 };
 
 /// This class provides access to building LLVM's passes.
 ///
 /// It's members provide the baseline state available to passes during their
 /// construction. The \c PassRegistry.def file specifies how to construct all
bool parseCGSCCPassPipeline(CGSCCPassManager &CGPM,
                               bool VerifyEachPass, bool DebugLogging);
   bool parseModulePassPipeline(ModulePassManager &MPM,
                                ArrayRef<PipelineElement> Pipeline,
                                bool VerifyEachPass, bool DebugLogging);
 
   void addPGOInstrPasses(ModulePassManager &MPM, bool DebugLogging,
                          OptimizationLevel Level, bool RunProfileGen,
                          std::string ProfileGenFile,
-                         std::string ProfileUseFile);
+                         std::string ProfileUseFile,
+                         std::string ProfileRemappingFile);
 
   void invokePeepholeEPCallbacks(FunctionPassManager &, OptimizationLevel);
 
   // Extension Point callbacks
   SmallVector<std::function<void(FunctionPassManager &, OptimizationLevel)>, 2>
       PeepholeEPCallbacks;
   SmallVector<std::function<void(LoopPassManager &, OptimizationLevel)>, 2>
       LateLoopOptimizationsEPCallbacks;

include/llvm/ProfileData/InstrProfReader.h

struct InstrProfReaderIndexBase {
   virtual uint64_t getVersion() const = 0;
   virtual bool isIRLevelProfile() const = 0;
   virtual Error populateSymtab(InstrProfSymtab &) = 0;
 };
 
 using OnDiskHashTableImplV3 =
     OnDiskIterableChainedHashTable<InstrProfLookupTrait>;
 
-template <typename HashTableImpl>
+template<typename HashTableImpl>
+class InstrProfReaderItaniumRemapper;
+
+template <typename HashTableImpl>
 class InstrProfReaderIndex : public InstrProfReaderIndexBase {
 private:
   std::unique_ptr<HashTableImpl> HashTable;
   typename HashTableImpl::data_iterator RecordIterator;
   uint64_t FormatVersion;
 
+  friend class InstrProfReaderItaniumRemapper<HashTableImpl>;
+
 public:
   InstrProfReaderIndex(const unsigned char *Buckets,
                        const unsigned char *const Payload,
                        const unsigned char *const Base,
                        IndexedInstrProf::HashT HashType, uint64_t Version);
   ~InstrProfReaderIndex() override = default;
 
   Error getRecords(ArrayRef<NamedInstrProfRecord> &Data) override;
public:
   }
 };
 
 /// Reader for the indexed binary instrprof format.
 class IndexedInstrProfReader : public InstrProfReader {
 private:
   /// The profile data file contents.
   std::unique_ptr<MemoryBuffer> DataBuffer;
+  /// The profile remapping file contents.
+  std::unique_ptr<MemoryBuffer> RemappingBuffer;
   /// The index into the profile data.
   std::unique_ptr<InstrProfReaderIndexBase> Index;
   /// Profile summary data.
   std::unique_ptr<ProfileSummary> Summary;
   // Index to the current record in the record array.
   unsigned RecordIndex;
 
   // Read the profile summary. Return a pointer pointing to one byte past the
   // end of the summary data if it exists or the input \c Cur.
   const unsigned char *readSummary(IndexedInstrProf::ProfVersion Version,
                                    const unsigned char *Cur);
 
 public:
-  IndexedInstrProfReader(std::unique_ptr<MemoryBuffer> DataBuffer)
-      : DataBuffer(std::move(DataBuffer)), RecordIndex(0) {}
+  IndexedInstrProfReader(
+      std::unique_ptr<MemoryBuffer> DataBuffer,
+      std::unique_ptr<MemoryBuffer> RemappingBuffer = nullptr)
+      : DataBuffer(std::move(DataBuffer)),
+        RemappingBuffer(std::move(RemappingBuffer)), RecordIndex(0) {}
   IndexedInstrProfReader(const IndexedInstrProfReader &) = delete;
   IndexedInstrProfReader &operator=(const IndexedInstrProfReader &) = delete;
 
   /// Return the profile version.
   uint64_t getVersion() const { return Index->getVersion(); }
   bool isIRLevelProfile() const override { return Index->isIRLevelProfile(); }
 
   /// Return true if the given buffer is in an indexed instrprof format.
public:
   Error getFunctionCounts(StringRef FuncName, uint64_t FuncHash,
                           std::vector<uint64_t> &Counts);
 
   /// Return the maximum of all known function counts.
   uint64_t getMaximumFunctionCount() { return Summary->getMaxFunctionCount(); }
 
   /// Factory method to create an indexed reader.
   static Expected<std::unique_ptr<IndexedInstrProfReader>>
-  create(const Twine &Path);
+  create(const Twine &Path, const Twine &RemappingPath = "");
 
   static Expected<std::unique_ptr<IndexedInstrProfReader>>
-  create(std::unique_ptr<MemoryBuffer> Buffer);
+  create(std::unique_ptr<MemoryBuffer> Buffer,
+         std::unique_ptr<MemoryBuffer> RemappingBuffer = nullptr);
 
   // Used for testing purpose only.
   void setValueProfDataEndianness(support::endianness Endianness) {
     Index->setValueProfDataEndianness(Endianness);
   }
 
   // See description in the base class. This interface is designed
   // to be used by llvm-profdata (for dumping). Avoid using this when
   // the client is the compiler.
   InstrProfSymtab &getSymtab() override;
   ProfileSummary &getSummary() { return *(Summary.get()); }
 };
 
 } // end namespace llvm
 
 #endif // LLVM_PROFILEDATA_INSTRPROFREADER_H

include/llvm/ProfileData/ProfRemappingReader.h

+//===- ProfRemappingReader.h - Read profile remapping file ------*- C++ -*-===//
+//
+//                      The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This file contains definitions needed for reading and applying profile
+// remapping files.
+//
+// NOTE: If you are making changes to this file format, please remember
+//       to document them in the Clang documentation at
+//       tools/clang/docs/UsersManual.rst.
+//
+// File format
+// -----------
+//
+// The profile remappings are written as an ASCII text file. Blank lines and
+// lines starting with a # are ignored. All other lines specify a kind of
+// mangled name fragment, along with two fragments of that kind that should
+// be treated as equivalent, separated by spaces.
+//
+// See http://itanium-cxx-abi.github.io/cxx-abi/abi.html#mangling for a
+// description of the Itanium name mangling scheme.
+//
+// The accepted fragment kinds are:
+//
+//  * name  A <name>, such as 6foobar or St3__1
+//  * type  A <type>, such as Ss or N4llvm9StringRefE
+//  * encoding  An <encoding> (a complete mangling without the leading _Z)
+//
+// For example:
+//
+// # Ignore int / long differences to allow profile reuse between
+// # 32-bit and 64-bit builds with differing size_t / ptrdiff_t / intptr_t.
+// type i l
+// type j m
+//
+// # Ignore differences between libc++ and libstdc++, and between libstdc++'s
+// # C++98 and C++11 ABIs.
+// name 3std St3__1
+// name 3std St7__cxx11
+//
+// # Substitutions must be remapped separately from namespace 'std' for now.
+// name Sa NSt3__19allocatorE
+// name Sb NSt3__112basic_stringE
+// type Ss NSt3__112basic_stringIcSt11char_traitsIcESaE
+// # ...
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_PROFILEDATA_PROFREMAPPINGREADER_H
+#define LLVM_PROFILEDATA_PROFREMAPPINGREADER_H
+
+#include "llvm/ADT/StringRef.h"
+#include "llvm/IR/LLVMContext.h"
+#include "llvm/Support/MemoryBuffer.h"
+#include "llvm/Demangle/Canonicalize.h"
+
+namespace llvm {
+
+class ProfileRemappingParseError
+    : public ErrorInfo<ProfileRemappingParseError> {
+public:
+  ProfileRemappingParseError(StringRef File, int64_t Line, Twine Message)
+      : File(File), Line(Line), Message(Message.str()) {}
+
+  void log(llvm::raw_ostream &OS) const override {
+    OS << File << ':' << Line << ": " << Message;
+  }
+  std::error_code convertToErrorCode() const override {
+    return llvm::inconvertibleErrorCode();
+  }
+
+  StringRef getFileName() const { return File; }
+  int64_t getLineNum() const { return Line; }
+  StringRef getMessage() const { return Message; }
+
+  static char ID;
+
+private:
+  std::string File;
+  int64_t Line;
+  std::string Message;
+};
+
+/// Profile name remapper.
+///
+/// Remaps the symbol names in profile data to match those in the program
+/// according to a set of rules specified in a given file.
+class ItaniumProfileRemappingReader {
+public:
+  /// Read remappings from the given buffer, which must live as long as
+  /// the remapper.
+  Error read(MemoryBuffer &B);
+
+  using Key = ItaniumManglingCanonicalizer::Key;
+
+  /// Map the given function name from the profiling data into a profile
+  /// data key. The result will be Key() if the name cannot be remapped.
+  Key remap(StringRef FunctionName) {
+    return Canonicalizer.canonicalize(FunctionName);
+  }
+
+  /// Map the given function name from the program into a profile data key.
+  ///
+  /// The result will be Key() if the name has no corresponding entry in the
+  /// profile data, in which case the original name should be looked up in the
+  /// profile data.
+  ///
+  /// There is no guarantee that return values other than Key() have ever been
+  /// returned by remap(...), but this should be rare.
+  Key lookup(StringRef FunctionName) {
+    return Canonicalizer.lookup(FunctionName);
+  }
+
+private:
+  ItaniumManglingCanonicalizer Canonicalizer;
+};
+
+} // end namespace llvm
+
+#endif // LLVM_PROFILEDATA_PROFREMAPPINGREADER_H

include/llvm/ProfileData/SampleProfReader.h

 #include "llvm/ADT/StringRef.h"
 #include "llvm/ADT/Twine.h"
 #include "llvm/IR/DiagnosticInfo.h"
 #include "llvm/IR/Function.h"
 #include "llvm/IR/LLVMContext.h"
 #include "llvm/IR/ProfileSummary.h"
 #include "llvm/ProfileData/GCOV.h"
 #include "llvm/ProfileData/SampleProf.h"
+#include "llvm/ProfileData/ProfRemappingReader.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/ErrorOr.h"
 #include "llvm/Support/MemoryBuffer.h"
 #include <algorithm>
 #include <cstdint>
 #include <memory>
 #include <string>
 #include <system_error>
public:
   /// Print all the profiles on stream \p OS.
   void dump(raw_ostream &OS = dbgs());
 
   /// Return the samples collected for function \p F.
   FunctionSamples *getSamplesFor(const Function &F) {
     // The function name may have been updated by adding suffix. In sample
     // profile, the function names are all stripped, so we need to strip
     // the function name suffix before matching with profile.
-    StringRef Fname = F.getName().split('.').first;
+    return getSamplesFor(F.getName().split('.').first);
+  }
+
+  /// Return the samples collected for function \p F.
+  virtual FunctionSamples *getSamplesFor(StringRef Fname) {
     std::string FGUID;
     Fname = getRepInFormat(Fname, getFormat(), FGUID);
-    if (Profiles.count(Fname))
-      return &Profiles[Fname];
+    auto It = Profiles.find(Fname);
+    if (It != Profiles.end())
+      return &It->second;
     return nullptr;
   }
 
   /// Return all the profiles.
   StringMap<FunctionSamples> &getProfiles() { return Profiles; }
 
   /// Report a parse error message.
   void reportError(int64_t LineNumber, Twine Msg) const {
protected:
   LLVMContext &Ctx;
 
   /// Memory buffer holding the profile file.
   std::unique_ptr<MemoryBuffer> Buffer;
 
   /// Profile summary information.
   std::unique_ptr<ProfileSummary> Summary;
 
+  /// Take ownership of the summary of this reader.
+  static std::unique_ptr<ProfileSummary>
+  takeSummary(SampleProfileReader &Reader) {
+    return std::move(Reader.Summary);
+  }
+
   /// Compute summary for this profile.
   void computeSummary();
 
   /// \brief The format of sample.
   SampleProfileFormat Format = SPF_None;
 };
 
 class SampleProfileReaderText : public SampleProfileReader {
protected:
   /// Function names in this profile.
   std::vector<std::string> Names;
 
   /// GCOV tags used to separate sections in the profile file.
   static const uint32_t GCOVTagAFDOFileNames = 0xaa000000;
   static const uint32_t GCOVTagAFDOFunction = 0xac000000;
 };
 
+class SampleProfileReaderItaniumRemapper : public SampleProfileReader {
+public:
+  SampleProfileReaderItaniumRemapper(
+      std::unique_ptr<MemoryBuffer> B, LLVMContext &C,
+      std::unique_ptr<SampleProfileReader> Underlying)
+      : SampleProfileReader(std::move(B), C, Underlying->getFormat()) {
+    Profiles = std::move(Underlying->getProfiles());
+    Summary = takeSummary(*Underlying);
+  }
+
+  /// Create a remapped sample profile from the given remapping file and
+  /// underlying samples.
+  static ErrorOr<std::unique_ptr<SampleProfileReader>>
+  create(const Twine &Filename, LLVMContext &C,
+         std::unique_ptr<SampleProfileReader> Underlying);
+
+  /// Read and validate the file header.
+  std::error_code readHeader() override { return sampleprof_error::success; }
+
+  /// Read sample profiles from the associated file.
+  std::error_code read() override;
+
+  /// Return the samples collected for function \p F.
+  FunctionSamples *getSamplesFor(StringRef FunctionName) override;
+  using SampleProfileReader::getSamplesFor;
+
+private:
+  ItaniumProfileRemappingReader Remappings;
+  DenseMap<ItaniumManglingCanonicalizer::Key, FunctionSamples*> SampleMap;
+};
+
 } // end namespace sampleprof
 
 } // end namespace llvm
 
 #endif // LLVM_PROFILEDATA_SAMPLEPROFREADER_H

include/llvm/Transforms/IPO/SampleProfile.h

 
 namespace llvm {
 
 class Module;
 
 /// The sample profiler data loader pass.
 class SampleProfileLoaderPass : public PassInfoMixin<SampleProfileLoaderPass> {
 public:
-  SampleProfileLoaderPass(std::string File = "", bool IsThinLTOPreLink = false)
-      : ProfileFileName(File), IsThinLTOPreLink(IsThinLTOPreLink) {}
+  SampleProfileLoaderPass(std::string File = "", std::string RemappingFile = "",
+                          bool IsThinLTOPreLink = false)
+      : ProfileFileName(File), ProfileRemappingFileName(RemappingFile),
+        IsThinLTOPreLink(IsThinLTOPreLink) {}
 
   PreservedAnalyses run(Module &M, ModuleAnalysisManager &AM);
 
 private:
   std::string ProfileFileName;
+  std::string ProfileRemappingFileName;
   bool IsThinLTOPreLink;
 };
 
 } // end namespace llvm
 
 #endif // LLVM_TRANSFORMS_SAMPLEPROFILE_H

include/llvm/Transforms/Instrumentation/PGOInstrumentation.h

 class PGOInstrumentationGen : public PassInfoMixin<PGOInstrumentationGen> {
 public:
   PreservedAnalyses run(Module &M, ModuleAnalysisManager &AM);
 };
 
 /// The profile annotation (profile-instr-use) pass for IR based PGO.
 class PGOInstrumentationUse : public PassInfoMixin<PGOInstrumentationUse> {
 public:
-  PGOInstrumentationUse(std::string Filename = "");
+  PGOInstrumentationUse(std::string Filename = "",
+                        std::string RemappingFilename = "");
 
   PreservedAnalyses run(Module &M, ModuleAnalysisManager &AM);
 
 private:
   std::string ProfileFileName;
+  std::string ProfileRemappingFileName;
 };
 
 /// The indirect function call promotion pass.
 class PGOIndirectCallPromotion : public PassInfoMixin<PGOIndirectCallPromotion> {
 public:
   PGOIndirectCallPromotion(bool IsInLTO = false, bool SamplePGO = false)
       : InLTO(IsInLTO), SamplePGO(SamplePGO) {}
 

lib/Demangle/ItaniumDemangle.cpp

 //===------------------------- ItaniumDemangle.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.
 //
 //===----------------------------------------------------------------------===//
 
 // FIXME: (possibly) incomplete list of features that clang mangles that this
 // file does not yet support:
 //   - C++ modules TS
 
+#include "llvm/Demangle/Demangle.h"
+
 #include "Compiler.h"
 #include "StringView.h"
 #include "Utility.h"
-#include "llvm/Demangle/Demangle.h"
+
+#ifndef STANDALONE_DEMANGLER
+#include "llvm/Demangle/Canonicalize.h"
+
+#include "llvm/ADT/DenseMap.h"
+#include "llvm/ADT/FoldingSet.h"
+#include "llvm/ADT/StringRef.h"
+#endif
 
 #include <cassert>
 #include <cctype>
 #include <cstdio>
 #include <cstdlib>
 #include <cstring>
 #include <numeric>
 #include <utility>
 #include <vector>
 
 namespace {
+#ifndef STANDALONE_DEMANGLER
+  void addString(llvm::FoldingSetNodeID &ID, StringView Str) {
+    ID.AddString(llvm::StringRef(Str.begin(), Str.size()));
+  }
+#endif
+
 // Base class of all AST nodes. The AST is built by the parser, then is
 // traversed by the printLeft/Right functions to produce a demangled string.
 class Node {
 public:
   enum Kind : unsigned char {
     KNodeArrayNode,
     KDotSuffix,
     KVendorExtQualType,
enum Kind : unsigned char {
     KVectorType,
     KParameterPack,
     KTemplateArgumentPack,
     KParameterPackExpansion,
     KTemplateArgs,
     KForwardTemplateReference,
     KNameWithTemplateArgs,
     KGlobalQualifiedName,
-    KStdQualifiedName,
     KExpandedSpecialSubstitution,
     KSpecialSubstitution,
     KCtorDtorName,
     KDtorName,
     KUnnamedTypeName,
     KClosureTypeName,
     KStructuredBindingName,
     KExpr,
public:
   /// affect how we format the output string.
   Cache FunctionCache;
 
   Node(Kind K_, Cache RHSComponentCache_ = Cache::No,
        Cache ArrayCache_ = Cache::No, Cache FunctionCache_ = Cache::No)
       : K(K_), RHSComponentCache(RHSComponentCache_), ArrayCache(ArrayCache_),
         FunctionCache(FunctionCache_) {}
 
+#ifndef STANDALONE_DEMANGLER
+  /// Compute a FoldingSetNodeID for the node created by invoking the
+  /// constructor with the given arguments.
+  static void profileCtor(llvm::FoldingSetNodeID &ID, Kind K, Cache = Cache::No,
+                          Cache = Cache::No, Cache = Cache::No) {
+    ID.AddInteger(K);
+    // Don't profile the cached values. They're not part of the value of the
+    // node for profiling purposes.
+  }
+
+  /// Compute a FoldingSetNodeID for this node.
+  virtual void profile(llvm::FoldingSetNodeID &ID) const { profileCtor(ID, K); }
+#endif
+
   bool hasRHSComponent(OutputStream &S) const {
     if (RHSComponentCache != Cache::Unknown)
       return RHSComponentCache == Cache::Yes;
     return hasRHSComponentSlow(S);
   }
 
   bool hasArray(OutputStream &S) const {
     if (ArrayCache != Cache::Unknown)
class NodeArray {
   Node **Elements;
   size_t NumElements;
 
 public:
   NodeArray() : Elements(nullptr), NumElements(0) {}
   NodeArray(Node **Elements_, size_t NumElements_)
       : Elements(Elements_), NumElements(NumElements_) {}
 
+#ifndef STANDALONE_DEMANGLER
+  void profile(llvm::FoldingSetNodeID &ID) {
+    ID.AddInteger(size());
+    for (Node *N : *this)
+      ID.AddPointer(N);
+  }
+#endif
+
   bool empty() const { return NumElements == 0; }
   size_t size() const { return NumElements; }
 
   Node **begin() const { return Elements; }
   Node **end() const { return Elements + NumElements; }
 
   Node *operator[](size_t Idx) const { return Elements[Idx]; }
 
for (size_t Idx = 0; Idx != NumElements; ++Idx) {
       FirstElement = false;
     }
   }
 };
 
 struct NodeArrayNode : Node {
   NodeArray Array;
   NodeArrayNode(NodeArray Array_) : Node(KNodeArrayNode), Array(Array_) {}
+
+#ifndef STANDALONE_DEMANGLER
+  static void profileCtor(llvm::FoldingSetNodeID &ID, NodeArray A) {
+    Node::profileCtor(ID, KNodeArrayNode);
+    A.profile(ID);
+  }
+  void profile(llvm::FoldingSetNodeID &ID) const override {
+    profileCtor(ID, Array);
+  }
+#endif
+
   void printLeft(OutputStream &S) const override {
     Array.printWithComma(S);
   }
 };
 
 class DotSuffix final : public Node {
   const Node *Prefix;
   const StringView Suffix;
 
 public:
-  DotSuffix(Node *Prefix_, StringView Suffix_)
+  DotSuffix(const Node *Prefix_, StringView Suffix_)
       : Node(KDotSuffix), Prefix(Prefix_), Suffix(Suffix_) {}
 
+#ifndef STANDALONE_DEMANGLER
+  static void profileCtor(llvm::FoldingSetNodeID &ID, const Node *Prefix,
+                          StringView Suffix) {
+    Node::profileCtor(ID, KDotSuffix);
+    ID.AddPointer(Prefix);
+    addString(ID, Suffix);
+  }
+  void profile(llvm::FoldingSetNodeID &ID) const override {
+    profileCtor(ID, Prefix, Suffix);
+  }
+#endif
+
   void printLeft(OutputStream &s) const override {
     Prefix->print(s);
     s += " (";
     s += Suffix;
     s += ")";
   }
 };
 
 class VendorExtQualType final : public Node {
   const Node *Ty;
   StringView Ext;
 
 public:
-  VendorExtQualType(Node *Ty_, StringView Ext_)
+  VendorExtQualType(const Node *Ty_, StringView Ext_)
       : Node(KVendorExtQualType), Ty(Ty_), Ext(Ext_) {}
 
+#ifndef STANDALONE_DEMANGLER
+  static void profileCtor(llvm::FoldingSetNodeID &ID, const Node *Ty,
+                          StringView Ext) {
+    Node::profileCtor(ID, KVendorExtQualType);
+    ID.AddPointer(Ty);
+    addString(ID, Ext);
+  }
+  void profile(llvm::FoldingSetNodeID &ID) const override {
+    profileCtor(ID, Ty, Ext);
+  }
+#endif
+
   void printLeft(OutputStream &S) const override {
     Ty->print(S);
     S += " ";
     S += Ext;
   }
 };
 
 enum FunctionRefQual : unsigned char {
if (Quals & QualConst)
       S += " const";
     if (Quals & QualVolatile)
       S += " volatile";
     if (Quals & QualRestrict)
       S += " restrict";
   }
 
 public:
-  QualType(Node *Child_, Qualifiers Quals_)
+  QualType(const Node *Child_, Qualifiers Quals_)
       : Node(KQualType, Child_->RHSComponentCache,
              Child_->ArrayCache, Child_->FunctionCache),
         Quals(Quals_), Child(Child_) {}
 
+#ifndef STANDALONE_DEMANGLER
+  static void profileCtor(llvm::FoldingSetNodeID &ID, const Node *Child,
+                          Qualifiers Quals) {
+    Node::profileCtor(ID, KQualType);
+    ID.AddPointer(Child);
+    ID.AddInteger(Quals);
+  }
+  void profile(llvm::FoldingSetNodeID &ID) const override {
+    profileCtor(ID, Child, Quals);
+  }
+#endif
+
   bool hasRHSComponentSlow(OutputStream &S) const override {
     return Child->hasRHSComponent(S);
   }
   bool hasArraySlow(OutputStream &S) const override {
     return Child->hasArray(S);
   }
   bool hasFunctionSlow(OutputStream &S) const override {
     return Child->hasFunction(S);
   }
 
   void printLeft(OutputStream &S) const override {
     Child->printLeft(S);
     printQuals(S);
   }
 
   void printRight(OutputStream &S) const override { Child->printRight(S); }
 };
 
 class ConversionOperatorType final : public Node {
   const Node *Ty;
 
 public:
-  ConversionOperatorType(Node *Ty_)
+  ConversionOperatorType(const Node *Ty_)
       : Node(KConversionOperatorType), Ty(Ty_) {}
 
+#ifndef STANDALONE_DEMANGLER
+  static void profileCtor(llvm::FoldingSetNodeID &ID, const Node *Ty) {
+    Node::profileCtor(ID, KConversionOperatorType);
+    ID.AddPointer(Ty);
+  }
+  void profile(llvm::FoldingSetNodeID &ID) const override {
+    profileCtor(ID, Ty);
+  }
+#endif
+
   void printLeft(OutputStream &S) const override {
     S += "operator ";
     Ty->print(S);
   }
 };
 
 class PostfixQualifiedType final : public Node {
   const Node *Ty;
   const StringView Postfix;
 
 public:
   PostfixQualifiedType(Node *Ty_, StringView Postfix_)
       : Node(KPostfixQualifiedType), Ty(Ty_), Postfix(Postfix_) {}
 
+#ifndef STANDALONE_DEMANGLER
+  static void profileCtor(llvm::FoldingSetNodeID &ID, const Node *Ty,
+                          StringView Postfix) {
+    Node::profileCtor(ID, KPostfixQualifiedType);
+    ID.AddPointer(Ty);
+    addString(ID, Postfix);
+  }
+  void profile(llvm::FoldingSetNodeID &ID) const override {
+    profileCtor(ID, Ty, Postfix);
+  }
+#endif
+
   void printLeft(OutputStream &s) const override {
     Ty->printLeft(s);
     s += Postfix;
   }
 };
 
 class NameType final : public Node {
   const StringView Name;
 
 public:
   NameType(StringView Name_) : Node(KNameType), Name(Name_) {}
 
+#ifndef STANDALONE_DEMANGLER
+  static void profileCtor(llvm::FoldingSetNodeID &ID, StringView Name) {
+    Node::profileCtor(ID, KNameType);
+    addString(ID, Name);
+  }
+  void profile(llvm::FoldingSetNodeID &ID) const override {
+    profileCtor(ID, Name);
+  }
+#endif
+
   StringView getName() const { return Name; }
   StringView getBaseName() const override { return Name; }
 
   void printLeft(OutputStream &s) const override { s += Name; }
 };
 
 class ElaboratedTypeSpefType : public Node {
   StringView Kind;
   Node *Child;
 public:
   ElaboratedTypeSpefType(StringView Kind_, Node *Child_)
       : Node(KElaboratedTypeSpefType), Kind(Kind_), Child(Child_) {}
 
+#ifndef STANDALONE_DEMANGLER
+  static void profileCtor(llvm::FoldingSetNodeID &ID, StringView Kind,
+                          Node *Child) {
+    Node::profileCtor(ID, KElaboratedTypeSpefType);
+    addString(ID, Kind);
+    ID.AddPointer(Child);
+  }
+  void profile(llvm::FoldingSetNodeID &ID) const override {
+    profileCtor(ID, Kind, Child);
+  }
+#endif
+
   void printLeft(OutputStream &S) const override {
     S += Kind;
     S += ' ';
     Child->print(S);
   }
 };
 
 struct AbiTagAttr : Node {
   Node *Base;
   StringView Tag;
 
   AbiTagAttr(Node* Base_, StringView Tag_)
       : Node(KAbiTagAttr, Base_->RHSComponentCache,
              Base_->ArrayCache, Base_->FunctionCache),
         Base(Base_), Tag(Tag_) {}
 
+#ifndef STANDALONE_DEMANGLER
+  static void profileCtor(llvm::FoldingSetNodeID &ID, Node *Base,
+                          StringView Tag) {
+    Node::profileCtor(ID, KAbiTagAttr);
+    ID.AddPointer(Base);
+    addString(ID, Tag);
+  }
+  void profile(llvm::FoldingSetNodeID &ID) const override {
+    profileCtor(ID, Base, Tag);
+  }
+#endif
+
   void printLeft(OutputStream &S) const override {
     Base->printLeft(S);
     S += "[abi:";
     S += Tag;
     S += "]";
   }
 };
 
 class EnableIfAttr : public Node {
   NodeArray Conditions;
 public:
   EnableIfAttr(NodeArray Conditions_)
       : Node(KEnableIfAttr), Conditions(Conditions_) {}
 
+#ifndef STANDALONE_DEMANGLER
+  static void profileCtor(llvm::FoldingSetNodeID &ID, NodeArray Conditions) {
+    Node::profileCtor(ID, KEnableIfAttr);
+    Conditions.profile(ID);
+  }
+  void profile(llvm::FoldingSetNodeID &ID) const override {
+    profileCtor(ID, Conditions);
+  }
+#endif
+
   void printLeft(OutputStream &S) const override {
     S += " [enable_if:";
     Conditions.printWithComma(S);
     S += ']';
   }
 };
 
 class ObjCProtoName : public Node {
-  Node *Ty;
+  const Node *Ty;
   StringView Protocol;
 
   friend class PointerType;
 
 public:
-  ObjCProtoName(Node *Ty_, StringView Protocol_)
+  ObjCProtoName(const Node *Ty_, StringView Protocol_)
       : Node(KObjCProtoName), Ty(Ty_), Protocol(Protocol_) {}
 
+#ifndef STANDALONE_DEMANGLER
+  static void profileCtor(llvm::FoldingSetNodeID &ID, const Node *Ty,
+                          StringView Protocol) {
+    Node::profileCtor(ID, KObjCProtoName);
+    ID.AddPointer(Ty);
+    addString(ID, Protocol);
+  }
+  void profile(llvm::FoldingSetNodeID &ID) const override {
+    profileCtor(ID, Ty, Protocol);
+  }
+#endif
+
   bool isObjCObject() const {
     return Ty->getKind() == KNameType &&
-           static_cast<NameType *>(Ty)->getName() == "objc_object";
+           static_cast<const NameType *>(Ty)->getName() == "objc_object";
   }
 
   void printLeft(OutputStream &S) const override {
     Ty->print(S);
     S += "<";
     S += Protocol;
     S += ">";
   }
 };
 
 class PointerType final : public Node {
   const Node *Pointee;
 
 public:
-  PointerType(Node *Pointee_)
+  PointerType(const Node *Pointee_)
       : Node(KPointerType, Pointee_->RHSComponentCache),
         Pointee(Pointee_) {}
 
+#ifndef STANDALONE_DEMANGLER
+  static void profileCtor(llvm::FoldingSetNodeID &ID, const Node *Pointee) {
+    Node::profileCtor(ID, KPointerType);
+    ID.AddPointer(Pointee);
+  }
+  void profile(llvm::FoldingSetNodeID &ID) const override {
+    profileCtor(ID, Pointee);
+  }
+#endif
+
   bool hasRHSComponentSlow(OutputStream &S) const override {
     return Pointee->hasRHSComponent(S);
   }
 
   void printLeft(OutputStream &s) const override {
     // We rewrite objc_object<SomeProtocol>* into id<SomeProtocol>.
     if (Pointee->getKind() != KObjCProtoName ||
         !static_cast<const ObjCProtoName *>(Pointee)->isObjCObject()) {
for (;;) {
       auto *RT = static_cast<const ReferenceType *>(SN);
       SoFar.second = RT->Pointee;
       SoFar.first = std::min(SoFar.first, RT->RK);
     }
     return SoFar;
   }
 
 public:
-  ReferenceType(Node *Pointee_, ReferenceKind RK_)
+  ReferenceType(const Node *Pointee_, ReferenceKind RK_)
       : Node(KReferenceType, Pointee_->RHSComponentCache),
         Pointee(Pointee_), RK(RK_) {}
 
+#ifndef STANDALONE_DEMANGLER
+  static void profileCtor(llvm::FoldingSetNodeID &ID, const Node *Pointee,
+                          ReferenceKind RK) {
+    Node::profileCtor(ID, KReferenceType);
+    ID.AddPointer(Pointee);
+    ID.AddInteger((unsigned)RK);
+  }
+  void profile(llvm::FoldingSetNodeID &ID) const override {
+    profileCtor(ID, Pointee, RK);
+  }
+#endif
+
   bool hasRHSComponentSlow(OutputStream &S) const override {
     return Pointee->hasRHSComponent(S);
   }
 
   void printLeft(OutputStream &s) const override {
     if (Printing)
       return;
     SwapAndRestore<bool> SavePrinting(Printing, true);
#endif
   }
 };
 
 class PointerToMemberType final : public Node {
   const Node *ClassType;
   const Node *MemberType;
 
 public:
-  PointerToMemberType(Node *ClassType_, Node *MemberType_)
+  PointerToMemberType(const Node *ClassType_, const Node *MemberType_)
       : Node(KPointerToMemberType, MemberType_->RHSComponentCache),
         ClassType(ClassType_), MemberType(MemberType_) {}
 
+#ifndef STANDALONE_DEMANGLER
+  static void profileCtor(llvm::FoldingSetNodeID &ID, const Node *ClassType,
+                          const Node *MemberType) {
+    Node::profileCtor(ID, KPointerToMemberType);
+    ID.AddPointer(ClassType);
+    ID.AddPointer(MemberType);
+  }
+  void profile(llvm::FoldingSetNodeID &ID) const override {
+    profileCtor(ID, ClassType, MemberType);
+  }
+#endif
+
   bool hasRHSComponentSlow(OutputStream &S) const override {
     return MemberType->hasRHSComponent(S);
   }
 
   void printLeft(OutputStream &s) const override {
     MemberType->printLeft(s);
     if (MemberType->hasArray(s) || MemberType->hasFunction(s))
       s += "(";
/* implicit */ NodeOrString(StringView Str) {
     First = static_cast<const void *>(FirstChar);
     Second = static_cast<const void *>(SecondChar);
   }
 
   /* implicit */ NodeOrString(Node *N)
       : First(static_cast<const void *>(N)), Second(nullptr) {}
   NodeOrString() : First(nullptr), Second(nullptr) {}
 
+  void profile(llvm::FoldingSetNodeID &ID) {
+    if (isEmpty()) {
+      ID.AddInteger(0);
+    } else if (isNode()) {
+      ID.AddInteger(1);
+      ID.AddPointer(asNode());
+    } else {
+      ID.AddInteger(2);
+      addString(ID, asString());
+    }
+  }
+
   bool isString() const { return Second && First; }
   bool isNode() const { return First && !Second; }
   bool isEmpty() const { return !First && !Second; }
 
   StringView asString() const {
     assert(isString());
     return StringView(static_cast<const char *>(First),
                       static_cast<const char *>(Second));
   }
 
   const Node *asNode() const {
     assert(isNode());
     return static_cast<const Node *>(First);
   }
 };
 
 class ArrayType final : public Node {
-  Node *Base;
+  const Node *Base;
   NodeOrString Dimension;
 
 public:
-  ArrayType(Node *Base_, NodeOrString Dimension_)
+  ArrayType(const Node *Base_, NodeOrString Dimension_ = NodeOrString())
       : Node(KArrayType,
              /*RHSComponentCache=*/Cache::Yes,
              /*ArrayCache=*/Cache::Yes),
         Base(Base_), Dimension(Dimension_) {}
 
-  // Incomplete array type.
-  ArrayType(Node *Base_)
-      : Node(KArrayType,
-             /*RHSComponentCache=*/Cache::Yes,
-             /*ArrayCache=*/Cache::Yes),
-        Base(Base_) {}
+#ifndef STANDALONE_DEMANGLER
+  static void profileCtor(llvm::FoldingSetNodeID &ID, const Node *Base,
+                          NodeOrString Dimension = NodeOrString()) {
+    Node::profileCtor(ID, KArrayType);
+    ID.AddPointer(Base);
+    Dimension.profile(ID);
+  }
+  void profile(llvm::FoldingSetNodeID &ID) const override {
+    profileCtor(ID, Base, Dimension);
+  }
+#endif
 
   bool hasRHSComponentSlow(OutputStream &) const override { return true; }
   bool hasArraySlow(OutputStream &) const override { return true; }
 
   void printLeft(OutputStream &S) const override { Base->printLeft(S); }
 
   void printRight(OutputStream &S) const override {
     if (S.back() != ']')
       S += " ";
     S += "[";
     if (Dimension.isString())
       S += Dimension.asString();
     else if (Dimension.isNode())
       Dimension.asNode()->print(S);
     S += "]";
     Base->printRight(S);
   }
 };
 
 class FunctionType final : public Node {
-  Node *Ret;
+  const Node *Ret;
   NodeArray Params;
   Qualifiers CVQuals;
   FunctionRefQual RefQual;
-  Node *ExceptionSpec;
+  const Node *ExceptionSpec;
 
 public:
-  FunctionType(Node *Ret_, NodeArray Params_, Qualifiers CVQuals_,
-               FunctionRefQual RefQual_, Node *ExceptionSpec_)
+  FunctionType(const Node *Ret_, NodeArray Params_, Qualifiers CVQuals_,
+               FunctionRefQual RefQual_, const Node *ExceptionSpec_)
       : Node(KFunctionType,
              /*RHSComponentCache=*/Cache::Yes, /*ArrayCache=*/Cache::No,
              /*FunctionCache=*/Cache::Yes),
         Ret(Ret_), Params(Params_), CVQuals(CVQuals_), RefQual(RefQual_),
         ExceptionSpec(ExceptionSpec_) {}
 
+#ifndef STANDALONE_DEMANGLER
+  static void profileCtor(llvm::FoldingSetNodeID &ID, const Node *Ret,
+                          NodeArray Params, Qualifiers CVQuals,
+                          FunctionRefQual RefQual, const Node *ExceptionSpec) {
+    Node::profileCtor(ID, KFunctionType);
+    ID.AddPointer(Ret);
+    Params.profile(ID);
+    ID.AddInteger((unsigned)CVQuals);
+    ID.AddInteger((unsigned)RefQual);
+    ID.AddPointer(ExceptionSpec);
+  }
+  void profile(llvm::FoldingSetNodeID &ID) const override {
+    profileCtor(ID, Ret, Params, CVQuals, RefQual, ExceptionSpec);
+  }
+#endif
+
   bool hasRHSComponentSlow(OutputStream &) const override { return true; }
   bool hasFunctionSlow(OutputStream &) const override { return true; }
 
   // Handle C++'s ... quirky decl grammar by using the left & right
   // distinction. Consider:
   //   int (*f(float))(char) {}
   // f is a function that takes a float and returns a pointer to a function
   // that takes a char and returns an int. If we're trying to print f, start
void printRight(OutputStream &S) const override {
     if (ExceptionSpec != nullptr) {
       S += ' ';
       ExceptionSpec->print(S);
     }
   }
 };
 
 class NoexceptSpec : public Node {
-  Node *E;
+  const Node *E;
 public:
-  NoexceptSpec(Node *E_) : Node(KNoexceptSpec), E(E_) {}
+  NoexceptSpec(const Node *E_) : Node(KNoexceptSpec), E(E_) {}
+
+#ifndef STANDALONE_DEMANGLER
+  static void profileCtor(llvm::FoldingSetNodeID &ID, const Node *E) {
+    Node::profileCtor(ID, KNoexceptSpec);
+    ID.AddPointer(E);
+  }
+  void profile(llvm::FoldingSetNodeID &ID) const override {
+    profileCtor(ID, E);
+  }
+#endif
 
   void printLeft(OutputStream &S) const override {
     S += "noexcept(";
     E->print(S);
     S += ")";
   }
 };
 
 class DynamicExceptionSpec : public Node {
   NodeArray Types;
 public:
   DynamicExceptionSpec(NodeArray Types_)
       : Node(KDynamicExceptionSpec), Types(Types_) {}
 
+#ifndef STANDALONE_DEMANGLER
+  static void profileCtor(llvm::FoldingSetNodeID &ID, NodeArray Types) {
+    Node::profileCtor(ID, KDynamicExceptionSpec);
+    Types.profile(ID);
+  }
+  void profile(llvm::FoldingSetNodeID &ID) const override {
+    profileCtor(ID, Types);
+  }
+#endif
+
   void printLeft(OutputStream &S) const override {
     S += "throw(";
     Types.printWithComma(S);
     S += ')';
   }
 };
 
 class FunctionEncoding final : public Node {
-  Node *Ret;
-  Node *Name;
+  const Node *Ret;
+  const Node *Name;
   NodeArray Params;
-  Node *Attrs;
+  const Node *Attrs;
   Qualifiers CVQuals;
   FunctionRefQual RefQual;
 
 public:
-  FunctionEncoding(Node *Ret_, Node *Name_, NodeArray Params_,
-                   Node *Attrs_, Qualifiers CVQuals_, FunctionRefQual RefQual_)
+  FunctionEncoding(const Node *Ret_, const Node *Name_, NodeArray Params_,
+                   const Node *Attrs_, Qualifiers CVQuals_,
+                   FunctionRefQual RefQual_)
       : Node(KFunctionEncoding,
              /*RHSComponentCache=*/Cache::Yes, /*ArrayCache=*/Cache::No,
              /*FunctionCache=*/Cache::Yes),
         Ret(Ret_), Name(Name_), Params(Params_), Attrs(Attrs_),
         CVQuals(CVQuals_), RefQual(RefQual_) {}
 
+#ifndef STANDALONE_DEMANGLER
+  static void profileCtor(llvm::FoldingSetNodeID &ID, const Node *Ret,
+                          const Node *Name, NodeArray Params, const Node *Attrs,
+                          Qualifiers CVQuals, FunctionRefQual RefQual) {
+    Node::profileCtor(ID, KFunctionEncoding);
+    ID.AddPointer(Ret);
+    ID.AddPointer(Name);
+    Params.profile(ID);
+    ID.AddPointer(Attrs);
+    ID.AddInteger((unsigned)CVQuals);
+    ID.AddInteger((unsigned)RefQual);
+  }
+  void profile(llvm::FoldingSetNodeID &ID) const override {
+    profileCtor(ID, Ret, Name, Params, Attrs, CVQuals, RefQual);
+  }
+#endif
+
   Qualifiers getCVQuals() const { return CVQuals; }
   FunctionRefQual getRefQual() const { return RefQual; }
   NodeArray getParams() const { return Params; }
-  Node *getReturnType() const { return Ret; }
+  const Node *getReturnType() const { return Ret; }
 
   bool hasRHSComponentSlow(OutputStream &) const override { return true; }
   bool hasFunctionSlow(OutputStream &) const override { return true; }
 
-  Node *getName() { return const_cast<Node *>(Name); }
+  const Node *getName() const { return Name; }
 
   void printLeft(OutputStream &S) const override {
     if (Ret) {
       Ret->printLeft(S);
       if (!Ret->hasRHSComponent(S))
         S += " ";
     }
     Name->print(S);
if (Attrs != nullptr)
       Attrs->print(S);
   }
 };
 
 class LiteralOperator : public Node {
   const Node *OpName;
 
 public:
-  LiteralOperator(Node *OpName_) : Node(KLiteralOperator), OpName(OpName_) {}
+  LiteralOperator(const Node *OpName_)
+      : Node(KLiteralOperator), OpName(OpName_) {}
+
+#ifndef STANDALONE_DEMANGLER
+  static void profileCtor(llvm::FoldingSetNodeID &ID, const Node *OpName) {
+    Node::profileCtor(ID, KLiteralOperator);
+    ID.AddPointer(OpName);
+  }
+  void profile(llvm::FoldingSetNodeID &ID) const override {
+    profileCtor(ID, OpName);
+  }
+#endif
 
   void printLeft(OutputStream &S) const override {
     S += "operator\"\" ";
     OpName->print(S);
   }
 };
 
 class SpecialName final : public Node {
   const StringView Special;
   const Node *Child;
 
 public:
-  SpecialName(StringView Special_, Node* Child_)
+  SpecialName(StringView Special_, const Node *Child_)
       : Node(KSpecialName), Special(Special_), Child(Child_) {}
 
+#ifndef STANDALONE_DEMANGLER
+  static void profileCtor(llvm::FoldingSetNodeID &ID, StringView Special,
+                          const Node *Child) {
+    Node::profileCtor(ID, KSpecialName);
+    addString(ID, Special);
+    ID.AddPointer(Child);
+  }
+  void profile(llvm::FoldingSetNodeID &ID) const override {
+    profileCtor(ID, Special, Child);
+  }
+#endif
+
   void printLeft(OutputStream &S) const override {
     S += Special;
     Child->print(S);
   }
 };
 
 class CtorVtableSpecialName final : public Node {
   const Node *FirstType;
   const Node *SecondType;
 
 public:
-  CtorVtableSpecialName(Node *FirstType_, Node *SecondType_)
+  CtorVtableSpecialName(const Node *FirstType_, const Node *SecondType_)
       : Node(KCtorVtableSpecialName),
         FirstType(FirstType_), SecondType(SecondType_) {}
 
+#ifndef STANDALONE_DEMANGLER
+  static void profileCtor(llvm::FoldingSetNodeID &ID, const Node *FirstType,
+                          const Node *SecondType) {
+    Node::profileCtor(ID, KCtorVtableSpecialName);
+    ID.AddPointer(FirstType);
+    ID.AddPointer(SecondType);
+  }
+  void profile(llvm::FoldingSetNodeID &ID) const override {
+    profileCtor(ID, FirstType, SecondType);
+  }
+#endif
+
   void printLeft(OutputStream &S) const override {
     S += "construction vtable for ";
     FirstType->print(S);
     S += "-in-";
     SecondType->print(S);
   }
 };
 
 struct NestedName : Node {
   Node *Qual;
   Node *Name;
 
   NestedName(Node *Qual_, Node *Name_)
       : Node(KNestedName), Qual(Qual_), Name(Name_) {}
 
+#ifndef STANDALONE_DEMANGLER
+  static void profileCtor(llvm::FoldingSetNodeID &ID, Node *Qual,
+                          Node *Name) {
+    Node::profileCtor(ID, KNestedName);
+    ID.AddPointer(Qual);
+    ID.AddPointer(Name);
+  }
+  void profile(llvm::FoldingSetNodeID &ID) const override {
+    profileCtor(ID, Qual, Name);
+  }
+#endif
+
   StringView getBaseName() const override { return Name->getBaseName(); }
 
   void printLeft(OutputStream &S) const override {
     Qual->print(S);
     S += "::";
     Name->print(S);
   }
 };
 
 struct LocalName : Node {
   Node *Encoding;
   Node *Entity;
 
   LocalName(Node *Encoding_, Node *Entity_)
       : Node(KLocalName), Encoding(Encoding_), Entity(Entity_) {}
 
+#ifndef STANDALONE_DEMANGLER
+  static void profileCtor(llvm::FoldingSetNodeID &ID, Node *Encoding,
+                          Node *Entity) {
+    Node::profileCtor(ID, KLocalName);
+    ID.AddPointer(Encoding);
+    ID.AddPointer(Entity);
+  }
+  void profile(llvm::FoldingSetNodeID &ID) const override {
+    profileCtor(ID, Encoding, Entity);
+  }
+#endif
+
   void printLeft(OutputStream &S) const override {
     Encoding->print(S);
     S += "::";
     Entity->print(S);
   }
 };
 
 class QualifiedName final : public Node {
   // qualifier::name
   const Node *Qualifier;
   const Node *Name;
 
 public:
-  QualifiedName(Node* Qualifier_, Node* Name_)
+  QualifiedName(const Node *Qualifier_, const Node *Name_)
       : Node(KQualifiedName), Qualifier(Qualifier_), Name(Name_) {}
 
+#ifndef STANDALONE_DEMANGLER
+  static void profileCtor(llvm::FoldingSetNodeID &ID, const Node *Qualifier,
+                          const Node *Name) {
+    Node::profileCtor(ID, KQualifiedName);
+    ID.AddPointer(Qualifier);
+    ID.AddPointer(Name);
+  }
+  void profile(llvm::FoldingSetNodeID &ID) const override {
+    profileCtor(ID, Qualifier, Name);
+  }
+#endif
+
   StringView getBaseName() const override { return Name->getBaseName(); }
 
   void printLeft(OutputStream &S) const override {
     Qualifier->print(S);
     S += "::";
     Name->print(S);
   }
 };
 
 class VectorType final : public Node {
   const Node *BaseType;
   const NodeOrString Dimension;
+  // FIXME: Is this just the same as '!BaseType'?
   const bool IsPixel;
 
 public:
   VectorType(NodeOrString Dimension_)
       : Node(KVectorType), BaseType(nullptr), Dimension(Dimension_),
         IsPixel(true) {}
-  VectorType(Node *BaseType_, NodeOrString Dimension_)
+  VectorType(const Node *BaseType_, NodeOrString Dimension_)
       : Node(KVectorType), BaseType(BaseType_),
         Dimension(Dimension_), IsPixel(false) {}
 
+#ifndef STANDALONE_DEMANGLER
+  static void profileCtor(llvm::FoldingSetNodeID &ID, NodeOrString Dimension) {
+    Node::profileCtor(ID, KVectorType);
+    ID.AddBoolean(true); // IsPixel
+    Dimension.profile(ID);
+  }
+  static void profileCtor(llvm::FoldingSetNodeID &ID, const Node *BaseType,
+                          NodeOrString Dimension) {
+    Node::profileCtor(ID, KVectorType);
+    ID.AddBoolean(false); // IsPixel
+    ID.AddPointer(BaseType);
+    Dimension.profile(ID);
+  }
+  void profile(llvm::FoldingSetNodeID &ID) const override {
+    if (IsPixel)
+      profileCtor(ID, Dimension);
+    else
+      profileCtor(ID, BaseType, Dimension);
+  }
+#endif
+
   void printLeft(OutputStream &S) const override {
     if (IsPixel) {
       S += "pixel vector[";
       S += Dimension.asString();
       S += "]";
     } else {
       BaseType->print(S);
       S += " vector[";
if (std::all_of(Data.begin(), Data.end(), [](Node* P) {
         }))
       FunctionCache = Cache::No;
     if (std::all_of(Data.begin(), Data.end(), [](Node* P) {
           return P->RHSComponentCache == Cache::No;
         }))
       RHSComponentCache = Cache::No;
   }
 
+#ifndef STANDALONE_DEMANGLER
+  static void profileCtor(llvm::FoldingSetNodeID &ID, NodeArray Data) {
+    Node::profileCtor(ID, KParameterPack);
+    Data.profile(ID);
+  }
+  void profile(llvm::FoldingSetNodeID &ID) const override {
+    profileCtor(ID, Data);
+  }
+#endif
+
   bool hasRHSComponentSlow(OutputStream &S) const override {
     initializePackExpansion(S);
     size_t Idx = S.CurrentPackIndex;
     return Idx < Data.size() && Data[Idx]->hasRHSComponent(S);
   }
   bool hasArraySlow(OutputStream &S) const override {
     initializePackExpansion(S);
     size_t Idx = S.CurrentPackIndex;

 /// TemplateParams table if the <template-args> this pack belongs to apply to an
 /// <encoding>.
 class TemplateArgumentPack final : public Node {
   NodeArray Elements;
 public:
   TemplateArgumentPack(NodeArray Elements_)
       : Node(KTemplateArgumentPack), Elements(Elements_) {}
 
+#ifndef STANDALONE_DEMANGLER
+  static void profileCtor(llvm::FoldingSetNodeID &ID, NodeArray Elements) {
+    Node::profileCtor(ID, KTemplateArgumentPack);
+    Elements.profile(ID);
+  }
+  void profile(llvm::FoldingSetNodeID &ID) const override {
+    profileCtor(ID, Elements);
+  }
+#endif
+
   NodeArray getElements() const { return Elements; }
 
   void printLeft(OutputStream &S) const override {
     Elements.printWithComma(S);
   }
 };
 
 /// A pack expansion. Below this node, there are some unexpanded ParameterPacks
 /// which each have Child->ParameterPackSize elements.
 class ParameterPackExpansion final : public Node {
   const Node *Child;
 
 public:
-  ParameterPackExpansion(Node* Child_)
+  ParameterPackExpansion(const Node *Child_)
       : Node(KParameterPackExpansion), Child(Child_) {}
 
+#ifndef STANDALONE_DEMANGLER
+  static void profileCtor(llvm::FoldingSetNodeID &ID, const Node *Child) {
+    Node::profileCtor(ID, KParameterPackExpansion);
+    ID.AddPointer(Child);
+  }
+  void profile(llvm::FoldingSetNodeID &ID) const override {
+    profileCtor(ID, Child);
+  }
+#endif
+
   const Node *getChild() const { return Child; }
 
   void printLeft(OutputStream &S) const override {
     constexpr unsigned Max = std::numeric_limits<unsigned>::max();
     SwapAndRestore<unsigned> SavePackIdx(S.CurrentPackIndex, Max);
     SwapAndRestore<unsigned> SavePackMax(S.CurrentPackMax, Max);
     size_t StreamPos = S.getCurrentPosition();
 

 };
 
 class TemplateArgs final : public Node {
   NodeArray Params;
 
 public:
   TemplateArgs(NodeArray Params_) : Node(KTemplateArgs), Params(Params_) {}
 
+#ifndef STANDALONE_DEMANGLER
+  static void profileCtor(llvm::FoldingSetNodeID &ID, NodeArray Params) {
+    Node::profileCtor(ID, KTemplateArgs);
+    Params.profile(ID);
+  }
+  void profile(llvm::FoldingSetNodeID &ID) const override {
+    profileCtor(ID, Params);
+  }
+#endif
+
   NodeArray getParams() { return Params; }
 
   void printLeft(OutputStream &S) const override {
     S += "<";
     Params.printWithComma(S);
     if (S.back() == '>')
       S += " ";
     S += ">";
struct ForwardTemplateReference : Node {
   // out if more than one print* function is active.
   mutable bool Printing = false;
 
   ForwardTemplateReference(size_t Index_)
       : Node(KForwardTemplateReference, Cache::Unknown, Cache::Unknown,
              Cache::Unknown),
         Index(Index_) {}
 
+  // We don't canonicalize these, because the index would mean different things
+  // in different mangled names, and we can't rely on the Ref being known in
+  // time.
+#ifndef STANDALONE_DEMANGLER
+  static void profileCtor(llvm::FoldingSetNodeID &ID, size_t Index) = delete;
+  void profile(llvm::FoldingSetNodeID &ID) const override {
+    llvm_unreachable("forward template reference should not be canonicalized");
+  }
+#endif
+
   bool hasRHSComponentSlow(OutputStream &S) const override {
     if (Printing)
       return false;
     SwapAndRestore<bool> SavePrinting(Printing, true);
     return Ref->hasRHSComponent(S);
   }
   bool hasArraySlow(OutputStream &S) const override {
     if (Printing)

 struct NameWithTemplateArgs : Node {
   // name<template_args>
   Node *Name;
   Node *TemplateArgs;
 
   NameWithTemplateArgs(Node *Name_, Node *TemplateArgs_)
       : Node(KNameWithTemplateArgs), Name(Name_), TemplateArgs(TemplateArgs_) {}
 
+#ifndef STANDALONE_DEMANGLER
+  static void profileCtor(llvm::FoldingSetNodeID &ID, Node *Name,
+                          Node *TemplateArgs) {
+    Node::profileCtor(ID, KNameWithTemplateArgs);
+    ID.AddPointer(Name);
+    ID.AddPointer(TemplateArgs);
+  }
+  void profile(llvm::FoldingSetNodeID &ID) const override {
+    profileCtor(ID, Name, TemplateArgs);
+  }
+#endif
+
   StringView getBaseName() const override { return Name->getBaseName(); }
 
   void printLeft(OutputStream &S) const override {
     Name->print(S);
     TemplateArgs->print(S);
   }
 };
 
 class GlobalQualifiedName final : public Node {
   Node *Child;
 
 public:
   GlobalQualifiedName(Node* Child_)
       : Node(KGlobalQualifiedName), Child(Child_) {}
 
-  StringView getBaseName() const override { return Child->getBaseName(); }
-
-  void printLeft(OutputStream &S) const override {
-    S += "::";
-    Child->print(S);
+#ifndef STANDALONE_DEMANGLER
+  static void profileCtor(llvm::FoldingSetNodeID &ID, Node *Child) {
+    Node::profileCtor(ID, KGlobalQualifiedName);
+    ID.AddPointer(Child);
   }
-};
-
-struct StdQualifiedName : Node {
-  Node *Child;
-
-  StdQualifiedName(Node *Child_) : Node(KStdQualifiedName), Child(Child_) {}
+  void profile(llvm::FoldingSetNodeID &ID) const override {
+    profileCtor(ID, Child);
+  }
+#endif
 
   StringView getBaseName() const override { return Child->getBaseName(); }
 
   void printLeft(OutputStream &S) const override {
-    S += "std::";
+    S += "::";
     Child->print(S);
   }
 };
 
 enum class SpecialSubKind {
   allocator,
   basic_string,
   string,
   istream,
   ostream,
   iostream,
 };
 
 class ExpandedSpecialSubstitution final : public Node {
   SpecialSubKind SSK;
 
 public:
   ExpandedSpecialSubstitution(SpecialSubKind SSK_)
       : Node(KExpandedSpecialSubstitution), SSK(SSK_) {}
 
+#ifndef STANDALONE_DEMANGLER
+  static void profileCtor(llvm::FoldingSetNodeID &ID, SpecialSubKind SSK) {
+    Node::profileCtor(ID, KExpandedSpecialSubstitution);
+    ID.AddInteger((unsigned)SSK);
+  }
+  void profile(llvm::FoldingSetNodeID &ID) const override {
+    profileCtor(ID, SSK);
+  }
+#endif
+
   StringView getBaseName() const override {
     switch (SSK) {
     case SpecialSubKind::allocator:
       return StringView("allocator");
     case SpecialSubKind::basic_string:
       return StringView("basic_string");
     case SpecialSubKind::string:
       return StringView("basic_string");

 
 class SpecialSubstitution final : public Node {
 public:
   SpecialSubKind SSK;
 
   SpecialSubstitution(SpecialSubKind SSK_)
       : Node(KSpecialSubstitution), SSK(SSK_) {}
 
+#ifndef STANDALONE_DEMANGLER
+  static void profileCtor(llvm::FoldingSetNodeID &ID, SpecialSubKind SSK) {
+    Node::profileCtor(ID, KSpecialSubstitution);
+    ID.AddInteger((unsigned)SSK);
+  }
+  void profile(llvm::FoldingSetNodeID &ID) const override {
+    profileCtor(ID, SSK);
+  }
+#endif
+
   StringView getBaseName() const override {
     switch (SSK) {
     case SpecialSubKind::allocator:
       return StringView("allocator");
     case SpecialSubKind::basic_string:
       return StringView("basic_string");
     case SpecialSubKind::string:
       return StringView("string");
#endif
   }
 };
 
 class CtorDtorName final : public Node {
   const Node *Basename;
   const bool IsDtor;
 
 public:
-  CtorDtorName(Node *Basename_, bool IsDtor_)
+  CtorDtorName(const Node *Basename_, bool IsDtor_)
       : Node(KCtorDtorName), Basename(Basename_), IsDtor(IsDtor_) {}
 
+#ifndef STANDALONE_DEMANGLER
+  static void profileCtor(llvm::FoldingSetNodeID &ID, const Node *Basename,
+                          bool IsDtor) {
+    Node::profileCtor(ID, KCtorDtorName);
+    ID.AddPointer(Basename);
+    ID.AddBoolean(IsDtor);
+  }
+  void profile(llvm::FoldingSetNodeID &ID) const override {
+    profileCtor(ID, Basename, IsDtor);
+  }
+#endif
+
   void printLeft(OutputStream &S) const override {
     if (IsDtor)
       S += "~";
     S += Basename->getBaseName();
   }
 };
 
 class DtorName : public Node {
   const Node *Base;
 
 public:
-  DtorName(Node *Base_) : Node(KDtorName), Base(Base_) {}
+  DtorName(const Node *Base_) : Node(KDtorName), Base(Base_) {}
+
+#ifndef STANDALONE_DEMANGLER
+  static void profileCtor(llvm::FoldingSetNodeID &ID, const Node *Base) {
+    Node::profileCtor(ID, KDtorName);
+    ID.AddPointer(Base);
+  }
+  void profile(llvm::FoldingSetNodeID &ID) const override {
+    profileCtor(ID, Base);
+  }
+#endif
 
   void printLeft(OutputStream &S) const override {
     S += "~";
     Base->printLeft(S);
   }
 };
 
 class UnnamedTypeName : public Node {
   const StringView Count;
 
 public:
   UnnamedTypeName(StringView Count_) : Node(KUnnamedTypeName), Count(Count_) {}
 
+#ifndef STANDALONE_DEMANGLER
+  static void profileCtor(llvm::FoldingSetNodeID &ID, StringView Count) {
+    Node::profileCtor(ID, KUnnamedTypeName);
+    addString(ID, Count);
+  }
+  void profile(llvm::FoldingSetNodeID &ID) const override {
+    profileCtor(ID, Count);
+  }
+#endif
+
   void printLeft(OutputStream &S) const override {
     S += "'unnamed";
     S += Count;
     S += "\'";
   }
 };
 
 class ClosureTypeName : public Node {
   NodeArray Params;
   StringView Count;
 
 public:
   ClosureTypeName(NodeArray Params_, StringView Count_)
       : Node(KClosureTypeName), Params(Params_), Count(Count_) {}
 
+#ifndef STANDALONE_DEMANGLER
+  static void profileCtor(llvm::FoldingSetNodeID &ID, NodeArray Params,
+                          StringView Count) {
+    Node::profileCtor(ID, KClosureTypeName);
+    Params.profile(ID);
+    addString(ID, Count);
+  }
+  void profile(llvm::FoldingSetNodeID &ID) const override {
+    profileCtor(ID, Params, Count);
+  }
+#endif
+
   void printLeft(OutputStream &S) const override {
     S += "\'lambda";
     S += Count;
     S += "\'(";
     Params.printWithComma(S);
     S += ")";
   }
 };
 
 class StructuredBindingName : public Node {
   NodeArray Bindings;
 public:
   StructuredBindingName(NodeArray Bindings_)
       : Node(KStructuredBindingName), Bindings(Bindings_) {}
 
+#ifndef STANDALONE_DEMANGLER
+  static void profileCtor(llvm::FoldingSetNodeID &ID, NodeArray Bindings) {
+    Node::profileCtor(ID, KStructuredBindingName);
+    Bindings.profile(ID);
+  }
+  void profile(llvm::FoldingSetNodeID &ID) const override {
+    profileCtor(ID, Bindings);
+  }
+#endif
+
   void printLeft(OutputStream &S) const override {
     S += '[';
     Bindings.printWithComma(S);
     S += ']';
   }
 };
 
 // -- Expression Nodes --
 
 struct Expr : public Node {
+  /// Expr kinds, used for profiling.
+  enum ExprKind : unsigned char {
+    KBinaryExpr,
+    KArraySubscriptExpr,
+    KPostfixExpr,
+    KConditionalExpr,
+    KMemberExpr,
+    KEnclosingExpr,
+    KCastExpr,
+    KSizeofParamPackExpr,
+    KCallExpr,
+    KNewExpr,
+    KDeleteExpr,
+    KPrefixExpr,
+    KFunctionParam,
+    KConversionExpr,
+    KInitListExpr,
+    KFoldExpr,
+    KThrowExpr,
+    KBoolExpr,
+    KIntegerCastExpr,
+    KIntegerExpr,
+    KFloatExpr,
+  };
+
   Expr(Kind K = KExpr) : Node(K) {}
+
+#ifndef STANDALONE_DEMANGLER
+  static void profileCtor(llvm::FoldingSetNodeID &ID, Kind K = KExpr) {
+    Node::profileCtor(ID, K);
+  }
+  void profile(llvm::FoldingSetNodeID &ID) const override {
+    profileCtor(ID, K);
+  }
 };
+#endif
 
 class BinaryExpr : public Expr {
   const Node *LHS;
   const StringView InfixOperator;
   const Node *RHS;
 
 public:
-  BinaryExpr(Node *LHS_, StringView InfixOperator_, Node *RHS_)
+  BinaryExpr(const Node *LHS_, StringView InfixOperator_, const Node *RHS_)
       : LHS(LHS_), InfixOperator(InfixOperator_), RHS(RHS_) {}
 
+#ifndef STANDALONE_DEMANGLER
+  static void profileCtor(llvm::FoldingSetNodeID &ID, const Node *LHS,
+                          StringView InfixOperator, const Node *RHS) {
+    Expr::profileCtor(ID);
+    ID.AddInteger(KBinaryExpr);
+    ID.AddPointer(LHS);
+    addString(ID, InfixOperator);
+    ID.AddPointer(RHS);
+  }
+  void profile(llvm::FoldingSetNodeID &ID) const override {
+    profileCtor(ID, LHS, InfixOperator, RHS);
+  }
+#endif
+
   void printLeft(OutputStream &S) const override {
     // might be a template argument expression, then we need to disambiguate
     // with parens.
     if (InfixOperator == ">")
       S += "(";
 
     S += "(";
     LHS->print(S);
     S += ") ";
     S += InfixOperator;
     S += " (";
     RHS->print(S);
     S += ")";
 
     if (InfixOperator == ">")
       S += ")";
   }
 };
 
 class ArraySubscriptExpr : public Expr {
   const Node *Op1;
   const Node *Op2;
 
 public:
-  ArraySubscriptExpr(Node *Op1_, Node *Op2_) : Op1(Op1_), Op2(Op2_) {}
+  ArraySubscriptExpr(const Node *Op1_, const Node *Op2_)
+      : Op1(Op1_), Op2(Op2_) {}
+
+#ifndef STANDALONE_DEMANGLER
+  static void profileCtor(llvm::FoldingSetNodeID &ID, const Node *Op1,
+                          const Node *Op2) {
+    Expr::profileCtor(ID);
+    ID.AddInteger(KArraySubscriptExpr);
+    ID.AddPointer(Op1);
+    ID.AddPointer(Op2);
+  }
+  void profile(llvm::FoldingSetNodeID &ID) const override {
+    profileCtor(ID, Op1, Op2);
+  }
+#endif
 
   void printLeft(OutputStream &S) const override {
     S += "(";
     Op1->print(S);
     S += ")[";
     Op2->print(S);
     S += "]";
   }
 };
 
 class PostfixExpr : public Expr {
   const Node *Child;
-  const StringView Operand;
+  const StringView Operator;
 
 public:
-  PostfixExpr(Node *Child_, StringView Operand_)
-      : Child(Child_), Operand(Operand_) {}
+  PostfixExpr(const Node *Child_, StringView Operator_)
+      : Child(Child_), Operator(Operator_) {}
+
+#ifndef STANDALONE_DEMANGLER
+  static void profileCtor(llvm::FoldingSetNodeID &ID, const Node *Child,
+                          StringView Operator) {
+    Expr::profileCtor(ID);
+    ID.AddInteger(KPostfixExpr);
+    ID.AddPointer(Child);
+    addString(ID, Operator);
+  }
+  void profile(llvm::FoldingSetNodeID &ID) const override {
+    profileCtor(ID, Child, Operator);
+  }
+#endif
 
   void printLeft(OutputStream &S) const override {
     S += "(";
     Child->print(S);
     S += ")";
-    S += Operand;
+    S += Operator;
   }
 };
 
 class ConditionalExpr : public Expr {
   const Node *Cond;
   const Node *Then;
   const Node *Else;
 
 public:
-  ConditionalExpr(Node *Cond_, Node *Then_, Node *Else_)
+  ConditionalExpr(const Node *Cond_, const Node *Then_, const Node *Else_)
       : Cond(Cond_), Then(Then_), Else(Else_) {}
 
+#ifndef STANDALONE_DEMANGLER
+  static void profileCtor(llvm::FoldingSetNodeID &ID, const Node *Cond,
+                          const Node *Then, const Node *Else) {
+    Expr::profileCtor(ID);
+    ID.AddInteger(KConditionalExpr);
+    ID.AddPointer(Cond);
+    ID.AddPointer(Then);
+    ID.AddPointer(Else);
+  }
+  void profile(llvm::FoldingSetNodeID &ID) const override {
+    profileCtor(ID, Cond, Then, Else);
+  }
+#endif
+
   void printLeft(OutputStream &S) const override {
     S += "(";
     Cond->print(S);
     S += ") ? (";
     Then->print(S);
     S += ") : (";
     Else->print(S);
     S += ")";
   }
 };
 
 class MemberExpr : public Expr {
   const Node *LHS;
   const StringView Kind;
   const Node *RHS;
 
 public:
-  MemberExpr(Node *LHS_, StringView Kind_, Node *RHS_)
+  MemberExpr(const Node *LHS_, StringView Kind_, const Node *RHS_)
       : LHS(LHS_), Kind(Kind_), RHS(RHS_) {}
 
+#ifndef STANDALONE_DEMANGLER
+  static void profileCtor(llvm::FoldingSetNodeID &ID, const Node *LHS,
+                          StringView Kind, const Node *RHS) {
+    Expr::profileCtor(ID);
+    ID.AddInteger(KMemberExpr);
+    ID.AddPointer(LHS);
+    addString(ID, Kind);
+    ID.AddPointer(RHS);
+  }
+  void profile(llvm::FoldingSetNodeID &ID) const override {
+    profileCtor(ID, LHS, Kind, RHS);
+  }
+#endif
+
   void printLeft(OutputStream &S) const override {
     LHS->print(S);
     S += Kind;
     RHS->print(S);
   }
 };
 
 class EnclosingExpr : public Expr {
   const StringView Prefix;
   const Node *Infix;
   const StringView Postfix;
 
 public:
   EnclosingExpr(StringView Prefix_, Node *Infix_, StringView Postfix_)
       : Prefix(Prefix_), Infix(Infix_), Postfix(Postfix_) {}
 
+#ifndef STANDALONE_DEMANGLER
+  static void profileCtor(llvm::FoldingSetNodeID &ID, StringView Prefix,
+                          const Node *Infix, StringView Postfix) {
+    Expr::profileCtor(ID);
+    ID.AddInteger(KEnclosingExpr);
+    addString(ID, Prefix);
+    ID.AddPointer(Infix);
+    addString(ID, Postfix);
+  }
+  void profile(llvm::FoldingSetNodeID &ID) const override {
+    profileCtor(ID, Prefix, Infix, Postfix);
+  }
+#endif
+
   void printLeft(OutputStream &S) const override {
     S += Prefix;
     Infix->print(S);
     S += Postfix;
   }
 };
 
 class CastExpr : public Expr {
   // cast_kind<to>(from)
   const StringView CastKind;
   const Node *To;
   const Node *From;
 
 public:
-  CastExpr(StringView CastKind_, Node *To_, Node *From_)
+  CastExpr(StringView CastKind_, const Node *To_, const Node *From_)
       : CastKind(CastKind_), To(To_), From(From_) {}
 
+#ifndef STANDALONE_DEMANGLER
+  static void profileCtor(llvm::FoldingSetNodeID &ID, StringView CastKind,
+                          const Node *To, const Node *From) {
+    Expr::profileCtor(ID);
+    ID.AddInteger(KCastExpr);
+    addString(ID, CastKind);
+    ID.AddPointer(To);
+    ID.AddPointer(From);
+  }
+  void profile(llvm::FoldingSetNodeID &ID) const override {
+    profileCtor(ID, CastKind, To, From);
+  }
+#endif
+
   void printLeft(OutputStream &S) const override {
     S += CastKind;
     S += "<";
     To->printLeft(S);
     S += ">(";
     From->printLeft(S);
     S += ")";
   }
 };
 
 class SizeofParamPackExpr : public Expr {
-  Node *Pack;
+  const Node *Pack;
 
 public:
-  SizeofParamPackExpr(Node *Pack_) : Pack(Pack_) {}
+  SizeofParamPackExpr(const Node *Pack_) : Pack(Pack_) {}
+
+#ifndef STANDALONE_DEMANGLER
+  static void profileCtor(llvm::FoldingSetNodeID &ID, const Node *Pack) {
+    Expr::profileCtor(ID);
+    ID.AddInteger(KSizeofParamPackExpr);
+    ID.AddPointer(Pack);
+  }
+  void profile(llvm::FoldingSetNodeID &ID) const override {
+    profileCtor(ID, Pack);
+  }
+#endif
 
   void printLeft(OutputStream &S) const override {
     S += "sizeof...(";
     ParameterPackExpansion PPE(Pack);
     PPE.printLeft(S);
     S += ")";
   }
 };
 
 class CallExpr : public Expr {
   const Node *Callee;
   NodeArray Args;
 
 public:
-  CallExpr(Node *Callee_, NodeArray Args_) : Callee(Callee_), Args(Args_) {}
+  CallExpr(const Node *Callee_, NodeArray Args_)
+      : Callee(Callee_), Args(Args_) {}
+
+#ifndef STANDALONE_DEMANGLER
+  static void profileCtor(llvm::FoldingSetNodeID &ID, const Node *Callee,
+                          NodeArray Args) {
+    Expr::profileCtor(ID);
+    ID.AddInteger(KCallExpr);
+    ID.AddPointer(Callee);
+    Args.profile(ID);
+  }
+  void profile(llvm::FoldingSetNodeID &ID) const override {
+    profileCtor(ID, Callee, Args);
+  }
+#endif
 
   void printLeft(OutputStream &S) const override {
     Callee->print(S);
     S += "(";
     Args.printWithComma(S);
     S += ")";
   }
 };
 
 class NewExpr : public Expr {
   // new (expr_list) type(init_list)
   NodeArray ExprList;
   Node *Type;
   NodeArray InitList;
   bool IsGlobal; // ::operator new ?
   bool IsArray;  // new[] ?
 public:
   NewExpr(NodeArray ExprList_, Node *Type_, NodeArray InitList_, bool IsGlobal_,
           bool IsArray_)
       : ExprList(ExprList_), Type(Type_), InitList(InitList_),
         IsGlobal(IsGlobal_), IsArray(IsArray_) {}
 
+#ifndef STANDALONE_DEMANGLER
+  static void profileCtor(llvm::FoldingSetNodeID &ID, NodeArray ExprList,
+                          Node *Type, NodeArray InitList, bool IsGlobal,
+                          bool IsArray) {
+    Expr::profileCtor(ID);
+    ID.AddInteger(KNewExpr);
+    ExprList.profile(ID);
+    ID.AddPointer(Type);
+    InitList.profile(ID);
+    ID.AddBoolean(IsGlobal);
+    ID.AddBoolean(IsArray);
+  }
+  void profile(llvm::FoldingSetNodeID &ID) const override {
+    profileCtor(ID, ExprList, Type, InitList, IsGlobal, IsArray);
+  }
+#endif
+
   void printLeft(OutputStream &S) const override {
     if (IsGlobal)
       S += "::operator ";
     S += "new";
     if (IsArray)
       S += "[]";
     S += ' ';
     if (!ExprList.empty()) {
class DeleteExpr : public Expr {
   Node *Op;
   bool IsGlobal;
   bool IsArray;
 
 public:
   DeleteExpr(Node *Op_, bool IsGlobal_, bool IsArray_)
       : Op(Op_), IsGlobal(IsGlobal_), IsArray(IsArray_) {}
 
+#ifndef STANDALONE_DEMANGLER
+  static void profileCtor(llvm::FoldingSetNodeID &ID, Node *Op, bool IsGlobal,
+                          bool IsArray) {
+    Expr::profileCtor(ID);
+    ID.AddInteger(KDeleteExpr);
+    ID.AddPointer(Op);
+    ID.AddBoolean(IsGlobal);
+    ID.AddBoolean(IsArray);
+  }
+  void profile(llvm::FoldingSetNodeID &ID) const override {
+    profileCtor(ID, Op, IsGlobal, IsArray);
+  }
+#endif
+
   void printLeft(OutputStream &S) const override {
     if (IsGlobal)
       S += "::";
     S += "delete";
     if (IsArray)
       S += "[] ";
     Op->print(S);
   }
 };
 
 class PrefixExpr : public Expr {
   StringView Prefix;
   Node *Child;
 
 public:
-  PrefixExpr(StringView Prefix_, Node *Child_) : Prefix(Prefix_), Child(Child_) {}
+  PrefixExpr(StringView Prefix_, Node *Child_)
+      : Prefix(Prefix_), Child(Child_) {}
+
+#ifndef STANDALONE_DEMANGLER
+  static void profileCtor(llvm::FoldingSetNodeID &ID, StringView Prefix,
+                          Node *Child) {
+    Expr::profileCtor(ID);
+    ID.AddInteger(KPrefixExpr);
+    addString(ID, Prefix);
+    ID.AddPointer(Child);
+  }
+  void profile(llvm::FoldingSetNodeID &ID) const override {
+    profileCtor(ID, Prefix, Child);
+  }
+#endif
 
   void printLeft(OutputStream &S) const override {
     S += Prefix;
     S += "(";
     Child->print(S);
     S += ")";
   }
 };
 
 class FunctionParam : public Expr {
   StringView Number;
 
 public:
   FunctionParam(StringView Number_) : Number(Number_) {}
 
+#ifndef STANDALONE_DEMANGLER
+  static void profileCtor(llvm::FoldingSetNodeID &ID, StringView Number) {
+    Expr::profileCtor(ID);
+    ID.AddInteger(KFunctionParam);
+    addString(ID, Number);
+  }
+  void profile(llvm::FoldingSetNodeID &ID) const override {
+    profileCtor(ID, Number);
+  }
+#endif
+
   void printLeft(OutputStream &S) const override {
     S += "fp";
     S += Number;
   }
 };
 
 class ConversionExpr : public Expr {
   const Node *Type;
   NodeArray Expressions;
 
 public:
   ConversionExpr(const Node *Type_, NodeArray Expressions_)
       : Type(Type_), Expressions(Expressions_) {}
 
+#ifndef STANDALONE_DEMANGLER
+  static void profileCtor(llvm::FoldingSetNodeID &ID, const Node *Type,
+                          NodeArray Expressions) {
+    Expr::profileCtor(ID);
+    ID.AddInteger(KConversionExpr);
+    ID.AddPointer(Type);
+    Expressions.profile(ID);
+  }
+  void profile(llvm::FoldingSetNodeID &ID) const override {
+    profileCtor(ID, Type, Expressions);
+  }
+#endif
+
   void printLeft(OutputStream &S) const override {
     S += "(";
     Type->print(S);
     S += ")(";
     Expressions.printWithComma(S);
     S += ")";
   }
 };
 
 class InitListExpr : public Expr {
-  Node *Ty;
+  const Node *Ty;
   NodeArray Inits;
 public:
-  InitListExpr(Node *Ty_, NodeArray Inits_) : Ty(Ty_), Inits(Inits_) {}
+  InitListExpr(const Node *Ty_, NodeArray Inits_) : Ty(Ty_), Inits(Inits_) {}
+
+#ifndef STANDALONE_DEMANGLER
+  static void profileCtor(llvm::FoldingSetNodeID &ID, const Node *Type,
+                          NodeArray Inits) {
+    Expr::profileCtor(ID);
+    ID.AddInteger(KInitListExpr);
+    ID.AddPointer(Type);
+    Inits.profile(ID);
+  }
+  void profile(llvm::FoldingSetNodeID &ID) const override {
+    profileCtor(ID, Ty, Inits);
+  }
+#endif
 
   void printLeft(OutputStream &S) const override {
     if (Ty)
       Ty->print(S);
     S += '{';
     Inits.printWithComma(S);
     S += '}';
   }
 };
 
 class BracedExpr : public Expr {
-  Node *Elem;
-  Node *Init;
+  const Node *Elem;
+  const Node *Init;
   bool IsArray;
 public:
-  BracedExpr(Node *Elem_, Node *Init_, bool IsArray_)
+  BracedExpr(const Node *Elem_, const Node *Init_, bool IsArray_)
       : Expr(KBracedExpr), Elem(Elem_), Init(Init_), IsArray(IsArray_) {}
 
+#ifndef STANDALONE_DEMANGLER
+  static void profileCtor(llvm::FoldingSetNodeID &ID, const Node *Elem,
+                          const Node *Init, bool IsArray) {
+    Expr::profileCtor(ID, KBracedExpr);
+    ID.AddPointer(Elem);
+    ID.AddPointer(Init);
+    ID.AddBoolean(IsArray);
+  }
+  void profile(llvm::FoldingSetNodeID &ID) const override {
+    profileCtor(ID, Elem, Init, IsArray);
+  }
+#endif
+
   void printLeft(OutputStream &S) const override {
     if (IsArray) {
       S += '[';
       Elem->print(S);
       S += ']';
     } else {
       S += '.';
       Elem->print(S);
     }
     if (Init->getKind() != KBracedExpr && Init->getKind() != KBracedRangeExpr)
       S += " = ";
     Init->print(S);
   }
 };
 
 class BracedRangeExpr : public Expr {
-  Node *First;
-  Node *Last;
-  Node *Init;
+  const Node *First;
+  const Node *Last;
+  const Node *Init;
 public:
-  BracedRangeExpr(Node *First_, Node *Last_, Node *Init_)
+  BracedRangeExpr(const Node *First_, const Node *Last_, const Node *Init_)
       : Expr(KBracedRangeExpr), First(First_), Last(Last_), Init(Init_) {}
 
+#ifndef STANDALONE_DEMANGLER
+  static void profileCtor(llvm::FoldingSetNodeID &ID, const Node *First,
+                          const Node *Last, const Node *Init) {
+    Expr::profileCtor(ID, KBracedRangeExpr);
+    ID.AddPointer(First);
+    ID.AddPointer(Last);
+    ID.AddPointer(Init);
+  }
+  void profile(llvm::FoldingSetNodeID &ID) const override {
+    profileCtor(ID, First, Last, Init);
+  }
+#endif
+
   void printLeft(OutputStream &S) const override {
     S += '[';
     First->print(S);
     S += " ... ";
     Last->print(S);
     S += ']';
     if (Init->getKind() != KBracedExpr && Init->getKind() != KBracedRangeExpr)
       S += " = ";
     Init->print(S);
   }
 };
 
 struct FoldExpr : Expr {
-  Node *Pack, *Init;
+  const Node *Pack, *Init;
   StringView OperatorName;
   bool IsLeftFold;
 
-  FoldExpr(bool IsLeftFold_, StringView OperatorName_, Node *Pack_, Node *Init_)
+  FoldExpr(bool IsLeftFold_, StringView OperatorName_, const Node *Pack_,
+           const Node *Init_)
       : Pack(Pack_), Init(Init_), OperatorName(OperatorName_),
         IsLeftFold(IsLeftFold_) {}
 
+#ifndef STANDALONE_DEMANGLER
+  static void profileCtor(llvm::FoldingSetNodeID &ID, bool IsLeftFold,
+                          StringView OperatorName, const Node *Pack,
+                          const Node *Init) {
+    Expr::profileCtor(ID);
+    ID.AddInteger(KFoldExpr);
+    ID.AddBoolean(IsLeftFold);
+    addString(ID, OperatorName);
+    ID.AddPointer(Pack);
+    ID.AddPointer(Init);
+  }
+  void profile(llvm::FoldingSetNodeID &ID) const override {
+    profileCtor(ID, IsLeftFold, OperatorName, Pack, Init);
+  }
+#endif
+
   void printLeft(OutputStream &S) const override {
     auto PrintPack = [&] {
       S += '(';
       ParameterPackExpansion(Pack).print(S);
       S += ')';
     };
 
     S += '(';
void printLeft(OutputStream &S) const override {
     S += ')';
   }
 };
 
 class ThrowExpr : public Expr {
   const Node *Op;
 
 public:
-  ThrowExpr(Node *Op_) : Op(Op_) {}
+  ThrowExpr(const Node *Op_) : Op(Op_) {}
+
+#ifndef STANDALONE_DEMANGLER
+  static void profileCtor(llvm::FoldingSetNodeID &ID, const Node *Op) {
+    Expr::profileCtor(ID);
+    ID.AddInteger(KThrowExpr);
+    ID.AddPointer(Op);
+  }
+  void profile(llvm::FoldingSetNodeID &ID) const override {
+    profileCtor(ID, Op);
+  }
+#endif
 
   void printLeft(OutputStream &S) const override {
     S += "throw ";
     Op->print(S);
   }
 };
 
 class BoolExpr : public Expr {
   bool Value;
 
 public:
   BoolExpr(bool Value_) : Value(Value_) {}
 
+#ifndef STANDALONE_DEMANGLER
+  static void profileCtor(llvm::FoldingSetNodeID &ID, bool Value) {
+    Expr::profileCtor(ID);
+    ID.AddInteger(KBoolExpr);
+    ID.AddBoolean(Value);
+  }
+  void profile(llvm::FoldingSetNodeID &ID) const override {
+    profileCtor(ID, Value);
+  }
+#endif
+
   void printLeft(OutputStream &S) const override {
     S += Value ? StringView("true") : StringView("false");
   }
 };
 
 class IntegerCastExpr : public Expr {
   // ty(integer)
-  Node *Ty;
+  const Node *Ty;
   StringView Integer;
 
 public:
-  IntegerCastExpr(Node *Ty_, StringView Integer_)
+  IntegerCastExpr(const Node *Ty_, StringView Integer_)
       : Ty(Ty_), Integer(Integer_) {}
 
+#ifndef STANDALONE_DEMANGLER
+  static void profileCtor(llvm::FoldingSetNodeID &ID, const Node *Ty,
+                          StringView Integer) {
+    Expr::profileCtor(ID);
+    ID.AddInteger(KIntegerCastExpr);
+    ID.AddPointer(Ty);
+    addString(ID, Integer);
+  }
+  void profile(llvm::FoldingSetNodeID &ID) const override {
+    profileCtor(ID, Ty, Integer);
+  }
+#endif
+
   void printLeft(OutputStream &S) const override {
     S += "(";
     Ty->print(S);
     S += ")";
     S += Integer;
   }
 };
 
 class IntegerExpr : public Expr {
   StringView Type;
   StringView Value;
 
 public:
   IntegerExpr(StringView Type_, StringView Value_) : Type(Type_), Value(Value_) {}
 
+#ifndef STANDALONE_DEMANGLER
+  static void profileCtor(llvm::FoldingSetNodeID &ID, StringView Type,
+                          StringView Value) {
+    Expr::profileCtor(ID);
+    ID.AddInteger(KIntegerExpr);
+    addString(ID, Type);
+    addString(ID, Value);
+  }
+  void profile(llvm::FoldingSetNodeID &ID) const override {
+    profileCtor(ID, Type, Value);
+  }
+#endif
+
   void printLeft(OutputStream &S) const override {
     if (Type.size() > 3) {
       S += "(";
       S += Type;
       S += ")";
     }
 
     if (Value[0] == 'n') {

 template <class Float> struct FloatData;
 
 template <class Float> class FloatExpr : public Expr {
   const StringView Contents;
 
 public:
   FloatExpr(StringView Contents_) : Contents(Contents_) {}
 
+#ifndef STANDALONE_DEMANGLER
+  static void profileCtor(llvm::FoldingSetNodeID &ID, StringView Contents) {
+    Expr::profileCtor(ID);
+    ID.AddInteger(KFloatExpr);
+    addString(ID, Contents);
+  }
+  void profile(llvm::FoldingSetNodeID &ID) const override {
+    profileCtor(ID, Contents);
+  }
+#endif
+
   void printLeft(OutputStream &s) const override {
     const char *first = Contents.begin();
     const char *last = Contents.end() + 1;
 
     const size_t N = FloatData<Float>::mangled_size;
     if (static_cast<std::size_t>(last - first) > N) {
       last = first + N;
       union {
public:
   void clear() { Last = First; }
 
   ~PODSmallVector() {
     if (!isInline())
       std::free(First);
   }
 };
 
+class DefaultAllocator {
+  BumpPointerAllocator Alloc;
+
+public:
+  void reset() { Alloc.reset(); }
+
+  template<typename T, typename ...Args> T *makeNode(Args &&...args) {
+    return new (Alloc.allocate(sizeof(T)))
+        T(std::forward<Args>(args)...);
+  }
+
+  void *allocateNodeArray(size_t sz) {
+    return Alloc.allocate(sizeof(Node *) * sz);
+  }
+};
+
+#ifndef STANDALONE_DEMANGLER
+class FoldingNodeAllocator {
+  class alignas(alignof(Node *)) NodeHeader : public llvm::FoldingSetNode {
+  public:
+    ::Node *getNode() { return reinterpret_cast<::Node*>(this + 1); }
+    void Profile(llvm::FoldingSetNodeID &ID) {
+      getNode()->profile(ID);
+    }
+  };
+
+  BumpPointerAllocator RawAlloc;
+  llvm::FoldingSet<NodeHeader> Nodes;
+
+public:
+  void reset() {}
+
+  template<typename T, typename ...Args>
+  std::pair<T *, bool> makeNodeImpl(bool CreateNewNodes, Args &&...args) {
+    llvm::FoldingSetNodeID ID;
+    T::profileCtor(ID, args...);
+
+    void *InsertPos;
+    if (NodeHeader *Existing = Nodes.FindNodeOrInsertPos(ID, InsertPos))
+      return {static_cast<T*>(Existing->getNode()), false};
+
+    if (!CreateNewNodes)
+      return {nullptr, true};
+
+    void *Storage = RawAlloc.allocate(sizeof(NodeHeader) + sizeof(T));
+    NodeHeader *New = new (Storage) NodeHeader;
+    T *Result = new (New->getNode()) T(std::forward<Args>(args)...);
+    Nodes.InsertNode(New, InsertPos);
+    return {Result, true};
+  }
+
+  template<typename T, typename ...Args> T *makeNode(Args &&...args) {
+    return makeNodeImpl<T>(true, std::forward<Args>(args)...).first;
+  }
+
+  void *allocateNodeArray(size_t sz) {
+    return RawAlloc.allocate(sizeof(Node *) * sz);
+  }
+};
+
+// FIXME: Don't canonicalize forward template references for now, because they
+// contain state (the resolved template node) that's not known at their point
+// of creation.
+template <>
+std::pair<ForwardTemplateReference *, bool>
+FoldingNodeAllocator::makeNodeImpl<ForwardTemplateReference, size_t&>(
+    bool, size_t &Index) {
+  return {new (RawAlloc.allocate(sizeof(ForwardTemplateReference)))
+              ForwardTemplateReference(Index),
+          true};
+}
+#endif
+
+template <typename Alloc = DefaultAllocator>
 struct Db {
   const char *First;
   const char *Last;
 
   // Name stack, this is used by the parser to hold temporary names that were
   // parsed. The parser collapses multiple names into new nodes to construct
   // the AST. Once the parser is finished, names.size() == 1.
   PODSmallVector<Node *, 32> Names;
struct Db {
 
   void (*TypeCallback)(void *, const char *) = nullptr;
   void *TypeCallbackContext = nullptr;
 
   bool TryToParseTemplateArgs = true;
   bool PermitForwardTemplateReferences = false;
   bool ParsingLambdaParams = false;
 
-  BumpPointerAllocator ASTAllocator;
+  Alloc ASTAllocator;
 
   Db(const char *First_, const char *Last_) : First(First_), Last(Last_) {}
 
   void reset(const char *First_, const char *Last_) {
     First = First_;
     Last = Last_;
     Names.clear();
     Subs.clear();
     TemplateParams.clear();
     ParsingLambdaParams = false;
     TryToParseTemplateArgs = true;
     PermitForwardTemplateReferences = false;
     ASTAllocator.reset();
   }
 
-  template <class T, class... Args> T *make(Args &&... args) {
-    return new (ASTAllocator.allocate(sizeof(T)))
-        T(std::forward<Args>(args)...);
+  template <class T, class... Args> Node *make(Args &&... args) {
+    return ASTAllocator.template makeNode<T>(std::forward<Args>(args)...);
   }
 
   template <class It> NodeArray makeNodeArray(It begin, It end) {
     size_t sz = static_cast<size_t>(end - begin);
-    void *mem = ASTAllocator.allocate(sizeof(Node *) * sz);
+    void *mem = ASTAllocator.allocateNodeArray(sz);
     Node **data = new (mem) Node *[sz];
     std::copy(begin, end, data);
     return NodeArray(data, sz);
   }
 
   NodeArray popTrailingNodeArray(size_t FromPosition) {
     assert(FromPosition <= Names.size());
     NodeArray res =

 
 // <name> ::= <nested-name> // N
 //        ::= <local-name> # See Scope Encoding below  // Z
 //        ::= <unscoped-template-name> <template-args>
 //        ::= <unscoped-name>
 //
 // <unscoped-template-name> ::= <unscoped-name>
 //                          ::= <substitution>
-Node *Db::parseName(NameState *State) {
+template<typename Alloc> Node *Db<Alloc>::parseName(NameState *State) {
   consumeIf('L'); // extension
 
   if (look() == 'N')
     return parseNestedName(State);
   if (look() == 'Z')
     return parseLocalName(State);
 
   //        ::= <unscoped-template-name> <template-args>
template<typename Alloc> Node *Db<Alloc>::parseName(NameState *State) {
   }
   //        ::= <unscoped-name>
   return N;
 }
 
 // <local-name> := Z <function encoding> E <entity name> [<discriminator>]
 //              := Z <function encoding> E s [<discriminator>]
 //              := Z <function encoding> Ed [ <parameter number> ] _ <entity name>
-Node *Db::parseLocalName(NameState *State) {
+template<typename Alloc> Node *Db<Alloc>::parseLocalName(NameState *State) {
   if (!consumeIf('Z'))
     return nullptr;
   Node *Encoding = parseEncoding();
   if (Encoding == nullptr || !consumeIf('E'))
     return nullptr;
 
   if (consumeIf('s')) {
     First = parse_discriminator(First, Last);
-    return make<LocalName>(Encoding, make<NameType>("string literal"));
+    auto *StringLitName = make<NameType>("string literal");
+    return make<LocalName>(Encoding, StringLitName);
   }
 
   if (consumeIf('d')) {
     parseNumber(true);
     if (!consumeIf('_'))
       return nullptr;
     Node *N = parseName(State);
     if (N == nullptr)
       return nullptr;
     return make<LocalName>(Encoding, N);
   }
 
   Node *Entity = parseName(State);
   if (Entity == nullptr)
     return nullptr;
   First = parse_discriminator(First, Last);
   return make<LocalName>(Encoding, Entity);
 }
 
 // <unscoped-name> ::= <unqualified-name>
 //                 ::= St <unqualified-name>   # ::std::
 // extension       ::= StL<unqualified-name>
-Node *Db::parseUnscopedName(NameState *State) {
+template<typename Alloc> Node *Db<Alloc>::parseUnscopedName(NameState *State) {
  if (consumeIf("StL") || consumeIf("St")) {
    Node *R = parseUnqualifiedName(State);
    if (R == nullptr)
      return nullptr;
-   return make<StdQualifiedName>(R);
+   return make<NestedName>(make<NameType>("std"), R);
  }
  return parseUnqualifiedName(State);
 }
 
 // <unqualified-name> ::= <operator-name> [abi-tags]
 //                    ::= <ctor-dtor-name>
 //                    ::= <source-name>
 //                    ::= <unnamed-type-name>
 //                    ::= DC <source-name>+ E      # structured binding declaration
-Node *Db::parseUnqualifiedName(NameState *State) {
+template<typename Alloc>
+Node *Db<Alloc>::parseUnqualifiedName(NameState *State) {
   // <ctor-dtor-name>s are special-cased in parseNestedName().
   Node *Result;
   if (look() == 'U')
     Result = parseUnnamedTypeName(State);
   else if (look() >= '1' && look() <= '9')
     Result = parseSourceName(State);
   else if (consumeIf("DC")) {
     size_t BindingsBegin = Names.size();
     do {
       Node *Binding = parseSourceName(State);
       if (Binding == nullptr)
         return nullptr;
       Names.push_back(Binding);
     } while (!consumeIf('E'));
     Result = make<StructuredBindingName>(popTrailingNodeArray(BindingsBegin));
   } else
     Result = parseOperatorName(State);
   if (Result != nullptr)
     Result = parseAbiTags(Result);
   return Result;
 }
 
 // <unnamed-type-name> ::= Ut [<nonnegative number>] _
 //                     ::= <closure-type-name>
 //
 // <closure-type-name> ::= Ul <lambda-sig> E [ <nonnegative number> ] _
 //
 // <lambda-sig> ::= <parameter type>+  # Parameter types or "v" if the lambda has no parameters
-Node *Db::parseUnnamedTypeName(NameState *) {
+template<typename Alloc> Node *Db<Alloc>::parseUnnamedTypeName(NameState *) {
   if (consumeIf("Ut")) {
     StringView Count = parseNumber();
     if (!consumeIf('_'))
       return nullptr;
     return make<UnnamedTypeName>(Count);
   }
   if (consumeIf("Ul")) {
     NodeArray Params;
if (consumeIf("Ul")) {
     if (!consumeIf('_'))
       return nullptr;
     return make<ClosureTypeName>(Params, Count);
   }
   return nullptr;
 }
 
 // <source-name> ::= <positive length number> <identifier>
-Node *Db::parseSourceName(NameState *) {
+template<typename Alloc> Node *Db<Alloc>::parseSourceName(NameState *) {
   size_t Length = 0;
   if (parsePositiveInteger(&Length))
     return nullptr;
   if (numLeft() < Length || Length == 0)
     return nullptr;
   StringView Name(First, First + Length);
   First += Length;
   if (Name.startsWith("_GLOBAL__N"))

 //                   ::= pt    # ->
 //                   ::= qu    # ?
 //                   ::= rm    # %
 //                   ::= rM    # %=
 //                   ::= rs    # >>
 //                   ::= rS    # >>=
 //                   ::= ss    # <=> C++2a
 //                   ::= v <digit> <source-name>        # vendor extended operator
-Node *Db::parseOperatorName(NameState *State) {
+template<typename Alloc> Node *Db<Alloc>::parseOperatorName(NameState *State) {
   switch (look()) {
   case 'a':
     switch (look(1)) {
     case 'a':
       First += 2;
       return make<NameType>("operator&&");
     case 'd':
     case 'n':

 // <ctor-dtor-name> ::= C1  # complete object constructor
 //                  ::= C2  # base object constructor
 //                  ::= C3  # complete object allocating constructor
 //   extension      ::= C5    # ?
 //                  ::= D0  # deleting destructor
 //                  ::= D1  # complete object destructor
 //                  ::= D2  # base object destructor
 //   extension      ::= D5    # ?
-Node *Db::parseCtorDtorName(Node *&SoFar, NameState *State) {
+template<typename Alloc>
+Node *Db<Alloc>::parseCtorDtorName(Node *&SoFar, NameState *State) {
   if (SoFar->K == Node::KSpecialSubstitution) {
     auto SSK = static_cast<SpecialSubstitution *>(SoFar)->SSK;
     switch (SSK) {
     case SpecialSubKind::string:
     case SpecialSubKind::istream:
     case SpecialSubKind::ostream:
     case SpecialSubKind::iostream:
       SoFar = make<ExpandedSpecialSubstitution>(SSK);

 //          ::= <prefix> <data-member-prefix>
 //  extension ::= L
 //
 // <data-member-prefix> := <member source-name> [<template-args>] M
 //
 // <template-prefix> ::= <prefix> <template unqualified-name>
 //                   ::= <template-param>
 //                   ::= <substitution>
-Node *Db::parseNestedName(NameState *State) {
+template<typename Alloc> Node *Db<Alloc>::parseNestedName(NameState *State) {
   if (!consumeIf('N'))
     return nullptr;
 
   Qualifiers CVTmp = parseCVQualifiers();
   if (State) State->CVQualifiers = CVTmp;
 
   if (consumeIf('O')) {
     if (State) State->ReferenceQualifier = FrefQualRValue;
   } else if (consumeIf('R')) {
     if (State) State->ReferenceQualifier = FrefQualLValue;
   } else
     if (State) State->ReferenceQualifier = FrefQualNone;
 
   Node *SoFar = nullptr;
   auto PushComponent = [&](Node *Comp) {
     if (SoFar) SoFar = make<NestedName>(SoFar, Comp);
     else       SoFar = Comp;
     if (State) State->EndsWithTemplateArgs = false;
+    return SoFar != nullptr;
   };
 
   if (consumeIf("St"))
     SoFar = make<NameType>("std");
 
   while (!consumeIf('E')) {
     consumeIf('L'); // extension
 
     // <data-member-prefix> := <member source-name> [<template-args>] M
     if (consumeIf('M')) {
       if (SoFar == nullptr)
         return nullptr;
       continue;
     }
 
     //          ::= <template-param>
     if (look() == 'T') {
       Node *TP = parseTemplateParam();
       if (TP == nullptr)
         return nullptr;
-      PushComponent(TP);
+      if (!PushComponent(TP))
+        return nullptr;
       Subs.push_back(SoFar);
       continue;
     }
 
     //          ::= <template-prefix> <template-args>
     if (look() == 'I') {
       Node *TA = parseTemplateArgs(State != nullptr);
       if (TA == nullptr || SoFar == nullptr)
         return nullptr;
       SoFar = make<NameWithTemplateArgs>(SoFar, TA);
       if (State) State->EndsWithTemplateArgs = true;
       Subs.push_back(SoFar);
       continue;
     }
 
     //          ::= <decltype>
     if (look() == 'D' && (look(1) == 't' || look(1) == 'T')) {
       Node *DT = parseDecltype();
       if (DT == nullptr)
         return nullptr;
-      PushComponent(DT);
+      if (!PushComponent(DT))
+        return nullptr;
       Subs.push_back(SoFar);
       continue;
     }
 
     //          ::= <substitution>
     if (look() == 'S' && look(1) != 't') {
       Node *S = parseSubstitution();
       if (S == nullptr)
         return nullptr;
-      PushComponent(S);
+      if (!PushComponent(S))
+        return nullptr;
       if (SoFar != S)
         Subs.push_back(S);
       continue;
     }
 
     // Parse an <unqualified-name> thats actually a <ctor-dtor-name>.
     if (look() == 'C' || (look() == 'D' && look(1) != 'C')) {
       if (SoFar == nullptr)
         return nullptr;
       Node *CtorDtor = parseCtorDtorName(SoFar, State);
       if (CtorDtor == nullptr)
         return nullptr;
-      PushComponent(CtorDtor);
+      if (!PushComponent(CtorDtor))
+        return nullptr;
       SoFar = parseAbiTags(SoFar);
       if (SoFar == nullptr)
         return nullptr;
       Subs.push_back(SoFar);
       continue;
     }
 
     //          ::= <prefix> <unqualified-name>
     Node *N = parseUnqualifiedName(State);
     if (N == nullptr)
       return nullptr;
-    PushComponent(N);
+    if (!PushComponent(N))
+      return nullptr;
     Subs.push_back(SoFar);
   }
 
   if (SoFar == nullptr || Subs.empty())
     return nullptr;
 
   Subs.pop_back();
   return SoFar;
 }
 
 // <simple-id> ::= <source-name> [ <template-args> ]
-Node *Db::parseSimpleId() {
+template<typename Alloc> Node *Db<Alloc>::parseSimpleId() {
   Node *SN = parseSourceName(/*NameState=*/nullptr);
   if (SN == nullptr)
     return nullptr;
   if (look() == 'I') {
     Node *TA = parseTemplateArgs();
     if (TA == nullptr)
       return nullptr;
     return make<NameWithTemplateArgs>(SN, TA);
   }
   return SN;
 }
 
 // <destructor-name> ::= <unresolved-type>  # e.g., ~T or ~decltype(f())
 //                   ::= <simple-id>        # e.g., ~A<2*N>
-Node *Db::parseDestructorName() {
+template<typename Alloc> Node *Db<Alloc>::parseDestructorName() {
   Node *Result;
   if (std::isdigit(look()))
     Result = parseSimpleId();
   else
     Result = parseUnresolvedType();
   if (Result == nullptr)
     return nullptr;
   return make<DtorName>(Result);
 }
 
 // <unresolved-type> ::= <template-param>
 //                   ::= <decltype>
 //                   ::= <substitution>
-Node *Db::parseUnresolvedType() {
+template<typename Alloc> Node *Db<Alloc>::parseUnresolvedType() {
   if (look() == 'T') {
     Node *TP = parseTemplateParam();
     if (TP == nullptr)
       return nullptr;
     Subs.push_back(TP);
     return TP;
   }
   if (look() == 'D') {
     Node *DT = parseDecltype();
     if (DT == nullptr)
       return nullptr;
     Subs.push_back(DT);
     return DT;
   }
   return parseSubstitution();
 }
 
 // <base-unresolved-name> ::= <simple-id>                                # unresolved name
 //          extension     ::= <operator-name>                            # unresolved operator-function-id
 //          extension     ::= <operator-name> <template-args>            # unresolved operator template-id
 //                        ::= on <operator-name>                         # unresolved operator-function-id
 //                        ::= on <operator-name> <template-args>         # unresolved operator template-id
 //                        ::= dn <destructor-name>                       # destructor or pseudo-destructor;
 //                                                                         # e.g. ~X or ~X<N-1>
-Node *Db::parseBaseUnresolvedName() {
+template<typename Alloc> Node *Db<Alloc>::parseBaseUnresolvedName() {
   if (std::isdigit(look()))
     return parseSimpleId();
 
   if (consumeIf("dn"))
     return parseDestructorName();
 
   consumeIf("on");
 

 //                   ::= [gs] sr <unresolved-qualifier-level>+ E <base-unresolved-name>
 //                                                                       # A::x, N::y, A<T>::z; "gs" means leading "::"
 //                   ::= sr <unresolved-type> <base-unresolved-name>     # T::x / decltype(p)::x
 //  extension        ::= sr <unresolved-type> <template-args> <base-unresolved-name>
 //                                                                       # T::N::x /decltype(p)::N::x
 //  (ignored)        ::= srN <unresolved-type>  <unresolved-qualifier-level>+ E <base-unresolved-name>
 //
 // <unresolved-qualifier-level> ::= <simple-id>
-Node *Db::parseUnresolvedName() {
+template<typename Alloc> Node *Db<Alloc>::parseUnresolvedName() {
   Node *SoFar = nullptr;
 
   // srN <unresolved-type> [<template-args>] <unresolved-qualifier-level>* E <base-unresolved-name>
   // srN <unresolved-type>                   <unresolved-qualifier-level>+ E <base-unresolved-name>
   if (consumeIf("srN")) {
     SoFar = parseUnresolvedType();
     if (SoFar == nullptr)
       return nullptr;
 
     if (look() == 'I') {
       Node *TA = parseTemplateArgs();
       if (TA == nullptr)
         return nullptr;
       SoFar = make<NameWithTemplateArgs>(SoFar, TA);
+      if (!SoFar)
+        return nullptr;
     }
 
     while (!consumeIf('E')) {
       Node *Qual = parseSimpleId();
       if (Qual == nullptr)
         return nullptr;
       SoFar = make<QualifiedName>(SoFar, Qual);
+      if (!SoFar)
+        return nullptr;
     }
 
     Node *Base = parseBaseUnresolvedName();
     if (Base == nullptr)
       return nullptr;
     return make<QualifiedName>(SoFar, Base);
   }
 
do {
       if (Qual == nullptr)
         return nullptr;
       if (SoFar)
         SoFar = make<QualifiedName>(SoFar, Qual);
       else if (Global)
         SoFar = make<GlobalQualifiedName>(Qual);
       else
         SoFar = Qual;
+      if (!SoFar)
+        return nullptr;
     } while (!consumeIf('E'));
   }
   //      sr <unresolved-type>                 <base-unresolved-name>
   //      sr <unresolved-type> <template-args> <base-unresolved-name>
   else {
     SoFar = parseUnresolvedType();
     if (SoFar == nullptr)
       return nullptr;
 
     if (look() == 'I') {
       Node *TA = parseTemplateArgs();
       if (TA == nullptr)
         return nullptr;
       SoFar = make<NameWithTemplateArgs>(SoFar, TA);
+      if (!SoFar)
+        return nullptr;
     }
   }
 
   assert(SoFar != nullptr);
 
   Node *Base = parseBaseUnresolvedName();
   if (Base == nullptr)
     return nullptr;
   return make<QualifiedName>(SoFar, Base);
 }
 
 // <abi-tags> ::= <abi-tag> [<abi-tags>]
 // <abi-tag> ::= B <source-name>
-Node *Db::parseAbiTags(Node *N) {
+template<typename Alloc> Node *Db<Alloc>::parseAbiTags(Node *N) {
   while (consumeIf('B')) {
     StringView SN = parseBareSourceName();
     if (SN.empty())
       return nullptr;
     N = make<AbiTagAttr>(N, SN);
+    if (!N)
+      return nullptr;
   }
   return N;
 }
 
 // <number> ::= [n] <non-negative decimal integer>
-StringView Db::parseNumber(bool AllowNegative) {
+template<typename Alloc>
+StringView Db<Alloc>::parseNumber(bool AllowNegative) {
   const char *Tmp = First;
   if (AllowNegative)
     consumeIf('n');
   if (numLeft() == 0 || !std::isdigit(*First))
     return StringView();
   while (numLeft() != 0 && std::isdigit(*First))
     ++First;
   return StringView(Tmp, First);
 }
 
 // <positive length number> ::= [0-9]*
-bool Db::parsePositiveInteger(size_t *Out) {
+template<typename Alloc> bool Db<Alloc>::parsePositiveInteger(size_t *Out) {
   *Out = 0;
   if (look() < '0' || look() > '9')
     return true;
   while (look() >= '0' && look() <= '9') {
     *Out *= 10;
     *Out += static_cast<size_t>(consume() - '0');
   }
   return false;
 }
 
-StringView Db::parseBareSourceName() {
+template<typename Alloc> StringView Db<Alloc>::parseBareSourceName() {
   size_t Int = 0;
   if (parsePositiveInteger(&Int) || numLeft() < Int)
     return StringView();
   StringView R(First, First + Int);
   First += Int;
   return R;
 }
 
 // <function-type> ::= [<CV-qualifiers>] [<exception-spec>] [Dx] F [Y] <bare-function-type> [<ref-qualifier>] E
 //
 // <exception-spec> ::= Do                # non-throwing exception-specification (e.g., noexcept, throw())
 //                  ::= DO <expression> E # computed (instantiation-dependent) noexcept
 //                  ::= Dw <type>+ E      # dynamic exception specification with instantiation-dependent types
 //
 // <ref-qualifier> ::= R                   # & ref-qualifier
 // <ref-qualifier> ::= O                   # && ref-qualifier
-Node *Db::parseFunctionType() {
+template<typename Alloc> Node *Db<Alloc>::parseFunctionType() {
   Qualifiers CVQuals = parseCVQualifiers();
 
   Node *ExceptionSpec = nullptr;
   if (consumeIf("Do")) {
     ExceptionSpec = make<NameType>("noexcept");
+    if (!ExceptionSpec)
+      return nullptr;
   } else if (consumeIf("DO")) {
     Node *E = parseExpr();
     if (E == nullptr || !consumeIf('E'))
       return nullptr;
     ExceptionSpec = make<NoexceptSpec>(E);
+    if (!ExceptionSpec)
+      return nullptr;
   } else if (consumeIf("Dw")) {
     size_t SpecsBegin = Names.size();
     while (!consumeIf('E')) {
       Node *T = parseType();
       if (T == nullptr)
         return nullptr;
       Names.push_back(T);
     }
     ExceptionSpec =
       make<DynamicExceptionSpec>(popTrailingNodeArray(SpecsBegin));
+    if (!ExceptionSpec)
+      return nullptr;
   }
 
   consumeIf("Dx"); // transaction safe
 
   if (!consumeIf('F'))
     return nullptr;
   consumeIf('Y'); // extern "C"
   Node *ReturnType = parseType();
return make<FunctionType>(ReturnType, Params, CVQuals,
                             ReferenceQualifier, ExceptionSpec);
 }
 
 // extension:
 // <vector-type>           ::= Dv <positive dimension number> _ <extended element type>
 //                         ::= Dv [<dimension expression>] _ <element type>
 // <extended element type> ::= <element type>
 //                         ::= p # AltiVec vector pixel
-Node *Db::parseVectorType() {
+template<typename Alloc> Node *Db<Alloc>::parseVectorType() {
   if (!consumeIf("Dv"))
     return nullptr;
   if (look() >= '1' && look() <= '9') {
     StringView DimensionNumber = parseNumber();
     if (!consumeIf('_'))
       return nullptr;
     if (consumeIf('p'))
       return make<VectorType>(DimensionNumber);
template<typename Alloc> Node *Db<Alloc>::parseVectorType() {
   Node *ElemType = parseType();
   if (!ElemType)
     return nullptr;
   return make<VectorType>(ElemType, StringView());
 }
 
 // <decltype>  ::= Dt <expression> E  # decltype of an id-expression or class member access (C++0x)
 //             ::= DT <expression> E  # decltype of an expression (C++0x)
-Node *Db::parseDecltype() {
+template<typename Alloc> Node *Db<Alloc>::parseDecltype() {
   if (!consumeIf('D'))
     return nullptr;
   if (!consumeIf('t') && !consumeIf('T'))
     return nullptr;
   Node *E = parseExpr();
   if (E == nullptr)
     return nullptr;
   if (!consumeIf('E'))
     return nullptr;
   return make<EnclosingExpr>("decltype(", E, ")");
 }
 
 // <array-type> ::= A <positive dimension number> _ <element type>
 //              ::= A [<dimension expression>] _ <element type>
-Node *Db::parseArrayType() {
+template<typename Alloc> Node *Db<Alloc>::parseArrayType() {
   if (!consumeIf('A'))
     return nullptr;
 
   if (std::isdigit(look())) {
     StringView Dimension = parseNumber();
     if (!consumeIf('_'))
       return nullptr;
     Node *Ty = parseType();
template<typename Alloc> Node *Db<Alloc>::parseArrayType() {
 
   Node *Ty = parseType();
   if (Ty == nullptr)
     return nullptr;
   return make<ArrayType>(Ty);
 }
 
 // <pointer-to-member-type> ::= M <class type> <member type>
-Node *Db::parsePointerToMemberType() {
+template<typename Alloc> Node *Db<Alloc>::parsePointerToMemberType() {
   if (!consumeIf('M'))
     return nullptr;
   Node *ClassType = parseType();
   if (ClassType == nullptr)
     return nullptr;
   Node *MemberType = parseType();
   if (MemberType == nullptr)
     return nullptr;
   return make<PointerToMemberType>(ClassType, MemberType);
 }
 
 // <class-enum-type> ::= <name>     # non-dependent type name, dependent type name, or dependent typename-specifier
 //                   ::= Ts <name>  # dependent elaborated type specifier using 'struct' or 'class'
 //                   ::= Tu <name>  # dependent elaborated type specifier using 'union'
 //                   ::= Te <name>  # dependent elaborated type specifier using 'enum'
-Node *Db::parseClassEnumType() {
+template<typename Alloc> Node *Db<Alloc>::parseClassEnumType() {
   StringView ElabSpef;
   if (consumeIf("Ts"))
     ElabSpef = "struct";
   else if (consumeIf("Tu"))
     ElabSpef = "union";
   else if (consumeIf("Te"))
     ElabSpef = "enum";
 
   Node *Name = parseName();
   if (Name == nullptr)
     return nullptr;
 
   if (!ElabSpef.empty())
     return make<ElaboratedTypeSpefType>(ElabSpef, Name);
 
   return Name;
 }
 
 // <qualified-type>     ::= <qualifiers> <type>
 // <qualifiers> ::= <extended-qualifier>* <CV-qualifiers>
 // <extended-qualifier> ::= U <source-name> [<template-args>] # vendor extended type qualifier
-Node *Db::parseQualifiedType() {
+template<typename Alloc> Node *Db<Alloc>::parseQualifiedType() {
   if (consumeIf('U')) {
     StringView Qual = parseBareSourceName();
     if (Qual.empty())
       return nullptr;
 
     // FIXME parse the optional <template-args> here!
 
     // extension            ::= U <objc-name> <objc-type>  # objc-type<identifier>

 //             ::= C <type>        # complex pair (C99)
 //             ::= G <type>        # imaginary (C99)
 //             ::= <substitution>  # See Compression below
 // extension   ::= U <objc-name> <objc-type>  # objc-type<identifier>
 // extension   ::= <vector-type> # <vector-type> starts with Dv
 //
 // <objc-name> ::= <k0 number> objcproto <k1 number> <identifier>  # k0 = 9 + <number of digits in k1> + k1
 // <objc-type> ::= <source-name>  # PU<11+>objcproto 11objc_object<source-name> 11objc_object -> id<source-name>
-Node *Db::parseType() {
+template<typename Alloc> Node *Db<Alloc>::parseType() {
   Node *Result = nullptr;
 
   if (TypeCallback != nullptr)
     TypeCallback(TypeCallbackContext, First);
 
   switch (look()) {
   //             ::= <qualified-type>
   case 'r':
template<typename Alloc> Node *Db<Alloc>::parseType() {
   // If we parsed a type, insert it into the substitution table. Note that all
   // <builtin-type>s and <substitution>s have already bailed out, because they
   // don't get substitutions.
   if (Result != nullptr)
     Subs.push_back(Result);
   return Result;
 }
 
-Node *Db::parsePrefixExpr(StringView Kind) {
+template<typename Alloc> Node *Db<Alloc>::parsePrefixExpr(StringView Kind) {
   Node *E = parseExpr();
   if (E == nullptr)
     return nullptr;
   return make<PrefixExpr>(Kind, E);
 }
 
-Node *Db::parseBinaryExpr(StringView Kind) {
+template<typename Alloc> Node *Db<Alloc>::parseBinaryExpr(StringView Kind) {
   Node *LHS = parseExpr();
   if (LHS == nullptr)
     return nullptr;
   Node *RHS = parseExpr();
   if (RHS == nullptr)
     return nullptr;
   return make<BinaryExpr>(LHS, Kind, RHS);
 }
 
-Node *Db::parseIntegerLiteral(StringView Lit) {
+template<typename Alloc> Node *Db<Alloc>::parseIntegerLiteral(StringView Lit) {
   StringView Tmp = parseNumber(true);
   if (!Tmp.empty() && consumeIf('E'))
     return make<IntegerExpr>(Lit, Tmp);
   return nullptr;
 }
 
 // <CV-Qualifiers> ::= [r] [V] [K]
-Qualifiers Db::parseCVQualifiers() {
+template<typename Alloc> Qualifiers Db<Alloc>::parseCVQualifiers() {
   Qualifiers CVR = QualNone;
   if (consumeIf('r'))
     addQualifiers(CVR, QualRestrict);
   if (consumeIf('V'))
     addQualifiers(CVR, QualVolatile);
   if (consumeIf('K'))
     addQualifiers(CVR, QualConst);
   return CVR;
 }
 
 // <function-param> ::= fp <top-level CV-Qualifiers> _                                     # L == 0, first parameter
 //                  ::= fp <top-level CV-Qualifiers> <parameter-2 non-negative number> _   # L == 0, second and later parameters
 //                  ::= fL <L-1 non-negative number> p <top-level CV-Qualifiers> _         # L > 0, first parameter
 //                  ::= fL <L-1 non-negative number> p <top-level CV-Qualifiers> <parameter-2 non-negative number> _   # L > 0, second and later parameters
-Node *Db::parseFunctionParam() {
+template<typename Alloc> Node *Db<Alloc>::parseFunctionParam() {
   if (consumeIf("fp")) {
     parseCVQualifiers();
     StringView Num = parseNumber();
     if (!consumeIf('_'))
       return nullptr;
     return make<FunctionParam>(Num);
   }
   if (consumeIf("fL")) {
template<typename Alloc> Node *Db<Alloc>::parseFunctionParam() {
   return nullptr;
 }
 
 // [gs] nw <expression>* _ <type> E                     # new (expr-list) type
 // [gs] nw <expression>* _ <type> <initializer>         # new (expr-list) type (init)
 // [gs] na <expression>* _ <type> E                     # new[] (expr-list) type
 // [gs] na <expression>* _ <type> <initializer>         # new[] (expr-list) type (init)
 // <initializer> ::= pi <expression>* E                 # parenthesized initialization
-Node *Db::parseNewExpr() {
+template<typename Alloc> Node *Db<Alloc>::parseNewExpr() {
   bool Global = consumeIf("gs");
   bool IsArray = look(1) == 'a';
   if (!consumeIf("nw") && !consumeIf("na"))
     return nullptr;
   size_t Exprs = Names.size();
   while (!consumeIf('_')) {
     Node *Ex = parseExpr();
     if (Ex == nullptr)
if (consumeIf("pi")) {
     return make<NewExpr>(ExprList, Ty, Inits, Global, IsArray);
   } else if (!consumeIf('E'))
     return nullptr;
   return make<NewExpr>(ExprList, Ty, NodeArray(), Global, IsArray);
 }
 
 // cv <type> <expression>                               # conversion with one argument
 // cv <type> _ <expression>* E                          # conversion with a different number of arguments
-Node *Db::parseConversionExpr() {
+template<typename Alloc> Node *Db<Alloc>::parseConversionExpr() {
   if (!consumeIf("cv"))
     return nullptr;
   Node *Ty;
   {
     SwapAndRestore<bool> SaveTemp(TryToParseTemplateArgs, false);
     Ty = parseType();
   }
 

 }
 
 // <expr-primary> ::= L <type> <value number> E                          # integer literal
 //                ::= L <type> <value float> E                           # floating literal
 //                ::= L <string type> E                                  # string literal
 //                ::= L <nullptr type> E                                 # nullptr literal (i.e., "LDnE")
 // FIXME:         ::= L <type> <real-part float> _ <imag-part float> E   # complex floating point literal (C 2000)
 //                ::= L <mangled-name> E                                 # external name
-Node *Db::parseExprPrimary() {
+template<typename Alloc> Node *Db<Alloc>::parseExprPrimary() {
   if (!consumeIf('L'))
     return nullptr;
   switch (look()) {
   case 'w':
     ++First;
     return parseIntegerLiteral("wchar_t");
   case 'b':
     if (consumeIf("b0E"))
template<typename Alloc> Node *Db<Alloc>::parseExprPrimary() {
   }
   }
 }
 
 // <braced-expression> ::= <expression>
 //                     ::= di <field source-name> <braced-expression>    # .name = expr
 //                     ::= dx <index expression> <braced-expression>     # [expr] = expr
 //                     ::= dX <range begin expression> <range end expression> <braced-expression>
-Node *Db::parseBracedExpr() {
+template<typename Alloc> Node *Db<Alloc>::parseBracedExpr() {
   if (look() == 'd') {
     switch (look(1)) {
     case 'i': {
       First += 2;
       Node *Field = parseSourceName(/*NameState=*/nullptr);
       if (Field == nullptr)
         return nullptr;
       Node *Init = parseBracedExpr();
template<typename Alloc> Node *Db<Alloc>::parseBracedExpr() {
   return parseExpr();
 }
 
 // (not yet in the spec)
 // <fold-expr> ::= fL <binary-operator-name> <expression> <expression>
 //             ::= fR <binary-operator-name> <expression> <expression>
 //             ::= fl <binary-operator-name> <expression>
 //             ::= fr <binary-operator-name> <expression>
-Node *Db::parseFoldExpr() {
+template<typename Alloc> Node *Db<Alloc>::parseFoldExpr() {
   if (!consumeIf('f'))
     return nullptr;
 
   char FoldKind = look();
   bool IsLeftFold, HasInitializer;
   HasInitializer = FoldKind == 'L' || FoldKind == 'R';
   if (FoldKind == 'l' || FoldKind == 'L')
     IsLeftFold = true;

 //              ::= <unresolved-name>                                    # f(p), N::f(p), ::f(p),
 //                                                                       # freestanding dependent name (e.g., T::x),
 //                                                                       # objectless nonstatic member reference
 //              ::= fL <binary-operator-name> <expression> <expression>
 //              ::= fR <binary-operator-name> <expression> <expression>
 //              ::= fl <binary-operator-name> <expression>
 //              ::= fr <binary-operator-name> <expression>
 //              ::= <expr-primary>
-Node *Db::parseExpr() {
+template<typename Alloc> Node *Db<Alloc>::parseExpr() {
   bool Global = consumeIf("gs");
   if (numLeft() < 2)
     return nullptr;
 
   switch (*First) {
   case 'L':
     return parseExprPrimary();
   case 'T':
case 'P': {
       First += 2;
       size_t ArgsBegin = Names.size();
       while (!consumeIf('E')) {
         Node *Arg = parseTemplateArg();
         if (Arg == nullptr)
           return nullptr;
         Names.push_back(Arg);
       }
-      return make<EnclosingExpr>(
-          "sizeof... (", make<NodeArrayNode>(popTrailingNodeArray(ArgsBegin)),
-          ")");
+      auto *Pack = make<NodeArrayNode>(popTrailingNodeArray(ArgsBegin));
+      return make<EnclosingExpr>("sizeof... (", Pack, ")");
     }
     }
     return nullptr;
   case 't':
     switch (First[1]) {
     case 'e': {
       First += 2;
       Node *Ex = parseExpr();

 // <call-offset> ::= h <nv-offset> _
 //               ::= v <v-offset> _
 //
 // <nv-offset> ::= <offset number>
 //               # non-virtual base override
 //
 // <v-offset>  ::= <offset number> _ <virtual offset number>
 //               # virtual base override, with vcall offset
-bool Db::parseCallOffset() {
+template<typename Alloc> bool Db<Alloc>::parseCallOffset() {
   // Just scan through the call offset, we never add this information into the
   // output.
   if (consumeIf('h'))
     return parseNumber(true).empty() || !consumeIf('_');
   if (consumeIf('v'))
     return parseNumber(true).empty() || !consumeIf('_') ||
            parseNumber(true).empty() || !consumeIf('_');
   return true;

 //                ::= GV <object name> # Guard variable for one-time initialization
 //                                     # No <type>
 //                ::= TW <object name> # Thread-local wrapper
 //                ::= TH <object name> # Thread-local initialization
 //                ::= GR <object name> _             # First temporary
 //                ::= GR <object name> <seq-id> _    # Subsequent temporaries
 //      extension ::= TC <first type> <number> _ <second type> # construction vtable for second-in-first
 //      extension ::= GR <object name> # reference temporary for object
-Node *Db::parseSpecialName() {
+template<typename Alloc> Node *Db<Alloc>::parseSpecialName() {
   switch (look()) {
   case 'T':
     switch (look(1)) {
     // TV <type>    # virtual table
     case 'V': {
       First += 2;
       Node *Ty = parseType();
       if (Ty == nullptr)
case 'G':
     }
   }
   return nullptr;
 }
 
 // <encoding> ::= <function name> <bare-function-type>
 //            ::= <data name>
 //            ::= <special-name>
-Node *Db::parseEncoding() {
+template<typename Alloc> Node *Db<Alloc>::parseEncoding() {
   if (look() == 'G' || look() == 'T')
     return parseSpecialName();
 
   auto IsEndOfEncoding = [&] {
     // The set of chars that can potentially follow an <encoding> (none of which
     // can start a <type>). Enumerating these allows us to avoid speculative
     // parsing.
     return numLeft() == 0 || look() == 'E' || look() == '.' || look() == '_';
#else
     static const size_t mangled_size = 20;  // May need to be adjusted to 16 or 24 on other platforms
 #endif
     static const size_t max_demangled_size = 40;
     static constexpr const char *spec = "%LaL";
 };
 
 constexpr const char *FloatData<long double>::spec;
 
-template <class Float> Node *Db::parseFloatingLiteral() {
+template<typename Alloc>
+template<class Float>
+Node *Db<Alloc>::parseFloatingLiteral() {
   const size_t N = FloatData<Float>::mangled_size;
   if (numLeft() <= N)
     return nullptr;
   StringView Data(First, First + N);
   for (char C : Data)
     if (!std::isxdigit(C))
       return nullptr;
   First += N;
   if (!consumeIf('E'))
     return nullptr;
   return make<FloatExpr<Float>>(Data);
 }
 
 // <seq-id> ::= <0-9A-Z>+
-bool Db::parseSeqId(size_t *Out) {
+template<typename Alloc> bool Db<Alloc>::parseSeqId(size_t *Out) {
   if (!(look() >= '0' && look() <= '9') &&
       !(look() >= 'A' && look() <= 'Z'))
     return true;
 
   size_t Id = 0;
   while (true) {
     if (look() >= '0' && look() <= '9') {
       Id *= 36;

 // <substitution> ::= Sa # ::std::allocator
 // <substitution> ::= Sb # ::std::basic_string
 // <substitution> ::= Ss # ::std::basic_string < char,
 //                                               ::std::char_traits<char>,
 //                                               ::std::allocator<char> >
 // <substitution> ::= Si # ::std::basic_istream<char,  std::char_traits<char> >
 // <substitution> ::= So # ::std::basic_ostream<char,  std::char_traits<char> >
 // <substitution> ::= Sd # ::std::basic_iostream<char, std::char_traits<char> >
-Node *Db::parseSubstitution() {
+template<typename Alloc> Node *Db<Alloc>::parseSubstitution() {
   if (!consumeIf('S'))
     return nullptr;
 
   if (std::islower(look())) {
     Node *SpecialSub;
     switch (look()) {
     case 'a':
       ++First;
case 'o':
       break;
     case 'd':
       ++First;
       SpecialSub = make<SpecialSubstitution>(SpecialSubKind::iostream);
       break;
     default:
       return nullptr;
     }
+    if (!SpecialSub)
+      return nullptr;
     // Itanium C++ ABI 5.1.2: If a name that would use a built-in <substitution>
     // has ABI tags, the tags are appended to the substitution; the result is a
     // substitutable component.
     Node *WithTags = parseAbiTags(SpecialSub);
     if (WithTags != SpecialSub) {
       Subs.push_back(WithTags);
       SpecialSub = WithTags;
     }
template<typename Alloc> Node *Db<Alloc>::parseSubstitution() {
   ++Index;
   if (!consumeIf('_') || Index >= Subs.size())
     return nullptr;
   return Subs[Index];
 }
 
 // <template-param> ::= T_    # first template parameter
 //                  ::= T <parameter-2 non-negative number> _
-Node *Db::parseTemplateParam() {
+template<typename Alloc> Node *Db<Alloc>::parseTemplateParam() {
   if (!consumeIf('T'))
     return nullptr;
 
   size_t Index = 0;
   if (!consumeIf('_')) {
     if (parsePositiveInteger(&Index))
       return nullptr;
     ++Index;
     if (!consumeIf('_'))
       return nullptr;
   }
 
   // Itanium ABI 5.1.8: In a generic lambda, uses of auto in the parameter list
   // are mangled as the corresponding artificial template type parameter.
   if (ParsingLambdaParams)
     return make<NameType>("auto");
 
   // If we're in a context where this <template-param> refers to a
   // <template-arg> further ahead in the mangled name (currently just conversion
   // operator types), then we should only look it up in the right context.
   if (PermitForwardTemplateReferences) {
-    ForwardTemplateRefs.push_back(make<ForwardTemplateReference>(Index));
-    return ForwardTemplateRefs.back();
+    Node *ForwardRef = make<ForwardTemplateReference>(Index);
+    if (!ForwardRef)
+      return nullptr;
+    assert(ForwardRef->getKind() == Node::KForwardTemplateReference);
+    ForwardTemplateRefs.push_back(
+        static_cast<ForwardTemplateReference *>(ForwardRef));
+    return ForwardRef;
   }
 
   if (Index >= TemplateParams.size())
     return nullptr;
   return TemplateParams[Index];
 }
 
 // <template-arg> ::= <type>                    # type or template
 //                ::= X <expression> E          # expression
 //                ::= <expr-primary>            # simple expressions
 //                ::= J <template-arg>* E       # argument pack
 //                ::= LZ <encoding> E           # extension
-Node *Db::parseTemplateArg() {
+template<typename Alloc> Node *Db<Alloc>::parseTemplateArg() {
   switch (look()) {
   case 'X': {
     ++First;
     Node *Arg = parseExpr();
     if (Arg == nullptr || !consumeIf('E'))
       return nullptr;
     return Arg;
   }
template<typename Alloc> Node *Db<Alloc>::parseTemplateArg() {
   }
   default:
     return parseType();
   }
 }
 
 // <template-args> ::= I <template-arg>* E
 //     extension, the abi says <template-arg>+
-Node *Db::parseTemplateArgs(bool TagTemplates) {
+template <typename Alloc>
+Node *Db<Alloc>::parseTemplateArgs(bool TagTemplates) {
   if (!consumeIf('I'))
     return nullptr;
 
   // <template-params> refer to the innermost <template-args>. Clear out any
   // outer args that we may have inserted into TemplateParams.
   if (TagTemplates)
     TemplateParams.clear();
 
   size_t ArgsBegin = Names.size();
   while (!consumeIf('E')) {
     if (TagTemplates) {
       auto OldParams = std::move(TemplateParams);
       Node *Arg = parseTemplateArg();
       TemplateParams = std::move(OldParams);
       if (Arg == nullptr)
         return nullptr;
       Names.push_back(Arg);
       Node *TableEntry = Arg;
       if (Arg->getKind() == Node::KTemplateArgumentPack) {
         TableEntry = make<ParameterPack>(
             static_cast<TemplateArgumentPack*>(TableEntry)->getElements());
+        if (!TableEntry)
+          return nullptr;
       }
       TemplateParams.push_back(TableEntry);
     } else {
       Node *Arg = parseTemplateArg();
       if (Arg == nullptr)
         return nullptr;
       Names.push_back(Arg);
     }
parse_discriminator(const char* first, const char* last)
     return first;
 }
 
 // <mangled-name> ::= _Z <encoding>
 //                ::= <type>
 // extension      ::= ___Z <encoding> _block_invoke
 // extension      ::= ___Z <encoding> _block_invoke<decimal-digit>+
 // extension      ::= ___Z <encoding> _block_invoke_<decimal-digit>+
-Node *Db::parse() {
+template<typename Alloc> Node *Db<Alloc>::parse() {
   if (consumeIf("_Z")) {
     Node *Encoding = parseEncoding();
     if (Encoding == nullptr)
       return nullptr;
     if (look() == '.') {
       Encoding = make<DotSuffix>(Encoding, StringView(First, Last));
       First = Last;
     }
char *llvm::itaniumDemangle(const char *MangledName, char *Buf,
                             size_t *N, int *Status) {
   if (MangledName == nullptr || (Buf != nullptr && N == nullptr)) {
     if (Status)
       *Status = demangle_invalid_args;
     return nullptr;
   }
 
   int InternalStatus = demangle_success;
-  Db Parser(MangledName, MangledName + std::strlen(MangledName));
+  Db<> Parser(MangledName, MangledName + std::strlen(MangledName));
   OutputStream S;
 
   Node *AST = Parser.parse();
 
   if (AST == nullptr)
     InternalStatus = demangle_invalid_mangled_name;
   else if (initializeOutputStream(Buf, N, S, 1024))
     InternalStatus = demangle_memory_alloc_failure;
char *llvm::itaniumDemangle(const char *MangledName, char *Buf,
   if (Status)
     *Status = InternalStatus;
   return InternalStatus == demangle_success ? Buf : nullptr;
 }
 
 bool llvm::itaniumFindTypesInMangledName(const char *MangledName, void *Ctx,
                                          void (*Callback)(void *,
                                                           const char *)) {
-  Db Parser(MangledName, MangledName + std::strlen(MangledName));
+  Db<> Parser(MangledName, MangledName + std::strlen(MangledName));
   Parser.TypeCallback = Callback;
   Parser.TypeCallbackContext = Ctx;
   return Parser.parse() == nullptr;
 }
 
 namespace llvm {
 
 ItaniumPartialDemangler::ItaniumPartialDemangler()
-    : RootNode(nullptr), Context(new Db{nullptr, nullptr}) {}
+    : RootNode(nullptr), Context(new Db<>{nullptr, nullptr}) {}
 
 ItaniumPartialDemangler::~ItaniumPartialDemangler() {
-  delete static_cast<Db *>(Context);
+  delete static_cast<Db<> *>(Context);
 }
 
 ItaniumPartialDemangler::ItaniumPartialDemangler(
     ItaniumPartialDemangler &&Other)
     : RootNode(Other.RootNode), Context(Other.Context) {
   Other.Context = Other.RootNode = nullptr;
 }
 
 ItaniumPartialDemangler &ItaniumPartialDemangler::
 operator=(ItaniumPartialDemangler &&Other) {
   std::swap(RootNode, Other.RootNode);
   std::swap(Context, Other.Context);
   return *this;
 }
 
 // Demangle MangledName into an AST, storing it into this->RootNode.
 bool ItaniumPartialDemangler::partialDemangle(const char *MangledName) {
-  Db *Parser = static_cast<Db *>(Context);
+  Db<> *Parser = static_cast<Db<> *>(Context);
   size_t Len = std::strlen(MangledName);
   Parser->reset(MangledName, MangledName + Len);
   RootNode = Parser->parse();
   return RootNode == nullptr;
 }
 
-static char *printNode(Node *RootNode, char *Buf, size_t *N) {
+static char *printNode(const Node *RootNode, char *Buf, size_t *N) {
   OutputStream S;
   if (initializeOutputStream(Buf, N, S, 128))
     return nullptr;
   RootNode->print(S);
   S += '\0';
   if (N != nullptr)
     *N = S.getCurrentPosition();
   return S.getBuffer();
 }
 
 char *ItaniumPartialDemangler::getFunctionBaseName(char *Buf, size_t *N) const {
   if (!isFunction())
     return nullptr;
 
-  Node *Name = static_cast<FunctionEncoding *>(RootNode)->getName();
+  const Node *Name = static_cast<const FunctionEncoding *>(RootNode)->getName();
 
   while (true) {
     switch (Name->getKind()) {
     case Node::KAbiTagAttr:
-      Name = static_cast<AbiTagAttr *>(Name)->Base;
-      continue;
-    case Node::KStdQualifiedName:
-      Name = static_cast<StdQualifiedName *>(Name)->Child;
+      Name = static_cast<const AbiTagAttr *>(Name)->Base;
       continue;
     case Node::KNestedName:
-      Name = static_cast<NestedName *>(Name)->Name;
+      Name = static_cast<const NestedName *>(Name)->Name;
       continue;
     case Node::KLocalName:
-      Name = static_cast<LocalName *>(Name)->Entity;
+      Name = static_cast<const LocalName *>(Name)->Entity;
       continue;
     case Node::KNameWithTemplateArgs:
-      Name = static_cast<NameWithTemplateArgs *>(Name)->Name;
+      Name = static_cast<const NameWithTemplateArgs *>(Name)->Name;
       continue;
     default:
       return printNode(Name, Buf, N);
     }
   }
 }
 
 char *ItaniumPartialDemangler::getFunctionDeclContextName(char *Buf,
                                                           size_t *N) const {
   if (!isFunction())
     return nullptr;
-  Node *Name = static_cast<FunctionEncoding *>(RootNode)->getName();
+  const Node *Name = static_cast<const FunctionEncoding *>(RootNode)->getName();
 
   OutputStream S;
   if (initializeOutputStream(Buf, N, S, 128))
     return nullptr;
 
  KeepGoingLocalFunction:
   while (true) {
     if (Name->getKind() == Node::KAbiTagAttr) {
-      Name = static_cast<AbiTagAttr *>(Name)->Base;
+      Name = static_cast<const AbiTagAttr *>(Name)->Base;
       continue;
     }
     if (Name->getKind() == Node::KNameWithTemplateArgs) {
-      Name = static_cast<NameWithTemplateArgs *>(Name)->Name;
+      Name = static_cast<const NameWithTemplateArgs *>(Name)->Name;
       continue;
     }
     break;
   }
 
   switch (Name->getKind()) {
-  case Node::KStdQualifiedName:
-    S += "std";
-    break;
   case Node::KNestedName:
-    static_cast<NestedName *>(Name)->Qual->print(S);
+    static_cast<const NestedName *>(Name)->Qual->print(S);
     break;
   case Node::KLocalName: {
-    auto *LN = static_cast<LocalName *>(Name);
+    auto *LN = static_cast<const LocalName *>(Name);
     LN->Encoding->print(S);
     S += "::";
     Name = LN->Entity;
     goto KeepGoingLocalFunction;
   }
   default:
     break;
   }
char *ItaniumPartialDemangler::getFunctionReturnType(
     char *Buf, size_t *N) const {
   if (!isFunction())
     return nullptr;
 
   OutputStream S;
   if (initializeOutputStream(Buf, N, S, 128))
     return nullptr;
 
-  if (Node *Ret = static_cast<FunctionEncoding *>(RootNode)->getReturnType())
+  if (const Node *Ret =
+          static_cast<const FunctionEncoding *>(RootNode)->getReturnType())
     Ret->print(S);
 
   S += '\0';
   if (N != nullptr)
     *N = S.getCurrentPosition();
   return S.getBuffer();
 }
 
 char *ItaniumPartialDemangler::finishDemangle(char *Buf, size_t *N) const {
   assert(RootNode != nullptr && "must call partialDemangle()");
   return printNode(static_cast<Node *>(RootNode), Buf, N);
 }
 
 bool ItaniumPartialDemangler::hasFunctionQualifiers() const {
   assert(RootNode != nullptr && "must call partialDemangle()");
   if (!isFunction())
     return false;
-  auto *E = static_cast<FunctionEncoding *>(RootNode);
+  auto *E = static_cast<const FunctionEncoding *>(RootNode);
   return E->getCVQuals() != QualNone || E->getRefQual() != FrefQualNone;
 }
 
 bool ItaniumPartialDemangler::isCtorOrDtor() const {
-  Node *N = static_cast<Node *>(RootNode);
+  const Node *N = static_cast<const Node *>(RootNode);
   while (N) {
     switch (N->getKind()) {
     default:
       return false;
     case Node::KCtorDtorName:
       return true;
 
     case Node::KAbiTagAttr:
-      N = static_cast<AbiTagAttr *>(N)->Base;
+      N = static_cast<const AbiTagAttr *>(N)->Base;
       break;
     case Node::KFunctionEncoding:
-      N = static_cast<FunctionEncoding *>(N)->getName();
+      N = static_cast<const FunctionEncoding *>(N)->getName();
       break;
     case Node::KLocalName:
-      N = static_cast<LocalName *>(N)->Entity;
+      N = static_cast<const LocalName *>(N)->Entity;
       break;
     case Node::KNameWithTemplateArgs:
-      N = static_cast<NameWithTemplateArgs *>(N)->Name;
+      N = static_cast<const NameWithTemplateArgs *>(N)->Name;
       break;
     case Node::KNestedName:
-      N = static_cast<NestedName *>(N)->Name;
-      break;
-    case Node::KStdQualifiedName:
-      N = static_cast<StdQualifiedName *>(N)->Child;
+      N = static_cast<const NestedName *>(N)->Name;
       break;
     }
   }
   return false;
 }
 
 bool ItaniumPartialDemangler::isFunction() const {
   assert(RootNode != nullptr && "must call partialDemangle()");
-  return static_cast<Node *>(RootNode)->getKind() == Node::KFunctionEncoding;
+  return static_cast<const Node *>(RootNode)->getKind() ==
+         Node::KFunctionEncoding;
 }
 
 bool ItaniumPartialDemangler::isSpecialName() const {
   assert(RootNode != nullptr && "must call partialDemangle()");
-  auto K = static_cast<Node *>(RootNode)->getKind();
+  auto K = static_cast<const Node *>(RootNode)->getKind();
   return K == Node::KSpecialName || K == Node::KCtorVtableSpecialName;
 }
 
 bool ItaniumPartialDemangler::isData() const {
   return !isFunction() && !isSpecialName();
 }
+}  // namespace llvm
+
+#ifndef STANDALONE_DEMANGLER
+namespace {
+class CanonicalizerAllocator : public FoldingNodeAllocator {
+  Node *MostRecentlyCreated = nullptr;
+  Node *TrackedNode = nullptr;
+  bool TrackedNodeIsUsed = false;
+  bool CreateNewNodes = true;
+  llvm::SmallDenseMap<Node*, Node*, 32> Remappings;
+
+public:
+  void reset() { MostRecentlyCreated = nullptr; }
+
+  void setCreateNewNodes(bool CNN) { CreateNewNodes = CNN; }
+
+  template<typename T, typename ...Args> Node *makeNode(Args &&...args) {
+    std::pair<Node *, bool> Result =
+        makeNodeImpl<T>(CreateNewNodes, std::forward<Args>(args)...);
+    if (Result.second) {
+      // Node is new. Make a note of that.
+      MostRecentlyCreated = Result.first;
+    } else if (Result.first) {
+      // Node is pre-existing; check if it's in our remapping table.
+      if (auto *N = Remappings.lookup(Result.first)) {
+        Result.first = N;
+        assert(Remappings.find(Result.first) == Remappings.end() &&
+               "should never need multiple remap steps");
+      }
+      if (Result.first == TrackedNode)
+        TrackedNodeIsUsed = true;
+    }
+    return Result.first;
+  }
+
+  void addRemapping(Node *A, Node *B) {
+    // Note, we don't need to check whether B is also remapped, because if it
+    // was we would have already remapped it when building it.
+    Remappings.insert(std::make_pair(A, B));
+  }
+
+  bool isMostRecentlyCreated(Node *N) const { return MostRecentlyCreated == N; }
+
+  void trackUsesOf(Node *N) {
+    TrackedNode = N;
+    TrackedNodeIsUsed = false;
+  }
+  bool trackedNodeIsUsed() const { return TrackedNodeIsUsed; }
+};
+}
+
+namespace llvm {
+struct ItaniumManglingCanonicalizer::Impl {
+  Db<CanonicalizerAllocator> Demangler = {nullptr, nullptr};
+};
+
+ItaniumManglingCanonicalizer::ItaniumManglingCanonicalizer() : P(new Impl) {}
+ItaniumManglingCanonicalizer::~ItaniumManglingCanonicalizer() { delete P; }
+
+ItaniumManglingCanonicalizer::EquivalenceError
+ItaniumManglingCanonicalizer::addEquivalence(FragmentKind Kind, StringRef First,
+                                             StringRef Second) {
+  auto &Alloc = P->Demangler.ASTAllocator;
+  Alloc.setCreateNewNodes(true);
+
+  auto Parse = [&](StringRef Str) {
+    P->Demangler.reset(Str.begin(), Str.end());
+    Node *N = nullptr;
+    switch (Kind) {
+      // A <name>, with minor extensions to allow arbitrary namespace and
+      // template names that can't easily be written as <name>s.
+    case FragmentKind::Name:
+      // Very special case: allow "St" as a shorthand for "3std". It's not
+      // valid as a <name> mangling, but is nonetheless the most natural
+      // way to name the 'std' namespace.
+      if (Str.size() == 2 && P->Demangler.consumeIf("St"))
+        N = P->Demangler.make<NameType>("std");
+      // We permit substitutions to name templates without their template
+      // arguments. This mostly just falls out, as almost all template names
+      // are valid as <name>s, but we also want to parse <substitution>s as
+      // <name>s, even though they're not.
+      else if (Str.startswith("S"))
+        // Parse the substitution and optional following template arguments.
+        N = P->Demangler.parseType();
+      else
+        N = P->Demangler.parseName();
+      break;
+
+      // A <type>.
+    case FragmentKind::Type:
+      N = P->Demangler.parseType();
+      break;
+
+      // An <encoding>.
+    case FragmentKind::Encoding:
+      N = P->Demangler.parseEncoding();
+      break;
+    }
+
+    // If we have trailing junk, the mangling is invalid.
+    if (P->Demangler.numLeft() != 0)
+      N = nullptr;
+
+    // If any node was created after N, then we cannot safely remap it because
+    // it might already be in use by another node.
+    return std::make_pair(N, Alloc.isMostRecentlyCreated(N));
+  };
+
+  Node *FirstNode, *SecondNode;
+  bool FirstIsNew, SecondIsNew;
+
+  std::tie(FirstNode, FirstIsNew) = Parse(First);
+  if (!FirstNode)
+    return EquivalenceError::InvalidFirstMangling;
+
+  Alloc.trackUsesOf(FirstNode);
+  std::tie(SecondNode, SecondIsNew) = Parse(Second);
+  if (!SecondNode)
+    return EquivalenceError::InvalidSecondMangling;
+
+  if (FirstIsNew && !Alloc.trackedNodeIsUsed())
+    Alloc.addRemapping(FirstNode, SecondNode);
+  else if (SecondIsNew)
+    Alloc.addRemapping(SecondNode, FirstNode);
+  else
+    return EquivalenceError::ManglingAlreadyUsed;
+
+  return EquivalenceError::Success;
+}
+
+ItaniumManglingCanonicalizer::Key
+ItaniumManglingCanonicalizer::canonicalize(StringRef Mangling) {
+  P->Demangler.ASTAllocator.setCreateNewNodes(true);
+  P->Demangler.reset(Mangling.begin(), Mangling.end());
+  return reinterpret_cast<Key>(P->Demangler.parse());
+}
+
+ItaniumManglingCanonicalizer::Key
+ItaniumManglingCanonicalizer::lookup(StringRef Mangling) {
+  P->Demangler.ASTAllocator.setCreateNewNodes(false);
+  P->Demangler.reset(Mangling.begin(), Mangling.end());
+  return reinterpret_cast<Key>(P->Demangler.parse());
 }
+} // namespace llvm
+#endif

lib/LTO/LTO.cpp

for (auto &V : UsedCfiDefs)
     AddUint64(V);
 
   AddUnsigned(UsedCfiDecls.size());
   for (auto &V : UsedCfiDecls)
     AddUint64(V);
 
   if (!Conf.SampleProfile.empty()) {
     auto FileOrErr = MemoryBuffer::getFile(Conf.SampleProfile);
+    if (FileOrErr) {
+      Hasher.update(FileOrErr.get()->getBuffer());
+
+      if (!Conf.ProfileRemapping.empty()) {
+        FileOrErr = MemoryBuffer::getFile(Conf.ProfileRemapping);
         if (FileOrErr)
           Hasher.update(FileOrErr.get()->getBuffer());
       }
+    }
+  }
 
   Key = toHex(Hasher.result());
 }
 
 static void thinLTOResolveWeakForLinkerGUID(
     GlobalValueSummaryList &GVSummaryList, GlobalValue::GUID GUID,
     DenseSet<GlobalValueSummary *> &GlobalInvolvedWithAlias,
     function_ref<bool(GlobalValue::GUID, const GlobalValueSummary *)>

lib/LTO/LTOBackend.cpp

 }
 
 static void runNewPMPasses(Config &Conf, Module &Mod, TargetMachine *TM,
                            unsigned OptLevel, bool IsThinLTO,
                            ModuleSummaryIndex *ExportSummary,
                            const ModuleSummaryIndex *ImportSummary) {
   Optional<PGOOptions> PGOOpt;
   if (!Conf.SampleProfile.empty())
-    PGOOpt = PGOOptions("", "", Conf.SampleProfile, false, true);
+    PGOOpt = PGOOptions("", "", Conf.SampleProfile, Conf.ProfileRemapping,
+                        false, true);
 
   PassBuilder PB(TM, PGOOpt);
   AAManager AA;
 
   // Parse a custom AA pipeline if asked to.
   if (!PB.parseAAPipeline(AA, "default"))
     report_fatal_error("Error parsing default AA pipeline");
 

lib/Passes/PassBuilder.cpp

PassBuilder::buildFunctionSimplificationPipeline(OptimizationLevel Level,
 
   return FPM;
 }
 
 void PassBuilder::addPGOInstrPasses(ModulePassManager &MPM, bool DebugLogging,
                                     PassBuilder::OptimizationLevel Level,
                                     bool RunProfileGen,
                                     std::string ProfileGenFile,
-                                    std::string ProfileUseFile) {
+                                    std::string ProfileUseFile,
+                                    std::string ProfileRemappingFile) {
   // Generally running simplification passes and the inliner with an high
   // threshold results in smaller executables, but there may be cases where
   // the size grows, so let's be conservative here and skip this simplification
   // at -Os/Oz.
   if (!isOptimizingForSize(Level)) {
     InlineParams IP;
 
     // In the old pass manager, this is a cl::opt. Should still this be one?
if (RunProfileGen) {
     InstrProfOptions Options;
     if (!ProfileGenFile.empty())
       Options.InstrProfileOutput = ProfileGenFile;
     Options.DoCounterPromotion = true;
     MPM.addPass(InstrProfiling(Options));
   }
 
   if (!ProfileUseFile.empty())
-    MPM.addPass(PGOInstrumentationUse(ProfileUseFile));
+    MPM.addPass(PGOInstrumentationUse(ProfileUseFile, ProfileRemappingFile));
 }
 
 static InlineParams
 getInlineParamsFromOptLevel(PassBuilder::OptimizationLevel Level) {
   auto O3 = PassBuilder::O3;
   unsigned OptLevel = Level > O3 ? 2 : Level;
   unsigned SizeLevel = Level > O3 ? Level - O3 : 0;
   return getInlineParams(OptLevel, SizeLevel);
if (PGOOpt && !PGOOpt->SampleProfileFile.empty() &&
       Phase == ThinLTOPhase::PostLink)
     EarlyFPM.addPass(InstCombinePass());
   MPM.addPass(createModuleToFunctionPassAdaptor(std::move(EarlyFPM)));
 
   if (PGOOpt && !PGOOpt->SampleProfileFile.empty()) {
     // Annotate sample profile right after early FPM to ensure freshness of
     // the debug info.
     MPM.addPass(SampleProfileLoaderPass(PGOOpt->SampleProfileFile,
+                                        PGOOpt->ProfileRemappingFile,
                                         Phase == ThinLTOPhase::PreLink));
     // Do not invoke ICP in the ThinLTOPrelink phase as it makes it hard
     // for the profile annotation to be accurate in the ThinLTO backend.
     if (Phase != ThinLTOPhase::PreLink)
       // We perform early indirect call promotion here, before globalopt.
       // This is important for the ThinLTO backend phase because otherwise
       // imported available_externally functions look unreferenced and are
       // removed.
PassBuilder::buildModuleSimplificationPipeline(OptimizationLevel Level,
 
   GlobalCleanupPM.addPass(SimplifyCFGPass());
   MPM.addPass(createModuleToFunctionPassAdaptor(std::move(GlobalCleanupPM)));
 
   // Add all the requested passes for instrumentation PGO, if requested.
   if (PGOOpt && Phase != ThinLTOPhase::PostLink &&
       (!PGOOpt->ProfileGenFile.empty() || !PGOOpt->ProfileUseFile.empty())) {
     addPGOInstrPasses(MPM, DebugLogging, Level, PGOOpt->RunProfileGen,
-                      PGOOpt->ProfileGenFile, PGOOpt->ProfileUseFile);
+                      PGOOpt->ProfileGenFile, PGOOpt->ProfileUseFile,
+                      PGOOpt->ProfileRemappingFile);
     MPM.addPass(PGOIndirectCallPromotion(false, false));
   }
 
   // Synthesize function entry counts for non-PGO compilation.
   if (EnableSyntheticCounts && !PGOOpt)
     MPM.addPass(SyntheticCountsPropagation());
 
   // Require the GlobalsAA analysis for the module so we can query it within

lib/ProfileData/CMakeLists.txt

 add_llvm_library(LLVMProfileData
   GCOV.cpp
   InstrProf.cpp
   InstrProfReader.cpp
   InstrProfWriter.cpp
   ProfileSummaryBuilder.cpp
+  ProfRemappingReader.cpp
   SampleProf.cpp
   SampleProfReader.cpp
   SampleProfWriter.cpp
 
   ADDITIONAL_HEADER_DIRS
   ${LLVM_MAIN_INCLUDE_DIR}/llvm/ProfileData
 
   DEPENDS
   intrinsics_gen
   )
 
 add_subdirectory(Coverage)

lib/ProfileData/InstrProfReader.cpp

 
 #include "llvm/ProfileData/InstrProfReader.h"
 #include "llvm/ADT/ArrayRef.h"
 #include "llvm/ADT/STLExtras.h"
 #include "llvm/ADT/StringRef.h"
 #include "llvm/IR/ProfileSummary.h"
 #include "llvm/ProfileData/InstrProf.h"
 #include "llvm/ProfileData/ProfileCommon.h"
+#include "llvm/ProfileData/ProfRemappingReader.h"
 #include "llvm/Support/Endian.h"
 #include "llvm/Support/Error.h"
 #include "llvm/Support/ErrorOr.h"
 #include "llvm/Support/MemoryBuffer.h"
 #include "llvm/Support/SwapByteOrder.h"
 #include <algorithm>
 #include <cctype>
 #include <cstddef>
InstrProfReader::create(std::unique_ptr<MemoryBuffer> Buffer) {
   // Initialize the reader and return the result.
   if (Error E = initializeReader(*Result))
     return std::move(E);
 
   return std::move(Result);
 }
 
 Expected<std::unique_ptr<IndexedInstrProfReader>>
-IndexedInstrProfReader::create(const Twine &Path) {
+IndexedInstrProfReader::create(const Twine &Path, const Twine &RemappingPath) {
   // Set up the buffer to read.
   auto BufferOrError = setupMemoryBuffer(Path);
   if (Error E = BufferOrError.takeError())
     return std::move(E);
-  return IndexedInstrProfReader::create(std::move(BufferOrError.get()));
+
+  // Set up the remapping buffer if requested.
+  std::unique_ptr<MemoryBuffer> RemappingBuffer;
+  std::string RemappingPathStr = RemappingPath.str();
+  if (!RemappingPathStr.empty()) {
+    auto RemappingBufferOrError = setupMemoryBuffer(RemappingPathStr);
+    if (Error E = RemappingBufferOrError.takeError())
+      return std::move(E);
+    RemappingBuffer = std::move(RemappingBufferOrError.get());
+  }
+
+  return IndexedInstrProfReader::create(std::move(BufferOrError.get()),
+                                        std::move(RemappingBuffer));
 }
 
 Expected<std::unique_ptr<IndexedInstrProfReader>>
-IndexedInstrProfReader::create(std::unique_ptr<MemoryBuffer> Buffer) {
+IndexedInstrProfReader::create(std::unique_ptr<MemoryBuffer> Buffer,
+                               std::unique_ptr<MemoryBuffer> RemappingBuffer) {
   // Sanity check the buffer.
   if (uint64_t(Buffer->getBufferSize()) > std::numeric_limits<unsigned>::max())
     return make_error<InstrProfError>(instrprof_error::too_large);
 
   // Create the reader.
   if (!IndexedInstrProfReader::hasFormat(*Buffer))
     return make_error<InstrProfError>(instrprof_error::bad_magic);
-  auto Result = llvm::make_unique<IndexedInstrProfReader>(std::move(Buffer));
+  auto Result = llvm::make_unique<IndexedInstrProfReader>(
+      std::move(Buffer), std::move(RemappingBuffer));
 
   // Initialize the reader and return the result.
   if (Error E = initializeReader(*Result))
     return std::move(E);
 
   return std::move(Result);
 }
 
InstrProfReaderIndex<HashTableImpl>::InstrProfReaderIndex(
     uint64_t Version) {
   FormatVersion = Version;
   HashTable.reset(HashTableImpl::Create(
       Buckets, Payload, Base,
       typename HashTableImpl::InfoType(HashType, Version)));
   RecordIterator = HashTable->data_begin();
 }
 
+template<typename HashTableImpl>
+class llvm::InstrProfReaderItaniumRemapper : public InstrProfReaderIndexBase {
+public:
+  InstrProfReaderItaniumRemapper(
+      std::unique_ptr<MemoryBuffer> RemapBuffer,
+      std::unique_ptr<InstrProfReaderIndex<HashTableImpl>> Underlying)
+      : RemapBuffer(std::move(RemapBuffer)), Underlying(std::move(Underlying)) {
+  }
+
+  Error populateRemappings() {
+    if (Error E = Remappings.read(*RemapBuffer))
+      return E;
+    for (StringRef Name : Underlying->HashTable->keys()) {
+      if (auto Key = Remappings.remap(Name))
+        MappedNames.insert({Key, Name});
+    }
+    return Error::success();
+  }
+
+  Error getRecords(StringRef FuncName,
+                   ArrayRef<NamedInstrProfRecord> &Data) override {
+    if (auto Key = Remappings.lookup(FuncName)) {
+      StringRef Remapped = MappedNames.lookup(Key);
+      if (!Remapped.empty())
+        FuncName = Remapped;
+    }
+    return Underlying->getRecords(FuncName, Data);
+  }
+
+  Error getRecords(ArrayRef<NamedInstrProfRecord> &Data) override {
+    return Underlying->getRecords(Data);
+  }
+  void advanceToNextKey() override { return Underlying->advanceToNextKey(); }
+  bool atEnd() const override { return Underlying->atEnd(); }
+  void setValueProfDataEndianness(support::endianness Endianness) override {
+    return Underlying->setValueProfDataEndianness(Endianness);
+  }
+  uint64_t getVersion() const override {
+    return Underlying->getVersion();
+  }
+  bool isIRLevelProfile() const override {
+    return Underlying->isIRLevelProfile();
+  }
+  Error populateSymtab(InstrProfSymtab &Symtab) override {
+    return Underlying->populateSymtab(Symtab);
+  }
+
+private:
+  /// The memory buffer containing the remapping configuration. Remappings
+  /// holds pointers into this buffer.
+  std::unique_ptr<MemoryBuffer> RemapBuffer;
+
+  /// The mangling remapper.
+  ItaniumProfileRemappingReader Remappings;
+
+  /// Mapping from mangled name keys to the name used for the key in the
+  /// profile data.
+  /// FIXME: Can we store a hashtable iterator instead of redoing lookup?
+  llvm::DenseMap<ItaniumProfileRemappingReader::Key, StringRef> MappedNames;
+
+  /// The real profile data reader.
+  std::unique_ptr<InstrProfReaderIndex<HashTableImpl>> Underlying;
+};
+
 bool IndexedInstrProfReader::hasFormat(const MemoryBuffer &DataBuffer) {
   using namespace support;
 
   if (DataBuffer.getBufferSize() < 8)
     return false;
   uint64_t Magic =
       endian::read<uint64_t, little, aligned>(DataBuffer.getBufferStart());
   // Verify that it's magical.
Error IndexedInstrProfReader::readHeader() {
   IndexedInstrProf::HashT HashType = static_cast<IndexedInstrProf::HashT>(
       endian::byte_swap<uint64_t, little>(Header->HashType));
   if (HashType > IndexedInstrProf::HashT::Last)
     return error(instrprof_error::unsupported_hash_type);
 
   uint64_t HashOffset = endian::byte_swap<uint64_t, little>(Header->HashOffset);
 
   // The rest of the file is an on disk hash table.
-  InstrProfReaderIndexBase *IndexPtr = nullptr;
-  IndexPtr = new InstrProfReaderIndex<OnDiskHashTableImplV3>(
+  auto IndexPtr =
+      llvm::make_unique<InstrProfReaderIndex<OnDiskHashTableImplV3>>(
           Start + HashOffset, Cur, Start, HashType, FormatVersion);
-  Index.reset(IndexPtr);
+
+  // Load the remapping table now if requested.
+  if (RemappingBuffer) {
+    auto Remapper = llvm::make_unique<
+        InstrProfReaderItaniumRemapper<OnDiskHashTableImplV3>>(
+        std::move(RemappingBuffer), std::move(IndexPtr));
+    if (Error E = Remapper->populateRemappings())
+      return E;
+    Index = std::move(Remapper);
+  } else {
+    Index = std::move(IndexPtr);
+  }
+
   return success();
 }
 
 InstrProfSymtab &IndexedInstrProfReader::getSymtab() {
   if (Symtab.get())
     return *Symtab.get();
 
   std::unique_ptr<InstrProfSymtab> NewSymtab = make_unique<InstrProfSymtab>();

lib/ProfileData/ProfRemappingReader.cpp

+//===- ProfRemappingReader.cpp - Read profile remapping file --------------===//
+//
+//                      The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This file contains definitions needed for reading and applying profile
+// remapping files.
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/ProfileData/ProfRemappingReader.h"
+#include "llvm/ADT/StringSwitch.h"
+#include "llvm/ADT/Twine.h"
+#include "llvm/IR/LLVMContext.h"
+#include "llvm/IR/DiagnosticInfo.h"
+#include "llvm/Support/LineIterator.h"
+
+using namespace llvm;
+
+char ProfileRemappingParseError::ID;
+
+/// Load a set of name remappings from a text file.
+///
+/// See the documentation at the top of the file for an explanation of
+/// the expected format.
+Error ItaniumProfileRemappingReader::read(MemoryBuffer &B) {
+  line_iterator LineIt(B, /*SkipBlanks=*/true, '#');
+
+  auto ReportError = [&](Twine Msg) {
+    return llvm::make_error<ProfileRemappingParseError>(
+        B.getBufferIdentifier(), LineIt.line_number(), Msg);
+  };
+
+  for (; !LineIt.is_at_eof(); ++LineIt) {
+    StringRef Line = *LineIt;
+    Line = Line.ltrim(' ');
+    // line_iterator only detects comments starting in column 1.
+    if (Line.startswith("#") || Line.empty())
+      continue;
+
+    SmallVector<StringRef, 4> Parts;
+    Line.split(Parts, ' ', /*MaxSplits*/-1, /*KeepEmpty*/false);
+
+    if (Parts.size() != 3)
+      return ReportError("Expected 'kind mangled_name mangled_name', "
+                         "found '" + Line + "'");
+
+    using FK = ItaniumManglingCanonicalizer::FragmentKind;
+    Optional<FK> FragmentKind = StringSwitch<Optional<FK>>(Parts[0])
+                                    .Case("name", FK::Name)
+                                    .Case("type", FK::Type)
+                                    .Case("encoding", FK::Encoding)
+                                    .Default(None);
+    if (!FragmentKind)
+      return ReportError("Invalid kind, expected 'name', 'type', or 'encoding',"
+                         " found '" + Parts[0] + "'");
+
+    using EE = ItaniumManglingCanonicalizer::EquivalenceError;
+    switch (Canonicalizer.addEquivalence(*FragmentKind, Parts[1], Parts[2])) {
+    case EE::Success:
+      break;
+
+    case EE::ManglingAlreadyUsed:
+      return ReportError("Manglings '" + Parts[1] + "' and '" + Parts[2] + "' "
+                         "have both been used in prior remappings. Move this "
+                         "remapping earlier in the file.");
+
+    case EE::InvalidFirstMangling:
+      return ReportError("Could not demangle '" + Parts[1] + "' "
+                         "as a <" + Parts[0] + ">; invalid mangling?");
+
+    case EE::InvalidSecondMangling:
+      return ReportError("Could not demangle '" + Parts[2] + "' "
+                         "as a <" + Parts[0] + ">; invalid mangling?");
+    }
+  }
+
+  return Error::success();
+}

lib/ProfileData/SampleProfReader.cpp

std::error_code SampleProfileReaderGCC::read() {
   return sampleprof_error::success;
 }
 
 bool SampleProfileReaderGCC::hasFormat(const MemoryBuffer &Buffer) {
   StringRef Magic(reinterpret_cast<const char *>(Buffer.getBufferStart()));
   return Magic == "adcg*704";
 }
 
+std::error_code SampleProfileReaderItaniumRemapper::read() {
+  // If the underlying data is in compact format, we can't remap it because
+  // we don't know what the original function names were.
+  if (getFormat() == SPF_Compact_Binary) {
+    Ctx.diagnose(DiagnosticInfoSampleProfile(
+        Buffer->getBufferIdentifier(),
+        "Profile data remapping cannot be applied to profile data "
+        "in compact format (original mangled names are not available).",
+        DS_Warning));
+    return sampleprof_error::success;
+  }
+
+  if (Error E = Remappings.read(*Buffer)) {
+    handleAllErrors(
+        std::move(E), [&](const ProfileRemappingParseError &ParseError) {
+          reportError(ParseError.getLineNum(), ParseError.getMessage());
+        });
+    return sampleprof_error::malformed;
+  }
+
+  for (auto &Sample : getProfiles())
+    if (auto Key = Remappings.remap(Sample.first()))
+      SampleMap.insert({Key, &Sample.second});
+
+  return sampleprof_error::success;
+}
+
+FunctionSamples *
+SampleProfileReaderItaniumRemapper::getSamplesFor(StringRef Fname) {
+  if (auto Key = Remappings.lookup(Fname))
+    return SampleMap.lookup(Key);
+  return SampleProfileReader::getSamplesFor(Fname);
+}
+
 /// Prepare a memory buffer for the contents of \p Filename.
 ///
 /// \returns an error code indicating the status of the buffer.
 static ErrorOr<std::unique_ptr<MemoryBuffer>>
 setupMemoryBuffer(const Twine &Filename) {
   auto BufferOrErr = MemoryBuffer::getFileOrSTDIN(Filename);
   if (std::error_code EC = BufferOrErr.getError())
     return EC;

 ErrorOr<std::unique_ptr<SampleProfileReader>>
 SampleProfileReader::create(const Twine &Filename, LLVMContext &C) {
   auto BufferOrError = setupMemoryBuffer(Filename);
   if (std::error_code EC = BufferOrError.getError())
     return EC;
   return create(BufferOrError.get(), C);
 }
 
+/// Create a sample profile remapper from the given input, to remap the
+/// function names in the given profile data.
+///
+/// \param Filename The file to open.
+///
+/// \param C The LLVM context to use to emit diagnostics.
+///
+/// \param Underlying The underlying profile data reader to remap.
+///
+/// \returns an error code indicating the status of the created reader.
+ErrorOr<std::unique_ptr<SampleProfileReader>>
+SampleProfileReaderItaniumRemapper::create(
+    const Twine &Filename, LLVMContext &C,
+    std::unique_ptr<SampleProfileReader> Underlying) {
+  auto BufferOrError = setupMemoryBuffer(Filename);
+  if (std::error_code EC = BufferOrError.getError())
+    return EC;
+  return llvm::make_unique<SampleProfileReaderItaniumRemapper>(
+      std::move(BufferOrError.get()), C, std::move(Underlying));
+}
+
 /// Create a sample profile reader based on the format of the input data.
 ///
 /// \param B The memory buffer to create the reader from (assumes ownership).
 ///
 /// \param C The LLVM context to use to emit diagnostics.
 ///
 /// \returns an error code indicating the status of the created reader.
 ErrorOr<std::unique_ptr<SampleProfileReader>>

lib/Transforms/IPO/SampleProfile.cpp

 #define DEBUG_TYPE "sample-profile"
 
 // Command line option to specify the file to read samples from. This is
 // mainly used for debugging.
 static cl::opt<std::string> SampleProfileFile(
     "sample-profile-file", cl::init(""), cl::value_desc("filename"),
     cl::desc("Profile file loaded by -sample-profile"), cl::Hidden);
 
+static cl::opt<std::string> SampleProfileRemappingFile(
+    "sample-profile-remapping-file", cl::init(""), cl::value_desc("filename"),
+    cl::desc("Profile remapping file loaded by -sample-profile"), cl::Hidden);
+
 static cl::opt<unsigned> SampleProfileMaxPropagateIterations(
     "sample-profile-max-propagate-iterations", cl::init(100),
     cl::desc("Maximum number of iterations to go through when propagating "
              "sample block/edge weights through the CFG."));
 
 static cl::opt<unsigned> SampleProfileRecordCoverage(
     "sample-profile-check-record-coverage", cl::init(0), cl::value_desc("N"),
     cl::desc("Emit a warning if less than N% of records in the input profile "

 /// Sample profile pass.
 ///
 /// This pass reads profile data from the file specified by
 /// -sample-profile-file and annotates every affected function with the
 /// profile information found in that file.
 class SampleProfileLoader {
 public:
   SampleProfileLoader(
-      StringRef Name, bool IsThinLTOPreLink,
+      StringRef Name, StringRef RemapName, bool IsThinLTOPreLink,
       std::function<AssumptionCache &(Function &)> GetAssumptionCache,
       std::function<TargetTransformInfo &(Function &)> GetTargetTransformInfo)
       : GetAC(std::move(GetAssumptionCache)),
         GetTTI(std::move(GetTargetTransformInfo)), Filename(Name),
-        IsThinLTOPreLink(IsThinLTOPreLink) {}
+        RemappingFilename(RemapName), IsThinLTOPreLink(IsThinLTOPreLink) {}
 
   bool doInitialization(Module &M);
   bool runOnModule(Module &M, ModuleAnalysisManager *AM,
                    ProfileSummaryInfo *_PSI);
 
   void dump() { Reader->dump(); }
 
 protected:
protected:
   std::unique_ptr<SampleProfileReader> Reader;
 
   /// Samples collected for the body of this function.
   FunctionSamples *Samples = nullptr;
 
   /// Name of the profile file to load.
   std::string Filename;
 
+  /// Name of the profile remapping file to load.
+  std::string RemappingFilename;
+
   /// Flag indicating whether the profile input loaded successfully.
   bool ProfileIsValid = false;
 
   /// Flag indicating if the pass is invoked in ThinLTO compile phase.
   ///
   /// In this phase, in annotation, we should not promote indirect calls.
   /// Instead, we will mark GUIDs that needs to be annotated to the function.
   bool IsThinLTOPreLink;

 
 class SampleProfileLoaderLegacyPass : public ModulePass {
 public:
   // Class identification, replacement for typeinfo
   static char ID;
 
   SampleProfileLoaderLegacyPass(StringRef Name = SampleProfileFile,
                                 bool IsThinLTOPreLink = false)
-      : ModulePass(ID), SampleLoader(Name, IsThinLTOPreLink,
-                                     [&](Function &F) -> AssumptionCache & {
-                                       return ACT->getAssumptionCache(F);
-                                     },
-                                     [&](Function &F) -> TargetTransformInfo & {
-                                       return TTIWP->getTTI(F);
-                                     }) {
+      : ModulePass(ID),
+        SampleLoader(Name, SampleProfileRemappingFile, IsThinLTOPreLink,
     initializeSampleProfileLoaderLegacyPassPass(
         *PassRegistry::getPassRegistry());
   }
 
   void dump() { SampleLoader.dump(); }
 
   bool doInitialization(Module &M) override {
     return SampleLoader.doInitialization(M);
bool SampleProfileLoader::doInitialization(Module &M) {
   auto ReaderOrErr = SampleProfileReader::create(Filename, Ctx);
   if (std::error_code EC = ReaderOrErr.getError()) {
     std::string Msg = "Could not open profile: " + EC.message();
     Ctx.diagnose(DiagnosticInfoSampleProfile(Filename, Msg));
     return false;
   }
   Reader = std::move(ReaderOrErr.get());
   ProfileIsValid = (Reader->read() == sampleprof_error::success);
+
+  if (!RemappingFilename.empty()) {
+    ReaderOrErr = SampleProfileReaderItaniumRemapper::create(
+        RemappingFilename, Ctx, std::move(Reader));
+    if (std::error_code EC = ReaderOrErr.getError()) {
+      std::string Msg = "Could not open profile remapping file: " + EC.message();
+      Ctx.diagnose(DiagnosticInfoSampleProfile(Filename, Msg));
+      return false;
+    }
+    Reader = std::move(ReaderOrErr.get());
+    ProfileIsValid = (Reader->read() == sampleprof_error::success);
+  }
   return true;
 }
 
 ModulePass *llvm::createSampleProfileLoaderPass() {
-  return new SampleProfileLoaderLegacyPass(SampleProfileFile);
+  return new SampleProfileLoaderLegacyPass();
 }
 
 ModulePass *llvm::createSampleProfileLoaderPass(StringRef Name) {
   return new SampleProfileLoaderLegacyPass(Name);
 }
 
 bool SampleProfileLoader::runOnModule(Module &M, ModuleAnalysisManager *AM,
                                       ProfileSummaryInfo *_PSI) {
auto GetAssumptionCache = [&](Function &F) -> AssumptionCache & {
     return FAM.getResult<AssumptionAnalysis>(F);
   };
   auto GetTTI = [&](Function &F) -> TargetTransformInfo & {
     return FAM.getResult<TargetIRAnalysis>(F);
   };
 
   SampleProfileLoader SampleLoader(
       ProfileFileName.empty() ? SampleProfileFile : ProfileFileName,
+      ProfileRemappingFileName.empty() ? SampleProfileRemappingFile
+                                       : ProfileRemappingFileName,
       IsThinLTOPreLink, GetAssumptionCache, GetTTI);
 
   SampleLoader.doInitialization(M);
 
   ProfileSummaryInfo *PSI = &AM.getResult<ProfileSummaryAnalysis>(M);
   if (!SampleLoader.runOnModule(M, &AM, PSI))
     return PreservedAnalyses::all();
 
   return PreservedAnalyses::none();
 }

lib/Transforms/Instrumentation/PGOInstrumentation.cpp

 
 // Command line option to specify the file to read profile from. This is
 // mainly used for testing.
 static cl::opt<std::string>
     PGOTestProfileFile("pgo-test-profile-file", cl::init(""), cl::Hidden,
                        cl::value_desc("filename"),
                        cl::desc("Specify the path of profile data file. This is"
                                 "mainly for test purpose."));
+static cl::opt<std::string> PGOTestProfileRemappingFile(
+    "pgo-test-profile-remapping-file", cl::init(""), cl::Hidden,
+    cl::value_desc("filename"),
+    cl::desc("Specify the path of profile remapping file. This is mainly for "
+             "test purpose."));
 
 // Command line option to disable value profiling. The default is false:
 // i.e. value profiling is enabled by default. This is for debug purpose.
 static cl::opt<bool> DisableValueProfiling("disable-vp", cl::init(false),
                                            cl::Hidden,
                                            cl::desc("Disable Value Profiling"));
 
 // Command line option to set the maximum number of VP annotations to write to
PreservedAnalyses PGOInstrumentationGen::run(Module &M,
 
   if (!InstrumentAllFunctions(M, LookupBPI, LookupBFI))
     return PreservedAnalyses::all();
 
   return PreservedAnalyses::none();
 }
 
 static bool annotateAllFunctions(
-    Module &M, StringRef ProfileFileName,
+    Module &M, StringRef ProfileFileName, StringRef ProfileRemappingFileName,
     function_ref<BranchProbabilityInfo *(Function &)> LookupBPI,
     function_ref<BlockFrequencyInfo *(Function &)> LookupBFI) {
   LLVM_DEBUG(dbgs() << "Read in profile counters: ");
   auto &Ctx = M.getContext();
   // Read the counter array from file.
-  auto ReaderOrErr = IndexedInstrProfReader::create(ProfileFileName);
+  auto ReaderOrErr =
+      IndexedInstrProfReader::create(ProfileFileName, ProfileRemappingFileName);
   if (Error E = ReaderOrErr.takeError()) {
     handleAllErrors(std::move(E), [&](const ErrorInfoBase &EI) {
       Ctx.diagnose(
           DiagnosticInfoPGOProfile(ProfileFileName.data(), EI.message()));
     });
     return false;
   }
 
static bool annotateAllFunctions(
   for (auto &F : ColdFunctions) {
     F->addFnAttr(Attribute::Cold);
     LLVM_DEBUG(dbgs() << "Set cold attribute to function: " << F->getName()
                       << "\n");
   }
   return true;
 }
 
-PGOInstrumentationUse::PGOInstrumentationUse(std::string Filename)
-    : ProfileFileName(std::move(Filename)) {
+PGOInstrumentationUse::PGOInstrumentationUse(std::string Filename,
+                                             std::string RemappingFilename)
+    : ProfileFileName(std::move(Filename)),
+      ProfileRemappingFileName(std::move(RemappingFilename)) {
   if (!PGOTestProfileFile.empty())
     ProfileFileName = PGOTestProfileFile;
+  if (!PGOTestProfileRemappingFile.empty())
+    ProfileRemappingFileName = PGOTestProfileRemappingFile;
 }
 
 PreservedAnalyses PGOInstrumentationUse::run(Module &M,
                                              ModuleAnalysisManager &AM) {
 
   auto &FAM = AM.getResult<FunctionAnalysisManagerModuleProxy>(M).getManager();
   auto LookupBPI = [&FAM](Function &F) {
     return &FAM.getResult<BranchProbabilityAnalysis>(F);
   };
 
   auto LookupBFI = [&FAM](Function &F) {
     return &FAM.getResult<BlockFrequencyAnalysis>(F);
   };
 
-  if (!annotateAllFunctions(M, ProfileFileName, LookupBPI, LookupBFI))
+  if (!annotateAllFunctions(M, ProfileFileName, ProfileRemappingFileName,
+                            LookupBPI, LookupBFI))
     return PreservedAnalyses::all();
 
   return PreservedAnalyses::none();
 }
 
 bool PGOInstrumentationUseLegacyPass::runOnModule(Module &M) {
   if (skipModule(M))
     return false;
 
   auto LookupBPI = [this](Function &F) {
     return &this->getAnalysis<BranchProbabilityInfoWrapperPass>(F).getBPI();
   };
   auto LookupBFI = [this](Function &F) {
     return &this->getAnalysis<BlockFrequencyInfoWrapperPass>(F).getBFI();
   };
 
-  return annotateAllFunctions(M, ProfileFileName, LookupBPI, LookupBFI);
+  return annotateAllFunctions(M, ProfileFileName, "", LookupBPI, LookupBFI);
 }
 
 static std::string getSimpleNodeName(const BasicBlock *Node) {
   if (!Node->getName().empty())
     return Node->getName();
 
   std::string SimpleNodeName;
   raw_string_ostream OS(SimpleNodeName);

test/Transforms/PGOProfile/Inputs/remap.map

+# foo:: and foo::detail:: are equivalent
+name 3foo N3foo6detailE
+
+# foo::qux and foo::quux are equivalent
+type N3foo3quxE N3foo4quuxE
+
+# N::X and M::X are equivalent
+name N1N1XE N1M1XE

test/Transforms/PGOProfile/Inputs/remap.proftext

+# :ir is the flag to indicate this is IR level profile.
+:ir
+_ZN3foo3barERKN1N1XINS_4quuxEEE
[phone]
+2
+3
+2
+

test/Transforms/PGOProfile/remap.ll

+; RUN: llvm-profdata merge %S/Inputs/remap.proftext -o %t.profdata
+; RUN: opt < %s -passes=pgo-instr-use -pgo-test-profile-file=%t.profdata -pgo-test-profile-remapping-file=%S/Inputs/remap.map -S | FileCheck %s --check-prefix=USE
+
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-unknown-linux-gnu"
+
+define i32 @_ZN3foo3barERKN1M1XINS_6detail3quxEEE(i32 %i) {
+; USE-LABEL: @_ZN3foo3barERKN1M1XINS_6detail3quxEEE
+; USE-SAME: !prof ![[FUNC_ENTRY_COUNT:[0-9]+]]
+entry:
+  %cmp = icmp sgt i32 %i, 0
+  br i1 %cmp, label %if.then, label %if.end
+; USE: br i1 %cmp, label %if.then, label %if.end
+; USE-SAME: !prof ![[BW_ENTRY:[0-9]+]]
+
+if.then:
+  %add = add nsw i32 %i, 2
+  br label %if.end
+
+if.end:
+  %retv = phi i32 [ %add, %if.then ], [ %i, %entry ]
+  ret i32 %retv
+}
+
+; USE-DAG: {{![0-9]+}} = !{i32 1, !"ProfileSummary", {{![0-9]+}}}
+; USE-DAG: {{![0-9]+}} = !{!"DetailedSummary", {{![0-9]+}}}
+; USE-DAG: ![[FUNC_ENTRY_COUNT]] = !{!"function_entry_count", i64 3}
+; USE-DAG: ![[BW_ENTRY]] = !{!"branch_weights", i32 2, i32 1}

test/Transforms/SampleProfile/Inputs/remap.map

+# foo:: and foo::detail:: are equivalent
+name 3foo N3foo6detailE
+
+# foo::qux and foo::quux are equivalent
+type N3foo3quxE N3foo4quuxE
+
+# N::X and M::X are equivalent
+name N1N1XE N1M1XE

test/Transforms/SampleProfile/Inputs/remap.prof

+_ZN3foo3barERKN1N1XINS_4quuxEEE:15680:2500
+ 1: 2500
+ 4: 1000
+ 5: 1000
+ 6: 800
+ 7: 500
+ 9: 10226
+ 10: 2243
+ 16: 0
+ 18: 0

test/Transforms/SampleProfile/remap.ll

+; RUN: opt %s -passes=sample-profile -sample-profile-file=%S/Inputs/remap.prof -sample-profile-remapping-file=%S/Inputs/remap.map | opt -analyze -branch-prob | FileCheck %s
+
+; Reduced from branch.ll
+
+declare i1 @foo()
+
+define void @_ZN3foo3barERKN1M1XINS_6detail3quxEEE() !dbg !2 {
+; CHECK: Printing analysis 'Branch Probability Analysis' for function '_ZN3foo3barERKN1M1XINS_6detail3quxEEE':
+
+entry:
+  %cmp = call i1 @foo(), !dbg !6
+  br i1 %cmp, label %if.then, label %if.end
+; CHECK:  edge entry -> if.then probability is 0x4ccf6b16 / 0x80000000 = 60.01%
+; CHECK:  edge entry -> if.end probability is 0x333094ea / 0x80000000 = 39.99%
+
+if.then:
+  br label %return
+
+if.end:
+  %cmp1 = call i1 @foo(), !dbg !7
+  br i1 %cmp1, label %if.then.2, label %if.else
+; CHECK: edge if.end -> if.then.2 probability is 0x6652c748 / 0x80000000 = 79.94%
+; CHECK: edge if.end -> if.else probability is 0x19ad38b8 / 0x80000000 = 20.06%
+
+if.then.2:
+  call i1 @foo(), !dbg !8
+  br label %for.cond
+
+for.cond:
+  %cmp5 = call i1 @foo()
+  br i1 %cmp5, label %for.body, label %for.end, !prof !9
+; CHECK: edge for.cond -> for.body probability is 0x73333333 / 0x80000000 = 90.00%
+; CHECK: edge for.cond -> for.end probability is 0x0ccccccd / 0x80000000 = 10.00%
+
+for.body:
+  br label %for.cond
+
+for.end:
+  br label %return
+
+if.else:
+  br label %return
+
+return:
+  ret void
+}
+
+!llvm.dbg.cu = !{!0}
+!llvm.module.flags = !{!4, !5}
+
+!0 = distinct !DICompileUnit(language: DW_LANG_C_plus_plus, file: !1, producer: "foo++", isOptimized: false, runtimeVersion: 0, emissionKind: NoDebug, enums: !{}, retainedTypes: !{})
+!1 = !DIFile(filename: "test.cc", directory: "/foo/bar")
+!2 = distinct !DISubprogram(name: "_ZN3foo3barERKN1M1XINS_6detail3quxEEE", scope: !1, file: !1, line: 4, type: !3, isLocal: false, isDefinition: true, scopeLine: 4, flags: DIFlagPrototyped, isOptimized: false, unit: !0, retainedNodes: !{})
+!3 = !DISubroutineType(types: !{})
+!4 = !{i32 2, !"Dwarf Version", i32 4}
+!5 = !{i32 2, !"Debug Info Version", i32 3}
+!6 = !DILocation(line: 5, column: 8, scope: !2)
+!7 = !DILocation(line: 8, column: 6, scope: !2)
+!8 = !DILocation(line: 10, column: 11, scope: !2)
+!9 = !{!"branch_weights", i32 90, i32 10}

tools/opt/NewPMDriver.cpp

cl::values(clEnumValN(NoPGO, "nopgo", "Do not use PGO."),
                clEnumValN(InstrGen, "new-pm-pgo-instr-gen-pipeline",
                           "Instrument the IR to generate profile."),
                clEnumValN(InstrUse, "new-pm-pgo-instr-use-pipeline",
                           "Use instrumented profile to guide PGO."),
                clEnumValN(SampleUse, "new-pm-pgo-sample-use-pipeline",
                           "Use sampled profile to guide PGO.")));
 static cl::opt<std::string> ProfileFile(
     "profile-file", cl::desc("Path to the profile."), cl::Hidden);
+static cl::opt<std::string>
+    ProfileRemappingFile("profile-remapping-file",
+                         cl::desc("Path to the profile remapping file."),
+                         cl::Hidden);
 static cl::opt<bool> DebugInfoForProfiling(
     "new-pm-debug-info-for-profiling", cl::init(false), cl::Hidden,
     cl::desc("Emit special debug info to enable PGO profile generation."));
 /// @}}
 
 template <typename PassManagerT>
 bool tryParsePipelineText(PassBuilder &PB, StringRef PipelineText) {
   if (PipelineText.empty())
bool llvm::runPassPipeline(StringRef Arg0, Module &M, TargetMachine *TM,
                            bool ShouldPreserveBitcodeUseListOrder,
                            bool EmitSummaryIndex, bool EmitModuleHash,
                            bool EnableDebugify) {
   bool VerifyEachPass = VK == VK_VerifyEachPass;
 
   Optional<PGOOptions> P;
   switch (PGOKindFlag) {
     case InstrGen:
-      P = PGOOptions(ProfileFile, "", "", true);
+      P = PGOOptions(ProfileFile, "", "", "", true);
       break;
     case InstrUse:
-      P = PGOOptions("", ProfileFile, "", false);
+      P = PGOOptions("", ProfileFile, "", ProfileRemappingFile, false);
       break;
     case SampleUse:
-      P = PGOOptions("", "", ProfileFile, false);
+      P = PGOOptions("", "", ProfileFile, ProfileRemappingFile, false);
       break;
     case NoPGO:
       if (DebugInfoForProfiling)
-        P = PGOOptions("", "", "", false, true);
+        P = PGOOptions("", "", "", "", false, true);
       else
         P = None;
   }
   PassBuilder PB(TM, P);
   registerEPCallbacks(PB, VerifyEachPass, DebugPM);
 
   // Load requested pass plugins and let them register pass builder callbacks
   for (auto &PluginFN : PassPlugins) {

unittests/Demangle/CMakeLists.txt

 set(LLVM_LINK_COMPONENTS
   Demangle
 )
 
 add_llvm_unittest(DemangleTests
+  CanonicalizeTest.cpp
   PartialDemangleTest.cpp
   FindTypesInMangledNameTest.cpp
 )

unittests/Demangle/CanonicalizeTest.cpp

+//===----------------------- CanonicalizeTest.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.
+//
+//===----------------------------------------------------------------------===//
+
+#include <cstdlib>
+#include <map>
+#include "llvm/Demangle/Canonicalize.h"
+#include "gtest/gtest.h"
+
+using EquivalenceError = llvm::ItaniumManglingCanonicalizer::EquivalenceError;
+using FragmentKind = llvm::ItaniumManglingCanonicalizer::FragmentKind;
+
+struct Equivalence {
+  FragmentKind Kind;
+  llvm::StringRef First;
+  llvm::StringRef Second;
+};
+
+// A set of manglings that should all be considered equivalent.
+using EquivalenceClass = std::initializer_list<llvm::StringRef>;
+
+struct Testcase {
+  // A set of equivalences to register.
+  std::initializer_list<Equivalence> Equivalences;
+  // A set of distinct equivalence classes created by registering the
+  // equivalences.
+  std::initializer_list<EquivalenceClass> Classes;
+};
+
+static std::initializer_list<Testcase> Testcases = {
+  // Three different manglings for std::string (old libstdc++, new libstdc++,
+  // libc++).
+  {
+    {
+      {FragmentKind::Type, "Ss",
+       "NSt3__112basic_stringIcNS_11char_traitsIcEENS_9allocatorIcEEEE"},
+      {FragmentKind::Type, "Ss",
+       "NSt7__cxx1112basic_stringIcSt11char_traitsIcESaIcEEE"},
+    },
+    {
+      {"_Z1fv"},
+      {"_Z1fSs",
+       "_Z1fNSt3__112basic_stringIcNS_11char_traitsIcEENS_9allocatorIcEEEE",
+       "_Z1fNSt7__cxx1112basic_stringIcSt11char_traitsIcESaIcEEE"},
+      {"_ZNKSs4sizeEv",
+       "_ZNKSt7__cxx1112basic_stringIcSt11char_traitsIcESaIcEE4sizeEv",
+       "_ZNKSt3__112basic_stringIcNS_11char_traitsIcEENS_9allocatorIcEEE4sizeEv"},
+    }
+  },
+
+  // Check that substitutions are properly handled.
+  {
+    {
+      // ::X <-> ::N::X<int>
+      {FragmentKind::Type, "1X", "N1N1XIiEE"},
+      // ::T<T<int, int>, T<int, int>> <-> T<int>
+      {FragmentKind::Type, "1TIS_IiiES0_E", "1TIiE"},
+      // A::B::foo <-> AB::foo
+      {FragmentKind::Name, "N1A1B3fooE", "N2AB3fooE"},
+    },
+    {
+      {"_Z1f1XPS_RS_", "_Z1fN1N1XIiEEPS1_RS1_"},
+      {"_ZN1A1B3fooE1TIS1_IiiES2_EPS3_RS3_", "_ZN2AB3fooE1TIiEPS1_RS1_"},
+    }
+  },
+
+  // Check that nested equivalences are properly handled.
+  {
+    {
+      // std::__1::char_traits == std::__cxx11::char_traits
+      // (Note that this is unused and should make no difference,
+      // but it should not cause us to fail to match up the cases
+      // below.)
+      {FragmentKind::Name,
+       "NSt3__111char_traitsE",
+       "NSt7__cxx1111char_traitsE"},
+      // std::__1::allocator == std::allocator
+      {FragmentKind::Name,
+       "NSt3__19allocatorE",
+       "Sa"}, // "Sa" is not strictly a <name> but we accept it as one.
+      // std::__1::vector == std::vector
+      {FragmentKind::Name,
+       "St6vector",
+       "NSt3__16vectorE"},
+      // std::__1::basic_string<
+      //   char
+      //   std::__1::char_traits<char>,
+      //   std::__1::allocator<char>> ==
+      // std::__cxx11::basic_string<
+      //   char,
+      //   std::char_traits<char>,
+      //   std::allocator<char>>
+      {FragmentKind::Type,
+       "NSt3__112basic_stringIcNS_11char_traitsIcEENS_9allocatorIcEEEE",
+       "NSt7__cxx1112basic_stringIcSt11char_traitsIcESaIcEEE"},
+      // X<A> <-> X<B>
+      {FragmentKind::Type, "1XI1AE", "1XI1BE"},
+      // X <-> Y
+      {FragmentKind::Name, "1X", "1Y"},
+    },
+    {
+      // f(std::string)
+      {"_Z1fNSt3__112basic_stringIcNS_11char_traitsIcEENS_9allocatorIcEEEE",
+       "_Z1fNSt7__cxx1112basic_stringIcSt11char_traitsIcESaIcEEE"},
+      // f(std::vector<int>)
+      {"_Z1fSt6vectorIiSaIiEE", "_Z1fNSt3__16vectorIiNS_9allocatorIiEEEE"},
+      // f(X<A>), f(X<B>), f(Y<A>), f(Y<B>)
+      {"_Z1f1XI1AE", "_Z1f1XI1BE", "_Z1f1YI1AE", "_Z1f1YI1BE"},
+      // f(X<C>), f(Y<C>)
+      {"_Z1f1XI1CE", "_Z1f1YI1CE"},
+    }
+  },
+
+  // Check namespace equivalences.
+  {
+    {
+      // std::__1 == std::__cxx11
+      {FragmentKind::Name, "St3__1", "St7__cxx11"},
+      // std::__1::allocator == std::allocator
+      {FragmentKind::Name, "NSt3__19allocatorE", "Sa"},
+      // std::vector == std::__1::vector
+      {FragmentKind::Name, "St6vector", "NSt3__16vectorE"},
+      // std::__cxx11::char_traits == std::char_traits
+      // (This indirectly means that std::__1::char_traits == std::char_traits,
+      // due to the std::__cxx11 == std::__1 equivalence, which is what we rely
+      // on below.)
+      {FragmentKind::Name, "NSt7__cxx1111char_traitsE", "St11char_traits"},
+    },
+    {
+      // f(std::foo)
+      {"_Z1fNSt7__cxx113fooE",
+       "_Z1fNSt3__13fooE"},
+      // f(std::string)
+      {"_Z1fNSt7__cxx1111char_traitsIcEE",
+       "_Z1fNSt3__111char_traitsIcEE",
+       "_Z1fSt11char_traitsIcE"},
+      // f(std::string)
+      {"_Z1fNSt3__112basic_stringIcNS_11char_traitsIcEENS_9allocatorIcEEEE",
+       "_Z1fNSt7__cxx1112basic_stringIcSt11char_traitsIcESaIcEEE"},
+      // f(std::vector<int>)
+      {"_Z1fSt6vectorIiSaIiEE", "_Z1fNSt3__16vectorIiNS_9allocatorIiEEEE"},
+    }
+  },
+
+  // Check namespace equivalences for namespace 'std'. We support using 'St'
+  // for this, despite it not technically being a <name>.
+  {
+    {
+      // std::__1 == std
+      {FragmentKind::Name, "St3__1", "St"},
+      // std::__1 == std::__cxx11
+      {FragmentKind::Name, "St3__1", "St7__cxx11"},
+      // FIXME: Should a 'std' equivalence also cover the predefined
+      // substitutions?
+      // std::__1::allocator == std::allocator
+      {FragmentKind::Name, "NSt3__19allocatorE", "Sa"},
+    },
+    {
+      {"_Z1fSt3foo", "_Z1fNSt3__13fooE", "_Z1fNSt7__cxx113fooE"},
+      {"_Z1fNSt3bar3bazE", "_Z1fNSt3__13bar3bazE"},
+      // f(std::string)
+      {"_Z1fNSt3__112basic_stringIcNS_11char_traitsIcEENS_9allocatorIcEEEE",
+       "_Z1fNSt7__cxx1112basic_stringIcSt11char_traitsIcESaIcEEE"},
+      // f(std::vector<int>)
+      {"_Z1fSt6vectorIiSaIiEE", "_Z1fNSt3__16vectorIiNS_9allocatorIiEEEE"},
+    }
+  },
+
+  // Check mutually-recursive equivalences.
+  {
+    {
+      {FragmentKind::Type, "1A", "1B"},
+      {FragmentKind::Type, "1A", "1C"},
+      {FragmentKind::Type, "1D", "1B"},
+      {FragmentKind::Type, "1C", "1E"},
+    },
+    {
+      {"_Z1f1A", "_Z1f1B", "_Z1f1C", "_Z1f1D", "_Z1f1E"},
+      {"_Z1f1F"},
+    }
+  },
+
+  // Check <encoding>s.
+  {
+    {
+      {FragmentKind::Encoding, "1fv", "1gv"},
+    },
+    {
+      // f(void) -> g(void)
+      {"_Z1fv", "_Z1gv"},
+      // static local 'n' in f(void) -> static local 'n' in g(void)
+      {"_ZZ1fvE1n", "_ZZ1gvE1n"},
+    }
+  },
+
+  // Corner case: the substitution can appear within its own expansion.
+  {
+    {
+      // X <-> Y<X>
+      {FragmentKind::Type, "1X", "1YI1XE"},
+      // A<B> <-> B
+      {FragmentKind::Type, "1AI1BE", "1B"},
+    },
+    {
+      // f(X) == f(Y<X>) == f(Y<Y<X>>) == f(Y<Y<Y<X>>>)
+      {"_Z1f1X", "_Z1f1YI1XE", "_Z1f1YIS_I1XEE", "_Z1f1YIS_IS_I1XEEE"},
+      // f(B) == f(A<B>) == f(A<A<B>>) == f(A<A<A<B>>>)
+      {"_Z1f1B", "_Z1f1AI1BE", "_Z1f1AIS_I1BEE", "_Z1f1AIS_IS_I1BEEE"},
+    }
+  },
+};
+
+template<bool CanonicalizeFirst>
+static void testTestcases() {
+  for (const auto &Testcase : Testcases) {
+    llvm::ItaniumManglingCanonicalizer Canonicalizer;
+    for (const auto &Equiv : Testcase.Equivalences) {
+      auto Result =
+          Canonicalizer.addEquivalence(Equiv.Kind, Equiv.First, Equiv.Second);
+      EXPECT_EQ(Result, EquivalenceError::Success)
+          << "couldn't add equivalence between " << Equiv.First << " and "
+          << Equiv.Second;
+    }
+
+    using CanonKey = llvm::ItaniumManglingCanonicalizer::Key;
+
+    std::map<const EquivalenceClass*, CanonKey> Keys;
+    if (CanonicalizeFirst)
+      for (const auto &Class : Testcase.Classes)
+        Keys.insert({&Class, Canonicalizer.canonicalize(*Class.begin())});
+
+    std::map<CanonKey, llvm::StringRef> Found;
+    for (const auto &Class : Testcase.Classes) {
+      CanonKey ClassKey = Keys[&Class];
+      for (llvm::StringRef Str : Class) {
+        // Force a copy to be made when calling lookup to test that it doesn't
+        // retain any part of the provided string.
+        CanonKey ThisKey = CanonicalizeFirst
+                               ? Canonicalizer.lookup(std::string(Str))
+                               : Canonicalizer.canonicalize(Str);
+        EXPECT_NE(ThisKey, CanonKey()) << "couldn't canonicalize " << Str;
+        if (ClassKey) {
+          EXPECT_EQ(ThisKey, ClassKey)
+              << Str << " not in the same class as " << *Class.begin();
+        } else {
+          ClassKey = ThisKey;
+        }
+      }
+      EXPECT_TRUE(Found.insert({ClassKey, *Class.begin()}).second)
+          << *Class.begin() << " is in the same class as " << Found[ClassKey];
+    }
+  }
+}
+
+TEST(CanonicalizeTest, TestCanonicalize) {
+  testTestcases<false>();
+}
+
+TEST(CanonicalizeTest, TestLookup) {
+  testTestcases<true>();
+}
+
+TEST(CanonicalizeTest, TestInvalidManglings) {
+  llvm::ItaniumManglingCanonicalizer Canonicalizer;
+  EXPECT_EQ(Canonicalizer.addEquivalence(FragmentKind::Type, "", "1X"),
+            EquivalenceError::InvalidFirstMangling);
+  EXPECT_EQ(Canonicalizer.addEquivalence(FragmentKind::Type, "1X", "1ab"),
+            EquivalenceError::InvalidSecondMangling);
+  EXPECT_EQ(Canonicalizer.canonicalize("_Z3fooE"),
+            llvm::ItaniumManglingCanonicalizer::Key());
+  EXPECT_EQ(Canonicalizer.canonicalize("foo"),
+            llvm::ItaniumManglingCanonicalizer::Key());
+}
+
+TEST(CanonicalizeTest, TestBadEquivalenceOrder) {
+  llvm::ItaniumManglingCanonicalizer Canonicalizer;
+  EXPECT_EQ(Canonicalizer.addEquivalence(FragmentKind::Type, "1A", "1B"),
+            EquivalenceError::Success);
+  EXPECT_EQ(Canonicalizer.addEquivalence(FragmentKind::Type, "1B", "1C"),
+            EquivalenceError::Success);
+  EXPECT_EQ(Canonicalizer.addEquivalence(FragmentKind::Type, "1C", "1A"),
+            EquivalenceError::ManglingAlreadyUsed);
+}

unittests/ProfileData/InstrProfTest.cpp

 namespace {
 
 struct InstrProfTest : ::testing::Test {
   InstrProfWriter Writer;
   std::unique_ptr<IndexedInstrProfReader> Reader;
 
   void SetUp() { Writer.setOutputSparse(false); }
 
-  void readProfile(std::unique_ptr<MemoryBuffer> Profile) {
-    auto ReaderOrErr = IndexedInstrProfReader::create(std::move(Profile));
+  void readProfile(std::unique_ptr<MemoryBuffer> Profile,
+                   std::unique_ptr<MemoryBuffer> Remapping = nullptr) {
+    auto ReaderOrErr = IndexedInstrProfReader::create(std::move(Profile),
+                                                      std::move(Remapping));
     EXPECT_THAT_ERROR(ReaderOrErr.takeError(), Succeeded());
     Reader = std::move(ReaderOrErr.get());
   }
 };
 
 struct SparseInstrProfTest : public InstrProfTest {
   void SetUp() { Writer.setOutputSparse(true); }
 };
for (int Padding = 0; Padding < 2; Padding++) {
           StringRef R = Symtab.getFuncName(IndexedInstrProf::ComputeHash(N[J]));
           ASSERT_EQ(StringRef(N[J]), R);
         }
       }
     }
   }
 }
 
+TEST_P(MaybeSparseInstrProfTest, remapping_test) {
+  Writer.addRecord({"_Z3fooi", 0x1234, {1, 2, 3, 4}}, Err);
+  Writer.addRecord({"_Z3barf", 0x567, {5, 6, 7}}, Err);
+  auto Profile = Writer.writeBuffer();
+  readProfile(std::move(Profile), llvm::MemoryBuffer::getMemBuffer(R"(
+    type i l
+    name 3bar 4quux
+  )"));
+
+  std::vector<uint64_t> Counts;
+  for (StringRef FooName : {"_Z3fooi", "_Z3fool"}) {
+    EXPECT_THAT_ERROR(Reader->getFunctionCounts(FooName, 0x1234, Counts),
+                      Succeeded());
+    ASSERT_EQ(4u, Counts.size());
+    EXPECT_EQ(1u, Counts[0]);
+    EXPECT_EQ(2u, Counts[1]);
+    EXPECT_EQ(3u, Counts[2]);
+    EXPECT_EQ(4u, Counts[3]);
+  }
+
+  for (StringRef BarName : {"_Z3barf", "_Z4quuxf"}) {
+    EXPECT_THAT_ERROR(Reader->getFunctionCounts(BarName, 0x567, Counts),
+                      Succeeded());
+    ASSERT_EQ(3u, Counts.size());
+    EXPECT_EQ(5u, Counts[0]);
+    EXPECT_EQ(6u, Counts[1]);
+    EXPECT_EQ(7u, Counts[2]);
+  }
+
+  for (StringRef BadName : {"_Z3foof", "_Z4quuxi", "_Z3barl", "", "_ZZZ"}) {
+    EXPECT_THAT_ERROR(Reader->getFunctionCounts(BadName, 0x1234, Counts),
+                      Failed());
+    EXPECT_THAT_ERROR(Reader->getFunctionCounts(BadName, 0x567, Counts),
+                      Failed());
+  }
+}
+
 TEST_F(SparseInstrProfTest, preserve_no_records) {
   Writer.addRecord({"foo", 0x1234, {0}}, Err);
   Writer.addRecord({"bar", 0x4321, {0, 0}}, Err);
   Writer.addRecord({"baz", 0x4321, {0, 0, 0}}, Err);
 
   auto Profile = Writer.writeBuffer();
   readProfile(std::move(Profile));
 
   auto I = Reader->begin(), E = Reader->end();
   ASSERT_TRUE(I == E);
 }
 
 INSTANTIATE_TEST_CASE_P(MaybeSparse, MaybeSparseInstrProfTest,
                         ::testing::Bool(),);
 
 } // end anonymous namespace

unittests/ProfileData/SampleProfTest.cpp

struct SampleProfTest : ::testing::Test {
   }
 
   void readProfile(std::unique_ptr<MemoryBuffer> &Profile) {
     auto ReaderOrErr = SampleProfileReader::create(Profile, Context);
     ASSERT_TRUE(NoError(ReaderOrErr.getError()));
     Reader = std::move(ReaderOrErr.get());
   }
 
-  void testRoundTrip(SampleProfileFormat Format) {
+  void testRoundTrip(SampleProfileFormat Format, bool Remap) {
     createWriter(Format);
 
     StringRef FooName("_Z3fooi");
     FunctionSamples FooSamples;
     FooSamples.setName(FooName);
     FooSamples.addTotalSamples(7711);
     FooSamples.addHeadSamples(610);
     FooSamples.addBodySamples(1, 0, 610);
void testRoundTrip(SampleProfileFormat Format, bool Remap) {
     Writer->getOutputStream().flush();
 
     auto Profile = MemoryBuffer::getMemBufferCopy(Data);
     readProfile(Profile);
 
     EC = Reader->read();
     ASSERT_TRUE(NoError(EC));
 
-    StringMap<FunctionSamples> &ReadProfiles = Reader->getProfiles();
-    ASSERT_EQ(2u, ReadProfiles.size());
+    if (Remap) {
+      auto MemBuffer = llvm::MemoryBuffer::getMemBuffer(R"(
+        # Types 'int' and 'long' are equivalent
+        type i l
+        # Function names 'foo' and 'faux' are equivalent
+        name 3foo 4faux
+      )");
+      Reader.reset(new SampleProfileReaderItaniumRemapper(
+          std::move(MemBuffer), Context, std::move(Reader)));
+      FooName = "_Z4fauxi";
+      BarName = "_Z3barl";
 
-    std::string FooGUID;
-    StringRef FooRep = getRepInFormat(FooName, Format, FooGUID);
-    FunctionSamples &ReadFooSamples = ReadProfiles[FooRep];
-    ASSERT_EQ(7711u, ReadFooSamples.getTotalSamples());
-    ASSERT_EQ(610u, ReadFooSamples.getHeadSamples());
-
-    std::string BarGUID;
-    StringRef BarRep = getRepInFormat(BarName, Format, BarGUID);
-    FunctionSamples &ReadBarSamples = ReadProfiles[BarRep];
-    ASSERT_EQ(20301u, ReadBarSamples.getTotalSamples());
-    ASSERT_EQ(1437u, ReadBarSamples.getHeadSamples());
+      EC = Reader->read();
+      ASSERT_TRUE(NoError(EC));
+    }
+
+    ASSERT_EQ(2u, Reader->getProfiles().size());
+
+    FunctionSamples *ReadFooSamples = Reader->getSamplesFor(FooName);
+    ASSERT_TRUE(ReadFooSamples != nullptr);
+    ASSERT_EQ(7711u, ReadFooSamples->getTotalSamples());
+    ASSERT_EQ(610u, ReadFooSamples->getHeadSamples());
+
+    FunctionSamples *ReadBarSamples = Reader->getSamplesFor(BarName);
+    ASSERT_TRUE(ReadBarSamples != nullptr);
+    ASSERT_EQ(20301u, ReadBarSamples->getTotalSamples());
+    ASSERT_EQ(1437u, ReadBarSamples->getHeadSamples());
     ErrorOr<SampleRecord::CallTargetMap> CTMap =
-        ReadBarSamples.findCallTargetMapAt(1, 0);
+        ReadBarSamples->findCallTargetMapAt(1, 0);
     ASSERT_FALSE(CTMap.getError());
 
     std::string MconstructGUID;
     StringRef MconstructRep =
         getRepInFormat(MconstructName, Format, MconstructGUID);
     std::string StringviewGUID;
     StringRef StringviewRep =
         getRepInFormat(StringviewName, Format, StringviewGUID);
void testRoundTrip(SampleProfileFormat Format, bool Remap) {
     PS = ProfileSummary::getFromMD(MD);
     ASSERT_TRUE(PS);
     VerifySummary(*PS);
     delete PS;
   }
 };
 
 TEST_F(SampleProfTest, roundtrip_text_profile) {
-  testRoundTrip(SampleProfileFormat::SPF_Text);
+  testRoundTrip(SampleProfileFormat::SPF_Text, false);
 }
 
 TEST_F(SampleProfTest, roundtrip_raw_binary_profile) {
-  testRoundTrip(SampleProfileFormat::SPF_Binary);
+  testRoundTrip(SampleProfileFormat::SPF_Binary, false);
 }
 
 TEST_F(SampleProfTest, roundtrip_compact_binary_profile) {
-  testRoundTrip(SampleProfileFormat::SPF_Compact_Binary);
+  testRoundTrip(SampleProfileFormat::SPF_Compact_Binary, false);
+}
+
+TEST_F(SampleProfTest, remap_text_profile) {
+  testRoundTrip(SampleProfileFormat::SPF_Text, true);
 }
 
 TEST_F(SampleProfTest, sample_overflow_saturation) {
   const uint64_t Max = std::numeric_limits<uint64_t>::max();
   sampleprof_error Result;
 
   StringRef FooName("_Z3fooi");
   FunctionSamples FooSamples;