Speed up Function::isIntrinsic() by adding a bit to GlobalValue. NFC

[jlebar]

Summary

Previously isIntrinsic() called getName(). This involves a hashtable
lookup, so is nontrivially expensive. And isIntrinsic() is called
frequently, particularly by dyn_cast<IntrinsicInstr>.

This patch steals a bit of IntID and uses that to store whether or not
getName() starts with "llvm."

[jlebar]

I reverted the old change in rL277087.

[jlebar]

Justin Bogner wrote in an email to the list:

I'm a bit less comfortable with this change than I was with the other
one - it's more of a straight performance hack this way, whereas the
other way fit better in a future where target-specific intrinsics are
more of a first class idea.

I'll let others comment on whether or not this is worth it as a
hopefully temporary thing for the performance gain in the short term.

Anyone else want to chime in here? To me it seems like a relatively simple change that gets us a substantial win, but I hear Justin B.'s position as well.

[rnk]

In D22949#518862, @jlebar wrote:

Justin Bogner wrote in an email to the list:

I'm a bit less comfortable with this change than I was with the other
one - it's more of a straight performance hack this way, whereas the
other way fit better in a future where target-specific intrinsics are
more of a first class idea.

Do you think we should move more towards LLVM having a single enum of all target intrinsics, or more towards a place where LLVM has target neutral intrinsics, and then there is a separate target-specific intrinsic ID space that mid-level optimizers can't know about?

This change actually seems like a step towards that world, which the AMDGPU backend is already half-in: all intrinsics are named "llvm.*" and many of them are not included in Intrinsic::ID.

Maybe in the long run we should move all target intrinsics out of include/llvm/IR/Intrinsics*.td, and down into lib/Target. We'd use TargetIntrinsicInfo to look up the ID. Then we can go back to the old, non-bitfield solution. It also makes it easier for us to compile out the intrinsic name to ID tables for disabled targets, which I think @beanz wanted to do. I don't think IR can talk to Target, so we probably can't do this the obvious way.

[jlebar]

Sean Silva wrote on the list:

Sorry if I missed it, but do you have perf measurements posted somewhere?

Sorry, those were in the patch for the last way I tried to do this. It's good for a 1.5% e2e speedup compiling an Eigen benchmark.

[beanz]

In D22949#519623, @rnk wrote:

which I think @beanz wanted to do.

@bogner has taken over my primary interests in that. In general I think pushing target-specific things (like intrinsics) into targets is a really great idea. I have this pipe dream of someday being able to make dynamically loadable targets, which I think would be really cool.

[chandlerc]

LGTM, let's ship it.

I alse hear Justin's concern here, especially what he wrote up on the mailing list. However, I like one thing he said: this will essentially get reverted if/when we go down that path. That seems totally fine to me considering how isolated this change is. When the time comes, it'll be easy and transparent to rip out. I think the performance hack in the interim is worth it, and will also keep us honest as we explore options to fix intrinsics in a more fundamental way by holding the higher performance bar.

-Chandler

[rnk]

Also, this comment in Value.h could use an update:

/// \brief Return a constant reference to the value's name.
///
/// This is cheap and guaranteed to return the same reference as long as the
/// value is not modified.
StringRef getName() const;

A hash table lookup is only cheap in grad school.

llvm/trunk/include/llvm/IR/GlobalValue.h

145 ↗

