// Copyright 2021 the V8 project authors. All rights reserved. // Use of this source code is governed by a BSD-style license that can be // found in the LICENSE file. // Collection of swiss table helpers that are independent from a specific // container, like SwissNameDictionary. Taken almost in verbatim from Abseil, // comments in this file indicate what is taken from what Abseil file. #include <climits> #include <cstdint> #include <type_traits> #include "src/base/bits.h" #include "src/base/logging.h" #include "src/base/memory.h" #ifndef V8_OBJECTS_SWISS_HASH_TABLE_HELPERS_H_ #define V8_OBJECTS_SWISS_HASH_TABLE_HELPERS_H_ // The following #defines are taken from Abseil's have_sse.h (but renamed). #ifndef V8_SWISS_TABLE_HAVE_SSE2_HOST #if (defined(__SSE2__) || \ (defined(_MSC_VER) && \ (defined(_M_X64) || (defined(_M_IX86) && _M_IX86_FP >= 2)))) #define V8_SWISS_TABLE_HAVE_SSE2_HOST … #else #define V8_SWISS_TABLE_HAVE_SSE2_HOST … #endif #endif #ifndef V8_SWISS_TABLE_HAVE_SSSE3_HOST #if defined(__SSSE3__) #define V8_SWISS_TABLE_HAVE_SSSE3_HOST … #else #define V8_SWISS_TABLE_HAVE_SSSE3_HOST … #endif #endif #if V8_SWISS_TABLE_HAVE_SSSE3_HOST && !V8_SWISS_TABLE_HAVE_SSE2_HOST #error "Bad configuration!" #endif // Unlike Abseil, we cannot select SSE purely by host capabilities. When // creating a snapshot, the group width must be compatible. The SSE // implementation uses a group width of 16, whereas the non-SSE version uses 8. // Thus we select the group size based on target capabilities and, if the host // does not match, select a polyfill implementation. This means, in supported // cross-compiling configurations, we must be able to determine matching target // capabilities from the host. #ifndef V8_SWISS_TABLE_HAVE_SSE2_TARGET #if V8_TARGET_ARCH_IA32 || V8_TARGET_ARCH_X64 // x64 always has SSE2, and ia32 without SSE2 is not supported by V8. #define V8_SWISS_TABLE_HAVE_SSE2_TARGET … #else #define V8_SWISS_TABLE_HAVE_SSE2_TARGET … #endif #endif #if V8_SWISS_TABLE_HAVE_SSE2_HOST #include <emmintrin.h> #endif #if V8_SWISS_TABLE_HAVE_SSSE3_HOST #include <tmmintrin.h> #endif namespace v8 { namespace internal { namespace swiss_table { // All definitions below are taken from Abseil's raw_hash_set.h with only minor // changes, like using existing V8 versions of certain helper functions. // Denotes the group of the control table currently being probed. // Implements quadratic probing by advancing by i groups after the i-th // (unsuccesful) probe. template <size_t GroupSize> class ProbeSequence { … }; // An abstraction over a bitmask. It provides an easy way to iterate through the // indexes of the set bits of a bitmask. When Shift=0 (platforms with SSE), // this is a true bitmask. // When Shift=3 (used on non-SSE platforms), we obtain a "byte mask", where each // logical bit is represented by a full byte. The logical bit 0 is represented // as 0x00, whereas 1 is represented as 0x80. Other values must not appear. // // For example: // for (int i : BitMask<uint32_t, 16>(0x5)) -> yields 0, 2 // for (int i : BitMask<uint64_t, 8, 3>(0x0000000080800000)) -> yields 2, 3 template <class T, int SignificantBits, int Shift = 0> class BitMask { … }; ctrl_t; h2_t; // The values here are selected for maximum performance. See the static asserts // below for details. enum Ctrl : ctrl_t { … }; static_assert …; static_assert …; static_assert …; static_assert …; static_assert …; static_assert …; // See below for explanation of H2. Just here for documentation purposes, Swiss // Table implementations rely on this being 7. static constexpr int kH2Bits = …; static constexpr int kNotFullMask = …; static_assert …; // Extracts H1 from the given overall hash, which means discarding the lowest 7 // bits of the overall hash. H1 is used to determine the first group to probe. inline static uint32_t H1(uint32_t hash) { … } // Extracts H2 from the given overall hash, which means using only the lowest 7 // bits of the overall hash. H2 is stored in the control table byte for each // present entry. inline static swiss_table::ctrl_t H2(uint32_t hash) { … } #if V8_SWISS_TABLE_HAVE_SSE2_HOST struct GroupSse2Impl { … }; #endif // V8_SWISS_TABLE_HAVE_SSE2_HOST // A portable, inefficient version of GroupSse2Impl. This exists so SSE2-less // hosts can generate snapshots for SSE2-capable targets. struct GroupSse2Polyfill { … }; struct GroupPortableImpl { … }; // Determine which Group implementation SwissNameDictionary uses. #if defined(V8_ENABLE_SWISS_NAME_DICTIONARY) && DEBUG // TODO(v8:11388) If v8_enable_swiss_name_dictionary is enabled, we are supposed // to use SwissNameDictionary as the dictionary backing store. If we want to use // the SIMD version of SwissNameDictionary, that would require us to compile SSE // instructions into the snapshot that exceed the minimum requirements for V8 // SSE support. Therefore, this fails a DCHECK. However, given the experimental // nature of v8_enable_swiss_name_dictionary mode, we only except this to be run // by developers/bots, that always have the necessary instructions. This means // that if v8_enable_swiss_name_dictionary is enabled and debug mode isn't, we // ignore the DCHECK that would fail in debug mode. However, if both // v8_enable_swiss_name_dictionary and debug mode are enabled, we must fallback // to the non-SSE implementation. Given that V8 requires SSE2, there should be a // solution that doesn't require the workaround present here. Instead, the // backend should only use SSE2 when compiling the SIMD version of // SwissNameDictionary into the builtin. using Group = GroupPortableImpl; #elif V8_SWISS_TABLE_HAVE_SSE2_TARGET // Use a matching group size between host and target. #if V8_SWISS_TABLE_HAVE_SSE2_HOST Group; #else #if V8_HOST_ARCH_IA32 || V8_HOST_ARCH_X64 // If we do not detect SSE2 when building for the ia32/x64 target, the // V8_SWISS_TABLE_HAVE_SSE2_TARGET logic will incorrectly cause the final output // to use the inefficient polyfill implementation. Detect this case and warn if // it happens. #warning "Did not detect required SSE2 support on ia32/x64." #endif using Group = GroupSse2Polyfill; #endif #else using Group = GroupPortableImpl; #endif } // namespace swiss_table } // namespace internal } // namespace v8 #endif // V8_OBJECTS_SWISS_HASH_TABLE_HELPERS_H_
Codebase Browser
chromium