[YAML][NFC] Use BumpPtrAllocator instead of unique_ptrs

[Amir]

Summary

Avoid both memory leaks and expensive dynamic allocations by using
SpecificBumpPtrAllocator for HNode types. It's expected they're not deallocated
until the Input class is destroyed, so deallocating all at once works well in
this case.

Reduces YAML profile pre-processing time in BOLT from

11.2067 (  3.2%)   1.6487 (  7.3%)  12.8554 (  3.5%)  12.8635 (  5.6%)  pre-process profile data

to

10.6613 (  3.1%)   1.6489 (  6.7%)  12.3102 (  3.3%)  12.3134 (  5.3%)  pre-process profile data

[Amir]

Use SpecificBumpPtrAllocators

[Amir]

Remove Input destructor override

[dblaikie]

What are the codepaths that currently destroy these nodes? Is there any mutability in the data structure, or is it only "build build build, use, then destroy"? If it's the latter, then yeah, arena allocation seems fine.

It's possible to match unique_ptr behavior and also free memory in setCurrentDocument.

Ah, so perhaps this answers my question - the deallocation is done at TopNode = ? *nod* Wuold probably be good to match the behavior there, to avoid continuous growth.

[Amir]

In D155006#4573881, @dblaikie wrote:

What are the codepaths that currently destroy these nodes?

From what I can tell there are just two: destructor of Input class and reassignment of TopNode in setCurrentDocument.

Is there any mutability in the data structure, or is it only "build build build, use, then destroy"? If it's the latter, then yeah, arena allocation seems fine.

I didn't observe any mutability, it's the latter.

It's possible to match unique_ptr behavior and also free memory in setCurrentDocument.

Ah, so perhaps this answers my question - the deallocation is done at TopNode = ? *nod* Wuold probably be good to match the behavior there, to avoid continuous growth.

Will do.

[Amir]

Call DestroyAll from setCurrentDocument

[dblaikie]

SGTM

[Amir]

In D155006#4574654, @dblaikie wrote:

SGTM

Thank you!

[Amir]

clang-format

llvm/include/llvm/Support/YAMLTraits.h

private:
   void scalarString(StringRef &, QuotingType) override;
   void blockScalarString(StringRef &) override;
   void scalarTag(std::string &) override;
   NodeKind getNodeKind() override;
   void setError(const Twine &message) override;
   bool canElideEmptySequence() override;
 
   class HNode {
-    virtual void anchor();
-
   public:
     HNode(Node *n) : _node(n) { }
-    virtual ~HNode() = default;
 
     static bool classof(const HNode *) { return true; }
 
     Node *_node;
+
+    void *operator new(size_t Size, BumpPtrAllocator &Alloc,
+                       size_t Alignment = 16) noexcept {
+      return Alloc.Allocate(Size, Alignment);
+    }
+
+    void operator delete(void *Ptr, BumpPtrAllocator &Alloc,
+                         size_t Size) noexcept {
+      Alloc.Deallocate(Ptr, Size, 0);
+    }
+
+    void operator delete(void *) noexcept = delete;
   };
 
   class EmptyHNode : public HNode {
-    void anchor() override;
-
   public:
     EmptyHNode(Node *n) : HNode(n) { }
 
     static bool classof(const HNode *n) { return NullNode::classof(n->_node); }
 
     static bool classof(const EmptyHNode *) { return true; }
   };
 
   class ScalarHNode : public HNode {
-    void anchor() override;
-
   public:
     ScalarHNode(Node *n, StringRef s) : HNode(n), _value(s) { }
 
     StringRef value() const { return _value; }
 
     static bool classof(const HNode *n) {
       return ScalarNode::classof(n->_node) ||
              BlockScalarNode::classof(n->_node);
     }
 
     static bool classof(const ScalarHNode *) { return true; }
 
   protected:
     StringRef _value;
   };
 
   class MapHNode : public HNode {
-    void anchor() override;
-
   public:
     MapHNode(Node *n) : HNode(n) { }
 
     static bool classof(const HNode *n) {
       return MappingNode::classof(n->_node);
     }
 
     static bool classof(const MapHNode *) { return true; }
 
-    using NameToNodeAndLoc =
-        StringMap<std::pair<std::unique_ptr<HNode>, SMRange>>;
+    using NameToNodeAndLoc = StringMap<std::pair<HNode *, SMRange>>;
 
     NameToNodeAndLoc Mapping;
     SmallVector<std::string, 6> ValidKeys;
   };
 
   class SequenceHNode : public HNode {
-    void anchor() override;
-
   public:
     SequenceHNode(Node *n) : HNode(n) { }
 
     static bool classof(const HNode *n) {
       return SequenceNode::classof(n->_node);
     }
 
     static bool classof(const SequenceHNode *) { return true; }
 
-    std::vector<std::unique_ptr<HNode>> Entries;
+    std::vector<HNode *> Entries;
   };
 
