[Metadata] Add a resize capability to MDNodes and add a push_back interface to MDNodes.

[wolfgangp]

Summary

See the discussion in D124548.

This patch depends on D125994 (the copy/move constructors and assignment ops for MDOperand).
Some notes:

• I have a slight preference for the term "resizable" over "dynamic", but I'd be happy to change it if you feel strongly about it.
• I only introduced a push_back() instead of append() for now. Could be introduced incrementally.
• Don't know if more tests are needed at a deeper level, but it seems all of the code is exercised except perhaps some assertions that are difficult to enfore (e.g. alignment).
• @dexonsmith You mentioned that phabricator reviews can be linked. I'm having trouble finding out how.

[wolfgangp]

You mentioned that phabricator reviews can be linked. I'm having trouble finding out how.

NM, found it.

[wolfgangp]

Use the default constructor for LargeStorageVector followed by a resize instead of the constructor using a numOps parameter. Doing the latter requires the copy constructor for MDOperand.

[dexonsmith]

llvm/include/llvm/IR/Metadata.h

1222

It’d be good to have a header comment explaining when it’s legal to resize.

llvm/lib/IR/Metadata.cpp

579

Nit: you can reduce nesting by returning early here.

590

Nit: you can reduce nesting by returning early inside the if and skipping the else.

llvm/unittests/IR/MetadataTest.cpp

3663

Is this enough to exceed small size? If not, it’s be good to add one that does.

[wolfgangp]

Addressed review comments.

Added 2 new unit tests. One for an MDNode initially allocated as "large", and a death test for the case of a temporary node that is later uniqued. We want to make sure it is not resizable after it's been uniqued, even though it was originally allocated as resizable.

[wolfgangp]

llvm/unittests/IR/MetadataTest.cpp

3663

The node is allocated with 0 operands, so it gets resized to a large after only 3 push_backs But we were missing a test for a node that is allocated as a large right away. I added a test for it.

[dexonsmith]

LGTM, thanks! I left a couple of nits inline for you to consider.

llvm/include/llvm/IR/Metadata.h

955–970

Nit: I suggest naming these Is{Resizable,Large}.

992–997

Nit: I'm not sure these accessors/mutators carry their weight, given that fields are already public in Header and Header is an implementation detail of MDOperand (no other users). I'd just as soon skip them and access the fields directly.