(On Diff #82623)

Please use unsigned so this doesn't grow Value on Windows. This program compiles without error with MSVC:

enum IntrinsicID : unsigned { ID0 = 0 };
struct Foo { IntrinsicID id : 31; bool bit : 1; };
struct Bar { IntrinsicID id : 31; unsigned bit : 1; };
static_assert(sizeof(Foo) == 8, "");
static_assert(sizeof(Bar) == 4, "");

include/llvm/IR/Function.h

public:
 
   /// getIntrinsicID - This method returns the ID number of the specified
   /// function, or Intrinsic::not_intrinsic if the function is not an
   /// intrinsic, or if the pointer is null.  This value is always defined to be
   /// zero to allow easy checking for whether a function is intrinsic or not.
   /// The particular intrinsic functions which correspond to this value are
   /// defined in llvm/Intrinsics.h.
   Intrinsic::ID getIntrinsicID() const LLVM_READONLY { return IntID; }
-  bool isIntrinsic() const { return getName().startswith("llvm."); }
+
+  /// isIntrinsic - Returns true if the function's name starts with "llvm.".
+  /// It's possible for this function to return true while getIntrinsicID()
+  /// returns Intrinsic::not_intrinsic!
+  bool isIntrinsic() const { return HasLLVMReservedName; }
 
   /// \brief Recalculate the ID for this function if it is an Intrinsic defined
   /// in llvm/Intrinsics.h.  Sets the intrinsic ID to Intrinsic::not_intrinsic
   /// if the name of this function does not match an intrinsic in that header.
   /// Note, this method does not need to be called directly, as it is called
   /// from Value::setName() whenever the name of this function changes.
   void recalculateIntrinsicID();
 

include/llvm/IR/GlobalValue.h

 
 protected:
   GlobalValue(Type *Ty, ValueTy VTy, Use *Ops, unsigned NumOps,
               LinkageTypes Linkage, const Twine &Name, unsigned AddressSpace)
       : Constant(PointerType::get(Ty, AddressSpace), VTy, Ops, NumOps),
         ValueType(Ty), Linkage(Linkage), Visibility(DefaultVisibility),
         UnnamedAddrVal(unsigned(UnnamedAddr::None)),
         DllStorageClass(DefaultStorageClass), ThreadLocal(NotThreadLocal),
-        IntID((Intrinsic::ID)0U), Parent(nullptr) {
+        IntID((Intrinsic::ID)0U), HasLLVMReservedName(false), Parent(nullptr) {
     setName(Name);
   }
 
   Type *ValueType;
   // All bitfields use unsigned as the underlying type so that MSVC will pack
   // them.
   unsigned Linkage : 4;       // The linkage of this global
   unsigned Visibility : 2;    // The visibility style of this global

 
 protected:
   /// \brief The intrinsic ID for this subclass (which must be a Function).
   ///
   /// This member is defined by this class, but not used for anything.
   /// Subclasses can use it to store their intrinsic ID, if they have one.
   ///
   /// This is stored here to save space in Function on 64-bit hosts.
-  Intrinsic::ID IntID;
+  Intrinsic::ID IntID : 31;
+
+  /// True if the function's name starts with "llvm.".  This corresponds to the
+  /// value of Function::isIntrinsic(), which may be true even if
+  /// Function::intrinsicID() returns Intrinsic::not_intrinsic.
+  bool HasLLVMReservedName : 1;
 
   unsigned getGlobalValueSubClassData() const {
     return SubClassData;
   }
   void setGlobalValueSubClassData(unsigned V) {
     assert(V < (1 << GlobalValueSubClassDataBits) && "It will not fit");
     SubClassData = V;
   }

lib/IR/Function.cpp

Function::Function(FunctionType *Ty, LinkageTypes Linkage, const Twine &name,
 
   // If the function has arguments, mark them as lazily built.
   if (Ty->getNumParams())
     setValueSubclassData(1);   // Set the "has lazy arguments" bit.
 
   if (ParentModule)
     ParentModule->getFunctionList().push_back(this);
 
+  HasLLVMReservedName = getName().startswith("llvm.");
   // Ensure intrinsics have the right parameter attributes.
   // Note, the IntID field will have been set in Value::setName if this function
   // name is a valid intrinsic ID.
   if (IntID)
     setAttributes(Intrinsic::getAttributes(getContext(), IntID));
 }
 
 Function::~Function() {
static ArrayRef<const char *> findTargetSubtable(StringRef Name) {
   // We've either found the target or just fall back to the generic set, which
   // is always first.
   const auto &TI = It != Targets.end() && It->Name == Target ? *It : Targets[0];
   return makeArrayRef(&IntrinsicNameTable[1] + TI.Offset, TI.Count);
 }
 
 /// \brief This does the actual lookup of an intrinsic ID which
 /// matches the given function name.
-static Intrinsic::ID lookupIntrinsicID(const ValueName *ValName) {
-  StringRef Name = ValName->getKey();
-
+static Intrinsic::ID lookupIntrinsicID(StringRef Name) {
   ArrayRef<const char *> NameTable = findTargetSubtable(Name);
   int Idx = Intrinsic::lookupLLVMIntrinsicByName(NameTable, Name);
   if (Idx == -1)
     return Intrinsic::not_intrinsic;
 
   // Intrinsic IDs correspond to the location in IntrinsicNameTable, but we have
   // an index into a sub-table.
   int Adjust = NameTable.data() - IntrinsicNameTable;
   Intrinsic::ID ID = static_cast<Intrinsic::ID>(Idx + Adjust);
 
   // If the intrinsic is not overloaded, require an exact match. If it is
   // overloaded, require a prefix match.
   bool IsPrefixMatch = Name.size() > strlen(NameTable[Idx]);
   return IsPrefixMatch == isOverloaded(ID) ? ID : Intrinsic::not_intrinsic;
 }
 
 void Function::recalculateIntrinsicID() {
-  const ValueName *ValName = this->getValueName();
-  if (!ValName || !isIntrinsic()) {
+  StringRef Name = getName();
+  if (!Name.startswith("llvm.")) {
+    HasLLVMReservedName = false;
     IntID = Intrinsic::not_intrinsic;
     return;
   }
-  IntID = lookupIntrinsicID(ValName);
+  HasLLVMReservedName = true;
+  IntID = lookupIntrinsicID(Name);
 }
 
 /// Returns a stable mangling for the type specified for use in the name
 /// mangling scheme used by 'any' types in intrinsic signatures.  The mangling
 /// of named types is simply their name.  Manglings for unnamed types consist
 /// of a prefix ('p' for pointers, 'a' for arrays, 'f_' for functions)
 /// combined with the mangling of their component types.  A vararg function
 /// type will have a suffix of 'vararg'.  Since function types can contain