LLVM  14.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"
14 #include "llvm/Support/Allocator.h"
15 
16 using namespace llvm;
17 using llvm::itanium_demangle::ForwardTemplateReference;
18 using llvm::itanium_demangle::Node;
20 using llvm::itanium_demangle::StringView;
21 
22 namespace {
23 struct FoldingSetNodeIDBuilder {
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 {
55  template<typename ...T> void operator()(T ...V) {
56  profileCtor(ID, NodeKind<NodeT>::Kind, V...);
57  }
58 };
59 
60 struct ProfileNode {
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;
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 
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;
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 /// Convert St3foo to NSt3fooE so that equivalences naming one also affect the
193 /// other.
194 template<>
195 struct CanonicalizerAllocator::MakeNodeImpl<
196  itanium_demangle::StdQualifiedName> {
197  CanonicalizerAllocator &Self;
198  Node *make(Node *Child) {
199  Node *StdNamespace = Self.makeNode<itanium_demangle::NameType>("std");
200  if (!StdNamespace)
201  return nullptr;
202  return Self.makeNode<itanium_demangle::NestedName>(StdNamespace, Child);
203  }
204 };
205 
206 // FIXME: Also expand built-in substitutions?
207 
208 using CanonicalizingDemangler =
209  itanium_demangle::ManglingParser<CanonicalizerAllocator>;
210 } // namespace
211 
213  CanonicalizingDemangler Demangler = {nullptr, nullptr};
214 };
215 
218 
221  StringRef Second) {
222  auto &Alloc = P->Demangler.ASTAllocator;
223  Alloc.setCreateNewNodes(true);
224 
225  auto Parse = [&](StringRef Str) {
226  P->Demangler.reset(Str.begin(), Str.end());
227  Node *N = nullptr;
228  switch (Kind) {
229  // A <name>, with minor extensions to allow arbitrary namespace and
230  // template names that can't easily be written as <name>s.
231  case FragmentKind::Name:
232  // Very special case: allow "St" as a shorthand for "3std". It's not
233  // valid as a <name> mangling, but is nonetheless the most natural
234  // way to name the 'std' namespace.
235  if (Str.size() == 2 && P->Demangler.consumeIf("St"))
236  N = P->Demangler.make<itanium_demangle::NameType>("std");
237  // We permit substitutions to name templates without their template
238  // arguments. This mostly just falls out, as almost all template names
239  // are valid as <name>s, but we also want to parse <substitution>s as
240  // <name>s, even though they're not.
241  else if (Str.startswith("S"))
242  // Parse the substitution and optional following template arguments.
243  N = P->Demangler.parseType();
244  else
245  N = P->Demangler.parseName();
246  break;
247 
248  // A <type>.
249  case FragmentKind::Type:
250  N = P->Demangler.parseType();
251  break;
252 
253  // An <encoding>.
255  N = P->Demangler.parseEncoding();
256  break;
257  }
258 
259  // If we have trailing junk, the mangling is invalid.
260  if (P->Demangler.numLeft() != 0)
261  N = nullptr;
262 
263  // If any node was created after N, then we cannot safely remap it because
264  // it might already be in use by another node.
265  return std::make_pair(N, Alloc.isMostRecentlyCreated(N));
266  };
267 
268  Node *FirstNode, *SecondNode;
269  bool FirstIsNew, SecondIsNew;
270 
271  std::tie(FirstNode, FirstIsNew) = Parse(First);
272  if (!FirstNode)
274 
275  Alloc.trackUsesOf(FirstNode);
276  std::tie(SecondNode, SecondIsNew) = Parse(Second);
277  if (!SecondNode)
279 
280  // If they're already equivalent, there's nothing to do.
281  if (FirstNode == SecondNode)
283 
284  if (FirstIsNew && !Alloc.trackedNodeIsUsed())
285  Alloc.addRemapping(FirstNode, SecondNode);
286  else if (SecondIsNew)
287  Alloc.addRemapping(SecondNode, FirstNode);
288  else
290 
292 }
293 
295 parseMaybeMangledName(CanonicalizingDemangler &Demangler, StringRef Mangling,
296  bool CreateNewNodes) {
297  Demangler.ASTAllocator.setCreateNewNodes(CreateNewNodes);
298  Demangler.reset(Mangling.begin(), Mangling.end());
299  // Attempt demangling only for names that look like C++ mangled names.
300  // Otherwise, treat them as extern "C" names. We permit the latter to
301  // be remapped by (eg)
302  // encoding 6memcpy 7memmove
303  // consistent with how they are encoded as local-names inside a C++ mangling.
304  Node *N;
305  if (Mangling.startswith("_Z") || Mangling.startswith("__Z") ||
306  Mangling.startswith("___Z") || Mangling.startswith("____Z"))
307  N = Demangler.parse();
308  else
310  StringView(Mangling.data(), Mangling.size()));
311  return reinterpret_cast<ItaniumManglingCanonicalizer::Key>(N);
312 }
313 
316  return parseMaybeMangledName(P->Demangler, Mangling, true);
317 }
318 
321  return parseMaybeMangledName(P->Demangler, Mangling, false);
322 }
llvm::StringRef::startswith
LLVM_NODISCARD bool startswith(StringRef Prefix) const
Check if this string starts with the given Prefix.
Definition: StringRef.h:286
llvm
---------------------— PointerInfo ------------------------------------—
Definition: AllocatorList.h:23
llvm::wasm::NameType
NameType
Definition: Wasm.h:208
llvm::ItaniumManglingCanonicalizer::FragmentKind::Type
@ Type
The mangling fragment is a <type>.
llvm::DenseMapBase< SmallDenseMap< KeyT, ValueT, 4, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >, KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >::lookup
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:197
StringRef.h
parseMaybeMangledName
static ItaniumManglingCanonicalizer::Key parseMaybeMangledName(CanonicalizingDemangler &Demangler, StringRef Mangling, bool CreateNewNodes)
Definition: ItaniumManglingCanonicalizer.cpp:295
P
This currently compiles esp xmm0 movsd esp eax eax esp ret We should use not the dag combiner This is because dagcombine2 needs to be able to see through the X86ISD::Wrapper which DAGCombine can t really do The code for turning x load into a single vector load is target independent and should be moved to the dag combiner The code for turning x load into a vector load can only handle a direct load from a global or a direct load from the stack It should be generalized to handle any load from P
Definition: README-SSE.txt:411
llvm::FoldingSetImpl< FoldingSet< T >, T >::InsertNode
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:470
Allocator.h
llvm::SmallDenseMap
Definition: DenseMap.h:880
llvm::ItaniumManglingCanonicalizer::FragmentKind
FragmentKind
Definition: ItaniumManglingCanonicalizer.h:58
llvm::FoldingSetImpl< FoldingSet< T >, T >::FindNodeOrInsertPos
T * FindNodeOrInsertPos(const FoldingSetNodeID &ID, void *&InsertPos)
FindNodeOrInsertPos - Look up the node specified by ID.
Definition: FoldingSet.h:462
DenseMap.h
T
#define T
Definition: Mips16ISelLowering.cpp:341
llvm::ItaniumManglingCanonicalizer::ItaniumManglingCanonicalizer
ItaniumManglingCanonicalizer()
Definition: ItaniumManglingCanonicalizer.cpp:216
new
Common register allocation spilling lr str ldr sxth r3 ldr mla r4 can lr mov lr str ldr sxth r3 mla r4 and then merge mul and lr str ldr sxth r3 mla r4 It also increase the likelihood the store may become dead bb27 Successors according to LLVM ID Predecessors according to mbb< bb27, 0x8b0a7c0 > Note ADDri is not a two address instruction its result reg1037 is an operand of the PHI node in bb76 and its operand reg1039 is the result of the PHI node We should treat it as a two address code and make sure the ADDri is scheduled after any node that reads reg1039 Use info(i.e. register scavenger) to assign it a free register to allow reuse the collector could move the objects and invalidate the derived pointer This is bad enough in the first but safe points can crop up unpredictably **array_addr i32 n y store obj * new
Definition: README.txt:125
Demangler
itanium_demangle::ManglingParser< DefaultAllocator > Demangler
Definition: ItaniumDemangle.cpp:324
llvm::ItaniumManglingCanonicalizer::Impl::Demangler
CanonicalizingDemangler Demangler
Definition: ItaniumManglingCanonicalizer.cpp:213
llvm::BumpPtrAllocatorImpl::Allocate
LLVM_ATTRIBUTE_RETURNS_NONNULL LLVM_ATTRIBUTE_RETURNS_NOALIAS void * Allocate(size_t Size, Align Alignment)
Allocate space at the specified alignment.
Definition: Allocator.h:145
llvm::ARM_PROC::A
@ A
Definition: ARMBaseInfo.h:34
Node::Kind
Kind
Definition: ItaniumDemangle.h:116
llvm::ms_demangle::QualifierMangleMode::Result
@ Result
ItaniumManglingCanonicalizer.h
B
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
First
into llvm powi allowing the code generator to produce balanced multiplication trees First
Definition: README.txt:54
llvm::ItaniumManglingCanonicalizer::Impl
Definition: ItaniumManglingCanonicalizer.cpp:212
llvm::ilist_detail::make
T & make()
llvm::ItaniumManglingCanonicalizer::EquivalenceError::Success
@ Success
llvm::lltok::Kind
Kind
Definition: LLToken.h:18
llvm::ItaniumManglingCanonicalizer::~ItaniumManglingCanonicalizer
~ItaniumManglingCanonicalizer()
Definition: ItaniumManglingCanonicalizer.cpp:217
llvm::ItaniumManglingCanonicalizer::FragmentKind::Name
@ Name
The mangling fragment is a <name> (or a predefined <substitution>).
llvm::StringRef::end
iterator end() const
Definition: StringRef.h:130
llvm::BumpPtrAllocatorImpl
Allocate memory in an ever growing pool, as if by bump-pointer.
Definition: Allocator.h:67
llvm::ItaniumManglingCanonicalizer::FragmentKind::Encoding
@ Encoding
The mangling fragment is an <encoding>.
llvm::DenseMapBase< SmallDenseMap< KeyT, ValueT, 4, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >, KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >::find
iterator find(const_arg_type_t< KeyT > Val)
Definition: DenseMap.h:150
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
StdQualifiedName
Definition: ItaniumDemangle.h:1329
Builder
assume Assume Builder
Definition: AssumeBundleBuilder.cpp:651
llvm::ItaniumManglingCanonicalizer::EquivalenceError::InvalidSecondMangling
@ InvalidSecondMangling
The second equivalent mangling is invalid.
llvm::FoldingSet
FoldingSet - This template class is used to instantiate a specialized implementation of the folding s...
Definition: FoldingSet.h:493
llvm::StringRef
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:58
llvm::FoldingSetBase::Node
Node - This class is used to maintain the singly linked bucket list in a folding set.
Definition: FoldingSet.h:133
llvm_unreachable
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
Definition: ErrorHandling.h:136
llvm::ItaniumManglingCanonicalizer::EquivalenceError::InvalidFirstMangling
@ InvalidFirstMangling
The first equivalent mangling is invalid.
llvm::ms_demangle::IntrinsicFunctionKind::New
@ New
llvm::FoldingSetNodeID
FoldingSetNodeID - This class is used to gather all the unique data bits of a node.
Definition: FoldingSet.h:313
llvm::DenseMapBase< SmallDenseMap< KeyT, ValueT, 4, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >, KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >::insert
std::pair< iterator, bool > insert(const std::pair< KeyT, ValueT > &KV)
Definition: DenseMap.h:207
FoldingSet.h
ItaniumDemangle.h
llvm::DenseMapBase< SmallDenseMap< KeyT, ValueT, 4, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >, KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >::end
iterator end()
Definition: DenseMap.h:83
llvm::ItaniumManglingCanonicalizer::EquivalenceError::ManglingAlreadyUsed
@ ManglingAlreadyUsed
Both the equivalent manglings have already been used as components of some other mangling we've looke...
llvm::ItaniumManglingCanonicalizer::EquivalenceError
EquivalenceError
Definition: ItaniumManglingCanonicalizer.h:43
llvm::ms_demangle::NodeKind
NodeKind
Definition: MicrosoftDemangleNodes.h:226
llvm::ItaniumManglingCanonicalizer::canonicalize
Key canonicalize(StringRef Mangling)
Form a canonical key for the specified mangling.
Definition: ItaniumManglingCanonicalizer.cpp:315
N
#define N
P
#define P(N)
llvm::ItaniumManglingCanonicalizer::addEquivalence
EquivalenceError addEquivalence(FragmentKind Kind, StringRef First, StringRef Second)
Add an equivalence between First and Second.
Definition: ItaniumManglingCanonicalizer.cpp:220
llvm::StringRef::data
const LLVM_NODISCARD char * data() const
data - Get a pointer to the start of the string (which may not be null terminated).
Definition: StringRef.h:149
llvm::AMDGPU::HSAMD::Kernel::Key::Args
constexpr char Args[]
Key for Kernel::Metadata::mArgs.
Definition: AMDGPUMetadata.h:389
llvm::StringRef::size
LLVM_NODISCARD size_t size() const
size - Get the string size.
Definition: StringRef.h:157
llvm::ItaniumManglingCanonicalizer::lookup
Key lookup(StringRef Mangling)
Find a canonical key for the specified mangling, if one has already been formed.
Definition: ItaniumManglingCanonicalizer.cpp:320
llvm::StringRef::begin
iterator begin() const
Definition: StringRef.h:128
llvm::ItaniumManglingCanonicalizer::Key
uintptr_t Key
Definition: ItaniumManglingCanonicalizer.h:72
llvm::Intrinsic::ID
unsigned ID
Definition: TargetTransformInfo.h:38