[IR] Teach `llvm::User` to co-allocate a descriptor.

[sanjoy]

Summary

With this change, subclasses of llvm::User will be able to co-allocate
a variable number of bytes (called a "descriptor") with the llvm::User
instance. The co-allocated descriptor can later be accessed using
llvm::User::getDescriptor. This will be used in later changes to
implement operand bundles.

This change steals one bit from NumUserOperands, but given that it is
still 28 bits wide I don't think this will be a practical issue.

This change does not allow allocating hung off uses with descriptors.
This only for simplicity, not for any fundamental reason; and we can
easily add this functionality later if needed.

[JosephTremoulet]

include/llvm/IR/User.h

49–57

I wonder what sort of alignment guarantees this should make / what sort of alignment expectations it should set. The end of this allocation will always be 4 bytes before a pointer-aligned address, correct? Maybe just note that in the comment so that callers can figure out how to get pointer alignment if they want it?

[sanjoy]

include/llvm/IR/User.h

49–57

Replied in D12456 (basically I'll move the assertions here, and add a top level comment).

[sanjoy]

I don't know why this hasn't showed up on llvm-commits yet, but I've
replied to the review on phabricator.

[sanjoy]

Address review.

[JosephTremoulet]

Looks good to me (not that I'm an expert on this code...), thanks for the update.

[pete]

This is just a question, not intended to block the commit if someone else gives a LGTM.

Have you considered making use of 'hung off uses' instead of adding DescBytes to new?

It would take a little work to change 'hung off uses' to actually be 'hung off bytes', and i haven't looked to see how possible that is, but it feels to me like it should be considered.

This also has the advantage of moving the desc bytes handling out of new so that all User's don't pay the price for checking them in new, and instead the rare case of meeting extra bytes can get them only on request.

Just my 2c though.

Cheers,
Pete

[sanjoy]

In D12455#238526, @pete wrote:

This is just a question, not intended to block the commit if someone else gives a LGTM.

Have you considered making use of 'hung off uses' instead of adding DescBytes to new?

It would take a little work to change 'hung off uses' to actually be 'hung off bytes', and i haven't looked to see how possible that is, but it feels to me like it should be considered.

This also has the advantage of moving the desc bytes handling out of new so that all User's don't pay the price for checking them in new, and instead the rare case of meeting extra bytes can get them only on request.

Is the only motivation for making the descriptor bytes be hung off
that we won't have to check DescriptorBytes == 0 in operator new
(I cannot think of anything else that hung off descriptor bytes will
help)?

If so, I think there is an easier way to fix this -- I can just
overload operator new into a version that takes the
DescriptorBytes argument, and a version that does not. Most of
Users will call the latter, and won't have to pay the penalty of
checking DescriptorBytes == 0. There will still be the penalty of
setting Obj->HasDescriptor = 0 in the latter, but I'd expect that to
be folded into whatever operator new does to set
Obj->HasHungOffUses = false. Does this sound reasonable to you?

[pete]

In D12455#238662, @sanjoy wrote:

In D12455#238526, @pete wrote:

This is just a question, not intended to block the commit if someone else gives a LGTM.

Have you considered making use of 'hung off uses' instead of adding DescBytes to new?

It would take a little work to change 'hung off uses' to actually be 'hung off bytes', and i haven't looked to see how possible that is, but it feels to me like it should be considered.

This also has the advantage of moving the desc bytes handling out of new so that all User's don't pay the price for checking them in new, and instead the rare case of meeting extra bytes can get them only on request.

Is the only motivation for making the descriptor bytes be hung off
that we won't have to check DescriptorBytes == 0 in operator new
(I cannot think of anything else that hung off descriptor bytes will
help)?

If so, I think there is an easier way to fix this -- I can just
overload operator new into a version that takes the
DescriptorBytes argument, and a version that does not. Most of
Users will call the latter, and won't have to pay the penalty of
checking DescriptorBytes == 0. There will still be the penalty of
setting Obj->HasDescriptor = 0 in the latter, but I'd expect that to
be folded into whatever operator new does to set
Obj->HasHungOffUses = false. Does this sound reasonable to you?

Yeah, that was the only motivation. Like I said, shouldn't block things if you think it'll be ok.

Saying that, I do prefer your suggestion to overload operator new. I'd be totally fine with that.

Thanks!

[pete]

Just noticed there was a LGTM already.

FWIW, i'm also happy to give a LGTM with/without the overloaded operator new. Up to you how you proceed on that.

[sanjoy]

• specialize operator new (addressing @pete's review comment)
• address @majnemer's off-line review comment -- return an ArrayRef and not an std::pair

[sanjoy]

@pete - can you please take a look to see if you're okay with how I've specialized operator new?

[sanjoy]

• add inline keyword to allocateFixedOperandUser

include/llvm/IR/User.h

 
 protected:
   /// Allocate a User with an operand pointer co-allocated.
   ///
   /// This is used for subclasses which need to allocate a variable number
   /// of operands, ie, 'hung off uses'.
   void *operator new(size_t Size);
 
-  /// Allocate a User with the operands co-allocated.
+  /// Allocate a User with the operands co-allocated.  If DescBytes is non-zero
+  /// then allocate an additional DescBytes bytes before the operands. These
+  /// bytes can be accessed by calling getDescriptor.
+  ///
+  /// DescBytes needs to be divisible by sizeof(void *).  The allocated
+  /// descriptor, if any, is aligned to sizeof(void *) bytes.
   ///
   /// This is used for subclasses which have a fixed number of operands.
-  void *operator new(size_t Size, unsigned Us);
+  void *operator new(size_t Size, unsigned Us, unsigned DescBytes = 0);
 
   User(Type *ty, unsigned vty, Use *OpList, unsigned NumOps)
       : Value(ty, vty) {
     assert(NumOps < (1u << NumUserOperandsBits) && "Too many operands");
     NumUserOperands = NumOps;
     // If we have hung off uses, then the operand list should initially be
     // null.
     assert((!HasHungOffUses || !getOperandList()) &&
public:
   }
   Use &getOperandUse(unsigned i) {
     assert(i < NumUserOperands && "getOperandUse() out of range!");
     return getOperandList()[i];
   }
 
   unsigned getNumOperands() const { return NumUserOperands; }
 
+  /// Returns the descriptor co-allocated with this User instance as a range of
+  /// bytes [Begin, End).
+  std::pair<const uint8_t *, const uint8_t *> getDescriptor() const;
+
+  /// Returns the descriptor co-allocated with this User instance as a range of
+  /// bytes [Begin, End).
+  std::pair<uint8_t *, uint8_t *> getDescriptor();
+
   /// Set the number of operands on a GlobalVariable.
   ///
   /// GlobalVariable always allocates space for a single operands, but
   /// doesn't always use it.
   ///
   /// FIXME: As that the number of operands is used to find the start of
   /// the allocated memory in operator delete, we need to always think we have
   /// 1 operand before delete.

include/llvm/IR/Value.h

protected:
   /// any.
   ///
   /// This is stored here to save space in User on 64-bit hosts.  Since most
   /// instances of Value have operands, 32-bit hosts aren't significantly
   /// affected.
   ///
   /// Note, this should *NOT* be used directly by any class other than User.
   /// User uses this value to find the Use list.
-  enum : unsigned { NumUserOperandsBits = 29 };
+  enum : unsigned { NumUserOperandsBits = 28 };
   unsigned NumUserOperands : NumUserOperandsBits;
 
   bool IsUsedByMD : 1;
   bool HasName : 1;
   bool HasHungOffUses : 1;
+  bool HasDescriptor : 1;
 
 private:
   template <typename UseT> // UseT == 'Use' or 'const Use'
   class use_iterator_impl
       : public std::iterator<std::forward_iterator_tag, UseT *> {
     UseT *U;
     explicit use_iterator_impl(UseT *u) : U(u) {}
     friend class Value;

lib/IR/User.cpp

auto *OldPtr =
         reinterpret_cast<char *>(OldOps + OldNumUses) + sizeof(Use::UserRef);
     auto *NewPtr =
         reinterpret_cast<char *>(NewOps + NewNumUses) + sizeof(Use::UserRef);
     std::copy(OldPtr, OldPtr + (OldNumUses * sizeof(BasicBlock *)), NewPtr);
   }
   Use::zap(OldOps, OldOps + OldNumUses, true);
 }
 
+
+// This is a private struct used by `User` to track the co-allocated descriptor
+// section.
+struct DescriptorInfo {
+  intptr_t SizeInBytes;
+};
+
+std::pair<const uint8_t *, const uint8_t *> User::getDescriptor() const {
+  return const_cast<User *>(this)->getDescriptor();
+}
+
+std::pair<uint8_t *, uint8_t *> User::getDescriptor() {
+  assert(HasDescriptor && "Don't call otherwise!");
+  assert(!HasHungOffUses && "Invariant!");
+
+  auto *DI = reinterpret_cast<DescriptorInfo *>(getIntrusiveOperands()) - 1;
+  assert(DI->SizeInBytes != 0 && "Should not have had a descriptor otherwise!");
+
+  return std::make_pair(reinterpret_cast<uint8_t *>(DI) - DI->SizeInBytes,
+                        reinterpret_cast<uint8_t *>(DI));
+}
+
 //===----------------------------------------------------------------------===//
 //                         User operator new Implementations
 //===----------------------------------------------------------------------===//
 
-void *User::operator new(size_t Size, unsigned Us) {
+void *User::operator new(size_t Size, unsigned Us, unsigned DescBytes) {
   assert(Us < (1u << NumUserOperandsBits) && "Too many operands");
-  void *Storage = ::operator new(Size + sizeof(Use) * Us);
-  Use *Start = static_cast<Use*>(Storage);
+
+  static_assert(sizeof(DescriptorInfo) % sizeof(void *) == 0, "Required below");
+
+  unsigned DescBytesToAllocate =
+      DescBytes == 0 ? 0 : (DescBytes + sizeof(DescriptorInfo));
+  assert(DescBytesToAllocate % sizeof(void *) == 0 &&
+         "We need this to satisfy alignment constraints for Uses");
+
+  uint8_t *Storage = static_cast<uint8_t *>(
+      ::operator new(Size + sizeof(Use) * Us + DescBytesToAllocate));
+  Use *Start = reinterpret_cast<Use *>(Storage + DescBytesToAllocate);
   Use *End = Start + Us;
   User *Obj = reinterpret_cast<User*>(End);
   Obj->NumUserOperands = Us;
   Obj->HasHungOffUses = false;
+  Obj->HasDescriptor = DescBytes != 0;
   Use::initTags(Start, End);
+
+  if (DescBytes != 0) {
+    auto *DescInfo = reinterpret_cast<DescriptorInfo *>(Storage + DescBytes);
+    DescInfo->SizeInBytes = DescBytes;
+  }
+
   return Obj;
 }
 
 void *User::operator new(size_t Size) {
   // Allocate space for a single Use*
   void *Storage = ::operator new(Size + sizeof(Use *));
   Use **HungOffOperandList = static_cast<Use **>(Storage);
   User *Obj = reinterpret_cast<User *>(HungOffOperandList + 1);
   Obj->NumUserOperands = 0;
   Obj->HasHungOffUses = true;
+  Obj->HasDescriptor = false;
   *HungOffOperandList = nullptr;
   return Obj;
 }
 
 //===----------------------------------------------------------------------===//
 //                         User operator delete Implementation
 //===----------------------------------------------------------------------===//
 
 void User::operator delete(void *Usr) {
   // Hung off uses use a single Use* before the User, while other subclasses
   // use a Use[] allocated prior to the user.
   User *Obj = static_cast<User *>(Usr);
   if (Obj->HasHungOffUses) {
+    assert(!Obj->HasDescriptor && "not supported!");
+
     Use **HungOffOperandList = static_cast<Use **>(Usr) - 1;
     // drop the hung off uses.
     Use::zap(*HungOffOperandList, *HungOffOperandList + Obj->NumUserOperands,
              /* Delete */ true);
     ::operator delete(HungOffOperandList);
+  } else if (Obj->HasDescriptor) {
+    Use *UseBegin = static_cast<Use *>(Usr) - Obj->NumUserOperands;
+    Use::zap(UseBegin, UseBegin + Obj->NumUserOperands, /* Delete */ false);
+
+    auto *DI = reinterpret_cast<DescriptorInfo *>(UseBegin) - 1;
+    uint8_t *Storage = reinterpret_cast<uint8_t *>(DI) - DI->SizeInBytes;
+    ::operator delete(Storage);
   } else {
     Use *Storage = static_cast<Use *>(Usr) - Obj->NumUserOperands;
     Use::zap(Storage, Storage + Obj->NumUserOperands,
              /* Delete */ false);
     ::operator delete(Storage);
   }
 }