LLVM  10.0.0svn
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 
11 #include "llvm/ADT/FoldingSet.h"
12 #include "llvm/ADT/StringRef.h"
14 #include "llvm/Support/Allocator.h"
15 
16 #include "llvm/ADT/DenseMap.h"
17 #include "llvm/ADT/FoldingSet.h"
18 #include "llvm/ADT/StringRef.h"
19 
20 using namespace llvm;
21 using llvm::itanium_demangle::ForwardTemplateReference;
22 using llvm::itanium_demangle::Node;
24 using llvm::itanium_demangle::StringView;
25 
26 namespace {
27 struct FoldingSetNodeIDBuilder {
29  void operator()(const Node *P) { ID.AddPointer(P); }
30  void operator()(StringView Str) {
31  ID.AddString(llvm::StringRef(Str.begin(), Str.size()));
32  }
33  template<typename T>
34  typename std::enable_if<std::is_integral<T>::value ||
35  std::is_enum<T>::value>::type
36  operator()(T V) {
37  ID.AddInteger((unsigned long long)V);
38  }
39  void operator()(itanium_demangle::NodeOrString NS) {
40  if (NS.isNode()) {
41  ID.AddInteger(0);
42  (*this)(NS.asNode());
43  } else if (NS.isString()) {
44  ID.AddInteger(1);
45  (*this)(NS.asString());
46  } else {
47  ID.AddInteger(2);
48  }
49  }
50  void operator()(itanium_demangle::NodeArray A) {
51  ID.AddInteger(A.size());
52  for (const Node *N : A)
53  (*this)(N);
54  }
55 };
56 
57 template<typename ...T>
58 void profileCtor(llvm::FoldingSetNodeID &ID, Node::Kind K, T ...V) {
59  FoldingSetNodeIDBuilder Builder = {ID};
60  Builder(K);
61  int VisitInOrder[] = {
62  (Builder(V), 0) ...,
63  0 // Avoid empty array if there are no arguments.
64  };
65  (void)VisitInOrder;
66 }
67 
68 // FIXME: Convert this to a generic lambda when possible.
69 template<typename NodeT> struct ProfileSpecificNode {
71  template<typename ...T> void operator()(T ...V) {
72  profileCtor(ID, NodeKind<NodeT>::Kind, V...);
73  }
74 };
75 
76 struct ProfileNode {
78  template<typename NodeT> void operator()(const NodeT *N) {
79  N->match(ProfileSpecificNode<NodeT>{ID});
80  }
81 };
82 
83 template<> void ProfileNode::operator()(const ForwardTemplateReference *N) {
84  llvm_unreachable("should never canonicalize a ForwardTemplateReference");
85 }
86 
87 void profileNode(llvm::FoldingSetNodeID &ID, const Node *N) {
88  N->visit(ProfileNode{ID});
89 }
90 
91 class FoldingNodeAllocator {
92  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  return reinterpret_cast<itanium_demangle::Node *>(this + 1);
97  }
98  void Profile(llvm::FoldingSetNodeID &ID) { profileNode(ID, getNode()); }
99  };
100 
101  BumpPtrAllocator RawAlloc;
103 
104 public:
105  void reset() {}
106 
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  // this code in a generic form.
115  return {new (RawAlloc.Allocate(sizeof(T), alignof(T)))
116  T(std::forward<Args>(As)...),
117  true};
118  }
119 
121  profileCtor(ID, NodeKind<T>::Kind, As...);
122 
123  void *InsertPos;
124  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  void *Storage =
133  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  Node *makeNode(Args &&...As) {
142  return getOrCreateNode<T>(true, std::forward<Args>(As)...).first;
143  }
144 
145  void *allocateNodeArray(size_t sz) {
146  return RawAlloc.Allocate(sizeof(Node *) * sz, alignof(Node *));
147  }
148 };
149 
150 class CanonicalizerAllocator : public FoldingNodeAllocator {
151  Node *MostRecentlyCreated = nullptr;
152  Node *TrackedNode = nullptr;
153  bool TrackedNodeIsUsed = false;
154  bool CreateNewNodes = true;
156 
157  template<typename T, typename ...Args> Node *makeNodeSimple(Args &&...As) {
158  std::pair<Node *, bool> Result =
159  getOrCreateNode<T>(CreateNewNodes, std::forward<Args>(As)...);
160  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  "should never need multiple remap steps");
169  }
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  template<typename T> struct MakeNodeImpl {
178  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  return MakeNodeImpl<T>{*this}.make(std::forward<Args>(As)...);
187  }
188 
189  void reset() { MostRecentlyCreated = nullptr; }
190 
191  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  // was we would have already remapped it when building it.
196  Remappings.insert(std::make_pair(A, B));
197  }
198 
199  bool isMostRecentlyCreated(Node *N) const { return MostRecentlyCreated == N; }
200 
201  void trackUsesOf(Node *N) {
202  TrackedNode = N;
203  TrackedNodeIsUsed = false;
204  }
205  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  CanonicalizerAllocator &Self;
214  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 // FIXME: Also expand built-in substitutions?
223 
224 using CanonicalizingDemangler =
225  itanium_demangle::ManglingParser<CanonicalizerAllocator>;
226 }
227 
229  CanonicalizingDemangler Demangler = {nullptr, nullptr};
230 };
231 
234 
237  StringRef Second) {
238  auto &Alloc = P->Demangler.ASTAllocator;
239  Alloc.setCreateNewNodes(true);
240 
241  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  // valid as a <name> mangling, but is nonetheless the most natural
250  // 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  // Parse the substitution and optional following template arguments.
259  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  break;
268 
269  // An <encoding>.
271  N = P->Demangler.parseEncoding();
272  break;
273  }
274 
275  // If we have trailing junk, the mangling is invalid.
276  if (P->Demangler.numLeft() != 0)
277  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  bool FirstIsNew, SecondIsNew;
286 
287  std::tie(FirstNode, FirstIsNew) = Parse(First);
288  if (!FirstNode)
290 
291  Alloc.trackUsesOf(FirstNode);
292  std::tie(SecondNode, SecondIsNew) = Parse(Second);
293  if (!SecondNode)
295 
296  // If they're already equivalent, there's nothing to do.
297  if (FirstNode == SecondNode)
299 
300  if (FirstIsNew && !Alloc.trackedNodeIsUsed())
301  Alloc.addRemapping(FirstNode, SecondNode);
302  else if (SecondIsNew)
303  Alloc.addRemapping(SecondNode, FirstNode);
304  else
306 
308 }
309 
312  P->Demangler.ASTAllocator.setCreateNewNodes(true);
313  P->Demangler.reset(Mangling.begin(), Mangling.end());
314  return reinterpret_cast<Key>(P->Demangler.parse());
315 }
316 
319  P->Demangler.ASTAllocator.setCreateNewNodes(false);
320  P->Demangler.reset(Mangling.begin(), Mangling.end());
321  return reinterpret_cast<Key>(P->Demangler.parse());
322 }
void AddPointer(const void *Ptr)
Add* - Add various data types to Bit data.
Definition: FoldingSet.cpp:51
This class represents lattice values for constants.
Definition: AllocatorList.h:23
T * FindNodeOrInsertPos(const FoldingSetNodeID &ID, void *&InsertPos)
FindNodeOrInsertPos - Look up the node specified by ID.
Definition: FoldingSet.h:444
This file defines the MallocAllocator and BumpPtrAllocator interfaces.
void AddInteger(signed I)
Definition: FoldingSet.cpp:60
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:451
FoldingSetNodeID - This class is used to gather all the unique data bits of a node.
Definition: FoldingSet.h:305
#define P(N)
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
Allocate memory in an ever growing pool, as if by bump-pointer.
Definition: Allocator.h:141
itanium_demangle::ManglingParser< DefaultAllocator > Demangler
FoldingSet - This template class is used to instantiate a specialized implementation of the folding s...
Definition: FoldingSet.h:473
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
The mangling fragment is an <encoding>.
Key lookup(StringRef Mangling)
Find a canonical key for the specified mangling, if one has already been formed.
Both the equivalent manglings have already been used as components of some other mangling we&#39;ve looke...
LLVM_ATTRIBUTE_RETURNS_NONNULL LLVM_ATTRIBUTE_RETURNS_NOALIAS void * Allocate(size_t Size, Align Alignment)
Allocate space at the specified alignment.
Definition: Allocator.h:215
iterator begin() const
Definition: StringRef.h:115
Node - This class is used to maintain the singly linked bucket list in a folding set.
Definition: FoldingSet.h:135
#define N
void AddString(StringRef String)
Definition: FoldingSet.cpp:86
The mangling fragment is a <name> (or a predefined <substitution>).
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:185
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
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:48
iterator end() const
Definition: StringRef.h:117
constexpr char Args[]
Key for Kernel::Metadata::mArgs.
Key canonicalize(StringRef Mangling)
Form a canonical key for the specified mangling.