LLVM 19.0.0git
ItaniumManglingCanonicalizer.cpp
Go to the documentation of this file.
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
10#include "llvm/ADT/DenseMap.h"
11#include "llvm/ADT/FoldingSet.h"
12#include "llvm/ADT/StringRef.h"
15
16using namespace llvm;
17using llvm::itanium_demangle::ForwardTemplateReference;
18using llvm::itanium_demangle::Node;
19using llvm::itanium_demangle::NodeKind;
20
21namespace {
22struct FoldingSetNodeIDBuilder {
24 void operator()(const Node *P) { ID.AddPointer(P); }
25 void operator()(std::string_view Str) {
26 if (Str.empty())
27 ID.AddString({});
28 else
29 ID.AddString(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((unsigned long long)V);
34 }
35 void operator()(itanium_demangle::NodeArray A) {
36 ID.AddInteger(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};
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 {
56 template<typename ...T> void operator()(T ...V) {
57 profileCtor(ID, NodeKind<NodeT>::Kind, V...);
58 }
59};
60
61struct ProfileNode {
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(ProfileNode{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, getNode()); }
84 };
85
86 BumpPtrAllocator RawAlloc;
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(sizeof(T), alignof(T)))
101 T(std::forward<Args>(As)...),
102 true};
103 }
104
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(sizeof(NodeHeader) + sizeof(T), alignof(NodeHeader));
119 NodeHeader *New = new (Storage) NodeHeader;
120 T *Result = new (New->getNode()) T(std::forward<Args>(As)...);
121 Nodes.InsertNode(New, InsertPos);
122 return {Result, true};
123 }
124
125 template<typename T, typename... Args>
126 Node *makeNode(Args &&...As) {
127 return getOrCreateNode<T>(true, std::forward<Args>(As)...).first;
128 }
129
130 void *allocateNodeArray(size_t sz) {
131 return RawAlloc.Allocate(sizeof(Node *) * sz, alignof(Node *));
132 }
133};
134
135class CanonicalizerAllocator : public FoldingNodeAllocator {
136 Node *MostRecentlyCreated = nullptr;
137 Node *TrackedNode = nullptr;
138 bool TrackedNodeIsUsed = false;
139 bool CreateNewNodes = true;
141
142 template<typename T, typename ...Args> Node *makeNodeSimple(Args &&...As) {
143 std::pair<Node *, bool> Result =
144 getOrCreateNode<T>(CreateNewNodes, std::forward<Args>(As)...);
145 if (Result.second) {
146 // Node is new. Make a note of that.
147 MostRecentlyCreated = Result.first;
148 } else if (Result.first) {
149 // Node is pre-existing; check if it's in our remapping table.
150 if (auto *N = Remappings.lookup(Result.first)) {
151 Result.first = N;
152 assert(!Remappings.contains(Result.first) &&
153 "should never need multiple remap steps");
154 }
155 if (Result.first == TrackedNode)
156 TrackedNodeIsUsed = true;
157 }
158 return Result.first;
159 }
160
161 /// Helper to allow makeNode to be partially-specialized on T.
162 template<typename T> struct MakeNodeImpl {
163 CanonicalizerAllocator &Self;
164 template<typename ...Args> Node *make(Args &&...As) {
165 return Self.makeNodeSimple<T>(std::forward<Args>(As)...);
166 }
167 };
168
169public:
170 template<typename T, typename ...Args> Node *makeNode(Args &&...As) {
171 return MakeNodeImpl<T>{*this}.make(std::forward<Args>(As)...);
172 }
173
174 void reset() { MostRecentlyCreated = nullptr; }
175
176 void setCreateNewNodes(bool CNN) { CreateNewNodes = CNN; }
177
178 void addRemapping(Node *A, Node *B) {
179 // Note, we don't need to check whether B is also remapped, because if it
180 // was we would have already remapped it when building it.
181 Remappings.insert(std::make_pair(A, B));
182 }
183
184 bool isMostRecentlyCreated(Node *N) const { return MostRecentlyCreated == N; }
185
186 void trackUsesOf(Node *N) {
187 TrackedNode = N;
188 TrackedNodeIsUsed = false;
189 }
190 bool trackedNodeIsUsed() const { return TrackedNodeIsUsed; }
191};
192
193// FIXME: Also expand built-in substitutions?
194
195using CanonicalizingDemangler =
196 itanium_demangle::ManglingParser<CanonicalizerAllocator>;
197} // namespace
198
200 CanonicalizingDemangler Demangler = {nullptr, nullptr};
201};
202
205
208 StringRef Second) {
209 auto &Alloc = P->Demangler.ASTAllocator;
210 Alloc.setCreateNewNodes(true);
211
212 auto Parse = [&](StringRef Str) {
213 P->Demangler.reset(Str.begin(), Str.end());
214 Node *N = nullptr;
215 switch (Kind) {
216 // A <name>, with minor extensions to allow arbitrary namespace and
217 // template names that can't easily be written as <name>s.
219 // Very special case: allow "St" as a shorthand for "3std". It's not
220 // valid as a <name> mangling, but is nonetheless the most natural
221 // way to name the 'std' namespace.
222 if (Str.size() == 2 && P->Demangler.consumeIf("St"))
223 N = P->Demangler.make<itanium_demangle::NameType>("std");
224 // We permit substitutions to name templates without their template
225 // arguments. This mostly just falls out, as almost all template names
226 // are valid as <name>s, but we also want to parse <substitution>s as
227 // <name>s, even though they're not.
228 else if (Str.starts_with("S"))
229 // Parse the substitution and optional following template arguments.
230 N = P->Demangler.parseType();
231 else
232 N = P->Demangler.parseName();
233 break;
234
235 // A <type>.
237 N = P->Demangler.parseType();
238 break;
239
240 // An <encoding>.
242 N = P->Demangler.parseEncoding();
243 break;
244 }
245
246 // If we have trailing junk, the mangling is invalid.
247 if (P->Demangler.numLeft() != 0)
248 N = nullptr;
249
250 // If any node was created after N, then we cannot safely remap it because
251 // it might already be in use by another node.
252 return std::make_pair(N, Alloc.isMostRecentlyCreated(N));
253 };
254
255 Node *FirstNode, *SecondNode;
256 bool FirstIsNew, SecondIsNew;
257
258 std::tie(FirstNode, FirstIsNew) = Parse(First);
259 if (!FirstNode)
261
262 Alloc.trackUsesOf(FirstNode);
263 std::tie(SecondNode, SecondIsNew) = Parse(Second);
264 if (!SecondNode)
266
267 // If they're already equivalent, there's nothing to do.
268 if (FirstNode == SecondNode)
270
271 if (FirstIsNew && !Alloc.trackedNodeIsUsed())
272 Alloc.addRemapping(FirstNode, SecondNode);
273 else if (SecondIsNew)
274 Alloc.addRemapping(SecondNode, FirstNode);
275 else
277
279}
280
282parseMaybeMangledName(CanonicalizingDemangler &Demangler, StringRef Mangling,
283 bool CreateNewNodes) {
284 Demangler.ASTAllocator.setCreateNewNodes(CreateNewNodes);
285 Demangler.reset(Mangling.begin(), Mangling.end());
286 // Attempt demangling only for names that look like C++ mangled names.
287 // Otherwise, treat them as extern "C" names. We permit the latter to
288 // be remapped by (eg)
289 // encoding 6memcpy 7memmove
290 // consistent with how they are encoded as local-names inside a C++ mangling.
291 Node *N;
292 if (Mangling.starts_with("_Z") || Mangling.starts_with("__Z") ||
293 Mangling.starts_with("___Z") || Mangling.starts_with("____Z"))
294 N = Demangler.parse();
295 else
296 N = Demangler.make<itanium_demangle::NameType>(
297 std::string_view(Mangling.data(), Mangling.size()));
298 return reinterpret_cast<ItaniumManglingCanonicalizer::Key>(N);
299}
300
303 return parseMaybeMangledName(P->Demangler, Mangling, true);
304}
305
308 return parseMaybeMangledName(P->Demangler, Mangling, false);
309}
static msgpack::DocNode getNode(msgpack::DocNode DN, msgpack::Type Type, MCValue Val)
This file defines the BumpPtrAllocator interface.
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
static GCRegistry::Add< ErlangGC > A("erlang", "erlang-compatible garbage collector")
This file defines the DenseMap class.
This file defines a hash set that can be used to remove duplication of nodes in a graph.
itanium_demangle::ManglingParser< DefaultAllocator > Demangler
static ItaniumManglingCanonicalizer::Key parseMaybeMangledName(CanonicalizingDemangler &Demangler, StringRef Mangling, bool CreateNewNodes)
Load MIR Sample Profile
#define P(N)
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
Allocate memory in an ever growing pool, as if by bump-pointer.
Definition: Allocator.h:66
LLVM_ATTRIBUTE_RETURNS_NONNULL void * Allocate(size_t Size, Align Alignment)
Allocate space at the specified alignment.
Definition: Allocator.h:148
ValueT lookup(const_arg_type_t< KeyT > Val) const
lookup - Return the entry for the specified key, or a default constructed value if no such entry exis...
Definition: DenseMap.h:202
bool contains(const_arg_type_t< KeyT > Val) const
Return true if the specified key is in the map, false otherwise.
Definition: DenseMap.h:145
std::pair< iterator, bool > insert(const std::pair< KeyT, ValueT > &KV)
Definition: DenseMap.h:220
Node - This class is used to maintain the singly linked bucket list in a folding set.
Definition: FoldingSet.h:138
void InsertNode(T *N, void *InsertPos)
InsertNode - Insert the specified node into the folding set, knowing that it is not already in the fo...
Definition: FoldingSet.h:513
T * FindNodeOrInsertPos(const FoldingSetNodeID &ID, void *&InsertPos)
FindNodeOrInsertPos - Look up the node specified by ID.
Definition: FoldingSet.h:505
FoldingSetNodeID - This class is used to gather all the unique data bits of a node.
Definition: FoldingSet.h:327
FoldingSet - This template class is used to instantiate a specialized implementation of the folding s...
Definition: FoldingSet.h:536
@ Encoding
The mangling fragment is an <encoding>.
@ Name
The mangling fragment is a <name> (or a predefined <substitution>).
@ Type
The mangling fragment is a <type>.
Key lookup(StringRef Mangling)
Find a canonical key for the specified mangling, if one has already been formed.
Key canonicalize(StringRef Mangling)
Form a canonical key for the specified mangling.
@ InvalidFirstMangling
The first equivalent mangling is invalid.
@ InvalidSecondMangling
The second equivalent mangling is invalid.
@ ManglingAlreadyUsed
Both the equivalent manglings have already been used as components of some other mangling we've looke...
EquivalenceError addEquivalence(FragmentKind Kind, StringRef First, StringRef Second)
Add an equivalence between First and Second.
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:50
bool starts_with(StringRef Prefix) const
Check if this string starts with the given Prefix.
Definition: StringRef.h:250
iterator begin() const
Definition: StringRef.h:111
constexpr size_t size() const
size - Get the string size.
Definition: StringRef.h:137
constexpr const char * data() const
data - Get a pointer to the start of the string (which may not be null terminated).
Definition: StringRef.h:131
iterator end() const
Definition: StringRef.h:113
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
constexpr char Args[]
Key for Kernel::Metadata::mArgs.
unsigned ID
LLVM IR allows to use arbitrary numbers as calling convention identifiers.
Definition: CallingConv.h:24
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
@ First
Helpers to iterate all locations in the MemoryEffectsBase class.
#define N
A forward-reference to a template argument that was not known at the point where the template paramet...
Determine the kind of a node from its type.