-  std::unique_ptr<Input::HNode> createHNodes(Node *node);
+  Input::HNode *createHNodes(Node *node);
   void setError(HNode *hnode, const Twine &message);
   void setError(Node *node, const Twine &message);
   void setError(const SMRange &Range, const Twine &message);
 
   void reportWarning(HNode *hnode, const Twine &message);
   void reportWarning(Node *hnode, const Twine &message);
   void reportWarning(const SMRange &Range, const Twine &message);
 
 public:
   // These are only used by operator>>. They could be private
   // if those templated things could be made friends.
   bool setCurrentDocument();
   bool nextDocument();
 
   /// Returns the current node that's being parsed by the YAML Parser.
   const Node *getCurrentNode() const;
 
   void setAllowUnknownKeys(bool Allow) override;
 
 private:
   SourceMgr                           SrcMgr; // must be before Strm
   std::unique_ptr<llvm::yaml::Stream> Strm;
-  std::unique_ptr<HNode>              TopNode;
+  HNode *TopNode = nullptr;
   std::error_code                     EC;
   BumpPtrAllocator                    StringAllocator;
+  BumpPtrAllocator HNodeAllocator;
   document_iterator                   DocIterator;
   llvm::BitVector                     BitValuesUsed;
   HNode *CurrentNode = nullptr;
   bool                                ScalarMatchFound = false;
   bool AllowUnknownKeys = false;
 };
 
 ///

llvm/lib/Support/YAMLTraits.cpp

if (DiagHandler)
     SrcMgr.setDiagHandler(DiagHandler, DiagHandlerCtxt);
   DocIterator = Strm->begin();
 }
 
 Input::~Input() = default;
 
 std::error_code Input::error() { return EC; }
 
-// Pin the vtables to this file.
-void Input::HNode::anchor() {}
-void Input::EmptyHNode::anchor() {}
-void Input::ScalarHNode::anchor() {}
-void Input::MapHNode::anchor() {}
-void Input::SequenceHNode::anchor() {}
-
 bool Input::outputting() const {
   return false;
 }
 
 bool Input::setCurrentDocument() {
   if (DocIterator != Strm->end()) {
     Node *N = DocIterator->getRoot();
     if (!N) {
       EC = make_error_code(errc::invalid_argument);
       return false;
     }
 
     if (isa<NullNode>(N)) {
       // Empty files are allowed and ignored
       ++DocIterator;
       return setCurrentDocument();
     }
     TopNode = createHNodes(N);
-    CurrentNode = TopNode.get();
+    CurrentNode = TopNode;
     return true;
   }
   return false;
 }
 
 bool Input::nextDocument() {
   return ++DocIterator != Strm->end();
 }