(If you have a short-term plan for a follow up that makes one of them non-trivial, maybe it'd be worth leaving that one behind, but otherwise...)

998

(Might skip this one too...)

[nikic]

FYI it looks like this change has some negative effect on compile-time (http://llvm-compile-time-tracker.com/compare.php?from=d572fc3b49bd53b7871223b3054b235cf99f6b61&to=e3f6eda8c6ebc567755377911746d4ca2367e649&stat=instructions) and in -g LTO builds on memory usage as well (http://llvm-compile-time-tracker.com/compare.php?from=d572fc3b49bd53b7871223b3054b235cf99f6b61&to=e3f6eda8c6ebc567755377911746d4ca2367e649&stat=max-rss). Is that expected?

[wolfgangp]

In D125998#3565739, @nikic wrote:

FYI it looks like this change has some negative effect on compile-time (http://llvm-compile-time-tracker.com/compare.php?from=d572fc3b49bd53b7871223b3054b235cf99f6b61&to=e3f6eda8c6ebc567755377911746d4ca2367e649&stat=instructions) and in -g LTO builds on memory usage as well (http://llvm-compile-time-tracker.com/compare.php?from=d572fc3b49bd53b7871223b3054b235cf99f6b61&to=e3f6eda8c6ebc567755377911746d4ca2367e649&stat=max-rss). Is that expected?

I am not surprised by the increased memory usage. The change introduces a resize capability to MDNodes, which when used more often in the future, should improve memory usage overall, especially with LTO. I am concerned about the compile time increase, which is a bit more than I expected. I reverted the patch for other reasons, but I'll check into runtime improvements before I reland.

[xbolva00]

This comment was removed by xbolva00.

llvm/include/llvm/IR/Metadata.h

 /// time, if any operand is a temporary node (or an unresolved uniqued node,
 /// which indicates a transitive temporary operand), the node itself will be
 /// unresolved.  As soon as all operands become resolved, it will drop RAUW
 /// support permanently.
 ///
 /// If an unresolved node is part of a cycle, \a resolveCycles() needs
 /// to be called on some member of the cycle once all temporary nodes have been
 /// replaced.
+///
+/// MDNodes can be large or small, as well as resizable or non-resizable.
+/// Large MDNodes' operands are allocated in a separate storage vector,
+/// whereas small MDNodes' operands are co-allocated. Distinct and temporary
+/// MDnodes are resizable, but only MDTuples support this capability.
+///
+/// Clients can add operands to resizable MDNodes using push_back().
 class MDNode : public Metadata {
   friend class ReplaceableMetadataImpl;
   friend class LLVMContextImpl;
   friend class DIArgList;
 
-  /// The header that is coallocated with an MDNode, along with the operands.
-  /// It is located immediately before the main body of the node. The operands
-  /// are in turn located immediately before the header.
+  /// The header that is coallocated with an MDNode along with its "small"
+  /// operands. It is located immediately before the main body of the node.
+  /// The operands are in turn located immediately before the header.
+  /// For resizable MDNodes, the space for the storage vector is also allocated
+  /// immediately before the header, overlapping with the operands.
   struct Header {
-    unsigned NumOperands;
+    bool Resizable : 1;
+    bool Large : 1;
+    size_t SmallSize : 4;
+    size_t SmallNumOps : 4;
+    size_t : sizeof(size_t) * CHAR_BIT - 10;
+
     unsigned NumUnresolved = 0;
+    using LargeStorageVector = SmallVector<MDOperand, 0>;
+
+    static constexpr size_t NumOpsFitInVector =
+        sizeof(LargeStorageVector) / sizeof(MDOperand);
+    static_assert(
+        NumOpsFitInVector * sizeof(MDOperand) == sizeof(LargeStorageVector),
+        "sizeof(LargeStorageVector) must be a multiple of sizeof(MDOperand)");
+
+    static constexpr size_t MaxSmallSize = 15;
 
     static constexpr size_t getOpSize(unsigned NumOps) {
       return sizeof(MDOperand) * NumOps;
     }
-    static constexpr size_t getAllocSize(unsigned NumOps) {
-      return getOpSize(NumOps) + sizeof(Header);
+    /// Returns the number of operands the node has space for based on its
+    /// allocation characteristics.
+    static size_t getSmallSize(size_t NumOps, bool isResizable, bool isLarge) {
+      return isLarge ? NumOpsFitInVector
+                     : std::max(NumOps, NumOpsFitInVector * isResizable);
+    }
+    /// Returns the number of bytes allocated for operands and header.
+    static size_t getAllocSize(StorageType Storage, size_t NumOps) {
+      return getOpSize(
+                 getSmallSize(NumOps, isResizable(Storage), isLarge(NumOps))) +
+             sizeof(Header);
+    }
+
+    /// Only temporary and distinct nodes are resizable.
+    static bool isResizable(StorageType Storage) { return Storage != Uniqued; }
+    static bool isLarge(size_t NumOps) { return NumOps > MaxSmallSize; }
+
+    bool isResizable() const { return Resizable; }
+    bool isLarge() const { return Large; }
+    size_t getSmallSize() const { return SmallSize; }
+    void setSmallSize(size_t NumOps) { SmallSize = NumOps; }
+    size_t getSmallNumOps() const { return SmallNumOps; }
+    void setSmallNumOps(size_t NumOps) { SmallNumOps = NumOps; }
+    size_t getNumOperands() const { return operands().size(); }
+
+    size_t getAllocSize() const {
+      return getOpSize(getSmallSize()) + sizeof(Header);
     }
     void *getAllocation() {
       return reinterpret_cast<char *>(this + 1) -
-             alignTo(getAllocSize(NumOperands), alignof(uint64_t));
+             alignTo(getAllocSize(), alignof(uint64_t));
     }
 
-    explicit Header(unsigned NumOperands);
+    void *getLargePtr() const;
+    void *getSmallPtr();
+
+    LargeStorageVector &getLarge() {
+      assert(isLarge());
+      return *reinterpret_cast<LargeStorageVector *>(getLargePtr());
+    }
+
+    const LargeStorageVector &getLarge() const {
+      assert(isLarge());
+      return *reinterpret_cast<const LargeStorageVector *>(getLargePtr());
+    }
+
+    void resizeSmall(size_t NumOps);
+    void resizeSmallToLarge(size_t NumOps);
+    void resize(size_t NumOps);
+
+    explicit Header(size_t NumOps, StorageType Storage);
     ~Header();
+
     MutableArrayRef<MDOperand> operands() {
-      return makeMutableArrayRef(
-          reinterpret_cast<MDOperand *>(this) - NumOperands, NumOperands);
+      if (isLarge())
+        return getLarge();
+      return makeMutableArrayRef(reinterpret_cast<MDOperand *>(this) -
+                                     getSmallSize(),
+                                 getSmallNumOps());
     }
+
     ArrayRef<MDOperand> operands() const {
-      return makeArrayRef(
-          reinterpret_cast<const MDOperand *>(this) - NumOperands, NumOperands);
+      if (isLarge())
+        return getLarge();
+      return makeArrayRef(reinterpret_cast<const MDOperand *>(this) -
+                              getSmallSize(),
+                          getSmallNumOps());
     }
   };
 
   Header &getHeader() { return *(reinterpret_cast<Header *>(this) - 1); }
 
   const Header &getHeader() const {
     return *(reinterpret_cast<const Header *>(this) - 1);
   }
 
   ContextAndReplaceableUses Context;
 
 protected:
   MDNode(LLVMContext &Context, unsigned ID, StorageType Storage,
          ArrayRef<Metadata *> Ops1, ArrayRef<Metadata *> Ops2 = None);
   ~MDNode() = default;
 
-  void *operator new(size_t Size, unsigned NumOps, StorageType Storage);
+  void *operator new(size_t Size, size_t NumOps, StorageType Storage);
   void operator delete(void *Mem);
 
   /// Required by std, but never called.
   void operator delete(void *, unsigned) {
     llvm_unreachable("Constructor throws?");
   }
 
   /// Required by std, but never called.
protected:
   unsigned getNumUnresolved() const { return getHeader().NumUnresolved; }
 
   void setNumUnresolved(unsigned N) { getHeader().NumUnresolved = N; }
   void storeDistinctInContext();
   template <class T, class StoreT>
   static T *storeImpl(T *N, StorageType Storage, StoreT &Store);
   template <class T> static T *storeImpl(T *N, StorageType Storage);
 
+  void resize(size_t NumOps) {
+    assert(getMetadataID() == MDTupleKind &&
+           "Resizing is not supported for this node kind");
+    getHeader().resize(NumOps);
+  }
+
 private:
   void handleChangedOperand(void *Ref, Metadata *New);
 
   /// Drop RAUW support, if any.
   void dropReplaceableUses();
 
   void resolveAfterOperandChange(Metadata *Old, Metadata *New);
   void decrementUnresolvedOperandCount();
public:
   op_range operands() const { return op_range(op_begin(), op_end()); }
 
   const MDOperand &getOperand(unsigned I) const {
     assert(I < getNumOperands() && "Out of range");
     return getHeader().operands()[I];
   }
 
   /// Return number of MDNode operands.
-  unsigned getNumOperands() const { return getHeader().NumOperands; }
+  unsigned getNumOperands() const { return getHeader().getNumOperands(); }
 
   /// Methods for support type inquiry through isa, cast, and dyn_cast:
   static bool classof(const Metadata *MD) {
     switch (MD->getMetadataID()) {
     default:
       return false;
 #define HANDLE_MDNODE_LEAF(CLASS)                                              \
   case CLASS##Kind:                                                            \
public:
   static TempMDTuple getTemporary(LLVMContext &Context,
                                   ArrayRef<Metadata *> MDs) {
     return TempMDTuple(getImpl(Context, MDs, Temporary));
   }
 
   /// Return a (temporary) clone of this.
   TempMDTuple clone() const { return cloneImpl(); }
 
+  /// Append an element to the tuple. This will resize the node.
+  void push_back(Metadata *MD) {
+    size_t NumOps = getNumOperands();
+    resize(NumOps + 1);
+    setOperand(NumOps, MD);
+  }
+
+  /// Shrink the operands by 1.
+  void pop_back() { resize(getNumOperands() - 1); }
+
   static bool classof(const Metadata *MD) {
     return MD->getMetadataID() == MDTupleKind;
   }
 };
 
 MDTuple *MDNode::get(LLVMContext &Context, ArrayRef<Metadata *> MDs) {
   return MDTuple::get(Context, MDs);
 }

llvm/lib/IR/Metadata.cpp

 // Assert that the MDNode types will not be unaligned by the objects
 // prepended to them.
 #define HANDLE_MDNODE_LEAF(CLASS)                                              \
   static_assert(                                                               \
       alignof(uint64_t) >= alignof(CLASS),                                     \
       "Alignment is insufficient after objects prepended to " #CLASS);
 #include "llvm/IR/Metadata.def"
 
-void *MDNode::operator new(size_t Size, unsigned NumOps,
-                           StorageType /* Storage */) {
+void *MDNode::operator new(size_t Size, size_t NumOps, StorageType Storage) {
   // uint64_t is the most aligned type we need support (ensured by static_assert
   // above)
-  size_t AllocSize = alignTo(Header::getAllocSize(NumOps), alignof(uint64_t));
+  size_t AllocSize =
+      alignTo(Header::getAllocSize(Storage, NumOps), alignof(uint64_t));
   char *Mem = reinterpret_cast<char *>(::operator new(AllocSize + Size));
-  Header *H = new (Mem + AllocSize - sizeof(Header)) Header(NumOps);
+  Header *H = new (Mem + AllocSize - sizeof(Header)) Header(NumOps, Storage);
   return reinterpret_cast<void *>(H + 1);
 }
 
 void MDNode::operator delete(void *N) {
   Header *H = reinterpret_cast<Header *>(N) - 1;
   void *Mem = H->getAllocation();
   H->~Header();
   ::operator delete(Mem);
default:
     llvm_unreachable("Invalid MDNode subclass");
 #define HANDLE_MDNODE_LEAF(CLASS)                                              \
   case CLASS##Kind:                                                            \
     return cast<CLASS>(this)->cloneImpl();
 #include "llvm/IR/Metadata.def"
   }
 }
 
-MDNode::Header::Header(unsigned NumOps) {
-  NumOperands = NumOps;
-  MDOperand *O = reinterpret_cast<MDOperand *>(this);
-  for (MDOperand *E = O - NumOps; O != E; --O)
-    (void)new (O - 1) MDOperand();
+MDNode::Header::Header(size_t NumOps, StorageType Storage) {
+  Large = isLarge(NumOps);
+  Resizable = isResizable(Storage);
+  setSmallSize(getSmallSize(NumOps, Resizable, Large));
+  if (Large) {
+    setSmallNumOps(0);
+    new (getLargePtr()) LargeStorageVector();
+    getLarge().resize(NumOps);
+  } else {
+    setSmallNumOps(NumOps);
+    MDOperand *O = reinterpret_cast<MDOperand *>(this) - getSmallSize();
+    for (MDOperand *E = O + getSmallSize(); O != E;)
+      (void)new (O++) MDOperand();
+  }
 }
 
 MDNode::Header::~Header() {
-  MDOperand *O = reinterpret_cast<MDOperand *>(this) - NumOperands;
-  for (MDOperand *E = O + NumOperands; O != E; ++O)
-    (void)O->~MDOperand();
+  if (Large) {
+    getLarge().~LargeStorageVector();
+  } else {
+    MDOperand *O = reinterpret_cast<MDOperand *>(this);
+    for (MDOperand *E = O - getSmallSize(); O != E; --O)
+      (void)(O - 1)->~MDOperand();
+  }
+}
+
+void *MDNode::Header::getLargePtr() const {
+  static_assert(alignof(LargeStorageVector) <= alignof(Header),
+                "LargeStorageVector too strongly aligned");
+  return reinterpret_cast<char *>(const_cast<Header *>(this)) -
+         sizeof(LargeStorageVector);
+}
+
+void *MDNode::Header::getSmallPtr() {
+  static_assert(alignof(MDOperand) <= alignof(Header),
+                "MDOperand too strongly aligned");
+  return reinterpret_cast<char *>(const_cast<Header *>(this)) -
+         sizeof(MDOperand) * SmallSize;
+}
+
+void MDNode::Header::resize(size_t NumOps) {
+  assert(Resizable && "Node is not resizable");
+  if (operands().size() == NumOps)
+    return;
+
+  if (isLarge())
+    getLarge().resize(NumOps);
+  else if (NumOps <= SmallSize)
+    resizeSmall(NumOps);
+  else
+    resizeSmallToLarge(NumOps);
+}
+
+void MDNode::Header::resizeSmall(size_t NumOps) {
+  assert(!isLarge() && "Expected a large MDNode");
+  assert(NumOps <= SmallSize && "NumOps too large for small resize");
+
+  MutableArrayRef<MDOperand> ExistingOps = operands();
+  assert(NumOps != ExistingOps.size() && "Expected a different size");
+
+  int NumNew = (int)NumOps - (int)ExistingOps.size();
+  MDOperand *O = ExistingOps.end();
+  if (NumNew > 0) {
+    for (int I = 0, E = NumNew; I != E; ++I)
+      new (O++) MDOperand();
+  } else {
+    for (int I = 0, E = NumNew; I != E; --I)
+      (--O)->~MDOperand();
+  }
+  setSmallNumOps(NumOps);
+  assert(O == operands().end() && "Operands not (un)initialized until the end");
+}
+
+void MDNode::Header::resizeSmallToLarge(size_t NumOps) {
+  assert(!isLarge() && "Expected a small MDNode");
+  assert(NumOps > SmallSize && "Expected NumOps to be larger than allocation");
+  LargeStorageVector NewOps;
+  NewOps.resize(NumOps);
+  llvm::move(operands(), NewOps.begin());
+  resizeSmall(0);
+  new (getLargePtr()) LargeStorageVector(std::move(NewOps));
+  Large = true;
 }
 
 static bool isOperandUnresolved(Metadata *Op) {
   if (auto *N = dyn_cast_or_null<MDNode>(Op))
     return !N->isResolved();
   return false;
 }
 

llvm/unittests/IR/MetadataTest.cpp

TEST_F(DebugVariableTest, DenseMap) {
   EXPECT_EQ(DebugVariableMap.count(DebugVariableFragB), 1u);
 
   EXPECT_EQ(DebugVariableMap.find(DebugVariableA)->second, 2u);
   EXPECT_EQ(DebugVariableMap.find(DebugVariableInlineA)->second, 3u);
   EXPECT_EQ(DebugVariableMap.find(DebugVariableB)->second, 6u);
   EXPECT_EQ(DebugVariableMap.find(DebugVariableFragB)->second, 12u);
 }
 
+typedef MetadataTest MDTupleAllocationTest;
+TEST_F(MDTupleAllocationTest, Resize) {
+  MDTuple *A = getTuple();
+  Metadata *Value1 = getConstantAsMetadata();
+  Metadata *Value2 = getConstantAsMetadata();
+  Metadata *Value3 = getConstantAsMetadata();
+
+  EXPECT_EQ(A->getNumOperands(), 0u);
+
+  // Add a couple of elements to it, which resizes the node.
+  A->push_back(Value1);
+  EXPECT_EQ(A->getNumOperands(), 1u);
+  EXPECT_EQ(A->getOperand(0), Value1);
+
+  A->push_back(Value2);
+  EXPECT_EQ(A->getNumOperands(), 2u);
+  EXPECT_EQ(A->getOperand(0), Value1);
+  EXPECT_EQ(A->getOperand(1), Value2);
+
+  // Append another element, which should resize the node
+  // to a "large" node, though not detectable by the user.
+  A->push_back(Value3);
+  EXPECT_EQ(A->getNumOperands(), 3u);
+  EXPECT_EQ(A->getOperand(0), Value1);
+  EXPECT_EQ(A->getOperand(1), Value2);
+  EXPECT_EQ(A->getOperand(2), Value3);
+
+  // Remove the last element
+  A->pop_back();
+  EXPECT_EQ(A->getNumOperands(), 2u);
+  EXPECT_EQ(A->getOperand(1), Value2);
+
+  // Allocate a node with 4 operands.
+  Metadata *Value4 = getConstantAsMetadata();
+  Metadata *Value5 = getConstantAsMetadata();
+
+  Metadata *Ops[] = {Value1, Value2, Value3, Value4};
+  MDTuple *B = MDTuple::getDistinct(Context, Ops);
+
+  EXPECT_EQ(B->getNumOperands(), 4u);
+  B->pop_back();
+  EXPECT_EQ(B->getNumOperands(), 3u);
+  B->push_back(Value5);
+  EXPECT_EQ(B->getNumOperands(), 4u);
+  EXPECT_EQ(B->getOperand(0), Value1);
+  EXPECT_EQ(B->getOperand(1), Value2);
+  EXPECT_EQ(B->getOperand(2), Value3);
+  EXPECT_EQ(B->getOperand(3), Value5);
+
+  // Check that we can resize temporary nodes as well.
+  auto Temp1 = MDTuple::getTemporary(Context, None);
+  EXPECT_EQ(Temp1->getNumOperands(), 0u);
+
+  Temp1->push_back(Value1);
+  EXPECT_EQ(Temp1->getNumOperands(), 1u);
+  EXPECT_EQ(Temp1->getOperand(0), Value1);
+
+  for (int i = 0; i < 11; i++)
+    Temp1->push_back(Value2);
+  EXPECT_EQ(Temp1->getNumOperands(), 12u);
+  EXPECT_EQ(Temp1->getOperand(2), Value2);
+  EXPECT_EQ(Temp1->getOperand(11), Value2);
+}
+
+TEST_F(MDTupleAllocationTest, Tracking) {
+  // Resize a tuple and check that we can still RAUW one of its operands.
+  auto *Value1 = getConstantAsMetadata();
+  MDTuple *A = getTuple();
+  A->push_back(Value1);
+  A->push_back(Value1);
+  A->push_back(Value1); // Causes a resize to large.
+  EXPECT_EQ(A->getOperand(0), Value1);
+  EXPECT_EQ(A->getOperand(1), Value1);
+  EXPECT_EQ(A->getOperand(2), Value1);
+
+  auto *Value2 = getConstantAsMetadata();
+  Value *V1 = Value1->getValue();
+  Value *V2 = Value2->getValue();
+  ValueAsMetadata::handleRAUW(V1, V2);
+  EXPECT_EQ(A->getOperand(0), Value2);
+  EXPECT_EQ(A->getOperand(1), Value2);
+  EXPECT_EQ(A->getOperand(2), Value2);
+}
+
+#ifdef GTEST_HAS_DEATH_TEST
+typedef MetadataTest MDTupleAllocationDeathTest;
+TEST_F(MDTupleAllocationDeathTest, ResizeRejected) {
+  MDTuple *A = MDTuple::get(Context, None);
+  auto *Value1 = getConstantAsMetadata();
+  EXPECT_DEATH(A->push_back(Value1), "Node is not resizable");
+}
+#endif
+
 } // end namespace