llvm/lib/ProfileData/ItaniumManglingCanonicalizer.cpp

   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/ProfileData/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
  21 namespace {
  22 struct FoldingSetNodeIDBuilder {
  23   llvm::FoldingSetNodeID &ID;
  24   void operator()(const Node *P) { ID.AddPointer(P); }
  25   void operator()(std::string_view Str) {
  26     if (Str.empty())
  27       ID.AddString({});
  28     else
  29       ID.AddString(llvm::StringRef(&*Str.begin(), Str.size()));
  30   }
  31   template <typename T>
  32   std::enable_if_t<std::is_integral_v<T> || std::is_enum_v<T>> operator()(T V) {
  33     ID.AddInteger((unsigned long long)V);
  34   }
  35   void operator()(itanium_demangle::NodeArray A) {
  36     ID.AddInteger(A.size());
  37     for (const Node *N : A)
  38       (*this)(N);
  39   }
  40 };
  41
  42 template<typename ...T>
  43 void profileCtor(llvm::FoldingSetNodeID &ID, Node::Kind K, T ...V) {
  44   FoldingSetNodeIDBuilder Builder = {ID};
  45   Builder(K);
  46   int VisitInOrder[] = {
  47     (Builder(V), 0) ...,
  48     0 // Avoid empty array if there are no arguments.
  49   };
  50   (void)VisitInOrder;
  51 }
  52
  53 // FIXME: Convert this to a generic lambda when possible.
  54 template<typename NodeT> struct ProfileSpecificNode {
  55   FoldingSetNodeID &ID;
  56   template<typename ...T> void operator()(T ...V) {
  57     profileCtor(ID, NodeKind<NodeT>::Kind, V...);
  58   }
  59 };
  60
  61 struct ProfileNode {
  62   FoldingSetNodeID &ID;
  63   template<typename NodeT> void operator()(const NodeT *N) {
  64     N->match(ProfileSpecificNode<NodeT>{ID});
  65   }
  66 };
  67
  68 template<> void ProfileNode::operator()(const ForwardTemplateReference *N) {
  69   llvm_unreachable("should never canonicalize a ForwardTemplateReference");
  70 }
  71
  72 void profileNode(llvm::FoldingSetNodeID &ID, const Node *N) {
  73   N->visit(ProfileNode{ID});
  74 }
  75
  76 class FoldingNodeAllocator {
  77   class alignas(alignof(Node *)) NodeHeader : public llvm::FoldingSetNode {
  78   public:
  79     // 'Node' in this context names the injected-class-name of the base class.
  80     itanium_demangle::Node *getNode() {
  81       return reinterpret_cast<itanium_demangle::Node *>(this + 1);
  82     }
  83     void Profile(llvm::FoldingSetNodeID &ID) { profileNode(ID, getNode()); }
  84   };
  85
  86   BumpPtrAllocator RawAlloc;
  87   llvm::FoldingSet<NodeHeader> Nodes;
  88
  89 public:
  90   void reset() {}
  91
  92   template <typename T, typename... Args>
  93   std::pair<Node *, bool> getOrCreateNode(bool CreateNewNodes, Args &&... As) {
  94     // FIXME: Don't canonicalize forward template references for now, because
  95     // they contain state (the resolved template node) that's not known at their
  96     // point of creation.
  97     if (std::is_same<T, ForwardTemplateReference>::value) {
  98       // Note that we don't use if-constexpr here and so we must still write
  99       // this code in a generic form.
 100       return {new (RawAlloc.Allocate(sizeof(T), alignof(T)))
 101                   T(std::forward<Args>(As)...),
 102               true};
 103     }
 104
 105     llvm::FoldingSetNodeID ID;
 106     profileCtor(ID, NodeKind<T>::Kind, As...);
 107
 108     void *InsertPos;
 109     if (NodeHeader *Existing = Nodes.FindNodeOrInsertPos(ID, InsertPos))
 110       return {static_cast<T*>(Existing->getNode()), false};
 111
 112     if (!CreateNewNodes)
 113       return {nullptr, true};
 114
 115     static_assert(alignof(T) <= alignof(NodeHeader),
 116                   "underaligned node header for specific node kind");
 117     void *Storage =
 118         RawAlloc.Allocate(sizeof(NodeHeader) + sizeof(T), alignof(NodeHeader));
 119     NodeHeader *New = new (Storage) NodeHeader;
 120     T *Result = new (New->getNode()) T(std::forward<Args>(As)...);
 121     Nodes.InsertNode(New, InsertPos);
 122     return {Result, true};
 123   }
 124
 125   template<typename T, typename... Args>
 126   Node *makeNode(Args &&...As) {
 127     return getOrCreateNode<T>(true, std::forward<Args>(As)...).first;
 128   }
 129
 130   void *allocateNodeArray(size_t sz) {
 131     return RawAlloc.Allocate(sizeof(Node *) * sz, alignof(Node *));
 132   }
 133 };
 134
 135 class CanonicalizerAllocator : public FoldingNodeAllocator {
 136   Node *MostRecentlyCreated = nullptr;
 137   Node *TrackedNode = nullptr;
 138   bool TrackedNodeIsUsed = false;
 139   bool CreateNewNodes = true;
 140   llvm::SmallDenseMap<Node*, Node*, 32> Remappings;
 141
 142   template<typename T, typename ...Args> Node *makeNodeSimple(Args &&...As) {
 143     std::pair<Node *, bool> Result =
 144         getOrCreateNode<T>(CreateNewNodes, std::forward<Args>(As)...);
 145     if (Result.second) {
 146       // Node is new. Make a note of that.
 147       MostRecentlyCreated = Result.first;
 148     } else if (Result.first) {
 149       // Node is pre-existing; check if it's in our remapping table.
 150       if (auto *N = Remappings.lookup(Result.first)) {
 151         Result.first = N;
 152         assert(!Remappings.contains(Result.first) &&
 153                "should never need multiple remap steps");
 154       }
 155       if (Result.first == TrackedNode)
 156         TrackedNodeIsUsed = true;
 157     }
 158     return Result.first;
 159   }
 160
 161   /// Helper to allow makeNode to be partially-specialized on T.
 162   template<typename T> struct MakeNodeImpl {
 163     CanonicalizerAllocator &Self;
 164     template<typename ...Args> Node *make(Args &&...As) {
 165       return Self.makeNodeSimple<T>(std::forward<Args>(As)...);
 166     }
 167   };
 168
 169 public:
 170   template<typename T, typename ...Args> Node *makeNode(Args &&...As) {
 171     return MakeNodeImpl<T>{*this}.make(std::forward<Args>(As)...);
 172   }
 173
 174   void reset() { MostRecentlyCreated = nullptr; }
 175
 176   void setCreateNewNodes(bool CNN) { CreateNewNodes = CNN; }
 177
 178   void addRemapping(Node *A, Node *B) {
 179     // Note, we don't need to check whether B is also remapped, because if it
 180     // was we would have already remapped it when building it.
 181     Remappings.insert(std::make_pair(A, B));
 182   }
 183
 184   bool isMostRecentlyCreated(Node *N) const { return MostRecentlyCreated == N; }
 185
 186   void trackUsesOf(Node *N) {
 187     TrackedNode = N;
 188     TrackedNodeIsUsed = false;
 189   }
 190   bool trackedNodeIsUsed() const { return TrackedNodeIsUsed; }
 191 };
 192
 193 // FIXME: Also expand built-in substitutions?
 194
 195 using CanonicalizingDemangler =
 196     itanium_demangle::ManglingParser<CanonicalizerAllocator>;
 197 } // namespace
 198
 199 struct ItaniumManglingCanonicalizer::Impl {
 200   CanonicalizingDemangler Demangler = {nullptr, nullptr};
 201 };
 202
 203 ItaniumManglingCanonicalizer::ItaniumManglingCanonicalizer() : P(new Impl) {}
 204 ItaniumManglingCanonicalizer::~ItaniumManglingCanonicalizer() { delete P; }
 205
 206 ItaniumManglingCanonicalizer::EquivalenceError
 207 ItaniumManglingCanonicalizer::addEquivalence(FragmentKind Kind, StringRef First,
 208                                              StringRef Second) {
 209   auto &Alloc = P->Demangler.ASTAllocator;
 210   Alloc.setCreateNewNodes(true);
 211
 212   auto Parse = [&](StringRef Str) {
 213     P->Demangler.reset(Str.begin(), Str.end());
 214     Node *N = nullptr;
 215     switch (Kind) {
 216       // A <name>, with minor extensions to allow arbitrary namespace and
 217       // template names that can't easily be written as <name>s.
 218     case FragmentKind::Name:
 219       // Very special case: allow "St" as a shorthand for "3std". It's not
 220       // valid as a <name> mangling, but is nonetheless the most natural
 221       // way to name the 'std' namespace.
 222       if (Str.size() == 2 && P->Demangler.consumeIf("St"))
 223         N = P->Demangler.make<itanium_demangle::NameType>("std");
 224       // We permit substitutions to name templates without their template
 225       // arguments. This mostly just falls out, as almost all template names
 226       // are valid as <name>s, but we also want to parse <substitution>s as
 227       // <name>s, even though they're not.
 228       else if (Str.startswith("S"))
 229         // Parse the substitution and optional following template arguments.
 230         N = P->Demangler.parseType();
 231       else
 232         N = P->Demangler.parseName();
 233       break;
 234
 235       // A <type>.
 236     case FragmentKind::Type:
 237       N = P->Demangler.parseType();
 238       break;
 239
 240       // An <encoding>.
 241     case FragmentKind::Encoding:
 242       N = P->Demangler.parseEncoding();
 243       break;
 244     }
 245
 246     // If we have trailing junk, the mangling is invalid.
 247     if (P->Demangler.numLeft() != 0)
 248       N = nullptr;
 249
 250     // If any node was created after N, then we cannot safely remap it because
 251     // it might already be in use by another node.
 252     return std::make_pair(N, Alloc.isMostRecentlyCreated(N));
 253   };
 254
 255   Node *FirstNode, *SecondNode;
 256   bool FirstIsNew, SecondIsNew;
 257
 258   std::tie(FirstNode, FirstIsNew) = Parse(First);
 259   if (!FirstNode)
 260     return EquivalenceError::InvalidFirstMangling;
 261
 262   Alloc.trackUsesOf(FirstNode);
 263   std::tie(SecondNode, SecondIsNew) = Parse(Second);
 264   if (!SecondNode)
 265     return EquivalenceError::InvalidSecondMangling;
 266
 267   // If they're already equivalent, there's nothing to do.
 268   if (FirstNode == SecondNode)
 269     return EquivalenceError::Success;
 270
 271   if (FirstIsNew && !Alloc.trackedNodeIsUsed())
 272     Alloc.addRemapping(FirstNode, SecondNode);
 273   else if (SecondIsNew)
 274     Alloc.addRemapping(SecondNode, FirstNode);
 275   else
 276     return EquivalenceError::ManglingAlreadyUsed;
 277
 278   return EquivalenceError::Success;
 279 }
 280
 281 static ItaniumManglingCanonicalizer::Key
 282 parseMaybeMangledName(CanonicalizingDemangler &Demangler, StringRef Mangling,
 283                       bool CreateNewNodes) {
 284   Demangler.ASTAllocator.setCreateNewNodes(CreateNewNodes);
 285   Demangler.reset(Mangling.begin(), Mangling.end());
 286   // Attempt demangling only for names that look like C++ mangled names.
 287   // Otherwise, treat them as extern "C" names. We permit the latter to
 288   // be remapped by (eg)
 289   //   encoding 6memcpy 7memmove
 290   // consistent with how they are encoded as local-names inside a C++ mangling.
 291   Node *N;
 292   if (Mangling.startswith("_Z") || Mangling.startswith("__Z") ||
 293       Mangling.startswith("___Z") || Mangling.startswith("____Z"))
 294     N = Demangler.parse();
 295   else
 296     N = Demangler.make<itanium_demangle::NameType>(
 297         std::string_view(Mangling.data(), Mangling.size()));
 298   return reinterpret_cast<ItaniumManglingCanonicalizer::Key>(N);
 299 }
 300
 301 ItaniumManglingCanonicalizer::Key
 302 ItaniumManglingCanonicalizer::canonicalize(StringRef Mangling) {
 303   return parseMaybeMangledName(P->Demangler, Mangling, true);
 304 }
 305
 306 ItaniumManglingCanonicalizer::Key
 307 ItaniumManglingCanonicalizer::lookup(StringRef Mangling) {
 308   return parseMaybeMangledName(P->Demangler, Mangling, false);
 309 }