[NFC][TLI] Replace std::lower_bound call in getLibFunc with DenseMap lookup

[0xdc03]

Summary

While std::lower_bound takes logarithmic time (relative to the length of
the array) to execute, DenseMap gives better performance characteristics
as it traverses few (if any) elements when collisions do occur,
especially when the number of elements are known in advance.

This gives a speedup of 0.24%:
https://llvm-compile-time-tracker.com/compare.php?from=ac00cca3d9c6c3e9118ebbe47aa5b3ba1ee7404f&to=7f3d4c8ce8cee3a236a2328e46b2a8374672b46e&stat=instructions:u

[nikic]

llvm/lib/Analysis/TargetLibraryInfo.cpp

967

This initialization isn't thread-safe. I believe the proper pattern is static const DenseMap<StringRef, unsigned> Indices = buildIndexMap(); or similar.

[0xdc03]

• Address reviewer comment
  • Fix thread safety issue

[nikic]

llvm/lib/Analysis/TargetLibraryInfo.cpp

945

StandardNames is a global variable in this file, no need to pass it as an argument.

946

Might be a bit more elegant to make this a map to LibFunc rather than unsigned?

[0xdc03]

• Change map from unsigned to LibFunc

[0xdc03]

llvm/lib/Analysis/TargetLibraryInfo.cpp

945

Unfortunately not:

error: 'StandardNames' is a private member of 'llvm::TargetLibraryInfoImpl'
  for (const auto &Func : TargetLibraryInfoImpl::StandardNames)
                                                 ^

I could make buildIndexMap a member of TargetLibraryInfoImpl

[nikic]

llvm/lib/Analysis/TargetLibraryInfo.cpp

945

Oh, I see. In that case I'd suggest to make the argument ArrayRef<StringLiteral> StandardNames to avoid any weird array passing semantics.

[0xdc03]

• Use a better array type

[nikic]

LGTM

llvm/lib/Analysis/TargetLibraryInfo.cpp

 //===-- TargetLibraryInfo.cpp - Runtime library information ----------------==//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 //
 // This file implements the TargetLibraryInfo class.
 //
 //===----------------------------------------------------------------------===//
 
 #include "llvm/Analysis/TargetLibraryInfo.h"
+#include "llvm/ADT/DenseMap.h"
 #include "llvm/IR/Constants.h"
 #include "llvm/InitializePasses.h"
 #include "llvm/Support/CommandLine.h"
 #include "llvm/TargetParser/Triple.h"
 using namespace llvm;
 
 static cl::opt<TargetLibraryInfoImpl::VectorLibrary> ClVectorLibrary(
     "vector-library", cl::Hidden, cl::desc("Vector functions library"),
static StringRef sanitizeFunctionName(StringRef funcName) {
   if (funcName.empty() || funcName.contains('\0'))
     return StringRef();
 
   // Check for \01 prefix that is used to mangle __asm declarations and
   // strip it if present.
   return GlobalValue::dropLLVMManglingEscape(funcName);
 }
 
+static DenseMap<StringRef, unsigned>
+buildIndexMap(const StringLiteral (&StandardNames)[LibFunc::NumLibFuncs]) {
+  DenseMap<StringRef, unsigned> Indices;
+  unsigned Idx = 0;
+  Indices.reserve(LibFunc::NumLibFuncs);
+  for (const auto &Func : StandardNames)
+    Indices[Func] = Idx++;
+  return Indices;
+}
+
 bool TargetLibraryInfoImpl::getLibFunc(StringRef funcName, LibFunc &F) const {
   funcName = sanitizeFunctionName(funcName);
   if (funcName.empty())
     return false;
 
-  const auto *Start = std::begin(StandardNames);
-  const auto *End = std::end(StandardNames);
-  const auto *I = std::lower_bound(Start, End, funcName);
-  if (I != End && *I == funcName) {
-    F = (LibFunc)(I - Start);
+  static const DenseMap<StringRef, unsigned> Indices =
+      buildIndexMap(StandardNames);
+
+  if (auto Loc = Indices.find(funcName); Loc != Indices.end()) {
+    F = (LibFunc)Loc->second;
     return true;
   }
   return false;
 }
 
 // Return true if ArgTy matches Ty.
 
 static bool matchType(FuncArgTypeID ArgTy, const Type *Ty, unsigned IntBits,
                       unsigned SizeTBits) {
   switch (ArgTy) {
   case Void:
     return Ty->isVoidTy();