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