1//===----------------- ItaniumManglingCanonicalizer.cpp -------------------===// 2// 3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4// See https://llvm.org/LICENSE.txt for license information. 5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6// 7//===----------------------------------------------------------------------===// 8 9#include "llvm/Support/ItaniumManglingCanonicalizer.h" 10#include "llvm/ADT/DenseMap.h" 11#include "llvm/ADT/FoldingSet.h" 12#include "llvm/ADT/StringRef.h" 13#include "llvm/Demangle/ItaniumDemangle.h" 14#include "llvm/Support/Allocator.h" 15 16using namespace llvm; 17using llvm::itanium_demangle::ForwardTemplateReference; 18using llvm::itanium_demangle::Node; 19using llvm::itanium_demangle::NodeKind; 20using llvm::itanium_demangle::StringView; 21 22namespace { 23struct FoldingSetNodeIDBuilder { 24 llvm::FoldingSetNodeID &ID; 25 void operator()(const Node *P) { ID.AddPointer(P); } 26 void operator()(StringView Str) { 27 ID.AddString(llvm::StringRef(Str.begin(), Str.size())); 28 } 29 template <typename T> 30 std::enable_if_t<std::is_integral<T>::value || std::is_enum<T>::value> 31 operator()(T V) { 32 ID.AddInteger((unsigned long long)V); 33 } 34 void operator()(itanium_demangle::NodeArray A) { 35 ID.AddInteger(A.size()); 36 for (const Node *N : A) 37 (*this)(N); 38 } 39}; 40 41template<typename ...T> 42void profileCtor(llvm::FoldingSetNodeID &ID, Node::Kind K, T ...V) { 43 FoldingSetNodeIDBuilder Builder = {ID}; 44 Builder(K); 45 int VisitInOrder[] = { 46 (Builder(V), 0) ..., 47 0 // Avoid empty array if there are no arguments. 48 }; 49 (void)VisitInOrder; 50} 51 52// FIXME: Convert this to a generic lambda when possible. 53template<typename NodeT> struct ProfileSpecificNode { 54 FoldingSetNodeID &ID; 55 template<typename ...T> void operator()(T ...V) { 56 profileCtor(ID, NodeKind<NodeT>::Kind, V...); 57 } 58}; 59 60struct ProfileNode { 61 FoldingSetNodeID &ID; 62 template<typename NodeT> void operator()(const NodeT *N) { 63 N->match(ProfileSpecificNode<NodeT>{ID}); 64 } 65}; 66 67template<> void ProfileNode::operator()(const ForwardTemplateReference *N) { 68 llvm_unreachable("should never canonicalize a ForwardTemplateReference"); 69} 70 71void profileNode(llvm::FoldingSetNodeID &ID, const Node *N) { 72 N->visit(ProfileNode{ID}); 73} 74 75class FoldingNodeAllocator { 76 class alignas(alignof(Node *)) NodeHeader : public llvm::FoldingSetNode { 77 public: 78 // 'Node' in this context names the injected-class-name of the base class. 79 itanium_demangle::Node *getNode() { 80 return reinterpret_cast<itanium_demangle::Node *>(this + 1); 81 } 82 void Profile(llvm::FoldingSetNodeID &ID) { profileNode(ID, getNode()); } 83 }; 84 85 BumpPtrAllocator RawAlloc; 86 llvm::FoldingSet<NodeHeader> Nodes; 87 88public: 89 void reset() {} 90 91 template <typename T, typename... Args> 92 std::pair<Node *, bool> getOrCreateNode(bool CreateNewNodes, Args &&... As) { 93 // FIXME: Don't canonicalize forward template references for now, because 94 // they contain state (the resolved template node) that's not known at their 95 // point of creation. 96 if (std::is_same<T, ForwardTemplateReference>::value) { 97 // Note that we don't use if-constexpr here and so we must still write 98 // this code in a generic form. 99 return {new (RawAlloc.Allocate(sizeof(T), alignof(T))) 100 T(std::forward<Args>(As)...), 101 true}; 102 } 103 104 llvm::FoldingSetNodeID ID; 105 profileCtor(ID, NodeKind<T>::Kind, As...); 106 107 void *InsertPos; 108 if (NodeHeader *Existing = Nodes.FindNodeOrInsertPos(ID, InsertPos)) 109 return {static_cast<T*>(Existing->getNode()), false}; 110 111 if (!CreateNewNodes) 112 return {nullptr, true}; 113 114 static_assert(alignof(T) <= alignof(NodeHeader), 115 "underaligned node header for specific node kind"); 116 void *Storage = 117 RawAlloc.Allocate(sizeof(NodeHeader) + sizeof(T), alignof(NodeHeader)); 118 NodeHeader *New = new (Storage) NodeHeader; 119 T *Result = new (New->getNode()) T(std::forward<Args>(As)...); 120 Nodes.InsertNode(New, InsertPos); 121 return {Result, true}; 122 } 123 124 template<typename T, typename... Args> 125 Node *makeNode(Args &&...As) { 126 return getOrCreateNode<T>(true, std::forward<Args>(As)...).first; 127 } 128 129 void *allocateNodeArray(size_t sz) { 130 return RawAlloc.Allocate(sizeof(Node *) * sz, alignof(Node *)); 131 } 132}; 133 134class CanonicalizerAllocator : public FoldingNodeAllocator { 135 Node *MostRecentlyCreated = nullptr; 136 Node *TrackedNode = nullptr; 137 bool TrackedNodeIsUsed = false; 138 bool CreateNewNodes = true; 139 llvm::SmallDenseMap<Node*, Node*, 32> Remappings; 140 141 template<typename T, typename ...Args> Node *makeNodeSimple(Args &&...As) { 142 std::pair<Node *, bool> Result = 143 getOrCreateNode<T>(CreateNewNodes, std::forward<Args>(As)...); 144 if (Result.second) { 145 // Node is new. Make a note of that. 146 MostRecentlyCreated = Result.first; 147 } else if (Result.first) { 148 // Node is pre-existing; check if it's in our remapping table. 149 if (auto *N = Remappings.lookup(Result.first)) { 150 Result.first = N; 151 assert(Remappings.find(Result.first) == Remappings.end() && 152 "should never need multiple remap steps"); 153 } 154 if (Result.first == TrackedNode) 155 TrackedNodeIsUsed = true; 156 } 157 return Result.first; 158 } 159 160 /// Helper to allow makeNode to be partially-specialized on T. 161 template<typename T> struct MakeNodeImpl { 162 CanonicalizerAllocator &Self; 163 template<typename ...Args> Node *make(Args &&...As) { 164 return Self.makeNodeSimple<T>(std::forward<Args>(As)...); 165 } 166 }; 167 168public: 169 template<typename T, typename ...Args> Node *makeNode(Args &&...As) { 170 return MakeNodeImpl<T>{*this}.make(std::forward<Args>(As)...); 171 } 172 173 void reset() { MostRecentlyCreated = nullptr; } 174 175 void setCreateNewNodes(bool CNN) { CreateNewNodes = CNN; } 176 177 void addRemapping(Node *A, Node *B) { 178 // Note, we don't need to check whether B is also remapped, because if it 179 // was we would have already remapped it when building it. 180 Remappings.insert(std::make_pair(A, B)); 181 } 182 183 bool isMostRecentlyCreated(Node *N) const { return MostRecentlyCreated == N; } 184 185 void trackUsesOf(Node *N) { 186 TrackedNode = N; 187 TrackedNodeIsUsed = false; 188 } 189 bool trackedNodeIsUsed() const { return TrackedNodeIsUsed; } 190}; 191 192/// Convert St3foo to NSt3fooE so that equivalences naming one also affect the 193/// other. 194template<> 195struct CanonicalizerAllocator::MakeNodeImpl< 196 itanium_demangle::StdQualifiedName> { 197 CanonicalizerAllocator &Self; 198 Node *make(Node *Child) { 199 Node *StdNamespace = Self.makeNode<itanium_demangle::NameType>("std"); 200 if (!StdNamespace) 201 return nullptr; 202 return Self.makeNode<itanium_demangle::NestedName>(StdNamespace, Child); 203 } 204}; 205 206// FIXME: Also expand built-in substitutions? 207 208using CanonicalizingDemangler = 209 itanium_demangle::ManglingParser<CanonicalizerAllocator>; 210} 211 212struct ItaniumManglingCanonicalizer::Impl { 213 CanonicalizingDemangler Demangler = {nullptr, nullptr}; 214}; 215 216ItaniumManglingCanonicalizer::ItaniumManglingCanonicalizer() : P(new Impl) {} 217ItaniumManglingCanonicalizer::~ItaniumManglingCanonicalizer() { delete P; } 218 219ItaniumManglingCanonicalizer::EquivalenceError 220ItaniumManglingCanonicalizer::addEquivalence(FragmentKind Kind, StringRef First, 221 StringRef Second) { 222 auto &Alloc = P->Demangler.ASTAllocator; 223 Alloc.setCreateNewNodes(true); 224 225 auto Parse = [&](StringRef Str) { 226 P->Demangler.reset(Str.begin(), Str.end()); 227 Node *N = nullptr; 228 switch (Kind) { 229 // A <name>, with minor extensions to allow arbitrary namespace and 230 // template names that can't easily be written as <name>s. 231 case FragmentKind::Name: 232 // Very special case: allow "St" as a shorthand for "3std". It's not 233 // valid as a <name> mangling, but is nonetheless the most natural 234 // way to name the 'std' namespace. 235 if (Str.size() == 2 && P->Demangler.consumeIf("St")) 236 N = P->Demangler.make<itanium_demangle::NameType>("std"); 237 // We permit substitutions to name templates without their template 238 // arguments. This mostly just falls out, as almost all template names 239 // are valid as <name>s, but we also want to parse <substitution>s as 240 // <name>s, even though they're not. 241 else if (Str.startswith("S")) 242 // Parse the substitution and optional following template arguments. 243 N = P->Demangler.parseType(); 244 else 245 N = P->Demangler.parseName(); 246 break; 247 248 // A <type>. 249 case FragmentKind::Type: 250 N = P->Demangler.parseType(); 251 break; 252 253 // An <encoding>. 254 case FragmentKind::Encoding: 255 N = P->Demangler.parseEncoding(); 256 break; 257 } 258 259 // If we have trailing junk, the mangling is invalid. 260 if (P->Demangler.numLeft() != 0) 261 N = nullptr; 262 263 // If any node was created after N, then we cannot safely remap it because 264 // it might already be in use by another node. 265 return std::make_pair(N, Alloc.isMostRecentlyCreated(N)); 266 }; 267 268 Node *FirstNode, *SecondNode; 269 bool FirstIsNew, SecondIsNew; 270 271 std::tie(FirstNode, FirstIsNew) = Parse(First); 272 if (!FirstNode) 273 return EquivalenceError::InvalidFirstMangling; 274 275 Alloc.trackUsesOf(FirstNode); 276 std::tie(SecondNode, SecondIsNew) = Parse(Second); 277 if (!SecondNode) 278 return EquivalenceError::InvalidSecondMangling; 279 280 // If they're already equivalent, there's nothing to do. 281 if (FirstNode == SecondNode) 282 return EquivalenceError::Success; 283 284 if (FirstIsNew && !Alloc.trackedNodeIsUsed()) 285 Alloc.addRemapping(FirstNode, SecondNode); 286 else if (SecondIsNew) 287 Alloc.addRemapping(SecondNode, FirstNode); 288 else 289 return EquivalenceError::ManglingAlreadyUsed; 290 291 return EquivalenceError::Success; 292} 293 294static ItaniumManglingCanonicalizer::Key 295parseMaybeMangledName(CanonicalizingDemangler &Demangler, StringRef Mangling, 296 bool CreateNewNodes) { 297 Demangler.ASTAllocator.setCreateNewNodes(CreateNewNodes); 298 Demangler.reset(Mangling.begin(), Mangling.end()); 299 // Attempt demangling only for names that look like C++ mangled names. 300 // Otherwise, treat them as extern "C" names. We permit the latter to 301 // be remapped by (eg) 302 // encoding 6memcpy 7memmove 303 // consistent with how they are encoded as local-names inside a C++ mangling. 304 Node *N; 305 if (Mangling.startswith("_Z") || Mangling.startswith("__Z") || 306 Mangling.startswith("___Z") || Mangling.startswith("____Z")) 307 N = Demangler.parse(); 308 else 309 N = Demangler.make<itanium_demangle::NameType>( 310 StringView(Mangling.data(), Mangling.size())); 311 return reinterpret_cast<ItaniumManglingCanonicalizer::Key>(N); 312} 313 314ItaniumManglingCanonicalizer::Key 315ItaniumManglingCanonicalizer::canonicalize(StringRef Mangling) { 316 return parseMaybeMangledName(P->Demangler, Mangling, true); 317} 318 319ItaniumManglingCanonicalizer::Key 320ItaniumManglingCanonicalizer::lookup(StringRef Mangling) { 321 return parseMaybeMangledName(P->Demangler, Mangling, false); 322} 323