bool Input::preflightKey(const char *Key, bool Required, bool, bool &UseDefault,
   if (!MN) {
     if (Required || !isa<EmptyHNode>(CurrentNode))
       setError(CurrentNode, "not a mapping");
     else
       UseDefault = true;
     return false;
   }
   MN->ValidKeys.push_back(Key);
-  HNode *Value = MN->Mapping[Key].first.get();
+  HNode *Value = MN->Mapping[Key].first;
   if (!Value) {
     if (Required)
       setError(CurrentNode, Twine("missing required key '") + Key + "'");
     else
       UseDefault = true;
     return false;
   }
   SaveInfo = CurrentNode;

 void Input::endSequence() {
 }
 
 bool Input::preflightElement(unsigned Index, void *&SaveInfo) {
   if (EC)
     return false;
   if (SequenceHNode *SQ = dyn_cast<SequenceHNode>(CurrentNode)) {
     SaveInfo = CurrentNode;
-    CurrentNode = SQ->Entries[Index].get();
+    CurrentNode = SQ->Entries[Index];
     return true;
   }
   return false;
 }
 
 void Input::postflightElement(void *SaveInfo) {
   CurrentNode = reinterpret_cast<HNode *>(SaveInfo);
 }
 
 unsigned Input::beginFlowSequence() { return beginSequence(); }
 
 bool Input::preflightFlowElement(unsigned index, void *&SaveInfo) {
   if (EC)
     return false;
   if (SequenceHNode *SQ = dyn_cast<SequenceHNode>(CurrentNode)) {
     SaveInfo = CurrentNode;
-    CurrentNode = SQ->Entries[index].get();
+    CurrentNode = SQ->Entries[index];
     return true;
   }
   return false;
 }
 
 void Input::postflightFlowElement(void *SaveInfo) {
   CurrentNode = reinterpret_cast<HNode *>(SaveInfo);
 }

 }
 
 bool Input::bitSetMatch(const char *Str, bool) {
   if (EC)
     return false;
   if (SequenceHNode *SQ = dyn_cast<SequenceHNode>(CurrentNode)) {
     unsigned Index = 0;
     for (auto &N : SQ->Entries) {
-      if (ScalarHNode *SN = dyn_cast<ScalarHNode>(N.get())) {
+      if (ScalarHNode *SN = dyn_cast<ScalarHNode>(N)) {
         if (SN->value().equals(Str)) {
           BitValuesUsed[Index] = true;
           return true;
         }
       } else {
         setError(CurrentNode, "unexpected scalar in sequence of bit values");
       }
       ++Index;
     }
   } else {
     setError(CurrentNode, "expected sequence of bit values");
   }
   return false;
 }
 
 void Input::endBitSetScalar() {
   if (EC)
     return;
   if (SequenceHNode *SQ = dyn_cast<SequenceHNode>(CurrentNode)) {
     assert(BitValuesUsed.size() == SQ->Entries.size());
     for (unsigned i = 0; i < SQ->Entries.size(); ++i) {
       if (!BitValuesUsed[i]) {
-        setError(SQ->Entries[i].get(), "unknown bit value");
+        setError(SQ->Entries[i], "unknown bit value");
         return;
       }
     }
   }
 }
 
 void Input::scalarString(StringRef &S, QuotingType) {
   if (ScalarHNode *SN = dyn_cast<ScalarHNode>(CurrentNode)) {

 void Input::reportWarning(Node *node, const Twine &message) {
   Strm->printError(node, message, SourceMgr::DK_Warning);
 }
 
 void Input::reportWarning(const SMRange &range, const Twine &message) {
   Strm->printError(range, message, SourceMgr::DK_Warning);
 }
 
-std::unique_ptr<Input::HNode> Input::createHNodes(Node *N) {
+Input::HNode *Input::createHNodes(Node *N) {
   SmallString<128> StringStorage;
   switch (N->getType()) {
   case Node::NK_Scalar: {
     ScalarNode *SN = dyn_cast<ScalarNode>(N);
     StringRef KeyStr = SN->getValue(StringStorage);
     if (!StringStorage.empty()) {
       // Copy string to permanent storage
       KeyStr = StringStorage.str().copy(StringAllocator);
     }
-    return std::make_unique<ScalarHNode>(N, KeyStr);
+    return new (HNodeAllocator) ScalarHNode(N, KeyStr);
   }
   case Node::NK_BlockScalar: {
     BlockScalarNode *BSN = dyn_cast<BlockScalarNode>(N);
     StringRef ValueCopy = BSN->getValue().copy(StringAllocator);
-    return std::make_unique<ScalarHNode>(N, ValueCopy);
+    return new (HNodeAllocator) ScalarHNode(N, ValueCopy);
   }
   case Node::NK_Sequence: {
     SequenceNode *SQ = dyn_cast<SequenceNode>(N);
-    auto SQHNode = std::make_unique<SequenceHNode>(N);
+    auto SQHNode = new (HNodeAllocator) SequenceHNode(N);
     for (Node &SN : *SQ) {
       auto Entry = createHNodes(&SN);
       if (EC)
         break;
-      SQHNode->Entries.push_back(std::move(Entry));
+      SQHNode->Entries.push_back(Entry);
     }
-    return std::move(SQHNode);
+    return SQHNode;
   }
   case Node::NK_Mapping: {
     MappingNode *Map = dyn_cast<MappingNode>(N);
-    auto mapHNode = std::make_unique<MapHNode>(N);
+    auto mapHNode = new (HNodeAllocator) MapHNode(N);
     for (KeyValueNode &KVN : *Map) {
       Node *KeyNode = KVN.getKey();
       ScalarNode *Key = dyn_cast_or_null<ScalarNode>(KeyNode);
       Node *Value = KVN.getValue();
       if (!Key || !Value) {
         if (!Key)
           setError(KeyNode, "Map key must be a scalar");
         if (!Value)
for (KeyValueNode &KVN : *Map) {
       if (mapHNode->Mapping.count(KeyStr))
         // From YAML spec: "The content of a mapping node is an unordered set of
         // key/value node pairs, with the restriction that each of the keys is
         // unique."
         setError(KeyNode, Twine("duplicated mapping key '") + KeyStr + "'");
       auto ValueHNode = createHNodes(Value);
       if (EC)
         break;
-      mapHNode->Mapping[KeyStr] =
-          std::make_pair(std::move(ValueHNode), KeyNode->getSourceRange());
+      mapHNode->Mapping[KeyStr] = {ValueHNode, KeyNode->getSourceRange()};
     }
     return std::move(mapHNode);
   }
   case Node::NK_Null:
-    return std::make_unique<EmptyHNode>(N);
+    return new (HNodeAllocator) EmptyHNode(N);
   default:
     setError(N, "unknown node kind");
     return nullptr;
   }
 }
 
 void Input::setError(const Twine &Message) {
   setError(CurrentNode, Message);