Store Arguments in a flat array instead of an iplist

[rnk]

Summary

This saves two pointers from Argument and eliminates some extra
allocations.

Arguments cannot be inserted or removed from a Function because that
would require changing its Type, which LLVM does not allow. Instead,
passes that change prototypes, like DeadArgElim, create a new Function
and copy over argument names and attributes. The primary benefit of
iplist is O(1) random insertion and removal. We just don't need that for
arguments, so don't use it.

[chandlerc]

include/llvm/IR/Function.h

50–51

You're not really using this in the way I would expect -- instead we use a raw pointer for the storage. We just return a const reference to this. That doesn't make a lot of sense.

I think you want to change the getArgumentList methods to operate in terms of ArrayRef, and either use this for the storage itself or not have it at all.

106–109

We already have getArgumentList?

lib/IR/Function.cpp

230–231

Why malloc?

[sanjoy]

include/llvm/IR/Argument.h

33

Do we need to store both? Why not have getArgNo return this - Parent->getArgBegin() (or equivalent)?

[chandlerc]

include/llvm/IR/Function.h

106–109

I see you're removing in another patch... Maybe rewrite the users of this in terms of arg_begin too?

[rnk]

include/llvm/IR/Argument.h

33

Sounds like a reasonable follow-up. I just added ArgNo in a previous CL, which was the minimal thing necessary to fix the non-linear behavior.

include/llvm/IR/Function.h

50–51

Oh, this is stale. Oops. I wasn't able to use OwningArrayRef because it tries to default construct its contents, and Argument doesn't have a default ctor, so... it seemed better to use malloc and do the low-level thing.

106–109

I can't, arg_begin() triggers lazy argument list creation. This is a helper intended for use inside stealArgumentListFrom, which doesn't want lazy argument list creation. This is a private method, fwiw. I could sink it to be a static helper that takes Arguments and NumArgs? We just don't have makeMutableArrayRef(...).

lib/IR/Function.cpp

230–231

Is there a way to use 'new' to allocate uninitialized memory suitable for this kind of placement new construction? I can do new char[sizeof(Argument)*NumArgs], but it didn't seem prettier. Regular array new wants a default ctor, which Argument doesn't have, and adding one would be wasteful. I just want to allocate some memory and initialize some complex, non-value type objects into it. How hard can that be? ¯\_(ツ)_/¯

[rnk]

• Delete stale typedef, sink arrayref helper

[rnk]

lib/IR/Function.cpp

230–231

Maybe you're suggesting ::operator new(...)? That'd work.

[chandlerc]

LGTM with whatever you decide about the allocator stuff.

lib/IR/Function.cpp

230–231

