Avoid out-of-bounds software prefetching in Abseil large-input hash. - Move the PiecewiseChunkSize check into a new LowLevelHashWithPrefetch helper that keeps software prefetching for inputs larger than kPrefetchBytes (5 cache lines, 320 bytes on 64-byte cache-line CPUs). - Handle 33..64-byte inputs directly in CombineLargeContiguousImplOn64BitLengthGt32 (1 branch, down from 2) and tail-call LowLevelHashLenGt64 without prefetching for 65..320 bytes (still 2 branches). - Stop prefetching in LowLevelHashWithPrefetch once remaining length fits within kPrefetchBytes, processing the tail without prefetching so prefetches never read past the buffer end. - Keep the loop pointer in a register across the 32-byte epilogue check to avoid loop-exit address recalculation. PiperOrigin-RevId: 1026839446
diff --git a/absl/base/attributes.h b/absl/base/attributes.h index b68c52c..608c26e 100644 --- a/absl/base/attributes.h +++ b/absl/base/attributes.h
@@ -203,6 +203,56 @@ #define ABSL_INTERNAL_MUSTTAIL #endif +// ABSL_INTERNAL_PRESERVE_MOST +// +// Tells the compiler to use the `preserve_most` calling convention for a +// function, which preserves all general-purpose registers (except R11 on +// x86-64) across the call. This shifts the burden of saving and restoring +// registers from the caller to the callee, reducing register spills and code +// size at call sites that invoke cold out-of-line slow paths. +// +// MANDATORY USAGE REQUIREMENTS: +// * Out-of-line slow paths: Apply to cold or rarely executed out-of-line +// functions called from hot inline fast paths, where shrinking caller +// register-spill code outweighs any extra callee save/restore instructions. +// * Hot functions: May also be used on small, self-contained functions +// that use minimal registers, benefiting callers without degrading +// performance of the function itself. +// * Benchmark justification: The performance or code-size impact of using +// `ABSL_INTERNAL_PRESERVE_MOST` MUST be clearly demonstrated by benchmarks. +// * Attribute ordering: Because this macro expands to a C++11 standard-style +// attribute, place it before GNU-style attribute macros on declarations. +// * Tail calls: Because parameter registers are also preserved for the caller, +// a function using this convention may only force a tail call when forwarding +// all incoming parameter registers unchanged. +// * ABI compatibility: `[[clang::preserve_most]]` alters the calling convention +// without changing C++ name mangling. Linking callers and callees built +// with mismatched conventions (for example, Clang >= 17 against GCC or +// Clang <= 16) links silently and corrupts registers at runtime. Because of +// this cross-TU ABI hazard (and lazy PLT R10 clobbers on older linkers), +// this macro is gated on `__GOOGLE_GRTE_VERSION__`, where all linked TUs +// use a single homogeneous Clang toolchain and GRTE runtime. +// * This macro is strictly for internal Abseil use and must not be exposed as a +// public Abseil API. +// +// See: https://clang.llvm.org/docs/AttributeReference.html#preserve-most +#if defined(ABSL_INTERNAL_PRESERVE_MOST) +#error "ABSL_INTERNAL_PRESERVE_MOST cannot be directly set." +#elif ABSL_HAVE_CPP_ATTRIBUTE(clang::preserve_most) && \ + /* Clang <= 16 clobbered return registers in epilogues (D143425). */ \ + defined(__clang__) && __clang_major__ >= 17 && \ + /* AArch64 lazy PLT resolver clobbers X10-X15. */ \ + defined(__x86_64__) && \ + /* Unsupported on Windows PE/COFF and across DLL boundaries. */ \ + !defined(_WIN32) && !defined(ABSL_BUILD_DLL) && \ + !defined(ABSL_CONSUME_DLL) && \ + /* Require GRTE for a single Clang toolchain ABI and PLT-safe R10. */ \ + defined(__GOOGLE_GRTE_VERSION__) && __GOOGLE_GRTE_VERSION__ >= 20180301L +#define ABSL_INTERNAL_PRESERVE_MOST [[clang::preserve_most]] +#else +#define ABSL_INTERNAL_PRESERVE_MOST +#endif + // ABSL_ATTRIBUTE_WEAK // // Tags a function as weak for the purposes of compilation and linking.
diff --git a/absl/base/attributes_test.cc b/absl/base/attributes_test.cc index a014a06..186cb39 100644 --- a/absl/base/attributes_test.cc +++ b/absl/base/attributes_test.cc
@@ -142,4 +142,31 @@ #endif } +ABSL_INTERNAL_PRESERVE_MOST ABSL_ATTRIBUTE_NOINLINE void +PreserveMostVoidCallee(int* out, int x) { + *out = x + 2; +} + +ABSL_INTERNAL_PRESERVE_MOST ABSL_ATTRIBUTE_NOINLINE void +PreserveMostVoidCaller(int* out, int x) { + ABSL_INTERNAL_MUSTTAIL return PreserveMostVoidCallee(out, x); +} + +ABSL_INTERNAL_PRESERVE_MOST ABSL_ATTRIBUTE_PURE_FUNCTION ABSL_ATTRIBUTE_NOINLINE + int + PreserveMostCallee(int a, int b) { + // Bitwise operations prevent folding into a single load-effective-address + // instruction so the callee must preserve incoming parameter registers. + return (a ^ 0x55aa) + (b ^ 0xaa55); +} + +TEST(Attributes, PreserveMost) { + volatile int init = 20; + int a = init; + int b = a + 2; + int out = 0; + PreserveMostVoidCaller(&out, a); + EXPECT_EQ(PreserveMostCallee(a, b) + a + b + out, + (20 ^ 0x55aa) + (22 ^ 0xaa55) + 20 + 22 + 22); +} } // namespace
diff --git a/absl/hash/internal/hash.cc b/absl/hash/internal/hash.cc index aa04def..b97c47a 100644 --- a/absl/hash/internal/hash.cc +++ b/absl/hash/internal/hash.cc
@@ -52,8 +52,13 @@ namespace { +// Software prefetch lookahead distance (320 bytes on 64-byte cache-line CPUs). +constexpr size_t kPrefetchBytes = 5 * ABSL_CACHELINE_SIZE; +static_assert(kPrefetchBytes >= 128 && kPrefetchBytes <= PiecewiseChunkSize(), + "kPrefetchBytes must lie in [128, PiecewiseChunkSize()]"); + void PrefetchFutureDataToLocalCache(const uint8_t* ptr) { - PrefetchToLocalCache(ptr + 5 * ABSL_CACHELINE_SIZE); + PrefetchToLocalCache(ptr + kPrefetchBytes); } #if defined(ABSL_AES_INTERNAL_HAVE_X86_SIMD) || \ @@ -216,8 +221,9 @@ return Mix4x16Vectors(na, nb, nc, nd); } -[[maybe_unused]] ABSL_ATTRIBUTE_NOINLINE uint64_t -LowLevelHashLenGt64(uint64_t seed, const unsigned char* ptr, size_t len) { +template <bool kPrefetch> +ABSL_ATTRIBUTE_ALWAYS_INLINE inline uint64_t LowLevelHashLenGt64Impl( + uint64_t seed, const unsigned char* ptr, size_t len) { assert(len > 64); const uint8_t* last_32_ptr = ptr + len - 32; @@ -257,17 +263,42 @@ } }; MixerCD mix_cd = {state2, state3}; + auto mix_64_bytes = [&](const uint8_t* p) ABSL_ATTRIBUTE_ALWAYS_INLINE { + mix_ab(p); + mix_cd(p + 32); + }; + if constexpr (kPrefetch) { + assert(len > kPrefetchBytes); + // Stop prefetching once remaining bytes fit within the prefetch distance + // so we never read past the end of the buffer. +#if defined(__clang__) +#pragma clang loop unroll(disable) +#endif + do { + PrefetchFutureDataToLocalCache(ptr); + mix_64_bytes(ptr); + ptr += 64; + len -= 64; + } while (len > kPrefetchBytes); + } + // Already 64B/iter and >1 iteration (>128B, ~2.2% in fleetbench) is rare, + // so avoid extra unroll bloat (and GPR spills under preserve_most). +#if defined(__clang__) +#pragma clang loop unroll(disable) +#endif do { - PrefetchFutureDataToLocalCache(ptr); - mix_ab(ptr); - mix_cd(ptr + 32); - + mix_64_bytes(ptr); ptr += 64; len -= 64; } while (len > 64); // We now have a data `ptr` with at most 64 bytes. if (len > 32) { + // Keep the loop pointer in its register rather than recomputing the exit + // offset from the initial arguments. +#if defined(__GNUC__) + asm("" : "+r"(ptr)); +#endif mix_ab(ptr); } mix_cd(last_32_ptr); @@ -295,8 +326,9 @@ return Mix32Bytes(last_32_ptr, Mix32Bytes(ptr, current_state)); } -[[maybe_unused]] ABSL_ATTRIBUTE_NOINLINE uint64_t -LowLevelHashLenGt64(uint64_t seed, const unsigned char* ptr, size_t len) { +template <bool kPrefetch> +ABSL_ATTRIBUTE_ALWAYS_INLINE inline uint64_t LowLevelHashLenGt64Impl( + uint64_t seed, const unsigned char* ptr, size_t len) { assert(len > 64); uint64_t current_state = seed ^ kStaticRandomData[0] ^ len; const uint8_t* last_32_ptr = ptr + len - 32; @@ -307,24 +339,43 @@ uint64_t duplicated_state1 = current_state; uint64_t duplicated_state2 = current_state; - do { - PrefetchFutureDataToLocalCache(ptr); - - uint64_t a = absl::base_internal::UnalignedLoad64(ptr); - uint64_t b = absl::base_internal::UnalignedLoad64(ptr + 8); - uint64_t c = absl::base_internal::UnalignedLoad64(ptr + 16); - uint64_t d = absl::base_internal::UnalignedLoad64(ptr + 24); - uint64_t e = absl::base_internal::UnalignedLoad64(ptr + 32); - uint64_t f = absl::base_internal::UnalignedLoad64(ptr + 40); - uint64_t g = absl::base_internal::UnalignedLoad64(ptr + 48); - uint64_t h = absl::base_internal::UnalignedLoad64(ptr + 56); + auto mix_64_bytes = [&](const uint8_t* p) ABSL_ATTRIBUTE_ALWAYS_INLINE { + uint64_t a = absl::base_internal::UnalignedLoad64(p); + uint64_t b = absl::base_internal::UnalignedLoad64(p + 8); + uint64_t c = absl::base_internal::UnalignedLoad64(p + 16); + uint64_t d = absl::base_internal::UnalignedLoad64(p + 24); + uint64_t e = absl::base_internal::UnalignedLoad64(p + 32); + uint64_t f = absl::base_internal::UnalignedLoad64(p + 40); + uint64_t g = absl::base_internal::UnalignedLoad64(p + 48); + uint64_t h = absl::base_internal::UnalignedLoad64(p + 56); current_state = Mix(a ^ kStaticRandomData[1], b ^ current_state); duplicated_state0 = Mix(c ^ kStaticRandomData[2], d ^ duplicated_state0); duplicated_state1 = Mix(e ^ kStaticRandomData[3], f ^ duplicated_state1); duplicated_state2 = Mix(g ^ kStaticRandomData[4], h ^ duplicated_state2); - + }; + if constexpr (kPrefetch) { + assert(len > kPrefetchBytes); + // Stop prefetching once remaining bytes fit within the prefetch distance + // so we never read past the end of the buffer. +#if defined(__clang__) +#pragma clang loop unroll(disable) +#endif + do { + PrefetchFutureDataToLocalCache(ptr); + mix_64_bytes(ptr); + ptr += 64; + len -= 64; + } while (len > kPrefetchBytes); + } + // Already 64B/iter and >1 iteration (>128B, ~2.2% in fleetbench) is rare, + // so avoid extra unroll bloat (and GPR spills under preserve_most). +#if defined(__clang__) +#pragma clang loop unroll(disable) +#endif + do { + mix_64_bytes(ptr); ptr += 64; len -= 64; } while (len > 64); @@ -344,14 +395,29 @@ } #endif // ABSL_AES_INTERNAL_HAVE_X86_SIMD -[[maybe_unused]] uint64_t LowLevelHashLenGt32(uint64_t seed, - const unsigned char* data, - size_t len) { - assert(len > 32); - if (ABSL_PREDICT_FALSE(len > 64)) { - ABSL_INTERNAL_MUSTTAIL return LowLevelHashLenGt64(seed, data, len); +ABSL_INTERNAL_PRESERVE_MOST ABSL_ATTRIBUTE_NOINLINE uint64_t +SplitAndCombineOn64Bit(uint64_t state, const unsigned char* first, size_t len); + +// Hashes inputs larger than the prefetch lookahead distance with bounded +// software prefetching, delegating multi-chunk inputs to chunked hashing. +[[maybe_unused]] ABSL_INTERNAL_PRESERVE_MOST ABSL_ATTRIBUTE_NOINLINE uint64_t +LowLevelHashWithPrefetch(uint64_t seed, const unsigned char* data, size_t len) { + assert(len > kPrefetchBytes); + if (ABSL_PREDICT_FALSE(len > PiecewiseChunkSize())) { + ABSL_INTERNAL_MUSTTAIL return SplitAndCombineOn64Bit(seed, data, len); } - return LowLevelHash33To64(seed, data, len); + return LowLevelHashLenGt64Impl<true>(seed, data, len); +} + +// Skips software prefetching until inputs exceed the prefetch lookahead +// distance, avoiding out-of-bounds prefetches on medium inputs. +[[maybe_unused]] ABSL_INTERNAL_PRESERVE_MOST ABSL_ATTRIBUTE_NOINLINE uint64_t +LowLevelHashLenGt64(uint64_t seed, const unsigned char* data, size_t len) { + assert(len > 64); + if (ABSL_PREDICT_FALSE(len > kPrefetchBytes)) { + ABSL_INTERNAL_MUSTTAIL return LowLevelHashWithPrefetch(seed, data, len); + } + return LowLevelHashLenGt64Impl<false>(seed, data, len); } ABSL_ATTRIBUTE_ALWAYS_INLINE inline uint64_t HashBlockOn32Bit( @@ -380,20 +446,15 @@ std::integral_constant<int, 4>{}); } -ABSL_ATTRIBUTE_ALWAYS_INLINE inline uint64_t HashBlockOn64Bit( - uint64_t state, const unsigned char* data, size_t len) { -#ifdef ABSL_HAVE_INTRINSIC_INT128 - ABSL_INTERNAL_MUSTTAIL return LowLevelHashLenGt32(state, data, len); -#else - return hash_internal::CityHash64WithSeed(reinterpret_cast<const char*>(data), - len, state); -#endif -} - -ABSL_ATTRIBUTE_NOINLINE uint64_t +ABSL_INTERNAL_PRESERVE_MOST ABSL_ATTRIBUTE_NOINLINE uint64_t SplitAndCombineOn64Bit(uint64_t state, const unsigned char* first, size_t len) { while (len >= PiecewiseChunkSize()) { - state = HashBlockOn64Bit(state, first, PiecewiseChunkSize()); +#ifdef ABSL_HAVE_INTRINSIC_INT128 + state = LowLevelHashWithPrefetch(state, first, PiecewiseChunkSize()); +#else + state = hash_internal::CityHash64WithSeed( + reinterpret_cast<const char*>(first), PiecewiseChunkSize(), state); +#endif len -= PiecewiseChunkSize(); first += PiecewiseChunkSize(); } @@ -420,16 +481,24 @@ return SplitAndCombineOn32Bit(state, first, len); } -ABSL_ATTRIBUTE_NOINLINE uint64_t +ABSL_INTERNAL_PRESERVE_MOST ABSL_ATTRIBUTE_NOINLINE uint64_t CombineLargeContiguousImplOn64BitLengthGt32(uint64_t state, const unsigned char* first, size_t len) { assert(len > 32); assert(sizeof(size_t) == 8); // NOLINT(misc-static-assert) +#ifdef ABSL_HAVE_INTRINSIC_INT128 + if (ABSL_PREDICT_FALSE(len > 64)) { + ABSL_INTERNAL_MUSTTAIL return LowLevelHashLenGt64(state, first, len); + } + return LowLevelHash33To64(state, first, len); +#else if (ABSL_PREDICT_TRUE(len <= PiecewiseChunkSize())) { - ABSL_INTERNAL_MUSTTAIL return HashBlockOn64Bit(state, first, len); + return hash_internal::CityHash64WithSeed( + reinterpret_cast<const char*>(first), len, state); } ABSL_INTERNAL_MUSTTAIL return SplitAndCombineOn64Bit(state, first, len); +#endif } ABSL_CONST_INIT const void* const MixingHashState::kSeed = &kSeed;
diff --git a/absl/hash/internal/hash.h b/absl/hash/internal/hash.h index e25788b..596cc36 100644 --- a/absl/hash/internal/hash.h +++ b/absl/hash/internal/hash.h
@@ -1091,10 +1091,11 @@ CombineLargeContiguousImplOn32BitLengthGt8(uint64_t state, const unsigned char* first, size_t len); -ABSL_ATTRIBUTE_PURE_FUNCTION ABSL_ATTRIBUTE_NOINLINE uint64_t -CombineLargeContiguousImplOn64BitLengthGt32(uint64_t state, - const unsigned char* first, - size_t len); +ABSL_INTERNAL_PRESERVE_MOST ABSL_ATTRIBUTE_PURE_FUNCTION ABSL_ATTRIBUTE_NOINLINE + uint64_t + CombineLargeContiguousImplOn64BitLengthGt32(uint64_t state, + const unsigned char* first, + size_t len); ABSL_ATTRIBUTE_ALWAYS_INLINE inline uint64_t CombineSmallContiguousImpl( uint64_t state, const unsigned char* first, size_t len) {