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