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<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 // FIXME: Also expand built-in substitutions?
193 
194 using CanonicalizingDemangler =
195  itanium_demangle::ManglingParser<CanonicalizerAllocator>;
196 } // namespace
197 
199  CanonicalizingDemangler Demangler = {nullptr, nullptr};
200 };
201 
204 
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>.
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)
260 
261  Alloc.trackUsesOf(FirstNode);
262  std::tie(SecondNode, SecondIsNew) = Parse(Second);
263  if (!SecondNode)
265 
266  // If they're already equivalent, there's nothing to do.
267  if (FirstNode == SecondNode)
269 
270  if (FirstIsNew && !Alloc.trackedNodeIsUsed())
271  Alloc.addRemapping(FirstNode, SecondNode);
272  else if (SecondIsNew)
273  Alloc.addRemapping(SecondNode, FirstNode);
274  else
276 
278 }
279 
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
296  StringView(Mangling.data(), Mangling.size()));
297  return reinterpret_cast<ItaniumManglingCanonicalizer::Key>(N);
298 }
299 
302  return parseMaybeMangledName(P->Demangler, Mangling, true);
303 }
304 
307  return parseMaybeMangledName(P->Demangler, Mangling, false);
308 }
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:281
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:202
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:199
llvm::StringRef::startswith
bool startswith(StringRef Prefix) const
Check if this string starts with the given Prefix.
Definition: StringRef.h:248
llvm::ARM_PROC::A
@ A
Definition: ARMBaseInfo.h:34
Node::Kind
Kind
Definition: ItaniumDemangle.h:157
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:198
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:123
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:203
llvm::ItaniumManglingCanonicalizer::FragmentKind::Name
@ Name
The mangling fragment is a <name> (or a predefined <substitution>).
Alloc
llvm::StringRef::end
iterator end() const
Definition: StringRef.h:105
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())
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:129
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:301
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:206
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:306
llvm::StringRef::begin
iterator begin() const
Definition: StringRef.h:103
llvm::ItaniumManglingCanonicalizer::Key
uintptr_t Key
Definition: ItaniumManglingCanonicalizer.h:71
llvm::Intrinsic::ID
unsigned ID
Definition: TargetTransformInfo.h:38