[Metadata] Add a resize/reserve capability for MDNodes

[wolfgangp]

Summary

This patch a starting point for what's discussed in D118416, which is adding a resize capability to MDNodes.

We're distinguishing between small (< 16 operands) and large MDNodes, with the latter having their operands allocated in hung-off storage. Temporary and distinct MDNodes can be resized (to a larger operand capacity, they can't be made smaller), to which end a pointer to separately allocated hung-off storage is kept in the location of the co-allocated operands. This means that MDNodes with 0 operands ('tiny') need some extra space allocated for the pointer, which is not necessary for uniqued MDNodes with 0 operands. In order to distinguish the 2 tiny node types we use the concept 'tiny resizable' and 'tiny fixed' MDNodes (in addition to large and small). Note that this extra complexity could be eliminated if we're OK with allocating extra space even for uniqued tiny nodes. Only 2-3% of MDNodes seem to have 0 operands, so maybe this would not be a big deal.

The patch does not (yet) address the O(N) issue that arises from handling ModuleFlags of type "Append" during LTO, though it does fix the memory issue mentioned in 51893. For that we'd presumably want to scan all participating modules and reserve enough space for the operands from the start. This will be addressed in a later patch.

I didn't add a push_back() interface because there wasn't a client for it, but it can be easily added if needed. I named the resize method 'reserve' because we don't support shrinking anything.

For now, only MDTuples can be resized.

AFAICT, there is no effect on bitcode reading or writing.

[dexonsmith]

Thanks for working on this! I think this will be a big improvement.

I have a few detailed suggestions inline (probably way too detailed, but I'm not sure I'll be super responsive in the next couple of weeks and didn't want to block you; don't feel you need to match my exact suggestions if you have a better idea).

I suggest splitting into multiple patches:

