[ADT] Refactor DenseMapInfo for integer types (NFC) #155549
Merged
Conversation
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
This patch consolidates DenseMapInfo<T> for integer types T with a common templated implementation. DenseMapInfo<char> is excluded because it uses ~0 for the empty key despite char being a signed type. Also, we preserve the tombstone key value for long, which is: std::numeric_limits<long>::max() - 1
|
@llvm/pr-subscribers-llvm-adt Author: Kazu Hirata (kazutakahirata) ChangesThis patch consolidates DenseMapInfo<T> for integer types T with a std::numeric_limits<long>::max() - 1 Full diff: https://github.com/llvm/llvm-project/pull/155549.diff 1 Files Affected:
diff --git a/llvm/include/llvm/ADT/DenseMapInfo.h b/llvm/include/llvm/ADT/DenseMapInfo.h
index 9d8fd893540a3..a3a459930b38a 100644
--- a/llvm/include/llvm/ADT/DenseMapInfo.h
+++ b/llvm/include/llvm/ADT/DenseMapInfo.h
@@ -17,6 +17,7 @@
#include <cassert>
#include <cstddef>
#include <cstdint>
+#include <limits>
#include <optional>
#include <tuple>
#include <type_traits>
@@ -101,122 +102,32 @@ template<> struct DenseMapInfo<char> {
}
};
-// Provide DenseMapInfo for unsigned chars.
-template <> struct DenseMapInfo<unsigned char> {
- static constexpr unsigned char getEmptyKey() { return ~0; }
- static constexpr unsigned char getTombstoneKey() { return ~0 - 1; }
- static unsigned getHashValue(const unsigned char &Val) { return Val * 37U; }
-
- static bool isEqual(const unsigned char &LHS, const unsigned char &RHS) {
- return LHS == RHS;
- }
-};
-
-// Provide DenseMapInfo for unsigned shorts.
-template <> struct DenseMapInfo<unsigned short> {
- static constexpr unsigned short getEmptyKey() { return 0xFFFF; }
- static constexpr unsigned short getTombstoneKey() { return 0xFFFF - 1; }
- static unsigned getHashValue(const unsigned short &Val) { return Val * 37U; }
-
- static bool isEqual(const unsigned short &LHS, const unsigned short &RHS) {
- return LHS == RHS;
- }
-};
-
-// Provide DenseMapInfo for unsigned ints.
-template<> struct DenseMapInfo<unsigned> {
- static constexpr unsigned getEmptyKey() { return ~0U; }
- static constexpr unsigned getTombstoneKey() { return ~0U - 1; }
- static unsigned getHashValue(const unsigned& Val) { return Val * 37U; }
-
- static bool isEqual(const unsigned& LHS, const unsigned& RHS) {
- return LHS == RHS;
- }
-};
-
-// Provide DenseMapInfo for unsigned longs.
-template<> struct DenseMapInfo<unsigned long> {
- static constexpr unsigned long getEmptyKey() { return ~0UL; }
- static constexpr unsigned long getTombstoneKey() { return ~0UL - 1L; }
-
- static unsigned getHashValue(const unsigned long& Val) {
- if constexpr (sizeof(Val) == 4)
- return DenseMapInfo<unsigned>::getHashValue(Val);
+// Provide DenseMapInfo for all integral types except char.
+//
+// The "char" case is excluded because it uses ~0 as the empty key despite
+// "char" being a signed type. "std::is_same_v<T, char>" is included below
+// for clarity; technically, we do not need it because the explicit
+// specialization above "wins",
+template <typename T>
+struct DenseMapInfo<
+ T, std::enable_if_t<std::is_integral_v<T> && !std::is_same_v<T, char>>> {
+ static constexpr T getEmptyKey() { return std::numeric_limits<T>::max(); }
+
+ static constexpr T getTombstoneKey() {
+ if constexpr (std::is_unsigned_v<T> || std::is_same_v<T, long>)
+ return std::numeric_limits<T>::max() - 1;
else
- return densemap::detail::mix(Val);
+ return std::numeric_limits<T>::min();
}
- static bool isEqual(const unsigned long& LHS, const unsigned long& RHS) {
- return LHS == RHS;
- }
-};
-
-// Provide DenseMapInfo for unsigned long longs.
-template<> struct DenseMapInfo<unsigned long long> {
- static constexpr unsigned long long getEmptyKey() { return ~0ULL; }
- static constexpr unsigned long long getTombstoneKey() { return ~0ULL - 1ULL; }
-
- static unsigned getHashValue(const unsigned long long& Val) {
- return densemap::detail::mix(Val);
- }
-
- static bool isEqual(const unsigned long long& LHS,
- const unsigned long long& RHS) {
- return LHS == RHS;
- }
-};
-
-// Provide DenseMapInfo for shorts.
-template <> struct DenseMapInfo<short> {
- static constexpr short getEmptyKey() { return 0x7FFF; }
- static constexpr short getTombstoneKey() { return -0x7FFF - 1; }
- static unsigned getHashValue(const short &Val) { return Val * 37U; }
- static bool isEqual(const short &LHS, const short &RHS) { return LHS == RHS; }
-};
-
-// Provide DenseMapInfo for ints.
-template<> struct DenseMapInfo<int> {
- static constexpr int getEmptyKey() { return 0x7fffffff; }
- static constexpr int getTombstoneKey() { return -0x7fffffff - 1; }
- static unsigned getHashValue(const int& Val) { return (unsigned)(Val * 37U); }
-
- static bool isEqual(const int& LHS, const int& RHS) {
- return LHS == RHS;
- }
-};
-
-// Provide DenseMapInfo for longs.
-template<> struct DenseMapInfo<long> {
- static constexpr long getEmptyKey() {
- return (1UL << (sizeof(long) * 8 - 1)) - 1UL;
- }
-
- static constexpr long getTombstoneKey() { return getEmptyKey() - 1L; }
-
- static unsigned getHashValue(const long& Val) {
- return (unsigned)(Val * 37UL);
- }
-
- static bool isEqual(const long& LHS, const long& RHS) {
- return LHS == RHS;
- }
-};
-
-// Provide DenseMapInfo for long longs.
-template<> struct DenseMapInfo<long long> {
- static constexpr long long getEmptyKey() { return 0x7fffffffffffffffLL; }
- static constexpr long long getTombstoneKey() {
- return -0x7fffffffffffffffLL - 1;
- }
-
- static unsigned getHashValue(const long long& Val) {
- return (unsigned)(Val * 37ULL);
+ static unsigned getHashValue(const T &Val) {
+ if constexpr (std::is_unsigned_v<T> && sizeof(T) > sizeof(unsigned))
+ return densemap::detail::mix(Val);
+ else
+ return (unsigned)(Val * 37U);
}
- static bool isEqual(const long long& LHS,
- const long long& RHS) {
- return LHS == RHS;
- }
+ static bool isEqual(const T &LHS, const T &RHS) { return LHS == RHS; }
};
// Provide DenseMapInfo for all pairs whose members have info.
|
tgymnich
approved these changes
Aug 27, 2025
kuhar
reviewed
Aug 27, 2025
|
LLVM Buildbot has detected a new failure on builder Full details are available at: https://lab.llvm.org/buildbot/#/builders/85/builds/12757 Here is the relevant piece of the build log for the reference |
topperc
reviewed
Aug 28, 2025
| // Provide DenseMapInfo for all integral types except char. | ||
| // | ||
| // The "char" case is excluded because it uses ~0 as the empty key despite | ||
| // "char" being a signed type. "std::is_same_v<T, char>" is included below |
There was a problem hiding this comment.
char is a signed type on x86, but it's an unsigned type on arm and risc-v. I don't know about other targets.
There was a problem hiding this comment.
@topperc Thanks! I think it's best not to touch char here.
There was a problem hiding this comment.
Agreed. I wasn't suggesting to change the code. It is best to not depend on the signedness of char on the platform.
WillFroom
reviewed
Aug 28, 2025
| if constexpr (std::is_unsigned_v<T> && sizeof(T) > sizeof(unsigned)) | ||
| return densemap::detail::mix(Val); | ||
| else | ||
| return static_cast<unsigned>(Val * 37U); |
There was a problem hiding this comment.
FYI this resulted in UB for signed types > int, created a fix here: #155826
WillFroom
added a commit
that referenced
this pull request
Aug 28, 2025
Fixes the signed overflow for signed types > int after #155549
|
@kazutakahirata I am going to revert to fix our bots? |
Or maybe not, #155826 probably works |
|
@vitalybuka @WillFroom Thank you for following up on this PR. I see that #155826 has landed. Is everything OK now? |
|
We bisected the blamelist and identified the patch 9c9e56b is the culprit for the stage2 build failures we saw on x86 platform. Sorry for the confusion.
|
I think so, the internal sanitizer errors we were seeing have been fixed after my patch afaict |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Add this suggestion to a batch that can be applied as a single commit.
This suggestion is invalid because no changes were made to the code.
Suggestions cannot be applied while the pull request is closed.
Suggestions cannot be applied while viewing a subset of changes.
Only one suggestion per line can be applied in a batch.
Add this suggestion to a batch that can be applied as a single commit.
Applying suggestions on deleted lines is not supported.
You must change the existing code in this line in order to create a valid suggestion.
Outdated suggestions cannot be applied.
This suggestion has been applied or marked resolved.
Suggestions cannot be applied from pending reviews.
Suggestions cannot be applied on multi-line comments.
Suggestions cannot be applied while the pull request is queued to merge.
Suggestion cannot be applied right now. Please check back later.
This patch consolidates DenseMapInfo for integer types T with a
common templated implementation. DenseMapInfo is excluded
because it uses ~0 for the empty key despite char being a signed type.
Also, we preserve the tombstone key value for long, which is:
std::numeric_limits::max() - 1