https://github.com/arsenm updated
https://github.com/llvm/llvm-project/pull/153801
>From 6e2b170ea709c205ad27b3e326a4d4ade7822f53 Mon Sep 17 00:00:00 2001
From: Matt Arsenault <matthew.arsena...@amd.com>
Date: Fri, 15 Aug 2025 09:45:46 +0900
Subject: [PATCH] RuntimeLibcalls: Fix building hash table with duplicate
entries
We were sizing the table appropriately for the number of LibcallImpls,
but many of those have identical names which were pushing up the
collision count unnecessarily. This ends up decreasing the table size
slightly, and makes it a bit faster.
BM_LookupRuntimeLibcallByNameRandomCalls improves by ~25% and
BM_LookupRuntimeLibcallByNameSampleData by ~5%.
As a secondary change, align the table size up to the next
power of 2. This makes the table larger than before, but improves
the sample data benchmark by an additional 5%.
---
llvm/test/TableGen/RuntimeLibcallEmitter.td | 4 +-
.../TableGen/Basic/RuntimeLibcallsEmitter.cpp | 76 ++++++++-----------
2 files changed, 35 insertions(+), 45 deletions(-)
diff --git a/llvm/test/TableGen/RuntimeLibcallEmitter.td
b/llvm/test/TableGen/RuntimeLibcallEmitter.td
index 7c62402227f7d..2d19d534ec3ef 100644
--- a/llvm/test/TableGen/RuntimeLibcallEmitter.td
+++ b/llvm/test/TableGen/RuntimeLibcallEmitter.td
@@ -176,9 +176,9 @@ def BlahLibrary : SystemRuntimeLibrary<isBlahArch, (add
calloc, LibraryWithCondi
// CHECK: iota_range<RTLIB::LibcallImpl>
RTLIB::RuntimeLibcallsInfo::lookupLibcallImplNameImpl(StringRef Name) {
// CHECK: static constexpr uint16_t HashTableNameToEnum[16] = {
-// CHECK: 2, // 0x000000705301b8, ___memset
+// CHECK: 2,
// CHECK: 0,
-// CHECK: 6, // 0x0000001417a2af, calloc
+// CHECK: 6,
// CHECK: 0,
// CHECK: };
diff --git a/llvm/utils/TableGen/Basic/RuntimeLibcallsEmitter.cpp
b/llvm/utils/TableGen/Basic/RuntimeLibcallsEmitter.cpp
index c305e6323ca9d..a8ec873f4587e 100644
--- a/llvm/utils/TableGen/Basic/RuntimeLibcallsEmitter.cpp
+++ b/llvm/utils/TableGen/Basic/RuntimeLibcallsEmitter.cpp
@@ -287,13 +287,6 @@ class RuntimeLibcallEmitter {
void run(raw_ostream &OS);
};
-/// Helper struct for the name hash table.
-struct LookupEntry {
- StringRef FuncName;
- uint64_t Hash = 0;
- unsigned TableValue = 0;
-};
-
} // End anonymous namespace.
void RuntimeLibcallEmitter::emitGetRuntimeLibcallEnum(raw_ostream &OS) const {
@@ -339,14 +332,17 @@ static void emitHashFunction(raw_ostream &OS) {
/// Return the table size, maximum number of collisions for the set of hashes
static std::pair<int, int>
computePerfectHashParameters(ArrayRef<uint64_t> Hashes) {
- const int SizeOverhead = 10;
- const int NumHashes = Hashes.size();
+ // Chosen based on experimentation with llvm/benchmarks/RuntimeLibcalls.cpp
+ const int SizeOverhead = 4;
// Index derived from hash -> number of collisions.
DenseMap<uint64_t, int> Table;
+ unsigned NumHashes = Hashes.size();
+
for (int MaxCollisions = 1;; ++MaxCollisions) {
- for (int N = NumHashes; N < SizeOverhead * NumHashes; ++N) {
+ for (unsigned N = NextPowerOf2(NumHashes - 1); N < SizeOverhead *
NumHashes;
+ N <<= 1) {
Table.clear();
bool NeedResize = false;
@@ -365,41 +361,29 @@ computePerfectHashParameters(ArrayRef<uint64_t> Hashes) {
}
}
-static std::vector<LookupEntry>
+static std::vector<unsigned>
constructPerfectHashTable(ArrayRef<RuntimeLibcallImpl> Keywords,
- ArrayRef<uint64_t> Hashes, int Size, int Collisions,
- StringToOffsetTable &OffsetTable) {
- DenseSet<StringRef> Seen;
- std::vector<LookupEntry> Lookup(Size * Collisions);
-
- for (const RuntimeLibcallImpl &LibCallImpl : Keywords) {
- StringRef ImplName = LibCallImpl.getLibcallFuncName();
-
- // We do not want to add repeated entries for cases with the same name,
only
- // an entry for the first, with the name collision enum values immediately
- // following.
- if (!Seen.insert(ImplName).second)
- continue;
-
- uint64_t HashValue = Hashes[LibCallImpl.getEnumVal() - 1];
+ ArrayRef<uint64_t> Hashes,
+ ArrayRef<unsigned> TableValues, int Size,
+ int Collisions, StringToOffsetTable &OffsetTable) {
+ std::vector<unsigned> Lookup(Size * Collisions);
+ for (auto [HashValue, TableValue] : zip(Hashes, TableValues)) {
uint64_t Idx = (HashValue % static_cast<uint64_t>(Size)) *
static_cast<uint64_t>(Collisions);
bool Found = false;
for (int J = 0; J < Collisions; ++J) {
- LookupEntry &Entry = Lookup[Idx + J];
- if (Entry.TableValue == 0) {
- Entry.FuncName = ImplName;
- Entry.TableValue = LibCallImpl.getEnumVal();
- Entry.Hash = HashValue;
+ unsigned &Entry = Lookup[Idx + J];
+ if (Entry == 0) {
+ Entry = TableValue;
Found = true;
break;
}
}
if (!Found)
- reportFatalInternalError("failure to hash " + ImplName);
+ reportFatalInternalError("failure to hash");
}
return Lookup;
@@ -409,15 +393,25 @@ constructPerfectHashTable(ArrayRef<RuntimeLibcallImpl>
Keywords,
void RuntimeLibcallEmitter::emitNameMatchHashTable(
raw_ostream &OS, StringToOffsetTable &OffsetTable) const {
std::vector<uint64_t> Hashes(RuntimeLibcallImplDefList.size());
+ std::vector<unsigned> TableValues(RuntimeLibcallImplDefList.size());
+ DenseSet<StringRef> SeenFuncNames;
size_t MaxFuncNameSize = 0;
size_t Index = 0;
+
for (const RuntimeLibcallImpl &LibCallImpl : RuntimeLibcallImplDefList) {
StringRef ImplName = LibCallImpl.getLibcallFuncName();
- MaxFuncNameSize = std::max(MaxFuncNameSize, ImplName.size());
- Hashes[Index++] = hash(ImplName);
+ if (SeenFuncNames.insert(ImplName).second) {
+ MaxFuncNameSize = std::max(MaxFuncNameSize, ImplName.size());
+ TableValues[Index] = LibCallImpl.getEnumVal();
+ Hashes[Index++] = hash(ImplName);
+ }
}
+ // Trim excess elements from non-unique entries.
+ Hashes.resize(SeenFuncNames.size());
+ TableValues.resize(SeenFuncNames.size());
+
LLVM_DEBUG({
for (const RuntimeLibcallImpl &LibCallImpl : RuntimeLibcallImplDefList) {
StringRef ImplName = LibCallImpl.getLibcallFuncName();
@@ -447,8 +441,9 @@ void RuntimeLibcallEmitter::emitNameMatchHashTable(
"#endif\n";
auto [Size, Collisions] = computePerfectHashParameters(Hashes);
- std::vector<LookupEntry> Lookup = constructPerfectHashTable(
- RuntimeLibcallImplDefList, Hashes, Size, Collisions, OffsetTable);
+ std::vector<unsigned> Lookup =
+ constructPerfectHashTable(RuntimeLibcallImplDefList, Hashes, TableValues,
+ Size, Collisions, OffsetTable);
LLVM_DEBUG(dbgs() << "Runtime libcall perfect hashing parameters: Size = "
<< Size << ", maximum collisions = " << Collisions <<
'\n');
@@ -463,13 +458,8 @@ void RuntimeLibcallEmitter::emitNameMatchHashTable(
OS << " static constexpr uint16_t HashTableNameToEnum[" << Lookup.size()
<< "] = {\n";
- for (auto [FuncName, Hash, TableVal] : Lookup) {
- OS << " " << TableVal << ',';
- if (TableVal != 0)
- OS << " // " << format_hex(Hash, 16) << ", " << FuncName;
-
- OS << '\n';
- }
+ for (unsigned TableVal : Lookup)
+ OS << " " << TableVal << ",\n";
OS << " };\n\n";
_______________________________________________
llvm-branch-commits mailing list
llvm-branch-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-branch-commits
