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 
16 using namespace llvm;
17 using llvm::itanium_demangle::ForwardTemplateReference;
18 using llvm::itanium_demangle::Node;
19 using llvm::itanium_demangle::NodeKind;
20 using llvm::itanium_demangle::StringView;
21 
22 namespace {
23 struct 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 
41 template<typename ...T>
42 void 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.
53 template<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 
60 struct ProfileNode {
61   FoldingSetNodeID &ID;
62   template<typename NodeT> void operator()(const NodeT *N) {
63     N->match(ProfileSpecificNode<NodeT>{ID});
64   }
65 };
66 
67 template<> void ProfileNode::operator()(const ForwardTemplateReference *N) {
68   llvm_unreachable("should never canonicalize a ForwardTemplateReference");
69 }
70 
71 void profileNode(llvm::FoldingSetNodeID &ID, const Node *N) {
72   N->visit(ProfileNode{ID});
73 }
74 
75 class 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 
88 public:
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 
134 class 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 
168 public:
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 // FIXME: Also expand built-in substitutions?
193 
194 using CanonicalizingDemangler =
195     itanium_demangle::ManglingParser<CanonicalizerAllocator>;
196 } // namespace
197 
198 struct ItaniumManglingCanonicalizer::Impl {
199   CanonicalizingDemangler Demangler = {nullptr, nullptr};
200 };
201 
202 ItaniumManglingCanonicalizer::ItaniumManglingCanonicalizer() : P(new Impl) {}
203 ItaniumManglingCanonicalizer::~ItaniumManglingCanonicalizer() { delete P; }
204 
205 ItaniumManglingCanonicalizer::EquivalenceError
206 ItaniumManglingCanonicalizer::addEquivalence(FragmentKind Kind, StringRef First,
207                                              StringRef Second) {
208   auto &Alloc = P->Demangler.ASTAllocator;
209   Alloc.setCreateNewNodes(true);
210 
211   auto Parse = [&](StringRef Str) {
212     P->Demangler.reset(Str.begin(), Str.end());
213     Node *N = nullptr;
214     switch (Kind) {
215       // A <name>, with minor extensions to allow arbitrary namespace and
216       // template names that can't easily be written as <name>s.
217     case FragmentKind::Name:
218       // Very special case: allow "St" as a shorthand for "3std". It's not
219       // valid as a <name> mangling, but is nonetheless the most natural
220       // way to name the 'std' namespace.
221       if (Str.size() == 2 && P->Demangler.consumeIf("St"))
222         N = P->Demangler.make<itanium_demangle::NameType>("std");
223       // We permit substitutions to name templates without their template
224       // arguments. This mostly just falls out, as almost all template names
225       // are valid as <name>s, but we also want to parse <substitution>s as
226       // <name>s, even though they're not.
227       else if (Str.startswith("S"))
228         // Parse the substitution and optional following template arguments.
229         N = P->Demangler.parseType();
230       else
231         N = P->Demangler.parseName();
232       break;
233 
234       // A <type>.
235     case FragmentKind::Type:
236       N = P->Demangler.parseType();
237       break;
238 
239       // An <encoding>.
240     case FragmentKind::Encoding:
241       N = P->Demangler.parseEncoding();
242       break;
243     }
244 
245     // If we have trailing junk, the mangling is invalid.
246     if (P->Demangler.numLeft() != 0)
247       N = nullptr;
248 
249     // If any node was created after N, then we cannot safely remap it because
250     // it might already be in use by another node.
251     return std::make_pair(N, Alloc.isMostRecentlyCreated(N));
252   };
253 
254   Node *FirstNode, *SecondNode;
255   bool FirstIsNew, SecondIsNew;
256 
257   std::tie(FirstNode, FirstIsNew) = Parse(First);
258   if (!FirstNode)
259     return EquivalenceError::InvalidFirstMangling;
260 
261   Alloc.trackUsesOf(FirstNode);
262   std::tie(SecondNode, SecondIsNew) = Parse(Second);
263   if (!SecondNode)
264     return EquivalenceError::InvalidSecondMangling;
265 
266   // If they're already equivalent, there's nothing to do.
267   if (FirstNode == SecondNode)
268     return EquivalenceError::Success;
269 
270   if (FirstIsNew && !Alloc.trackedNodeIsUsed())
271     Alloc.addRemapping(FirstNode, SecondNode);
272   else if (SecondIsNew)
273     Alloc.addRemapping(SecondNode, FirstNode);
274   else
275     return EquivalenceError::ManglingAlreadyUsed;
276 
277   return EquivalenceError::Success;
278 }
279 
280 static ItaniumManglingCanonicalizer::Key
281 parseMaybeMangledName(CanonicalizingDemangler &Demangler, StringRef Mangling,
282                       bool CreateNewNodes) {
283   Demangler.ASTAllocator.setCreateNewNodes(CreateNewNodes);
284   Demangler.reset(Mangling.begin(), Mangling.end());
285   // Attempt demangling only for names that look like C++ mangled names.
286   // Otherwise, treat them as extern "C" names. We permit the latter to
287   // be remapped by (eg)
288   //   encoding 6memcpy 7memmove
289   // consistent with how they are encoded as local-names inside a C++ mangling.
290   Node *N;
291   if (Mangling.startswith("_Z") || Mangling.startswith("__Z") ||
292       Mangling.startswith("___Z") || Mangling.startswith("____Z"))
293     N = Demangler.parse();
294   else
295     N = Demangler.make<itanium_demangle::NameType>(
296         StringView(Mangling.data(), Mangling.size()));
297   return reinterpret_cast<ItaniumManglingCanonicalizer::Key>(N);
298 }
299 
300 ItaniumManglingCanonicalizer::Key
301 ItaniumManglingCanonicalizer::canonicalize(StringRef Mangling) {
302   return parseMaybeMangledName(P->Demangler, Mangling, true);
303 }
304 
305 ItaniumManglingCanonicalizer::Key
306 ItaniumManglingCanonicalizer::lookup(StringRef Mangling) {
307   return parseMaybeMangledName(P->Demangler, Mangling, false);
308 }
309