LLVM  16.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_v<T> || std::is_enum_v<T>> operator()(T V) {
31  ID.AddInteger((unsigned long long)V);
32  }
33  void operator()(itanium_demangle::NodeArray A) {
34  ID.AddInteger(A.size());
35  for (const Node *N : A)
36  (*this)(N);
37  }
38 };
39 
40 template<typename ...T>
41 void profileCtor(llvm::FoldingSetNodeID &ID, Node::Kind K, T ...V) {
42  FoldingSetNodeIDBuilder Builder = {ID};
43  Builder(K);
44  int VisitInOrder[] = {
45  (Builder(V), 0) ...,
46  0 // Avoid empty array if there are no arguments.
47  };
48  (void)VisitInOrder;
49 }
50 
51 // FIXME: Convert this to a generic lambda when possible.
52 template<typename NodeT> struct ProfileSpecificNode {
54  template<typename ...T> void operator()(T ...V) {
55  profileCtor(ID, NodeKind<NodeT>::Kind, V...);
56  }
57 };
58 
59 struct ProfileNode {
61  template<typename NodeT> void operator()(const NodeT *N) {
62  N->match(ProfileSpecificNode<NodeT>{ID});
63  }
64 };
65 
66 template<> void ProfileNode::operator()(const ForwardTemplateReference *N) {
67  llvm_unreachable("should never canonicalize a ForwardTemplateReference");
68 }
69 
70 void profileNode(llvm::FoldingSetNodeID &ID, const Node *N) {
71  N->visit(ProfileNode{ID});
72 }
73 
74 class FoldingNodeAllocator {
75  class alignas(alignof(Node *)) NodeHeader : public llvm::FoldingSetNode {
76  public:
77  // 'Node' in this context names the injected-class-name of the base class.
78  itanium_demangle::Node *getNode() {
79  return reinterpret_cast<itanium_demangle::Node *>(this + 1);
80  }
81  void Profile(llvm::FoldingSetNodeID &ID) { profileNode(ID, getNode()); }
82  };
83 
84  BumpPtrAllocator RawAlloc;
86 
87 public:
88  void reset() {}
89 
90  template <typename T, typename... Args>
91  std::pair<Node *, bool> getOrCreateNode(bool CreateNewNodes, Args &&... As) {
92  // FIXME: Don't canonicalize forward template references for now, because
93  // they contain state (the resolved template node) that's not known at their
94  // point of creation.
95  if (std::is_same<T, ForwardTemplateReference>::value) {
96  // Note that we don't use if-constexpr here and so we must still write
97  // this code in a generic form.
98  return {new (RawAlloc.Allocate(sizeof(T), alignof(T)))
99  T(std::forward<Args>(As)...),
100  true};
101  }
102 
104  profileCtor(ID, NodeKind<T>::Kind, As...);
105 
106  void *InsertPos;
107  if (NodeHeader *Existing = Nodes.FindNodeOrInsertPos(ID, InsertPos))
108  return {static_cast<T*>(Existing->getNode()), false};
109 
110  if (!CreateNewNodes)
111  return {nullptr, true};
112 
113  static_assert(alignof(T) <= alignof(NodeHeader),
114  "underaligned node header for specific node kind");
115  void *Storage =
116  RawAlloc.Allocate(sizeof(NodeHeader) + sizeof(T), alignof(NodeHeader));
117  NodeHeader *New = new (Storage) NodeHeader;
118  T *Result = new (New->getNode()) T(std::forward<Args>(As)...);
119  Nodes.InsertNode(New, InsertPos);
120  return {Result, true};
121  }
122 
123  template<typename T, typename... Args>
124  Node *makeNode(Args &&...As) {
125  return getOrCreateNode<T>(true, std::forward<Args>(As)...).first;
126  }
127 
128  void *allocateNodeArray(size_t sz) {
129  return RawAlloc.Allocate(sizeof(Node *) * sz, alignof(Node *));
130  }
131 };
132 
133 class CanonicalizerAllocator : public FoldingNodeAllocator {
134  Node *MostRecentlyCreated = nullptr;
135  Node *TrackedNode = nullptr;
136  bool TrackedNodeIsUsed = false;
137  bool CreateNewNodes = true;
139 
140  template<typename T, typename ...Args> Node *makeNodeSimple(Args &&...As) {
141  std::pair<Node *, bool> Result =
142  getOrCreateNode<T>(CreateNewNodes, std::forward<Args>(As)...);
143  if (Result.second) {
144  // Node is new. Make a note of that.
145  MostRecentlyCreated = Result.first;
146  } else if (Result.first) {
147  // Node is pre-existing; check if it's in our remapping table.
148  if (auto *N = Remappings.lookup(Result.first)) {
149  Result.first = N;
150  assert(Remappings.find(Result.first) == Remappings.end() &&
151  "should never need multiple remap steps");
152  }
153  if (Result.first == TrackedNode)
154  TrackedNodeIsUsed = true;
155  }
156  return Result.first;
157  }
158 
159  /// Helper to allow makeNode to be partially-specialized on T.
160  template<typename T> struct MakeNodeImpl {
161  CanonicalizerAllocator &Self;
162  template<typename ...Args> Node *make(Args &&...As) {
163  return Self.makeNodeSimple<T>(std::forward<Args>(As)...);
164  }
165  };
166 
167 public:
168  template<typename T, typename ...Args> Node *makeNode(Args &&...As) {
169  return MakeNodeImpl<T>{*this}.make(std::forward<Args>(As)...);
170  }
171 
172  void reset() { MostRecentlyCreated = nullptr; }
173 
174  void setCreateNewNodes(bool CNN) { CreateNewNodes = CNN; }
175 
176  void addRemapping(Node *A, Node *B) {
177  // Note, we don't need to check whether B is also remapped, because if it
178  // was we would have already remapped it when building it.
179  Remappings.insert(std::make_pair(A, B));
180  }
181 
182  bool isMostRecentlyCreated(Node *N) const { return MostRecentlyCreated == N; }
183 
184  void trackUsesOf(Node *N) {
185  TrackedNode = N;
186  TrackedNodeIsUsed = false;
187  }
188  bool trackedNodeIsUsed() const { return TrackedNodeIsUsed; }
189 };
190 
191 // FIXME: Also expand built-in substitutions?
192 
193 using CanonicalizingDemangler =
194  itanium_demangle::ManglingParser<CanonicalizerAllocator>;
195 } // namespace
196 
198  CanonicalizingDemangler Demangler = {nullptr, nullptr};
199 };
200 
203 
206  StringRef Second) {
207  auto &Alloc = P->Demangler.ASTAllocator;
208  Alloc.setCreateNewNodes(true);
209 
210  auto Parse = [&](StringRef Str) {
211  P->Demangler.reset(Str.begin(), Str.end());
212  Node *N = nullptr;
213  switch (Kind) {
214  // A <name>, with minor extensions to allow arbitrary namespace and
215  // template names that can't easily be written as <name>s.
216  case FragmentKind::Name:
217  // Very special case: allow "St" as a shorthand for "3std". It's not
218  // valid as a <name> mangling, but is nonetheless the most natural
219  // way to name the 'std' namespace.
220  if (Str.size() == 2 && P->Demangler.consumeIf("St"))
221  N = P->Demangler.make<itanium_demangle::NameType>("std");
222  // We permit substitutions to name templates without their template
223  // arguments. This mostly just falls out, as almost all template names
224  // are valid as <name>s, but we also want to parse <substitution>s as
225  // <name>s, even though they're not.
226  else if (Str.startswith("S"))
227  // Parse the substitution and optional following template arguments.
228  N = P->Demangler.parseType();
229  else
230  N = P->Demangler.parseName();
231  break;
232 
233  // A <type>.
234  case FragmentKind::Type:
235  N = P->Demangler.parseType();
236  break;
237 
238  // An <encoding>.
240  N = P->Demangler.parseEncoding();
241  break;
242  }
243 
244  // If we have trailing junk, the mangling is invalid.
245  if (P->Demangler.numLeft() != 0)
246  N = nullptr;
247 
248  // If any node was created after N, then we cannot safely remap it because
249  // it might already be in use by another node.
250  return std::make_pair(N, Alloc.isMostRecentlyCreated(N));
251  };
252 
253  Node *FirstNode, *SecondNode;
254  bool FirstIsNew, SecondIsNew;
255 
256  std::tie(FirstNode, FirstIsNew) = Parse(First);
257  if (!FirstNode)
259 
260  Alloc.trackUsesOf(FirstNode);
261  std::tie(SecondNode, SecondIsNew) = Parse(Second);
262  if (!SecondNode)
264 
265  // If they're already equivalent, there's nothing to do.
266  if (FirstNode == SecondNode)
268 
269  if (FirstIsNew && !Alloc.trackedNodeIsUsed())
270  Alloc.addRemapping(FirstNode, SecondNode);
271  else if (SecondIsNew)
272  Alloc.addRemapping(SecondNode, FirstNode);
273  else
275 
277 }
278 
280 parseMaybeMangledName(CanonicalizingDemangler &Demangler, StringRef Mangling,
281  bool CreateNewNodes) {
282  Demangler.ASTAllocator.setCreateNewNodes(CreateNewNodes);
283  Demangler.reset(Mangling.begin(), Mangling.end());
284  // Attempt demangling only for names that look like C++ mangled names.
285  // Otherwise, treat them as extern "C" names. We permit the latter to
286  // be remapped by (eg)
287  // encoding 6memcpy 7memmove
288  // consistent with how they are encoded as local-names inside a C++ mangling.
289  Node *N;
290  if (Mangling.startswith("_Z") || Mangling.startswith("__Z") ||
291  Mangling.startswith("___Z") || Mangling.startswith("____Z"))
292  N = Demangler.parse();
293  else
295  StringView(Mangling.data(), Mangling.size()));
296  return reinterpret_cast<ItaniumManglingCanonicalizer::Key>(N);
297 }
298 
301  return parseMaybeMangledName(P->Demangler, Mangling, true);
302 }
303 
306  return parseMaybeMangledName(P->Demangler, Mangling, false);
307 }
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
llvm::wasm::NameType
NameType
Definition: Wasm.h:222
llvm::ItaniumManglingCanonicalizer::FragmentKind::Type
@ Type
The mangling fragment is a <type>.
T
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:280
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:497
Allocator.h
llvm::SmallDenseMap
Definition: DenseMap.h:880
llvm::ItaniumManglingCanonicalizer::FragmentKind
FragmentKind
Definition: ItaniumManglingCanonicalizer.h:57
llvm::FoldingSetImpl< FoldingSet< T >, T >::FindNodeOrInsertPos
T * FindNodeOrInsertPos(const FoldingSetNodeID &ID, void *&InsertPos)
FindNodeOrInsertPos - Look up the node specified by ID.
Definition: FoldingSet.h:489
DenseMap.h
llvm::ItaniumManglingCanonicalizer::ItaniumManglingCanonicalizer
ItaniumManglingCanonicalizer()
Definition: ItaniumManglingCanonicalizer.cpp:201
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:366
llvm::ItaniumManglingCanonicalizer::Impl::Demangler
CanonicalizingDemangler Demangler
Definition: ItaniumManglingCanonicalizer.cpp:198
llvm::StringRef::startswith
bool startswith(StringRef Prefix) const
Definition: StringRef.h:260
llvm::ARM_PROC::A
@ A
Definition: ARMBaseInfo.h:34
Node::Kind
Kind
Definition: ItaniumDemangle.h:158
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:197
llvm::StringRef::data
const char * data() const
data - Get a pointer to the start of the string (which may not be null terminated).
Definition: StringRef.h:131
llvm::ilist_detail::make
T & make()
llvm::ItaniumManglingCanonicalizer::EquivalenceError::Success
@ Success
llvm::lltok::Kind
Kind
Definition: LLToken.h:18
llvm::CallingConv::ID
unsigned ID
LLVM IR allows to use arbitrary numbers as calling convention identifiers.
Definition: CallingConv.h:24
llvm::ItaniumManglingCanonicalizer::~ItaniumManglingCanonicalizer
~ItaniumManglingCanonicalizer()
Definition: ItaniumManglingCanonicalizer.cpp:202
llvm::ItaniumManglingCanonicalizer::FragmentKind::Name
@ Name
The mangling fragment is a <name> (or a predefined <substitution>).
llvm::StringRef::end
iterator end() const
Definition: StringRef.h:113
llvm::BumpPtrAllocatorImpl
Allocate memory in an ever growing pool, as if by bump-pointer.
Definition: Allocator.h:63
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())
llvm::FoldingSetNodeID::AddPointer
void AddPointer(const void *Ptr)
Add* - Add various data types to Bit data.
Definition: FoldingSet.h:330
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:520
llvm::StringRef
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:50
llvm::FoldingSetBase::Node
Node - This class is used to maintain the singly linked bucket list in a folding set.
Definition: FoldingSet.h:136
llvm_unreachable
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
Definition: ErrorHandling.h:143
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:318
Profile
Load MIR Sample Profile
Definition: MIRSampleProfile.cpp:70
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
llvm::StringRef::size
constexpr size_t size() const
size - Get the string size.
Definition: StringRef.h:137
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:84
llvm::BumpPtrAllocatorImpl::Allocate
LLVM_ATTRIBUTE_RETURNS_NONNULL void * Allocate(size_t Size, Align Alignment)
Allocate space at the specified alignment.
Definition: Allocator.h:148
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:42
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:300
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:205
llvm::AMDGPU::HSAMD::Kernel::Key::Args
constexpr char Args[]
Key for Kernel::Metadata::mArgs.
Definition: AMDGPUMetadata.h:394
llvm::ItaniumManglingCanonicalizer::lookup
Key lookup(StringRef Mangling)
Find a canonical key for the specified mangling, if one has already been formed.
Definition: ItaniumManglingCanonicalizer.cpp:305
llvm::StringRef::begin
iterator begin() const
Definition: StringRef.h:111
llvm::ItaniumManglingCanonicalizer::Key
uintptr_t Key
Definition: ItaniumManglingCanonicalizer.h:71