1. Prep: Fix MDOperand(MDOperand&&) (etc.) so that std::move() is efficient.
2. Prep: Refactor MDNode to clean up current allocation a bit, and to front-load NFC changes to keep (3) as clean as possible. (See operator delete comment for details.)
3. The heart of this patch: make MDTuple resizable with a resize() API.
4. Optional: Add the append() APIs (not sure they're needed but seem nice to have).
5. Follow-up: improve module append flags, using (3) and/or (4).

For (3), the heart of this patch, a couple of specific comments to call out:

• I think the API should be protected in MDNode and only exposed as public in MDTuple (for now; matching the assertion).
• Might be cleaner to offload growth/capacity logic to SmallVector or similar (when we're in hung-off territory); see MDNode::reserve() for details.

In order to distinguish the 2 tiny node types we use the concept 'tiny resizable' and 'tiny fixed' MDNodes (in addition to large and small). Note that this extra complexity could be eliminated if we're OK with allocating extra space even for uniqued tiny nodes. Only 2-3% of MDNodes seem to have 0 operands, so maybe this would not be a big deal.

I think it's okay to allocate some extra space. But I think we can factor three modes ("fixed", "dynamic:small", and "dynamic:large") without too much complexity. "fixed" and "dynamic:small" can have identical layout; just one is allowed to resize and the other isn't.

I named the resize method 'reserve' because we don't support shrinking anything.

That seems like an arbitrary restriction. Why not shrink?

I feel like it would be simpler to *only* have resize() (not reserve or append, although those could be built on top I suppose).

• If resize grows, it adds nullptr arguments. The MDNodeTest.Print unit test confirms my memory that nullptr is a valid operand value.
• If resize shrinks, it drops the refs. The allocation never shrinks, but I don't see why we'd arbitrarily restrict it not to be allowed.

llvm/include/llvm/IR/Metadata.h

950

I think(?) it's technically UB (or at least an extension) to use [1] for an array that's bigger. I suggest leaving this out, but adding an acccessor that does the math:

MutableArrayRef<MDOperand> getOperands() {
  return makeMutableArrayRef(reinterpret_cast<MDOperand *>(this + 1), NumOperands);
}
ArrayRef<MDOperand> getOperands() const {
  return const_cast<HungOffOperandStorage *>(this)->getOperands();
}

and you can add a static assert that the alignment will be okay (if it fails some day we can add alignas noise).

953–960

It's obvious to me what the layout is. Can you add a comment above Info that spells it out clearly? Bitfield syntax (// unsigned Name : Size;) would be clear I think. (I'm not totally convinced the abstraction improves readability or reduces bugs but I'm not against it if you think it helps.)

969–972

Usually we do sizes as size_t, except when we're optimizing storage. There's no storage here though.

1032–1060

These all feel very private to me, not protected. (Also, I'm really not sure all this boilerplate is better than a normal bitfield.)

1040–1042

Else where in LLVM coallocated storage is usually called "small". I suggest using the word "small" instead of "coalloc".

1129–1131

I think this should be protected and only enabled on MDTuple for now. Callers can do a cast<MDTuple>()... although, with the append() API, is there even a reason to need this? I don't see any uses except in tests, and the tests could just call append().

1294–1300

I think append should be protected and only exposed in MDTuple, for now. Most of the node kinds have a fixed operand count and calling append() would corrupt them.

1389

Is an explicit capacity really useful/needed? I don't see any uses of this parameter except tests. It might be useful in tests to *access* the capacity (to confirm growth doubles or whatever), but if tests want to influence the capacity seems like they could just use append().

llvm/lib/IR/Metadata.cpp

569

It's a bit sketchy calling anything on N during delete (hence the msan suppression)... it seems even dodgier to call a member function that we can't even see.

Maybe as a prep commit we can refine MDNode's layout to fix the msan issue by moving the first 64-bits ahead of the MDNode. In MDNode, something like:

class MDNode {
  struct Header {
    unsigned NumOperands;
    unsigned NumUnresolved = 0;

    static constexpr size_t getAllocSize(unsigned NumOps) {
      return sizeof(MDOperand) * NumOps + sizeof(Header);
    }
    void *getAlloc() {
      return reinterpret_cast<char *>(this + 1) - getAllocSize(NumOperands);
    }

    MutableArrayRef<MDOperand> operands();
    ArrayRef<MDOperand> operands() const;
    explicit Header(unsigned NumOperands);
    ~Header();
  };
  Header &getHeader() {
    return *(reinterpret_cast<Header *>(this) - 1);
  }
  const Header &getHeader() const {
    return *(reinterpret_cast<const Header *>(this) - 1);
  }

Header is will be coallocated immediately before MDNode, and contain everything necessary to understand its layout.

When allocating:

void *Mem = malloc(Header::getAllocSize(NumOps) + Size);
Header &H = new(reinterpret_cast<char *>(Mem) + OpsAlloc) Header(NumOps);
return reinterpret_cast<void *>(&H + 1);

Here, when deleting:

void MDNode::operator delete(void *Mem) {
  Header *H = reinterpret_cast<Header *>(Mem) - 1;
  Mem = H->getAlloc();
  H->~Header(); // destroys operands
  ::operator delete(Mem);
}

This prep commit would be almost NFC (no functionality change) -- except for fixing the MSan thing and dropping the suppression -- and you could make other refactorings in it to remove NFC noise from this patch, making this one easier to review.

For example, you can structure Header helper functions to be similar to what this commit will land with HungOffOperandStorage; maybe you can share the implementations... or maybe not, but it could simplify the code a bit if you did.

571–572

This logic doesn't look quite right to me. If there's a capacity of 2 and only 1 op, then I think we'll have this in memory:

struct {
  MDOperand Op0;
  char Op1[sizeof(MDOperand)] Op1;
  MDNode Node;
};

I think you need to skip over Op1 to avoid destroying something that hasn't been constructed, and I'm not seeing how that happens...

But if you make the change I suggested above in a prep commit, using Header::ops_begin() and Header::ops_end(), then you won't even have to modify this loop here.

587–589

Ah, just spotted this late. Glad to see it, but seems like the related APIs should *only* show up in the public interface of MDTuple.

596–597

(I was a bit confused by NumOps - 1 here at first, but then I looked at HungOffOperandStorage and figured it out. I suggested a refactoring there that would make this just NumOps... a bit simpler I think.)

I'm not seeing the exponential resizing that I think we want. I think we want std::max(NumOps, OldOpSize * 2) or something like that, in order to grow. (Maybe I missed it and it's elsewhere? See, for example, SmallVectorBase::grow().)

There should also be an assertion for overflow if we go over uint32_t.

I'm wondering if it'd be better to defer most of the "growth" logic (except the first grow) to a battle-hardened vector class (for now, SmallVector). Here's the layout I'm thinking of:

// Pseudo-code, using template parameters for runtime things...
template <class Size> struct MDOperandCharArray {
  alignas(alignof(MDOperand)) char Buffer[sizeof(MDOperand) * Size];
};
template <size_t InitNumOps, bool IsDynamic> struct Layout {
  using LargeStorageVector = SmallVector<MDOperand, 0>;

  constexpr size_t NumOpsFitInVector = sizeof(LargeStorageVector) / sizeof(MDOperand);
  static_assert(NumOpsFitInVector * sizeof(MDOperand) == sizeof(LargeStorageVector));

  constexpr size_t MaxSmallSize = 15;
  constexpr bool InitLarge = InitNumOps > MaxSmallSize;
  constexpr bool NeedsLarge = InitLarge || IsDynamic;
  constexpr size_t MinSmallSize = NeedsLarge ? NumOpsFitInVector : 0;

  size_t SmallSize = MinSmallSize <= Size && Size <= MaxSmallSize ? InitNumOps : MinSmallSize;
  MDOperandCharArray<SmallSize> Ops;
  Header H;
  MDNode N;
  MDNodeSubclassTail Tail;
};

For dynamic nodes that start with 0 or 1 ops, Layout is bigger than what you have (for 64-bit, minimum small size of 2). But otherwise I think it's similar.

(Long-term, could add a (generic) TinyVector to ADT that is pointer-sized, and it could be used here to shrink the local allocation.)

Growing/shrinking would look like:

void Header::resize(size_t NumOps) {
  assert(IsDynamic);
  if (operands().size() == NumOps)
    return;

  if (!isSmall())
    getLarge().resize(NumOps);
  else if (NumOps <= SmallSize)
    resizeSmall(NumOps);
  else
    resizeSmallToLarge(NumOps);
}
void Header::resizeSmallToLarge(size_t NumOps) {
  assert(isSmall());
  assert(NumOps > SmallSize);
  LargeStorageVector NewOps(NumOps);
  llvm::move(operands(), NewOps.begin());
  resizeSmall(0);
  new (getLargePtr()) LargeStorageVector(std::move(NewOps));
  setToLarge(); // Sets the bit in Header that says large storage.
}
void Header::resizeSmall(size_t NumOps) {
  MutableArrayRef<MDOperand> ExistingOps = operands();
  assert(isSmall());
  assert(NumOps <= SmallSize);
  assert(NumOps != ExistingOps.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); // Records NumOps in Header.
  assert(O == ExistingOps.end());
}
void *Header::getLargePtr() {
  // Store it close by Header so it's more likely to be in the same cache line.
  static_assert(alignof(LargeStorageVector) <= alignof(Header));
  return reinterpret_cast<char *>(this) - sizeof(LargeStorageVector);
}
void *Header::getSmallPtr() {
  static_assert(alignof(MDOperand) <= alignof(Header));
  return reinterpret_cast<char *>(this) - sizeof(MDOperand) * SmallSize;
}
LargeStorageVector &getLarge() {
  assert(!isSmall());
  return *reinterpret_cast<LargeStorageVector *>(getLargePtr());
}
MutableArrayRef<MDOperand> Header::operands() {
  if (!isSmall())
    return getLarge();
  return makeMutableArrayRef(reinterpret_cast<MDOperand *>(getSmallPtr()), SmallNumOps);
}

607–610

What does the move constructor do? Can we fix it in a prep commit?

953

I think we usually use a C-style cast for integer casts (i.e., (size_t)Capacity). I don't feel strongly though if you prefer this; maybe check to see if it's documented in the LLVM coding style guide?

llvm/lib/Linker/IRMover.cpp

1413–1422

This is simpler if you can assume MDTuple, since you don't need to clone and replace. You can just make a new one without worrying about other fields.

(IIRC, clone() has some overhead by being temporary to start...)

1418

Not much point in the flag being uniqued if it's pointing at something that isn't uniqued. I wonder if this should be MDTuple::getDistinct() (leave it as-is if it's already the right kind).

1444–1462

Can we delay this usage to a follow-up patch? I'd rather add the IR feature first (since it's non-trivial) and then add the adoption.

It is useful to see it at the same time to understand usage. Phabricator has a feature to link two reviews together (edit related revisions -> child/parent).

[wolfgangp]

llvm/include/llvm/IR/Metadata.h

953–960

I'm not sure it helps either. I'm always a bit uncertain about how much the availability of abstractions constitutes an encouragement to use them. In this case, I guess it makes the derivation of properties like max values from bitfields a bit easier, but it's not that hard to get it right anyway. Otherwise it feels like abstraction for abstractions sake. I'd be happy to get rid of it if you agree.

1389

I had envisioned a slightly different usage model in that clients would figure out in advance how many operands they need and reserve the space first. With the automatic expansion done by resize() I was afraid of too much waste, given how much space large LTO links are already using, for example.

llvm/lib/IR/Metadata.cpp

571–572

Hmm, all the allocated operands should have been constructed in operator new. In this scheme the idea was that operator new allocates the capacity and the constructor assigns the actual operands, of which there may be fewer than the capacity. Either way, all allocated operand slots should be properly constructed.

In any case, if we don't separate capacity and number of actual assigned operands, this is academic.

607–610

The move constructor copies the operand to the newly allocated slot and does retrack(). Optionally, it could also null out the old location (or call the destructor on it).

llvm/lib/Linker/IRMover.cpp

1444–1462

Yeah, I'll follow the sequence you suggested up at the top.

[dexonsmith]

llvm/include/llvm/IR/Metadata.h

953–960

SGTM!

1389

With automatic expansion it'll be a strict improvement in memory usage over what it was before (previously, all previous sizes would still be around) and it changes a quadratic operation to amortized linear (calling Metadata::retrack() isn't cheap). I think it's a better starting point.

If a profile shows that the automatically-expanded nodes are too expensive in practice, could add a shrink_to_fit() later.

llvm/lib/IR/Metadata.cpp

571–572

Ah, as soon as I saw the word "capacity" I assumed there would be storage where the operands had not been constructed (similar to a vector). I do think automatic expansion is the right default for resizable storage.

607–610

Not obvious to me how this is different, but I think if there's an improvement to make in the move constructor we should fix it, and this (or SmallVector<MDOperand>) should just use it.

llvm/include/llvm/IR/Metadata.h

 /// They represent the different flavors of metadata that live in LLVM.
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_IR_METADATA_H
 #define LLVM_IR_METADATA_H
 
 #include "llvm/ADT/ArrayRef.h"
+#include "llvm/ADT/Bitfields.h"
 #include "llvm/ADT/DenseMap.h"
 #include "llvm/ADT/DenseMapInfo.h"
 #include "llvm/ADT/None.h"
 #include "llvm/ADT/PointerUnion.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/ADT/StringRef.h"
 #include "llvm/ADT/ilist_node.h"
 #include "llvm/ADT/iterator_range.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.
+///
+/// Temporary and distinct MDNodes are resizable, but this is at present only
+/// supported for MDTuples. At allocation time, depending on desired capacity,
+/// operands are either co-allocated with the node or allocated separately in
+/// hung-off storage.
 class MDNode : public Metadata {
   friend class ReplaceableMetadataImpl;
   friend class LLVMContextImpl;
   friend class DIArgList;
 
+  // See the comment for operator new for more information on allocation types.
+  enum class AllocationType : uint8_t {
+    TinyFixed,
+    TinyResizable,
+    Small,
+    Large
+  };
+
+  /// How operands are stored if not co-allocated with the node.
+  /// \a Capacity determines the actual size.
+  struct HungOffOperandStorage {
+    unsigned Capacity;
     unsigned NumOperands;
+    MDOperand Operands[1];
+  };
+
+  unsigned Info; // Storage for the following bitfields.
+
+  using AllocType =
+      Bitfield::Element<AllocationType, 0, 2, AllocationType::Large>;
+  /// The capacity of an MDNode with co-allocated operands.
+  using CoallocCapacity = Bitfield::Element<unsigned, AllocType::NextBit, 4>;
+  using CoallocNumOperands =
+      Bitfield::Element<unsigned, CoallocCapacity::NextBit, 4>;
+
   unsigned NumUnresolved;
 
   ContextAndReplaceableUses Context;
 
 protected:
+  using HungOffPtr = std::unique_ptr<HungOffOperandStorage>;
+  using CoCapType = CoallocCapacity::Type;
+  static constexpr unsigned CoCapSize = CoallocCapacity::Bits;
+  /// The maximum number of MDOperands that can be coallocated with an MDNode.
+  static constexpr unsigned MaxCoallocCapacity =
+      bitfields_details::BitPatterns<CoCapType, CoCapSize>::Umax;
+
+private:
+  /// Number of MDOperands to cover enough storage space for a HungOffPtr.
+  /// Nodes with at least this many operands do not need extra storage
+  /// allocated. This is host-dependent, but probably 1 in most cases.
+  static constexpr unsigned MinOpsForPtr =
+      (sizeof(HungOffPtr) - 1) / sizeof(MDOperand) + 1;
+
+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);
+  /// For purposes of initial allocation, we differentiate between 4 different
+  /// allocation types:
+  /// (1) "large" nodes with a capacity of more than MaxCoallocCapacity (15)
+  ///     operands,
+  /// (2) "small" nodes with a capacity of fewer than MaxCoallocCapacity but at
+  ///     least MinOpsForPtr operands,
+  /// (3) "tinyResizable" nodes with a capacity of fewer than MinOpsForPtr
+  ///     operands and with distinct or temporary storage type,
+  /// (4) "tinyFixed" nodes with unique storage type.
+  ///
+  /// Nodes of type (1) store their operands in hung-off storage, whereas all
+  /// the other types' operands are co-allocated. All nodes except type (4) are
+  /// resizable. Any resize makes a node into a "large" one. Nodes of type (3)
+  /// require extra space to accommodate a pointer to hung-off storage, in case
+  /// they need to be resized.
+  ///
+  /// Note that an MDNode's change in storage type (e.g. temporary->uniqued)
+  /// does not affect their allocation type. However, once a node becomes
+  /// uniqued, it can no longer be resized, no matter its allocation type.
+  ///
+  /// \c NumOps determines the capacity of the new node. The actual number
+  /// of operands is set by the constructors.
+  void *operator new(size_t Size, unsigned 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.
   void operator delete(void *, unsigned, bool) {
     llvm_unreachable("Constructor throws?");
   }
 
   void dropAllReferences();
 
-  MDOperand *mutable_begin() { return mutable_end() - NumOperands; }
-  MDOperand *mutable_end() { return reinterpret_cast<MDOperand *>(this); }
+  void setNumOperands(unsigned NOps) {
+    assert(NOps <= getCapacity() &&
+           "Number of operands exceeds capacity of MDNode");
+    if (getAllocationType() == AllocationType::Large)
+      hungoff()->NumOperands = NOps;
+    else
+      setCoallocNumOperands(NOps);
+  }
+
+  AllocationType getAllocationType() const {
+    return Bitfield::get<AllocType>(Info);
+  }
+
+  void setAllocationType(AllocationType Type) {
+    Bitfield::set<AllocType>(Info, Type);
+  }
+
+  unsigned getCoallocCapacity() const {
+    return Bitfield::get<CoallocCapacity>(Info);
+  }
+
+  void setCoallocCapacity(unsigned Cap) {
+    Bitfield::set<CoallocCapacity>(Info, Cap);
+  }
+
+  unsigned getCoallocNumOperands() const {
+    return Bitfield::get<CoallocNumOperands>(Info);
+  }
+
+  void setCoallocNumOperands(unsigned Num) {
+    Bitfield::set<CoallocNumOperands>(Info, Num);
+  }
+
+  HungOffPtr &hungoff() const {
+    assert(getAllocationType() == AllocationType::Large &&
+           "Expected large MDNode");
+    return *(reinterpret_cast<HungOffPtr *>(const_cast<MDNode *>(this)) - 1);
+  }
+
+  MDOperand *mutable_begin() {
+    return getAllocationType() == AllocationType::Large
+               ? hungoff()->Operands
+               : reinterpret_cast<MDOperand *>(this) - getCoallocCapacity();
+  }
+
+  MDOperand *mutable_end() { return mutable_begin() + getNumOperands(); }
 
   using mutable_op_range = iterator_range<MDOperand *>;
 
   mutable_op_range mutable_operands() {
     return mutable_op_range(mutable_begin(), mutable_end());
   }
 
 public:
public:
   ///
   /// \pre \a isTemporary() must be \c true.
   void replaceAllUsesWith(Metadata *MD) {
     assert(isTemporary() && "Expected temporary node");
     if (Context.hasReplaceableUses())
       Context.getReplaceableUses()->replaceAllUsesWith(MD);
   }
 
+  /// Increase the operand capacity to \c NumOps.
+  /// \pre Must be either a temporary or distinct node.
+  void reserve(unsigned NumOps);
+
   /// Resolve cycles.
   ///
   /// Once all forward declarations have been resolved, force cycles to be
   /// resolved.
   ///
   /// \pre No operands (or operands' operands, etc.) have \a isTemporary().
   void resolveCycles();
 
protected:
   void setOperand(unsigned I, Metadata *New);
 
   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);
 
 private:
+
+  static AllocationType determineAllocationType(unsigned NumOps,
+                                                StorageType Storage) {
+    return NumOps > MaxCoallocCapacity ? AllocationType::Large
+           : NumOps > MinOpsForPtr     ? AllocationType::Small
+           : Storage == Uniqued        ? AllocationType::TinyFixed
+                                       : AllocationType::TinyResizable;
+  }
+
+  void ensureCapacity(unsigned NumOps) {
+    if (NumOps > getCapacity())
+      reserve(NumOps);
+  }
+
   void handleChangedOperand(void *Ref, Metadata *New);
 
   /// Drop RAUW support, if any.
   void dropReplaceableUses();
 
   void resolveAfterOperandChange(Metadata *Old, Metadata *New);
   void decrementUnresolvedOperandCount();
   void countUnresolvedOperands();
public:
 
   op_iterator op_end() const {
     return const_cast<MDNode *>(this)->mutable_end();
   }
 
   op_range operands() const { return op_range(op_begin(), op_end()); }
 
   const MDOperand &getOperand(unsigned I) const {
-    assert(I < NumOperands && "Out of range");
+    assert(I < getNumOperands() && "Out of range");
     return op_begin()[I];
   }
 
+  /// Append a range of operands to the existing ones. Performs a
+  /// resize/reserve if necessary. Only allowed for distinct and temporary
+  /// storage classes.
+  void append(ArrayRef<Metadata *> Ops);
+
+  void append(ArrayRef<MDOperand> Ops) {
+    append(makeArrayRef(
+        reinterpret_cast<Metadata **>(const_cast<MDOperand *>(Ops.begin())),
+        Ops.size()));
+  }
+
+  template <class T>
+  void
+  append(std::enable_if_t<std::is_convertible<T, Metadata *>::value, T> Op) {
+    append(makeArrayRef(Op));
+  }
+
   /// Return number of MDNode operands.
-  unsigned getNumOperands() const { return NumOperands; }
+  unsigned getNumOperands() const {
+    return getAllocationType() == AllocationType::Large
+               ? hungoff()->NumOperands
+               : getCoallocNumOperands();
+  }
+
+  unsigned getCapacity() const {
+    return getAllocationType() == AllocationType::Large ? hungoff()->Capacity
+                                                        : getCoallocCapacity();
+  }
 
   /// 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:                                                            \
class MDTuple : public MDNode {
   }
 
   ~MDTuple() { dropAllReferences(); }
 
   void setHash(unsigned Hash) { SubclassData32 = Hash; }
   void recalculateHash();
 
   static MDTuple *getImpl(LLVMContext &Context, ArrayRef<Metadata *> MDs,
-                          StorageType Storage, bool ShouldCreate = true);
+                          StorageType Storage, unsigned Capacity,
+                          bool ShouldCreate = true);
 
   TempMDTuple cloneImpl() const {
-    return getTemporary(getContext(), SmallVector<Metadata *, 4>(operands()));
+    return getTemporary(getContext(), SmallVector<Metadata *, 4>(operands()),
+                        getCapacity());
   }
 
 public:
   /// Get the hash, if any.
   unsigned getHash() const { return SubclassData32; }
 
   static MDTuple *get(LLVMContext &Context, ArrayRef<Metadata *> MDs) {
-    return getImpl(Context, MDs, Uniqued);
+    return getImpl(Context, MDs, Uniqued, MDs.size());
   }
 
   static MDTuple *getIfExists(LLVMContext &Context, ArrayRef<Metadata *> MDs) {
-    return getImpl(Context, MDs, Uniqued, /* ShouldCreate */ false);
+    return getImpl(Context, MDs, Uniqued, MDs.size(), /* ShouldCreate */ false);
   }
 
   /// Return a distinct node.
   ///
   /// Return a distinct node -- i.e., a node that is not uniqued.
-  static MDTuple *getDistinct(LLVMContext &Context, ArrayRef<Metadata *> MDs) {
-    return getImpl(Context, MDs, Distinct);
+  static MDTuple *getDistinct(LLVMContext &Context, ArrayRef<Metadata *> MDs,
+                              unsigned Capacity = 0) {
+    return getImpl(Context, MDs, Distinct, Capacity);
   }
 
   /// Return a temporary node.
   ///
   /// For use in constructing cyclic MDNode structures. A temporary MDNode is
   /// not uniqued, may be RAUW'd, and must be manually deleted with
   /// deleteTemporary.
   static TempMDTuple getTemporary(LLVMContext &Context,
-                                  ArrayRef<Metadata *> MDs) {
-    return TempMDTuple(getImpl(Context, MDs, Temporary));
+                                  ArrayRef<Metadata *> MDs,
+                                  unsigned Capacity = 0) {
+    return TempMDTuple(getImpl(Context, MDs, Temporary, Capacity));
   }
 
   /// Return a (temporary) clone of this.
   TempMDTuple clone() const { return cloneImpl(); }
 
   static bool classof(const Metadata *MD) {
     return MD->getMetadataID() == MDTupleKind;
   }

llvm/lib/AsmParser/LLParser.cpp

bool LLParser::parseGlobalValueVector(SmallVectorImpl<Constant *> &Elts,
   return false;
 }
 
 bool LLParser::parseMDTuple(MDNode *&MD, bool IsDistinct) {
   SmallVector<Metadata *, 16> Elts;
   if (parseMDNodeVector(Elts))
     return true;
 
-  MD = (IsDistinct ? MDTuple::getDistinct : MDTuple::get)(Context, Elts);
+  MD = IsDistinct ? MDTuple::getDistinct(Context, Elts)
+                  : MDTuple::get(Context, Elts);
   return false;
 }
 
 /// MDNode:
 ///  ::= !{ ... }
 ///  ::= !7
 ///  ::= !DILocation(...)
 bool LLParser::parseMDNode(MDNode *&N) {

llvm/lib/CodeGen/MIRParser/MIParser.cpp

bool MIParser::parseMachineMetadata() {
 
   return false;
 }
 
 bool MIParser::parseMDTuple(MDNode *&MD, bool IsDistinct) {
   SmallVector<Metadata *, 16> Elts;
   if (parseMDNodeVector(Elts))
     return true;
-  MD = (IsDistinct ? MDTuple::getDistinct
-                   : MDTuple::get)(MF.getFunction().getContext(), Elts);
+  MD = IsDistinct ? MDTuple::getDistinct(MF.getFunction().getContext(), Elts)
+                  : MDTuple::get(MF.getFunction().getContext(), Elts);
   return false;
 }
 
 bool MIParser::parseMDNodeVector(SmallVectorImpl<Metadata *> &Elts) {
   if (Token.isNot(MIToken::lbrace))
     return error("expected '{' here");
   lex();
 

llvm/lib/IR/DebugInfoMetadata.cpp

DILocation *DILocation::getImpl(LLVMContext &Context, unsigned Line,
   } else {
     assert(ShouldCreate && "Expected non-uniqued nodes to always be created");
   }
 
   SmallVector<Metadata *, 2> Ops;
   Ops.push_back(Scope);
   if (InlinedAt)
     Ops.push_back(InlinedAt);
-  return storeImpl(new (Ops.size()) DILocation(Context, Storage, Line, Column,
-                                               Ops, ImplicitCode),
+  return storeImpl(new (Ops.size(), Storage) DILocation(
+                       Context, Storage, Line, Column, Ops, ImplicitCode),
                    Storage, Context.pImpl->DILocations);
 }
 
 const DILocation *
 DILocation::getMergedLocations(ArrayRef<const DILocation *> Locs) {
   if (Locs.empty())
     return nullptr;
   if (Locs.size() == 1)
if (Storage == Uniqued) {
     Hash = Key.getHash();
   } else {
     assert(ShouldCreate && "Expected non-uniqued nodes to always be created");
   }
 
   // Use a nullptr for empty headers.
   assert(isCanonical(Header) && "Expected canonical MDString");
   Metadata *PreOps[] = {Header};
-  return storeImpl(new (DwarfOps.size() + 1) GenericDINode(
+  return storeImpl(new (DwarfOps.size() + 1, Storage) GenericDINode(
                        Context, Storage, Hash, Tag, PreOps, DwarfOps),
                    Storage, Context.pImpl->GenericDINodes);
 }
 
 void GenericDINode::recalculateHash() {
   setHash(GenericDINodeInfo::KeyTy::calculateHash(this));
 }
 
 #define UNWRAP_ARGS_IMPL(...) __VA_ARGS__
 #define UNWRAP_ARGS(ARGS) UNWRAP_ARGS_IMPL ARGS
 #define DEFINE_GETIMPL_LOOKUP(CLASS, ARGS)                                     \
   do {                                                                         \
     if (Storage == Uniqued) {                                                  \
       if (auto *N = getUniqued(Context.pImpl->CLASS##s,                        \
                                CLASS##Info::KeyTy(UNWRAP_ARGS(ARGS))))         \
         return N;                                                              \
       if (!ShouldCreate)                                                       \
         return nullptr;                                                        \
     } else {                                                                   \
       assert(ShouldCreate &&                                                   \
              "Expected non-uniqued nodes to always be created");               \
     }                                                                          \
   } while (false)
 #define DEFINE_GETIMPL_STORE(CLASS, ARGS, OPS)                                 \
-  return storeImpl(new (array_lengthof(OPS))                                   \
+  return storeImpl(new (array_lengthof(OPS), Storage)                          \
                        CLASS(Context, Storage, UNWRAP_ARGS(ARGS), OPS),        \
                    Storage, Context.pImpl->CLASS##s)
 #define DEFINE_GETIMPL_STORE_NO_OPS(CLASS, ARGS)                               \
-  return storeImpl(new (0u) CLASS(Context, Storage, UNWRAP_ARGS(ARGS)),        \
+  return storeImpl(new (0u, Storage)                                           \
+                       CLASS(Context, Storage, UNWRAP_ARGS(ARGS)),             \
                    Storage, Context.pImpl->CLASS##s)
 #define DEFINE_GETIMPL_STORE_NO_CONSTRUCTOR_ARGS(CLASS, OPS)                   \
-  return storeImpl(new (array_lengthof(OPS)) CLASS(Context, Storage, OPS),     \
+  return storeImpl(new (array_lengthof(OPS), Storage)                          \
+                       CLASS(Context, Storage, OPS),                           \
                    Storage, Context.pImpl->CLASS##s)
 #define DEFINE_GETIMPL_STORE_N(CLASS, ARGS, OPS, NUM_OPS)                      \
-  return storeImpl(new (NUM_OPS)                                               \
+  return storeImpl(new (NUM_OPS, Storage)                                      \
                        CLASS(Context, Storage, UNWRAP_ARGS(ARGS), OPS),        \
                    Storage, Context.pImpl->CLASS##s)
 
 DISubrange::DISubrange(LLVMContext &C, StorageType Storage,
                        ArrayRef<Metadata *> Ops)
     : DINode(C, DISubrangeKind, Storage, dwarf::DW_TAG_subrange_type, Ops) {}
 DISubrange *DISubrange::getImpl(LLVMContext &Context, int64_t Count, int64_t Lo,
                                 StorageType Storage, bool ShouldCreate) {
Metadata *Ops[] = {File,
                      SplitDebugFilename,
                      EnumTypes,
                      RetainedTypes,
                      GlobalVariables,
                      ImportedEntities,
                      Macros,
                      SysRoot,
                      SDK};
-  return storeImpl(new (array_lengthof(Ops)) DICompileUnit(
+  return storeImpl(new (array_lengthof(Ops), Storage) DICompileUnit(
                        Context, Storage, SourceLanguage, IsOptimized,
                        RuntimeVersion, EmissionKind, DWOId, SplitDebugInlining,
                        DebugInfoForProfiling, NameTableKind, RangesBaseAddress,
                        Ops),
                    Storage);
 }
 
 Optional<DICompileUnit::DebugEmissionKind>

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) {
+void *MDNode::operator new(size_t Size, unsigned NumOps, StorageType Storage) {
+  AllocationType AllocType = determineAllocationType(NumOps, Storage);
   size_t OpSize = NumOps * sizeof(MDOperand);
+
+  // For large nodes we do not co-allocate operands.
+  if (AllocType == AllocationType::Large)
+    OpSize = 0;
+  // All allocation types except small uniqued nodes must reserve extra space
+  // for a pointer to hung-off storage to enable resizing.
+  if (AllocType != AllocationType::TinyFixed)
+    OpSize = std::max(OpSize, sizeof(HungOffPtr));
   // uint64_t is the most aligned type we need support (ensured by static_assert
   // above)
   OpSize = alignTo(OpSize, alignof(uint64_t));
+
+  // Allocate the main node.
   void *Ptr = reinterpret_cast<char *>(::operator new(OpSize + Size)) + OpSize;
-  MDOperand *O = static_cast<MDOperand *>(Ptr);
-  for (MDOperand *E = O - NumOps; O != E; --O)
-    (void)new (O - 1) MDOperand;
+  MDNode *NewNode = reinterpret_cast<MDNode *>(Ptr);
+  NewNode->setCoallocCapacity(AllocType == AllocationType::Large ? 0 : NumOps);
+  NewNode->setCoallocNumOperands(0);
+  NewNode->setAllocationType(AllocType);
+
+  // Allocate hung-off storage for large nodes.
+  if (AllocType == AllocationType::Large) {
+    size_t HungOffSize =
+        sizeof(HungOffOperandStorage) + (NumOps - 1) * sizeof(MDOperand);
+    auto HungOffStorage =
+        reinterpret_cast<HungOffPtr::pointer>(::operator new(HungOffSize));
+    HungOffStorage->Capacity = NumOps;
+    HungOffStorage->NumOperands = 0;
+    new (&NewNode->hungoff()) HungOffPtr(HungOffStorage);
+  }
+
+  MDOperand *O = NewNode->mutable_begin();
+  for (MDOperand *E = O + NumOps; O != E; ++O)
+    (void)new (O) MDOperand;
   return Ptr;
 }
 
 // Repress memory sanitization, due to use-after-destroy by operator
 // delete. Bug report 24578 identifies this issue.
 LLVM_NO_SANITIZE_MEMORY_ATTRIBUTE void MDNode::operator delete(void *Mem) {
   MDNode *N = static_cast<MDNode *>(Mem);
-  size_t OpSize = N->NumOperands * sizeof(MDOperand);
-  OpSize = alignTo(OpSize, alignof(uint64_t));
+  MDOperand *O = N->mutable_begin() + N->getCapacity();
 
-  MDOperand *O = static_cast<MDOperand *>(Mem);
-  for (MDOperand *E = O - N->NumOperands; O != E; --O)
+  for (MDOperand *E = O - N->getCapacity(); O != E; --O)
     (O - 1)->~MDOperand();
+
+  if (N->getAllocationType() == AllocationType::Large)
+    ::operator delete(N->hungoff().release());
+
+  // Deallocate the main node.
+  size_t OpSize = N->getCoallocCapacity() * sizeof(MDOperand);
+  if (N->getAllocationType() != AllocationType::TinyFixed)
+    OpSize = std::max(OpSize, sizeof(HungOffPtr));
+  OpSize = alignTo(OpSize, alignof(uint64_t));
+
   ::operator delete(reinterpret_cast<char *>(Mem) - OpSize);
 }
 
+void MDNode::reserve(unsigned NumOps) {
+  assert(
+      getMetadataID() == MDTupleKind &&
+      "Increasing the number of operands is not supported for this node kind");
+  assert(!isUniqued() &&
+         "Cannot increase the number of operands of a uniqued node");
+  if (NumOps <= getCapacity())
+    return;
+
+  size_t OldOpSize = getNumOperands() * sizeof(MDOperand);
+  size_t HungOffSize =
+      sizeof(HungOffOperandStorage) + (NumOps - 1) * sizeof(MDOperand);
+
+  // Allocate the hung-off operand storage.
+  auto HOPtr =
+      reinterpret_cast<HungOffPtr::pointer>(::operator new(HungOffSize));
+  HOPtr->Capacity = NumOps;
+  HOPtr->NumOperands = getNumOperands();
+
+  MDOperand *OldOps = mutable_begin();
+  MDOperand *NewOps = HOPtr->Operands;
+  // FIXME: Should we define MDOperand's move constructor to do this?
+  std::memcpy(NewOps, OldOps, OldOpSize);
+  for (MDOperand *OO = OldOps, *NO = NewOps; OO != op_end(); OO++, NO++)
+    MetadataTracking::retrack(OO, **OO, NO);
+
+  // Initialize the extra MDOperands.
+  for (MDOperand *O = NewOps + getNumOperands(), *E = NewOps + NumOps; O != E;
+       ++O)
+    (void)new (O) MDOperand;
+
+  if (getAllocationType() == AllocationType::Large)
+    ::operator delete(hungoff().release());
+  setAllocationType(AllocationType::Large);
+  new (&hungoff()) HungOffPtr(HOPtr);
+}
+
+void MDNode::append(ArrayRef<Metadata *> Ops) {
+  unsigned NumNewOps = getNumOperands() + Ops.size();
+  ensureCapacity(NumNewOps);
+  unsigned Op = getNumOperands();
+  setNumOperands(NumNewOps);
+  for (Metadata *M : Ops)
+    setOperand(Op++, M);
+}
+
 MDNode::MDNode(LLVMContext &Context, unsigned ID, StorageType Storage,
                ArrayRef<Metadata *> Ops1, ArrayRef<Metadata *> Ops2)
-    : Metadata(ID, Storage), NumOperands(Ops1.size() + Ops2.size()),
-      NumUnresolved(0), Context(Context) {
+    : Metadata(ID, Storage), NumUnresolved(0), Context(Context) {
+  setNumOperands(Ops1.size() + Ops2.size());
   unsigned Op = 0;
   for (Metadata *MD : Ops1)
     setOperand(Op++, MD);
   for (Metadata *MD : Ops2)
     setOperand(Op++, MD);
 
   if (!isUniqued())
     return;
MDNode *MDNode::replaceWithDistinctImpl() {
   return this;
 }
 
 void MDTuple::recalculateHash() {
   setHash(MDTupleInfo::KeyTy::calculateHash(this));
 }
 
 void MDNode::dropAllReferences() {
-  for (unsigned I = 0, E = NumOperands; I != E; ++I)
+  for (unsigned I = 0, E = getNumOperands(); I != E; ++I)
     setOperand(I, nullptr);
   if (Context.hasReplaceableUses()) {
     Context.getReplaceableUses()->resolveAllUses(/* ResolveUsers */ false);
     (void)Context.takeReplaceableUses();
   }
 }
 
 void MDNode::handleChangedOperand(void *Ref, Metadata *New) {
#define HANDLE_MDNODE_LEAF_UNIQUABLE(CLASS)                                    \
   case CLASS##Kind:                                                            \
     getContext().pImpl->CLASS##s.erase(cast<CLASS>(this));                     \
     break;
 #include "llvm/IR/Metadata.def"
   }
 }
 
 MDTuple *MDTuple::getImpl(LLVMContext &Context, ArrayRef<Metadata *> MDs,
-                          StorageType Storage, bool ShouldCreate) {
+                          StorageType Storage, unsigned Capacity,
+                          bool ShouldCreate) {
   unsigned Hash = 0;
   if (Storage == Uniqued) {
     MDTupleInfo::KeyTy Key(MDs);
     if (auto *N = getUniqued(Context.pImpl->MDTuples, Key))
       return N;
     if (!ShouldCreate)
       return nullptr;
     Hash = Key.getHash();
   } else {
     assert(ShouldCreate && "Expected non-uniqued nodes to always be created");
   }
 
-  return storeImpl(new (MDs.size()) MDTuple(Context, Storage, Hash, MDs),
+  size_t Size = std::max(MDs.size(), static_cast<size_t>(Capacity));
+  return storeImpl(new (Size, Storage) MDTuple(Context, Storage, Hash, MDs),
                    Storage, Context.pImpl->MDTuples);
 }
 
 void MDNode::deleteTemporary(MDNode *N) {
   assert(N->isTemporary() && "Expected temporary node");
   N->replaceAllUsesWith(nullptr);
   N->deleteAsSubclass();
 }
if (!isUniqued()) {
     setOperand(I, New);
     return;
   }
 
   handleChangedOperand(mutable_begin() + I, New);
 }
 
 void MDNode::setOperand(unsigned I, Metadata *New) {
-  assert(I < NumOperands);
+  assert(I < getNumOperands());
   mutable_begin()[I].reset(New, isUniqued() ? this : nullptr);
 }
 
 /// Get a node or a self-reference that looks like it.
 ///
 /// Special handling for finding self-references, for use by \a
 /// MDNode::concatenate() and \a MDNode::intersect() to maintain behaviour from
 /// when self-referencing nodes were still uniqued.  If the first operand has

llvm/lib/Linker/IRMover.cpp

if (SrcBehaviorValue != DstBehaviorValue) {
                          SrcBehaviorValue == Module::Warning);
       if (!(MaxAndWarn || MinAndWarn))
         return stringErr("linking module flags '" + ID->getString() +
                          "': IDs have conflicting behaviors in '" +
                          SrcM->getModuleIdentifier() + "' and '" +
                          DstM.getModuleIdentifier() + "'");
     }
 
-    auto replaceDstValue = [&](MDNode *New) {
-      Metadata *FlagOps[] = {DstOp->getOperand(0), ID, New};
-      MDNode *Flag = MDNode::get(DstM.getContext(), FlagOps);
-      DstModFlags->setOperand(DstIndex, Flag);
-      Flags[ID].first = Flag;
-    };
-
     // Emit a warning if the values differ and either source or destination
     // request Warning behavior.
     if ((DstBehaviorValue == Module::Warning ||
          SrcBehaviorValue == Module::Warning) &&
         SrcOp->getOperand(2) != DstOp->getOperand(2)) {
       std::string Str;
       raw_string_ostream(Str)
           << "linking module flags '" << ID->getString()
if (DstBehaviorValue == Module::Max || SrcBehaviorValue == Module::Max) {
           (SrcValue->getZExtValue() > DstValue->getZExtValue() ? SrcOp : DstOp)
               ->getOperand(2)};
       MDNode *Flag = MDNode::get(DstM.getContext(), FlagOps);
       DstModFlags->setOperand(DstIndex, Flag);
       Flags[ID].first = Flag;
       continue;
     }
 
+    auto ensureDistinctOp = [&](MDNode *DstValue) {
+      if (DstValue->isDistinct())
+        return DstValue;
+      MDNode *New = MDNode::replaceWithDistinct(DstValue->clone());
+      Metadata *FlagOps[] = {DstOp->getOperand(0), ID, New};
+      MDNode *Flag = MDNode::get(DstM.getContext(), FlagOps);
+      DstModFlags->setOperand(DstIndex, Flag);
+      Flags[ID].first = Flag;
+      return New;
+    };
+
     // Perform the merge for standard behavior types.
     switch (SrcBehaviorValue) {
     case Module::Require:
     case Module::Override:
       llvm_unreachable("not possible");
     case Module::Error: {
       // Emit an error if the values differ.
       if (SrcOp->getOperand(2) != DstOp->getOperand(2))
         return stringErr("linking module flags '" + ID->getString() +
                          "': IDs have conflicting values in '" +
                          SrcM->getModuleIdentifier() + "' and '" +
                          DstM.getModuleIdentifier() + "'");
       continue;
     }
     case Module::Warning: {
       break;
     }
     case Module::Max: {
       break;
     }
     case Module::Append: {
-      MDNode *DstValue = cast<MDNode>(DstOp->getOperand(2));
+      MDNode *DstValue = ensureDistinctOp(cast<MDNode>(DstOp->getOperand(2)));
       MDNode *SrcValue = cast<MDNode>(SrcOp->getOperand(2));
-      SmallVector<Metadata *, 8> MDs;
-      MDs.reserve(DstValue->getNumOperands() + SrcValue->getNumOperands());
-      MDs.append(DstValue->op_begin(), DstValue->op_end());
-      MDs.append(SrcValue->op_begin(), SrcValue->op_end());
-
-      replaceDstValue(MDNode::get(DstM.getContext(), MDs));
+      DstValue->append(makeArrayRef(SrcValue->op_begin(), SrcValue->op_end()));
       break;
     }
     case Module::AppendUnique: {
       SmallSetVector<Metadata *, 16> Elts;
-      MDNode *DstValue = cast<MDNode>(DstOp->getOperand(2));
+      MDNode *DstValue = ensureDistinctOp(cast<MDNode>(DstOp->getOperand(2)));
       MDNode *SrcValue = cast<MDNode>(SrcOp->getOperand(2));
       Elts.insert(DstValue->op_begin(), DstValue->op_end());
       Elts.insert(SrcValue->op_begin(), SrcValue->op_end());
-
-      replaceDstValue(MDNode::get(DstM.getContext(),
-                                  makeArrayRef(Elts.begin(), Elts.end())));
+      // There should not be any duplicates in DstValue's original operands,
+      // therefore all of SrcValue's operands that were added must be trailing
+      // DstValue's operands.
+      DstValue->append(
+          makeArrayRef(Elts.begin() + DstValue->getNumOperands(), Elts.end()));
       break;
     }
     }
 
   }
 
   // Check all of the requirements.
   for (unsigned I = 0, E = Requirements.size(); I != E; ++I) {
     MDNode *Requirement = Requirements[I];
     MDString *Flag = cast<MDString>(Requirement->getOperand(0));

llvm/lib/Transforms/Instrumentation/CGProfile.cpp

addModuleFlags(Module &M,
   for (auto E : Counts) {
     Metadata *Vals[] = {ValueAsMetadata::get(E.first.first),
                         ValueAsMetadata::get(E.first.second),
                         MDB.createConstant(ConstantInt::get(
                             Type::getInt64Ty(Context), E.second))};
     Nodes.push_back(MDNode::get(Context, Vals));
   }
 
-  M.addModuleFlag(Module::Append, "CG Profile", MDNode::get(Context, Nodes));
+  M.addModuleFlag(Module::Append, "CG Profile",
+                  MDNode::getDistinct(Context, Nodes));
   return true;
 }
 
 static bool runCGProfilePass(
     Module &M, function_ref<BlockFrequencyInfo &(Function &)> GetBFI,
     function_ref<TargetTransformInfo &(Function &)> GetTTI, bool LazyBFI) {
   MapVector<std::pair<Function *, Function *>, uint64_t> Counts;
   InstrProfSymtab Symtab;

llvm/test/Instrumentation/cgprofile.ll

 }
 
 !1 = !{!"function_entry_count", i64 32}
 !2 = !{!"branch_weights", i32 5, i32 10}
 !3 = !{!"VP", i32 0, i64 1600, i64 7651369219802541373, i64 1030, i64 -4377547752858689819, i64 410, i64 -6929281286627296573, i64 150, i64 -2545542355363006406, i64 10, i64 3667884930908592509, i64 1, i64 15435711456043681792, i64 0}
 
 ; CHECK: !llvm.module.flags = !{![[cgprof:[0-9]+]]}
 ; CHECK: ![[cgprof]] = !{i32 5, !"CG Profile", ![[prof:[0-9]+]]}
-; CHECK: ![[prof]] = !{![[e0:[0-9]+]], ![[e1:[0-9]+]], ![[e2:[0-9]+]], ![[e3:[0-9]+]], ![[e4:[0-9]+]], ![[e5:[0-9]+]], ![[e6:[0-9]+]]}
+; CHECK: ![[prof]] = distinct !{![[e0:[0-9]+]], ![[e1:[0-9]+]], ![[e2:[0-9]+]], ![[e3:[0-9]+]], ![[e4:[0-9]+]], ![[e5:[0-9]+]], ![[e6:[0-9]+]]}
 ; CHECK: ![[e0]] = !{void ()* @a, void ()* @b, i64 32}
 ; CHECK: ![[e1]] = !{void (i1)* @freq, i32 ()* @func4, i64 1030}
 ; CHECK: ![[e2]] = !{void (i1)* @freq, i32 ()* @func2, i64 410}
 ; CHECK: ![[e3]] = !{void (i1)* @freq, i32 ()* @func3, i64 150}
 ; CHECK: ![[e4]] = !{void (i1)* @freq, i32 ()* @func1, i64 10}
 ; CHECK: ![[e5]] = !{void (i1)* @freq, void ()* @a, i64 11}
 ; CHECK: ![[e6]] = !{void (i1)* @freq, void ()* @b, i64 21}
 ; CHECK-NOT: !{void (i1)* @freq, void ()* @func5, i64 1}
 ; CHECK-NOT: !{void (i1)* @freq, void ()* @func6, i64 0}

llvm/test/Linker/module-flags-8-a.ll

 ; RUN: llvm-link %s %p/module-flags-8-b.ll -S -o - | sort | FileCheck %s
 
 ; Test append-type module flags.
 
 ; CHECK: !0 = !{i32 5, !"flag-0", !1}
-; CHECK: !1 = !{i32 0, i32 0, i32 1}
+; CHECK: !1 = distinct !{i32 0, i32 0, i32 1}
 ; CHECK: !2 = !{i32 6, !"flag-1", !3}
-; CHECK: !3 = !{i32 0, i32 1, i32 2}
+; CHECK: !3 = distinct !{i32 0, i32 1, i32 2}
 ; CHECK: !llvm.module.flags = !{!0, !2}
 
 !0 = !{ i32 5, !"flag-0", !{ i32 0 } }
 !1 = !{ i32 6, !"flag-1", !{ i32 0, i32 1 } }
 
 !llvm.module.flags = !{ !0, !1 }

llvm/test/Linker/module-flags-dont-change-others.ll

 ; RUN: llvm-link %s %S/Inputs/module-flags-dont-change-others.ll -S -o - | FileCheck %s
 
 ; Test that module-flag linking doesn't change other metadata.  In particular,
 ; !named should still point at the unmodified tuples (!3, !4, and !5) that
 ; happen to also serve as module flags.
 
 ; CHECK: !named = !{!0, !1, !2, !3, !4, !5}
-; CHECK: !llvm.module.flags = !{!6, !7, !8}
+; CHECK: !llvm.module.flags = !{!6, !7, !9}
 !named = !{!0, !1, !2, !3, !4, !5}
 !llvm.module.flags = !{!3, !4, !5}
 
 ; CHECK: !0 = !{}
 ; CHECK: !1 = !{!0}
 ; CHECK: !2 = !{!0, !1}
 ; CHECK: !3 = !{i32 1, !"foo", i32 927}
 ; CHECK: !4 = !{i32 5, !"bar", !0}
 ; CHECK: !5 = !{i32 6, !"baz", !1}
 ; CHECK: !6 = !{i32 4, !"foo", i32 37}
-; CHECK: !7 = !{i32 5, !"bar", !1}
-; CHECK: !8 = !{i32 6, !"baz", !2}
+; CHECK: !7 = !{i32 5, !"bar", !8}
+; CHECK: !8 = distinct !{!0}
+; CHECK: !9 = !{i32 6, !"baz", !10}
+; CHECK: !10 = distinct !{!0, !1}
 !0 = !{}
 !1 = !{!0}
 !2 = !{!0, !1}
 !3 = !{i32 1, !"foo", i32 927}
 !4 = !{i32 5, !"bar", !0}
 !5 = !{i32 6, !"baz", !1}

llvm/test/Transforms/FunctionImport/cg_profile.ll

 ; Check that bitcast in "CG Profile" related metadata nodes (in this test case,
 ; generated during function importing in IRMover's RAUW operations) are accepted
 ; by verifier.
 ; RUN: opt -cg-profile -module-summary %s -o %t.bc
 ; RUN: opt -module-summary %p/Inputs/cg_profile.ll -o %t2.bc
 ; RUN: llvm-lto -thinlto -o %t3 %t.bc %t2.bc
 ; RUN: opt -function-import -print-imports -summary-file %t3.thinlto.bc %t.bc \
 ; RUN:   -S 2>&1 | FileCheck %s
 
 ; CHECK:      !0 = !{i32 1, !"EnableSplitLTOUnit", i32 0}
 ; CHECK-NEXT: !1 = !{i32 5, !"CG Profile", !2}
-; CHECK-NEXT: !2 = !{!3}
+; CHECK-NEXT: !2 = distinct !{!3}
 ; CHECK-NEXT: !3 = !{void ()* @foo, void (%class.A*)* bitcast (void (%class.A.0*)* @bar to void (%class.A*)*), i64 2753}
 
 target datalayout = "e-m:e-p270:32:32-p271:32:32-p272:64:64-i64:64-f80:128-n8:16:32:64-S128"
 target triple = "x86_64-unknown-linux-gnu"
 
 ; %class.A is defined differently in %p/Inputs/cg_profile.ll. This is to trigger
 ; bitcast.
 %class.A = type { i8 }

llvm/unittests/IR/MetadataTest.cpp

protected:
 
   MDNode *getNode() { return MDNode::get(Context, None); }
   MDNode *getNode(Metadata *MD) { return MDNode::get(Context, MD); }
   MDNode *getNode(Metadata *MD1, Metadata *MD2) {
     Metadata *MDs[] = {MD1, MD2};
     return MDNode::get(Context, MDs);
   }
 
-  MDTuple *getTuple() { return MDTuple::getDistinct(Context, None); }
+  MDTuple *getTuple(unsigned Capacity = 0) {
+    return MDTuple::getDistinct(Context, None, Capacity);
+  }
   DISubroutineType *getSubroutineType() {
     return DISubroutineType::getDistinct(Context, DINode::FlagZero, 0,
                                          getNode(nullptr));
   }
   DISubprogram *getSubprogram() {
     return DISubprogram::getDistinct(
         Context, nullptr, "", "", nullptr, 0, nullptr, 0, nullptr, 0, 0,
         DINode::FlagZero, DISubprogram::SPFlagZero, nullptr);
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();
+
+  // We can allocate a zero-length tuple and add elements to it.
+  EXPECT_EQ(A->getNumOperands(), 0u);
+  EXPECT_EQ(A->getCapacity(), 0u);
+
+  A->append(Value1);
+  EXPECT_EQ(A->getNumOperands(), 1u);
+  EXPECT_EQ(A->getCapacity(), 1u);
+  EXPECT_EQ(A->getOperand(0), Value1);
+
+  A->append(Value2);
+  EXPECT_EQ(A->getNumOperands(), 2u);
+  EXPECT_EQ(A->getCapacity(), 2u);
+  EXPECT_EQ(A->getOperand(0), Value1);
+  EXPECT_EQ(A->getOperand(1), Value2);
+
+  // Allocate a "small" MDnode, append a couple of values, and reserve more
+  // space for operands afterwards.
+  MDTuple *B = getTuple(/* Capacity = */ 4);
+
+  EXPECT_EQ(B->getCapacity(), 4u);
+  EXPECT_EQ(B->getNumOperands(), 0u);
+
+  Metadata *Value3 = getConstantAsMetadata();
+  Metadata *Value4 = getConstantAsMetadata();
+  Metadata *Value5 = getConstantAsMetadata();
+
+  Metadata *Ops[] = {Value3, Value4};
+  B->append(makeArrayRef(Ops, 2));
+
+  EXPECT_EQ(B->getCapacity(), 4u);
+  EXPECT_EQ(B->getNumOperands(), 2u);
+  EXPECT_EQ(B->getOperand(0), Value3);
+  EXPECT_EQ(B->getOperand(1), Value4);
+
+  B->reserve(12);
+  EXPECT_EQ(B->getCapacity(), 12u);
+  EXPECT_EQ(B->getOperand(0), Value3);
+  EXPECT_EQ(B->getOperand(1), Value4);
+
+  B->append(Value5);
+  EXPECT_EQ(B->getNumOperands(), 3u);
+  EXPECT_EQ(B->getOperand(2), Value5);
+
+  // Check that we can increase the capacity of temporary nodes as well.
+  auto Temp1 = MDTuple::getTemporary(Context, None);
+  EXPECT_EQ(Temp1->getNumOperands(), 0u);
+  EXPECT_EQ(Temp1->getCapacity(), 0u);
+
+  Temp1->append(Value1);
+  EXPECT_EQ(Temp1->getNumOperands(), 1u);
+  EXPECT_EQ(Temp1->getCapacity(), 1u);
+  EXPECT_EQ(Temp1->getOperand(0), Value1);
+
+  Temp1->reserve(12);
+  EXPECT_EQ(Temp1->getNumOperands(), 1u);
+  EXPECT_EQ(Temp1->getCapacity(), 12u);
+  EXPECT_EQ(Temp1->getOperand(0), Value1);
+
+  Temp1->append(Value2);
+  EXPECT_EQ(Temp1->getNumOperands(), 2u);
+  EXPECT_EQ(Temp1->getCapacity(), 12u);
+  EXPECT_EQ(Temp1->getOperand(1), 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(1);
+  A->append(Value1);
+  A->reserve(2);
+  EXPECT_EQ(A->getOperand(0), Value1);
+
+  auto *Value2 = getConstantAsMetadata();
+  Value *V1 = Value1->getValue();
+  Value *V2 = Value2->getValue();
+  ValueAsMetadata::handleRAUW(V1, V2);
+  EXPECT_EQ(A->getOperand(0), Value2);
+}
+
+#ifdef GTEST_HAS_DEATH_TEST
+typedef MetadataTest MDTupleAllocationDeathTest;
+TEST_F(MDTupleAllocationDeathTest, ResizeRejected) {
+  MDNode *A = getNode();
+  EXPECT_DEATH(A->reserve(1),
+               "Cannot increase the number of operands of a uniqued node");
+
+  auto *B = getFile();
+  EXPECT_DEATH(
+      B->reserve(2),
+      "Increasing the number of operands is not supported for this node kind");
+}
+#endif
+
 } // end namespace

llvm/unittests/Linker/LinkModulesTest.cpp

 #include "llvm-c/Linker.h"
 #include "llvm/ADT/STLExtras.h"
 #include "llvm/AsmParser/Parser.h"
 #include "llvm/IR/BasicBlock.h"
 #include "llvm/IR/DataLayout.h"
 #include "llvm/IR/Function.h"
 #include "llvm/IR/IRBuilder.h"
 #include "llvm/IR/Module.h"
+#include "llvm/IR/Verifier.h"
 #include "llvm/Linker/Linker.h"
 #include "llvm/Support/SourceMgr.h"
 #include "gtest/gtest.h"
 
 using namespace llvm;
 
 namespace {
 
TEST_F(LinkModuleTest, RemangleIntrinsics) {
 
   // "struct.rtx_def" from Foo and "struct.rtx_def.0" from Bar are isomorphic
   // types, so they must be uniquified by linker. Check that they use the same
   // intrinsic definition.
   Function *F = Foo->getFunction("llvm.memset.p0s_struct.rtx_defs.i32");
   ASSERT_EQ(F->getNumUses(), (unsigned)2);
 }
 
+TEST_F(LinkModuleTest, AppendModuleFlags) {
+  LLVMContext C;
+  SMDiagnostic Err;
+
+  // Link 2 modules with "append" metadata nodes. In the linked module,
+  // check that the 3rd operand has been resized and has hung off oeprands.
+
+  const char *FooStr = R"IR(
+    declare void @foo(i32, i32)
+    declare i32  @bar(i32)
+    declare i32  @baz(i32, i32)
+
+    !llvm.module.flags = !{!0}
+    !0 = !{i32 5, !"CG Profile", !1}
+    !1 = distinct !{!2, !3}
+    !2 = !{void (i32, i32)* @foo, i32 (i32)* @bar, i64 1}
+    !3 = !{void (i32, i32)* @foo, i32 (i32, i32)* @baz, i64 1}
+    )IR";
+
+  const char *BarStr = R"IR(
+    declare void @bar(i32, i32)
+    declare i32  @baz(i32)
+    declare i32  @fie(i32, i32)
+
+    !llvm.module.flags = !{!0}
+    !0 = !{i32 5, !"CG Profile", !1}
+    !1 = !{!2, !3}
+    !2 = !{void (i32, i32)* @bar, i32 (i32)* @baz, i64 1}
+    !3 = !{void (i32, i32)* @bar, i32 (i32, i32)* @fie, i64 1}
+    )IR";
+
+  std::unique_ptr<Module> Foo = parseAssemblyString(FooStr, Err, C);
+  assert(Foo);
+  const NamedMDNode *ModFlags1 = Foo->getModuleFlagsMetadata();
+  const MDNode *FirstFlag1 = ModFlags1->getOperand(0);
+  ASSERT_TRUE(FirstFlag1->getNumOperands() == 3);
+  const MDNode *MDListTuple1 = cast<MDNode>(FirstFlag1->getOperand(2).get());
+
+  std::unique_ptr<Module> Bar = parseAssemblyString(BarStr, Err, C);
+  assert(Bar);
+  const NamedMDNode *ModFlags2 = Bar->getModuleFlagsMetadata();
+  const MDNode *FirstFlag2 = ModFlags2->getOperand(0);
+  ASSERT_TRUE(FirstFlag2->getNumOperands() == 3);
+
+  bool Failed = Linker::linkModules(*Foo, std::move(Bar));
+  ASSERT_FALSE(Failed);
+
+  const NamedMDNode *ModFlags = Foo->getModuleFlagsMetadata();
+  const MDNode *FirstFlag = ModFlags->getOperand(0);
+  ASSERT_TRUE(FirstFlag->getNumOperands() == 3);
+  const MDNode *MDListTuple2 = cast<MDNode>(FirstFlag->getOperand(2).get());
+  ASSERT_TRUE(MDListTuple2->isDistinct());
+  ASSERT_TRUE(MDListTuple2->getNumOperands() == 4);
+  ASSERT_EQ(MDListTuple1, MDListTuple2);
+}
+
 } // end anonymous namespace