TableGen: Emit statically generated hash table for runtime libcalls (#150192)

a96121089b9c94e08c6632f91f2dffc73c0ffa28 reverted a change
to use a binary search on the string name table because it
was too slow. This replaces it with a static string hash
table based on the known set of libcall names. Microbenchmarking
shows this is similarly fast to using DenseMap. It's possibly
slightly slower than using StringSet, though these aren't an
exact comparison. This also saves on the one time use construction
of the map, so it could be better in practice.

This search isn't simple set check, since it does find the
range of possible matches with the same name. There's also
an additional check for whether the current target supports
the name. The runtime constructed set doesn't require this,
since it only adds the symbols live for the target.

Followed algorithm from this post
http://0x80.pl/notesen/2023-04-30-lookup-in-strings.html

I'm also thinking the 2 special case global symbols should
just be added to RuntimeLibcalls. There are also other global
references emitted in the backend that aren't tracked; we probably
should just use this as a centralized database for all compiler
selected symbols.

1 files changed, 22 insertions, 25 deletions

diff --git a/llvm/lib/Object/IRSymtab.cpp b/llvm/lib/Object/IRSymtab.cpp
index 0f19495..0043f02 100644
--- a/llvm/lib/Object/IRSymtab.cpp
+++ b/llvm/lib/Object/IRSymtab.cpp
@@ -46,7 +46,7 @@ static cl::opt<bool> DisableBitcodeVersionUpgrade(
     "disable-bitcode-version-upgrade", cl::Hidden,
     cl::desc("Disable automatic bitcode upgrade for version mismatch"));
 
-static const char *PreservedSymbols[] = {
+static constexpr StringLiteral PreservedSymbols[] = {
     // There are global variables, so put it here instead of in
     // RuntimeLibcalls.td.
     // TODO: Are there similar such variables?
@@ -54,6 +54,10 @@ static const char *PreservedSymbols[] = {
     "__stack_chk_guard",
 };
 
+static bool isPreservedGlobalVarName(StringRef Name) {
+  return PreservedSymbols[0] == Name || PreservedSymbols[1] == Name;
+}
+
 namespace {
 
 const char *getExpectedProducerName() {
@@ -81,12 +85,16 @@ struct Builder {
   // The StringTableBuilder does not create a copy of any strings added to it,
   // so this provides somewhere to store any strings that we create.
   Builder(SmallVector<char, 0> &Symtab, StringTableBuilder &StrtabBuilder,
-          BumpPtrAllocator &Alloc)
-      : Symtab(Symtab), StrtabBuilder(StrtabBuilder), Saver(Alloc) {}
+          BumpPtrAllocator &Alloc, const Triple &TT)
+      : Symtab(Symtab), StrtabBuilder(StrtabBuilder), Saver(Alloc), TT(TT),
+        Libcalls(TT) {}
 
   DenseMap<const Comdat *, int> ComdatMap;
   Mangler Mang;
-  Triple TT;
+  const Triple &TT;
+
+  // FIXME: This shouldn't be here.
+  RTLIB::RuntimeLibcallsInfo Libcalls;
 
   std::vector<storage::Comdat> Comdats;
   std::vector<storage::Module> Mods;
@@ -98,6 +106,10 @@ struct Builder {
 
   std::vector<storage::Str> DependentLibraries;
 
+  bool isPreservedLibFuncName(StringRef Name) {
+    return Libcalls.getSupportedLibcallImpl(Name) != RTLIB::Unsupported;
+  }
+
   void setStr(storage::Str &S, StringRef Value) {
     S.Offset = StrtabBuilder.add(Value);
     S.Size = Value.size();
@@ -213,19 +225,6 @@ Expected<int> Builder::getComdatIndex(const Comdat *C, const Module *M) {
   return P.first->second;
 }
 
-static StringSet<> buildPreservedSymbolsSet(const Triple &TT) {
-  StringSet<> PreservedSymbolSet;
-  PreservedSymbolSet.insert(std::begin(PreservedSymbols),
-                            std::end(PreservedSymbols));
-  // FIXME: Do we need to pass in ABI fields from TargetOptions?
-  RTLIB::RuntimeLibcallsInfo Libcalls(TT);
-  for (RTLIB::LibcallImpl Impl : Libcalls.getLibcallImpls()) {
-    if (Impl != RTLIB::Unsupported)
-      PreservedSymbolSet.insert(Libcalls.getLibcallImplName(Impl));
-  }
-  return PreservedSymbolSet;
-}
-
 Error Builder::addSymbol(const ModuleSymbolTable &Msymtab,
                          const SmallPtrSet<GlobalValue *, 4> &Used,
                          ModuleSymbolTable::Symbol Msym) {
@@ -279,13 +278,11 @@ Error Builder::addSymbol(const ModuleSymbolTable &Msymtab,
     return Error::success();
   }
 
-  setStr(Sym.IRName, GV->getName());
-
-  static const StringSet<> PreservedSymbolsSet =
-      buildPreservedSymbolsSet(GV->getParent()->getTargetTriple());
-  bool IsPreservedSymbol = PreservedSymbolsSet.contains(GV->getName());
+  StringRef GVName = GV->getName();
+  setStr(Sym.IRName, GVName);
 
-  if (Used.count(GV) || IsPreservedSymbol)
+  if (Used.count(GV) || isPreservedLibFuncName(GVName) ||
+      isPreservedGlobalVarName(GVName))
     Sym.Flags |= 1 << storage::Symbol::FB_used;
   if (GV->isThreadLocal())
     Sym.Flags |= 1 << storage::Symbol::FB_tls;
@@ -352,7 +349,6 @@ Error Builder::build(ArrayRef<Module *> IRMods) {
   setStr(Hdr.Producer, kExpectedProducerName);
   setStr(Hdr.TargetTriple, IRMods[0]->getTargetTriple().str());
   setStr(Hdr.SourceFileName, IRMods[0]->getSourceFileName());
-  TT = IRMods[0]->getTargetTriple();
 
   for (auto *M : IRMods)
     if (Error Err = addModule(M))
@@ -378,7 +374,8 @@ Error Builder::build(ArrayRef<Module *> IRMods) {
 Error irsymtab::build(ArrayRef<Module *> Mods, SmallVector<char, 0> &Symtab,
                       StringTableBuilder &StrtabBuilder,
                       BumpPtrAllocator &Alloc) {
-  return Builder(Symtab, StrtabBuilder, Alloc).build(Mods);
+  const Triple &TT = Mods[0]->getTargetTriple();
+  return Builder(Symtab, StrtabBuilder, Alloc, TT).build(Mods);
 }
 
 // Upgrade a vector of bitcode modules created by an old version of LLVM by