Index: llvm/include/llvm/IR/Metadata.h =================================================================== --- llvm/include/llvm/IR/Metadata.h +++ llvm/include/llvm/IR/Metadata.h @@ -935,38 +935,111 @@ /// 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; + + 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(this + 1) - - alignTo(getAllocSize(NumOperands), alignof(uint64_t)); + alignTo(getAllocSize(), alignof(uint64_t)); + } + + void *getLargePtr() const; + void *getSmallPtr(); + + LargeStorageVector &getLarge() { + assert(isLarge()); + return *reinterpret_cast(getLargePtr()); } - explicit Header(unsigned NumOperands); + const LargeStorageVector &getLarge() const { + assert(isLarge()); + return *reinterpret_cast(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 operands() { - return makeMutableArrayRef( - reinterpret_cast(this) - NumOperands, NumOperands); + if (isLarge()) + return getLarge(); + return makeMutableArrayRef(reinterpret_cast(this) - + getSmallSize(), + getSmallNumOps()); } + ArrayRef operands() const { - return makeArrayRef( - reinterpret_cast(this) - NumOperands, NumOperands); + if (isLarge()) + return getLarge(); + return makeArrayRef(reinterpret_cast(this) - + getSmallSize(), + getSmallNumOps()); } }; @@ -983,7 +1056,7 @@ ArrayRef Ops1, ArrayRef 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. @@ -1147,6 +1220,12 @@ static T *storeImpl(T *N, StorageType Storage, StoreT &Store); template 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); @@ -1202,13 +1281,19 @@ op_range operands() const { return op_range(op_begin(), op_end()); } + ArrayRef operandsAsArrayRef() const { + SmallVector MDs; + MDs.append(op_begin(), op_end()); + return makeArrayRef(MDs); + } + 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) { @@ -1293,6 +1378,16 @@ /// 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; } Index: llvm/lib/IR/Metadata.cpp =================================================================== --- llvm/lib/IR/Metadata.cpp +++ llvm/lib/IR/Metadata.cpp @@ -523,13 +523,13 @@ "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(::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(H + 1); } @@ -568,17 +568,86 @@ } } -MDNode::Header::Header(unsigned NumOps) { - NumOperands = NumOps; - MDOperand *O = reinterpret_cast(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(NumOps); + } else { + setSmallNumOps(NumOps); + MDOperand *O = reinterpret_cast(this) - getSmallSize(); + for (MDOperand *E = O + getSmallSize(); O != E;) + (void)new (O++) MDOperand(); + } } MDNode::Header::~Header() { - MDOperand *O = reinterpret_cast(this) - NumOperands; - for (MDOperand *E = O + NumOperands; O != E; ++O) - (void)O->~MDOperand(); + if (Large) { + getLarge().~LargeStorageVector(); + } else { + MDOperand *O = reinterpret_cast(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(const_cast
(this)) - + sizeof(LargeStorageVector); +} + +void *MDNode::Header::getSmallPtr() { + static_assert(alignof(MDOperand) <= alignof(Header), + "MDOperand too strongly aligned"); + return reinterpret_cast(const_cast
(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 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(NumOps); + llvm::move(operands(), NewOps.begin()); + resizeSmall(0); + new (getLargePtr()) LargeStorageVector(std::move(NewOps)); + Large = true; } static bool isOperandUnresolved(Metadata *Op) { Index: llvm/unittests/IR/MetadataTest.cpp =================================================================== --- llvm/unittests/IR/MetadataTest.cpp +++ llvm/unittests/IR/MetadataTest.cpp @@ -3602,4 +3602,97 @@ 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