Make Argument::getArgNo() constant time, not O(#args)

[rnk]

Summary

getArgNo is actually hot in LLVM, because its how we check for
attributes on arguments:

bool Argument::hasNonNullAttr() const {
  if (!getType()->isPointerTy()) return false;
  if (getParent()->getAttributes().
        hasAttribute(getArgNo()+1, Attribute::NonNull))
    return true;

It actually shows up as the 23rd hottest leaf function in a 13s sample
of LTO of llc.

This grows Argument by four bytes, but I have another pending patch to
shrink it by removing its ilist_node base.

[chandlerc]

This seems like a very reasonable tradeoff and a clean patch. Especially reasonable given the subsequent improvements. Ship it.

[mehdi_amini]

It actually shows up as the 23rd hottest leaf function in a 13s sample of LTO of llc.

Impressive! Nice finding :)

[sabuasal]

Hi,
This seems like a nice optimization.

I was just wondering if it is a good idea to silently push this with a default argument for ArgNo. there is other locations in LLVM where an Argument object is constructed with the default parameter without realizing that this will break their getArgNo.

for example:
git grep -n "new Argument("
lib/AsmParser/LLParser.cpp:2533: FwdVal = new Argument(Ty, Name);
lib/AsmParser/LLParser.cpp:2573: FwdVal = new Argument(Ty);
lib/Bitcode/Reader/ValueList.cpp:116: Value *V = new Argument(Ty);

[rnk]

In D31057#711679, @sabuasal wrote:

Hi,
This seems like a nice optimization.

Thanks!

I was just wondering if it is a good idea to silently push this with a default argument for ArgNo. there is other locations in LLVM where an Argument object is constructed with the default parameter without realizing that this will break their getArgNo.

for example:
git grep -n "new Argument("
lib/AsmParser/LLParser.cpp:2533: FwdVal = new Argument(Ty, Name);
lib/AsmParser/LLParser.cpp:2573: FwdVal = new Argument(Ty);
lib/Bitcode/Reader/ValueList.cpp:116: Value *V = new Argument(Ty);

These arguments are all only ever used to forward declare a Value. They never have a parent function. getArgNo() will return 0, but if getParent() returns null, what does that really mean?

After searching for calls to new Argument across clang and LLVM, I realized that everyone uses the code in Function to construct the argument list. Perhaps one nice side effect of eliminating this field and computing getArgNo() from getParent() is that it would be impossible to get the argument number of an unparented argument. That seems like a better argument for doing it than the memory usage of this field.

llvm/trunk/include/llvm/IR/Argument.h

 /// 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> {
   virtual void anchor();
   Function *Parent;
+  unsigned ArgNo;
 
   friend class SymbolTableListTraits<Argument>;
   void setParent(Function *parent);
 
 public:
   /// If \p F is specified, the argument is inserted at the end of the argument
   /// list for \p F.
-  explicit Argument(Type *Ty, const Twine &Name = "", Function *F = nullptr);
+  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;
+  unsigned getArgNo() const { 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.

llvm/trunk/lib/IR/Function.cpp

 template class llvm::SymbolTableListTraits<BasicBlock>;
 
 //===----------------------------------------------------------------------===//
 // Argument Implementation
 //===----------------------------------------------------------------------===//
 
 void Argument::anchor() { }
 
-Argument::Argument(Type *Ty, const Twine &Name, Function *Par)
-  : Value(Ty, Value::ArgumentVal) {
+Argument::Argument(Type *Ty, const Twine &Name, Function *Par, unsigned ArgNo)
+  : Value(Ty, Value::ArgumentVal), ArgNo(ArgNo) {
   Parent = nullptr;
 
   if (Par)
     Par->getArgumentList().push_back(this);
   setName(Name);
 }
 
 void Argument::setParent(Function *parent) {
   Parent = parent;
 }
 
-unsigned Argument::getArgNo() const {
-  const Function *F = getParent();
-  assert(F && "Argument is not in a function");
-
-  Function::const_arg_iterator AI = F->arg_begin();
-  unsigned ArgIdx = 0;
-  for (; &*AI != this; ++AI)
-    ++ArgIdx;
-
-  return ArgIdx;
-}
-
 bool Argument::hasNonNullAttr() const {
   if (!getType()->isPointerTy()) return false;
   if (getParent()->getAttributes().
         hasAttribute(getArgNo()+1, Attribute::NonNull))
     return true;
   else if (getDereferenceableBytes() > 0 &&
            getType()->getPointerAddressSpace() == 0)
     return true;

 }
 
 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)));
+    ArgumentList.push_back(
+        new Argument(FT->getParamType(i), "", nullptr, i));
   }
 
   // Clear the lazy arguments bit.
   unsigned SDC = getSubclassDataFromValue();
   const_cast<Function*>(this)->setValueSubclassData(SDC &= ~(1<<0));
 }
 
 void Function::stealArgumentListFrom(Function &Src) {