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