Is std::allocator<Argument>().allocate(NumArgs) too verbose/arcane? It has the semantics I think we want here. (And `.deallocate(...)' below.)

Anyways, I don't feel particularly strongly about this.

245–247

We should either have makeArrayRef produce a MutableArrayRef for non-const pointers or we should add a makeMutableArrayRef that accepts non-const pointers. Then I don't think you'll need this.

That can bea follow-up cleanup.

[rnk]

lib/IR/Function.cpp

230–231

Nope, sounds good, gets rid of the reinterpret_cast. Thanks!

245–247

I think we want the second, or we'll need to add a conversion from MutableArrayRef<T> to ArrayRef<T> to avoid breaking callers of makeArrayRef with non-const pointers. MutableArrayRef is pretty niche, though, so I'm gonna leave it alone for now.

include/llvm/IR/Argument.h

 
 #include "llvm/ADT/Twine.h"
 #include "llvm/ADT/ilist_node.h"
 #include "llvm/IR/Attributes.h"
 #include "llvm/IR/Value.h"
 
 namespace llvm {
 
-template <typename NodeTy> class SymbolTableListTraits;
-
 /// This class represents an incoming formal argument to a Function. A formal
 /// argument, since it is ``formal'', does not contain an actual value but
 /// instead represents the type, argument number, and attributes of an argument
 /// for a specific function. When used in the body of said function, the
 /// argument of course represents the value of the actual argument that the
 /// function was called with.
-class Argument : public Value, public ilist_node<Argument> {
+class Argument : public Value {
   virtual void anchor();
   Function *Parent;
   unsigned ArgNo;
 
-  friend class SymbolTableListTraits<Argument>;
+  friend class Function;
   void setParent(Function *parent);
 
 public:
   /// Argument constructor.
-  explicit Argument(Type *Ty, const Twine &Name = "", unsigned ArgNo = 0);
+  explicit Argument(Type *Ty, const Twine &Name = "", Function *F = nullptr,
+                    unsigned ArgNo = 0);
 
   inline const Function *getParent() const { return Parent; }
   inline       Function *getParent()       { return Parent; }
 
   /// Return the index of this formal argument in its containing function.
   ///
   /// For example in "void foo(int a, float b)" a is 0 and b is 1.
-  unsigned getArgNo() const { return ArgNo; }
+  unsigned getArgNo() const {
+    assert(Parent && "can't get number of unparented arg");
+    return ArgNo;
+  }
 
   /// Return true if this argument has the nonnull attribute. Also returns true
   /// if at least one byte is known to be dereferenceable and the pointer is in
   /// addrspace(0).
   bool hasNonNullAttr() const;
 
   /// If this argument has the dereferenceable attribute, return the number of
   /// bytes known to be dereferenceable. Otherwise, zero is returned.

include/llvm/IR/Function.h

 
 template <typename T> class Optional;
 class AssemblyAnnotationWriter;
 class FunctionType;
 class LLVMContext;
 class DISubprogram;
 
 class Function : public GlobalObject, public ilist_node<Function> {
 public:
-  typedef SymbolTableList<Argument> ArgumentListType;
   typedef SymbolTableList<BasicBlock> BasicBlockListType;
 
   // BasicBlock iterators...
   typedef BasicBlockListType::iterator iterator;
   typedef BasicBlockListType::const_iterator const_iterator;
 
-  typedef ArgumentListType::iterator arg_iterator;
-  typedef ArgumentListType::const_iterator const_arg_iterator;
+  typedef Argument *arg_iterator;
+  typedef const Argument *const_arg_iterator;
 
 private:
   // Important things that make up a function!
   BasicBlockListType  BasicBlocks;        ///< The basic blocks
-  mutable ArgumentListType ArgumentList;  ///< The formal arguments
+  mutable Argument *Arguments;            ///< The formal arguments
+  size_t NumArgs;
   std::unique_ptr<ValueSymbolTable>
       SymTab;                             ///< Symbol table of args/instructions
   AttributeSet AttributeSets;             ///< Parameter attributes
 
   /*
    * Value::SubclassData
    *
    * bit 0      : HasLazyArguments

 private:
   void CheckLazyArguments() const {
     if (hasLazyArguments())
       BuildLazyArguments();
   }
 
   void BuildLazyArguments() const;
 
+  void clearArguments();
+
   /// Function ctor - If the (optional) Module argument is specified, the
   /// function is automatically inserted into the end of the function list for
   /// the module.
   ///
   Function(FunctionType *Ty, LinkageTypes Linkage,
            const Twine &N = "", Module *M = nullptr);
 
 public:
   Function(const Function&) = delete;
   void operator=(const Function&) = delete;
public:
   void eraseFromParent() override;
 
   /// Steal arguments from another function.
   ///
   /// Drop this function's arguments and splice in the ones from \c Src.
   /// Requires that this has no function body.
   void stealArgumentListFrom(Function &Src);
 
-  static ArgumentListType Function::*getSublistAccess(Argument*) {
-    return &Function::ArgumentList;
-  }
-
   /// Get the underlying elements of the Function... the basic block list is
   /// empty for external functions.
   ///
   const BasicBlockListType &getBasicBlockList() const { return BasicBlocks; }
         BasicBlockListType &getBasicBlockList()       { return BasicBlocks; }
 
   static BasicBlockListType Function::*getSublistAccess(BasicBlock*) {
     return &Function::BasicBlocks;
public:
   const BasicBlock        &back() const { return BasicBlocks.back();  }
         BasicBlock        &back()       { return BasicBlocks.back();  }
 
 /// @name Function Argument Iteration
 /// @{
 
   arg_iterator arg_begin() {
     CheckLazyArguments();
-    return ArgumentList.begin();
+    return Arguments;
   }
   const_arg_iterator arg_begin() const {
     CheckLazyArguments();
-    return ArgumentList.begin();
+    return Arguments;
   }
 
   arg_iterator arg_end() {
     CheckLazyArguments();
-    return ArgumentList.end();
+    return Arguments + NumArgs;
   }
   const_arg_iterator arg_end() const {
     CheckLazyArguments();
-    return ArgumentList.end();
+    return Arguments + NumArgs;
   }
 
   iterator_range<arg_iterator> args() {
     return make_range(arg_begin(), arg_end());
   }
   iterator_range<const_arg_iterator> args() const {
     return make_range(arg_begin(), arg_end());
   }
 
 /// @}
 
-  size_t arg_size() const { return getFunctionType()->getNumParams(); }
+  size_t arg_size() const { return NumArgs; }
   bool arg_empty() const { return arg_size() == 0; }
 
   /// \brief Check whether this function has a personality function.
   bool hasPersonalityFn() const {
     return getSubclassDataFromValue() & (1<<3);
   }
 
   /// \brief Get the personality function associated with this function.

lib/IR/Core.cpp

 void LLVMGetParams(LLVMValueRef FnRef, LLVMValueRef *ParamRefs) {
   Function *Fn = unwrap<Function>(FnRef);
   for (Function::arg_iterator I = Fn->arg_begin(),
                               E = Fn->arg_end(); I != E; I++)
     *ParamRefs++ = wrap(&*I);
 }
 
 LLVMValueRef LLVMGetParam(LLVMValueRef FnRef, unsigned index) {
-  Function::arg_iterator AI = unwrap<Function>(FnRef)->arg_begin();
-  while (index --> 0)
-    AI++;
-  return wrap(&*AI);
+  Function *Fn = unwrap<Function>(FnRef);
+  return wrap(&Fn->arg_begin()[index]);
 }
 
 LLVMValueRef LLVMGetParamParent(LLVMValueRef V) {
   return wrap(unwrap<Argument>(V)->getParent());
 }
 
 LLVMValueRef LLVMGetFirstParam(LLVMValueRef Fn) {
   Function *Func = unwrap<Function>(Fn);
   Function::arg_iterator I = Func->arg_begin();
   if (I == Func->arg_end())
     return nullptr;
   return wrap(&*I);
 }
 
 LLVMValueRef LLVMGetLastParam(LLVMValueRef Fn) {
   Function *Func = unwrap<Function>(Fn);
   Function::arg_iterator I = Func->arg_end();
   if (I == Func->arg_begin())
     return nullptr;
   return wrap(&*--I);
 }
 
 LLVMValueRef LLVMGetNextParam(LLVMValueRef Arg) {
   Argument *A = unwrap<Argument>(Arg);
-  Function::arg_iterator I(A);
-  if (++I == A->getParent()->arg_end())
+  Function *Fn = A->getParent();
+  if (A->getArgNo() + 1 >= Fn->arg_size())
     return nullptr;
-  return wrap(&*I);
+  return wrap(&Fn->arg_begin()[A->getArgNo() + 1]);
 }
 
 LLVMValueRef LLVMGetPreviousParam(LLVMValueRef Arg) {
   Argument *A = unwrap<Argument>(Arg);
-  Function::arg_iterator I(A);
-  if (I == A->getParent()->arg_begin())
+  if (A->getArgNo() == 0)
     return nullptr;
-  return wrap(&*--I);
+  return wrap(&A->getParent()->arg_begin()[A->getArgNo() - 1]);
 }
 
 void LLVMSetParamAlignment(LLVMValueRef Arg, unsigned align) {
   Argument *A = unwrap<Argument>(Arg);
   AttrBuilder B;
   B.addAlignmentAttr(align);
   A->addAttr(AttributeSet::get(A->getContext(),A->getArgNo() + 1, B));
 }

lib/IR/Function.cpp

 #include "llvm/IR/LLVMContext.h"
 #include "llvm/IR/MDBuilder.h"
 #include "llvm/IR/Metadata.h"
 #include "llvm/IR/Module.h"
 using namespace llvm;
 
 // Explicit instantiations of SymbolTableListTraits since some of the methods
 // are not in the public header file...
-template class llvm::SymbolTableListTraits<Argument>;
 template class llvm::SymbolTableListTraits<BasicBlock>;
 
 //===----------------------------------------------------------------------===//
 // Argument Implementation
 //===----------------------------------------------------------------------===//
 
 void Argument::anchor() { }
 
-Argument::Argument(Type *Ty, const Twine &Name, unsigned ArgNo)
-    : Value(Ty, Value::ArgumentVal), Parent(nullptr), ArgNo(ArgNo) {
+Argument::Argument(Type *Ty, const Twine &Name, Function *Par, unsigned ArgNo)
+    : Value(Ty, Value::ArgumentVal), Parent(Par), ArgNo(ArgNo) {
   setName(Name);
 }
 
 void Argument::setParent(Function *parent) {
   Parent = parent;
 }
 
 bool Argument::hasNonNullAttr() const {

 
 //===----------------------------------------------------------------------===//
 // Function Implementation
 //===----------------------------------------------------------------------===//
 
 Function::Function(FunctionType *Ty, LinkageTypes Linkage, const Twine &name,
                    Module *ParentModule)
     : GlobalObject(Ty, Value::FunctionVal,
-                   OperandTraits<Function>::op_begin(this), 0, Linkage, name) {
+                   OperandTraits<Function>::op_begin(this), 0, Linkage, name),
+      Arguments(nullptr), NumArgs(Ty->getNumParams()) {
   assert(FunctionType::isValidReturnType(getReturnType()) &&
          "invalid return type");
   setGlobalObjectSubClassData(0);
 
   // We only need a symbol table for a function if the context keeps value names
   if (!getContext().shouldDiscardValueNames())
     SymTab = make_unique<ValueSymbolTable>();
 
Function::Function(FunctionType *Ty, LinkageTypes Linkage, const Twine &name,
   if (IntID)
     setAttributes(Intrinsic::getAttributes(getContext(), IntID));
 }
 
 Function::~Function() {
   dropAllReferences();    // After this it is safe to delete instructions.
 
   // Delete all of the method arguments and unlink from symbol table...
-  ArgumentList.clear();
+  if (Arguments)
+    clearArguments();
 
   // Remove the function from the on-the-side GC table.
   clearGC();
 }
 
 void Function::BuildLazyArguments() const {
   // Create the arguments vector, all arguments start out unnamed.
-  FunctionType *FT = getFunctionType();
-  for (unsigned i = 0, e = FT->getNumParams(); i != e; ++i) {
-    assert(!FT->getParamType(i)->isVoidTy() &&
-           "Cannot have void typed arguments!");
-    ArgumentList.push_back(
-        new Argument(FT->getParamType(i), "", i));
+  auto *FT = getFunctionType();
+  if (NumArgs > 0) {
+    Arguments =
+        reinterpret_cast<Argument *>(malloc(sizeof(Argument) * NumArgs));
+    for (unsigned i = 0, e = NumArgs; i != e; ++i) {
+      Type *ArgTy = FT->getParamType(i);
+      assert(!ArgTy->isVoidTy() && "Cannot have void typed arguments!");
+      new (Arguments + i) Argument(ArgTy, "", const_cast<Function *>(this), i);
+    }
   }
 
   // Clear the lazy arguments bit.
   unsigned SDC = getSubclassDataFromValue();
   const_cast<Function*>(this)->setValueSubclassData(SDC &= ~(1<<0));
+  assert(!hasLazyArguments());
+}
+
+static MutableArrayRef<Argument> makeArgArray(Argument *Args, size_t Count) {
+  return MutableArrayRef<Argument>(Args, Count);
+}
+
+void Function::clearArguments() {
+  for (Argument &A : makeArgArray(Arguments, NumArgs)) {
+    A.setName("");
+    A.~Argument();
+  }
+  free(Arguments);
+  Arguments = nullptr;
 }
 
 void Function::stealArgumentListFrom(Function &Src) {
   assert(isDeclaration() && "Expected no references to current arguments");
 
   // Drop the current arguments, if any, and set the lazy argument bit.
   if (!hasLazyArguments()) {
-    assert(llvm::all_of(ArgumentList,
+    assert(llvm::all_of(makeArgArray(Arguments, NumArgs),
                         [](const Argument &A) { return A.use_empty(); }) &&
            "Expected arguments to be unused in declaration");
-    ArgumentList.clear();
+    clearArguments();
     setValueSubclassData(getSubclassDataFromValue() | (1 << 0));
   }
 
   // Nothing to steal if Src has lazy arguments.
   if (Src.hasLazyArguments())
     return;
 
   // Steal arguments from Src, and fix the lazy argument bits.
-  ArgumentList.splice(ArgumentList.end(), Src.ArgumentList);
+  assert(arg_size() == Src.arg_size());
+  Arguments = Src.Arguments;
+  Src.Arguments = nullptr;
+  for (Argument &A : makeArgArray(Arguments, NumArgs)) {
+    // FIXME: This does the work of transferNodesFromList inefficiently.
+    SmallString<128> Name;
+    if (A.hasName())
+      Name = A.getName();
+    if (!Name.empty())
+      A.setName("");
+    A.setParent(this);
+    if (!Name.empty())
+      A.setName(Name);
+  }
+
   setValueSubclassData(getSubclassDataFromValue() & ~(1 << 0));
+  assert(!hasLazyArguments());
   Src.setValueSubclassData(Src.getSubclassDataFromValue() | (1 << 0));
 }
 
 // dropAllReferences() - This function causes all the subinstructions to "let
 // go" of all references that they are maintaining.  This allows one to
 // 'delete' a whole class at a time, even though there may be circular
 // references... first all references are dropped, and all use counts go to
 // zero.  Then everything is deleted for real.  Note that no operations are